引数の組み合わせの数が少ない関数を実装する場合、あらかじめ計算済みの値を配列に埋めておいて返す方法と、 switch case で対応する値を返す方法と、を使うことがある。

どちらも値の置かれたアドレスを計算できる。片やそのアドレスの値をロードして返し、他方はアドレスにジャンプして返す、という処理になるので速度は同じでは？　とおもっていた。
しかしそんなことはなく、 最適化をしなければ 配列方式が五倍ちかく高速¹だった。

使った C コンパイラーは、以下のとおり。

$ gcc --version
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.13.sdk/usr/include/c++/4.2.1
Apple LLVM version 9.0.0 (clang-900.0.39.2)
Target: x86_64-apple-darwin17.4.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

#比較プログラム
8bit の値を二つ受け取って、なんらかの計算をして²結果を 8bit の値としてもどす、関数 calc。

int8_t calc(int8_t x, int8_t y);

これをすべての 8bit の値の組み合わせで呼び出すことにして、さらに 100 回まわすのに、どれだけ時間がかかるかを比較した。

/* main.c */
#include <stdint.h>

extern int8_t calc(int8_t x, int8_t y);

int main() {
  int a = 0;
  int i = 65536 * 100;
  while (i--) {
    const int8_t x = i / 256;
    const int8_t y = i % 256;
    a += calc(x, y);
  }
  return a;
}

速度比較結果

配列テーブルによる実装を呼び出した結果³。

$ gcc -o main main.c by_array.c && time ./main

real	0m0.067s
user	0m0.064s
sys	0m0.002s

一方で switch - case での実装を呼び出した結果。

$ gcc -o main main.c by_switch.c && time ./main

real	0m0.326s
user	0m0.320s
sys	0m0.002s

配列方式がおよそ 0.07 秒に対し、 switch case 方式は 0.33 秒。

#両方式実装
比較に使ったそれぞれの関数実装は以下のとおり。

##by_array.c
速度比較が目的なので、すべて 0 埋めしたテーブルを使った。

/* by_array.c */
#include <stdint.h>
int8_t calc(int8_t x, int8_t y) {
  static int8_t table[65536] = {0};
  return table[(y + 128) << 8 | (x + 128)];
}

##by_switch.c

あまりに行数が多くなるので一部だけ掲載。

#include <stdint.h>
int8_t calc(int8_t x, int8_t y) {
  switch ((y + 128) << 8 | (x + 128)) {
  default:
  case 0: return 0;
  case 1: return 0;
  case 2: return 0;
  ...
  case 65535: return 0;
  }
}

上記コードは、以下のジェネレーターで生成した。

/* mk_by_switch.c */
#include <stdio.h>
int main() {
  int i;
  puts("#include <stdint.h>");
  puts("int8_t calc(int8_t x, int8_t y) {");
  puts("  switch ((y + 128) << 8 | (x + 128)) {");
  puts("  default:");
  for (i = 0; i < 65536; ++i) {
    printf("  case %d: return 0;\n", i);
  }
  puts("  }");
  puts("}");
  return 0;
}

これを、こう。

$ make mk_by_switch && ./mk_by_switch > by_switch.c

#おまけ：アセンブリ
最適化で爆速になった理由が気になるので switch 側のコードがどんなアセンブリに落とされたのか調べておく。

わかりやすさのために、各 case 文の return 値を (i % 256) - 128 に変えている。

##最適化なし
gcc -S by_switch.c で生成。以下、抜粋。

        .section        __TEXT,__text,regular,pure_instructions
        .macosx_version_min 10, 13
        .globl  _calc
        .p2align        4, 0x90
_calc:                                  ## @calc
        .cfi_startproc
## BB#0:
        pushq   %rbp
...
        jmpq    *%rdx
LBB0_1:
        jmp     LBB0_2
LBB0_2:
        movb    $-128, -1(%rbp)
        jmp     LBB0_65538
LBB0_3:
        movb    $-127, -1(%rbp)
        jmp     LBB0_65538
LBB0_4:
        movb    $-126, -1(%rbp)
        jmp     LBB0_65538
...
        jmp     LBB0_65538
LBB0_65537:
        movb    $127, -1(%rbp)
