switch case と配列によるジャンプテーブルルックアップ。（最適化無しなら）早いのは配列

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

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

[^0]: 最適化なしの比較。しかし恐ろしいことに O3 最適化をかけると、ほぼ等速に。連邦のモビルスーツはバケモノか。

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

```bash
$ 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 の値を二つ受け取って、なんらかの計算をして[^1]結果を 8bit の値としてもどす、関数 `calc`。

[^1]: なんらかの計算をしている、ように見えて、実際には計算などせずに固定の値を返すだけ。

```c
int8_t calc(int8_t x, int8_t y);
```

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

```c
/* 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;
}
```

# 速度比較結果
配列テーブルによる実装を呼び出した結果[^2]。

[^2]: 大雑把に比較できれば十分だと考え time コマンドを利用した。

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

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

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

```text
$ 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 埋めしたテーブルを使った。

```c
/* 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

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

```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;
  }
}
```

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

```c
/* 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;
}
```

これを、こう。

```bash
$ 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` 引いて[^3] `65534` と比較。超えたらラベル `LBB0_2` にジャンプ。
`LBB0_2` ラベルでは `-128` を `eax` に積んで関数からのリターン処理。つまり、こちらは `default` ケースの処理[^4]。
`LBB0_2` に飛ばなかった場合は、 `-127` を `di` レジスターのハーフワード、つまり 8bit 値に足して、関数からの戻り値に設定。（先に `edi` の値をデクリメントしているので、これで辻褄があう）

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

[^3]: なぜ引いたのかは、よくわからない……。
[^4]: 実際に `LBB0_2` に飛ぶことはない。というのは引数は `x`, `y` とも `int8_t` なので switch 文の式の値が `65536` 以上には決してならないから。

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

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

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

```text
        .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 を計算してそのまま返すコードに変換される。

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

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

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

```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 モジュールの外に掃き出して、

```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 最適化アセンブリは以下のとおり。

```text
	.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` というコードに変換されている。

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

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

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