LBB0_65538:
        movsbl  -1(%rbp), %eax
        popq    %rbp
        retq
...

LBB0_1 ラベルが default ケース。そのままケース 0 の LBB0_2 ラベルにジャンプしている。
LBB0_2 では、即値 -128 をスタックに積んで LBB0_65538 ラベルにジャンプ。
以降、同様に return する値をスタックに積んで LBB0_65538 ラベルにジャンプしている。
LBB_65538 ラベルでは、スタックから eax レジスターに戻すべき値を読み出して、スタックレジスターを復帰してから呼び出し元に戻る、という処理が書かれている。

まさに教科書を読むかのよう。ジャンプ位置を計算して、それぞれ対応する即値を返すコードになっている。

##O3 最適化
gcc -O3 -S by_switch.c で生成。同様に抜粋、しようとおもったけれど、全部載せられる。

        .section        __TEXT,__text,regular,pure_instructions
        .macosx_version_min 10, 13
        .globl  _calc
        .p2align        4, 0x90
_calc:                                  ## @calc
        .cfi_startproc
## BB#0:
        pushq   %rbp
Lcfi0:
        .cfi_def_cfa_offset 16
Lcfi1:
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
Lcfi2:
        .cfi_def_cfa_register %rbp
        shll    $8, %esi
        addl    $32768, %esi            ## imm = 0x8000
        subl    $-128, %edi
        orl     %esi, %edi
        decl    %edi
        cmpl    $65534, %edi            ## imm = 0xFFFE
        ja      LBB0_2
## BB#1:
        addb    $-127, %dil
        movsbl  %dil, %eax
        popq    %rbp
        retq
LBB0_2:
        movl    $-128, %eax
        popq    %rbp
        retq
        .cfi_endproc

.subsections_via_symbols

計算、しきっている……！
たぶんだけれど、各命令語の後ろの l はハーフワードアクセス、レジスターの下位 16bit を使う処理、だよね。

Lcfi2 ラベルから。 8bit シフトしているところから esi レジスターに引数 y の値が乗っている。これに 0x8000 を足して符号反転。というより続く edi レジスターの x の処理と同様 -128 を引く、つまり 128 を足してから 8bit シフトした、と読んで良い。
そして or で (y + 128) << 8 | (x + 128) の値が edi レジスターに乗る。
ここから 1 引いて⁴ 65534 と比較。超えたらラベル LBB0_2 にジャンプ。
LBB0_2 ラベルでは -128 を eax に積んで関数からのリターン処理。つまり、こちらは default ケースの処理⁵。
LBB0_2 に飛ばなかった場合は、 -127 を di レジスターのハーフワード、つまり 8bit 値に足して、関数からの戻り値に設定。（先に edi の値をデクリメントしているので、これで辻褄があう）

コンパイラー、恐ろしい子……！

#[補足]未最適化のby_array.cアセンブリ
コメントで by_array.c は clang だと単純に 0 リターンするだけのコードになるので、速度比較として不適切ではないかと指摘をいただいた。

確認してみたところ、 わたしの環境 ではきちんと比較できるコードになっていたので追記報告。

gcc -S by_array.c で最適化なしで処理。

        .section        __TEXT,__text,regular,pure_instructions
        .macosx_version_min 10, 13
        .globl  _calc
        .p2align        4, 0x90
_calc:                                  ## @calc
        .cfi_startproc
## BB#0:
        pushq   %rbp
Lcfi0:
        .cfi_def_cfa_offset 16
Lcfi1:
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
Lcfi2:
        .cfi_def_cfa_register %rbp
        movb    %sil, %al
        movb    %dil, %cl
        leaq    _calc.table(%rip), %rdx
        movb    %cl, -1(%rbp)
        movb    %al, -2(%rbp)
        movsbl  -2(%rbp), %esi
        addl    $128, %esi
        shll    $8, %esi
        movsbl  -1(%rbp), %edi
        addl    $128, %edi
        orl     %edi, %esi
        movslq  %esi, %r8
        movsbl  (%rdx,%r8), %eax
        popq    %rbp
        retq
        .cfi_endproc

.zerofill __DATA,__bss,_calc.table,65536,4 ## @calc.table

.subsections_via_symbols

末尾のゼロ埋め bss セクションに、 65536 バイト分の領域が確保され _calc.table というシンボル名が付加されている。
コードテキストの Lcfi2 ラベル以降は、ざっくり引数 y 相当の esi レジスターと x 相当の edi レジスターで (y + 128) << 8 | (x + 128) の値になるアドレスオフセットを計算し leaq _calc.talbe(%rip), %rdx で rdx レジスターにロードした_calc.table シンボルのアドレスからの相対参照で movsbl (%rdx,%r8), %eax と eax レジスターにテーブルの値をロードして呼び出し元に返すという、これまた至極教科書的なコードが生成されている。

O3 最適化をかけた場合、コメントでいただいたコードと同じ、 0 を計算してそのまま返すコードに変換される。

Lcfi2:
        .cfi_def_cfa_register %rbp
        xorl    %eax, %eax
        popq    %rbp
        retq

蛇足だけれど、 eax レジスター上の値を、自身の値と xor することで 0 を得るのは、 x86 系での頻出イディオムです。

##テーブル参照でのO3最適化で、なおオフセット参照を強制する
蛇足ついでに O3 最適化で by_array.c をコンパイルして、しかしテーブルオフセット相対参照を最適化させない邪魔は、できるということも示しておきます。
（最適化すれば早くなるところを、なぜ、人間は邪魔するのでしょうね？　意地悪ですね）

/* by_array.c */
#include <stdint.h>

extern int8_t table[65536];

int8_t calc(int8_t x, int8_t y) {
  return table[(y + 128) << 8 | (x + 128)];
}

つまり、テーブルを by_array.c モジュールの外に掃き出して、

/* by_array_aux.c */
#include <stdint.h>

int8_t table[65536] = {0};

と、テーブルを別モジュールで定義する。

実行形式は gcc -o main by_array.c by_array_aux.c で生成。
コンパイラー邪魔版の by_array.c、 O3 最適化アセンブリは以下のとおり。

	.section	__TEXT,__text,regular,pure_instructions
	.macosx_version_min 10, 13
	.globl	_calc
	.p2align	4, 0x90
_calc:                                  ## @calc
	.cfi_startproc
## BB#0:
	pushq	%rbp
Lcfi0:
	.cfi_def_cfa_offset 16
Lcfi1:
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
Lcfi2:
	.cfi_def_cfa_register %rbp
	shll	$8, %esi
	addl	$32768, %esi            ## imm = 0x8000
	subl	$-128, %edi
	orl	%esi, %edi
	movslq	%edi, %rax
	movq	_table@GOTPCREL(%rip), %rcx
	movsbl	(%rcx,%rax), %eax
	popq	%rbp
	retq
	.cfi_endproc

オフセット計算が、先に確認した switch case O3 版に似たものになっていて、参照するテーブルシンボル _table のアドレスを GOT から得るべく movq _table@GOTPCREL(%rip), %rcx というコードに変換されている。

めでたくコンパイラーの最適化を邪魔して、きちんとテーブルから値を読ませることができました。

まとめると、テーブルルックアップによる処理を実装するなら、テーブルはモジュール内にインラインしておくと良い。
その心は、コンパイラーが、テーブル内の値の関係を推測して計算コードに置き換えてくれるかもしれないからです。テーブルのバイト実体を全部削除して、オブジェクトコードのサイズを小さくしてくれるかもしれないし、あるいはテーブルをオフセット参照せずに素早く返すべき値を計算して返すコードを生成してくれるかもしれない。

コンパイラー、恐ろしい子……！（二回目）

最適化なしの比較。しかし恐ろしいことに O3 最適化をかけると、ほぼ等速に。連邦のモビルスーツはバケモノか。 ↩
なんらかの計算をしている、ように見えて、実際には計算などせずに固定の値を返すだけ。 ↩
大雑把に比較できれば十分だと考え time コマンドを利用した。 ↩
なぜ引いたのかは、よくわからない……。 ↩
実際に LBB0_2 に飛ぶことはない。というのは引数は x, y とも int8_t なので switch 文の式の値が 65536 以上には決してならないから。 ↩