引数の組み合わせの数が少ない関数を実装する場合、あらかじめ計算済みの値を配列に埋めておいて返す方法と、 switch case で対応する値を返す方法と、を使うことがある。
どちらも値の置かれたアドレスを計算できる。片やそのアドレスの値をロードして返し、他方はアドレスにジャンプして返す、という処理になるので速度は同じでは？ とおもっていた。
しかしそんなことはなく、 最適化をしなければ 配列方式が五倍ちかく高速1だった。
使った 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 の値を二つ受け取って、なんらかの計算をして2結果を 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;
}
速度比較結果
配列テーブルによる実装を呼び出した結果3。
$ 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 引いて4 65534 と比較。超えたらラベル LBB0_2 にジャンプ。
LBB0_2 ラベルでは -128 を eax に積んで関数からのリターン処理。つまり、こちらは default ケースの処理5。
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 というコードに変換されている。
めでたくコンパイラーの最適化を邪魔して、きちんとテーブルから値を読ませることができました。
まとめると、テーブルルックアップによる処理を実装するなら、テーブルはモジュール内にインラインしておくと良い。
その心は、コンパイラーが、テーブル内の値の関係を推測して計算コードに置き換えてくれるかもしれないからです。テーブルのバイト実体を全部削除して、オブジェクトコードのサイズを小さくしてくれるかもしれないし、あるいはテーブルをオフセット参照せずに素早く返すべき値を計算して返すコードを生成してくれるかもしれない。
コンパイラー、恐ろしい子……！（二回目）
clang だと単に 0 を返すコードになるようですが比較としてあんま筋が良くない気がしますね。
https://godbolt.org/g/aAAxoV
-O3' を指定した際の出力コードはどうなったでしょうか?-O3' を指定してもすぐにコンパイルは終了したのですが、clang では数分待ってもコンパイルが終了しなかったので出力コードの確認は諦めました。当方の環境では、gcc では
20分ほど掛かりましたが clang でのコンパイルも終了しました。出力コードは配列参照版と変わらないですね。
@fujitanozomu さん、コメントありがとうございます。
by_array.c が、速度を比較するコードとして不適切なのではないかという疑問、もっともだと感じ、調査した内容を追記しました。
そもそもの話としてコンパイラの最適化機能に不具合がある等の事情でもない限りは完成したプログラムは最適化を有効化して出力したコードとなるのだし最適化を禁止した条件で速度を比較する意味がわかりません。
@fujitanozomu 再びのコメントありがとうございます。
最終的に動かすことを目的としたプログラムは、サイズや速度、なにがしかの最適化を施して使う。おっしゃるとおりと思います。
ところで、本稿は、最終的に動かすものを興味の対象としていません。
初出時から一貫して、ルックアップテーブルによるジャンプが配列を使った場合と switch case を使った場合とで、それらが機械語にどのように翻訳されるのか、同じか、違いがあるなら、それはどこなのかを照準しています。
これを踏まえて、より良い記事とするための改稿案を提案くださると幸いです。
最適化を禁止した実験が無駄だという、ご意見は受け止めます。
けれど、この記事の主旨はそこではありません。最適化を最優先にした論旨展開への変更はしかねます。（最適化によってジャンプがなくなってしまうことは、ご確認くださったとおりです）
最適化禁止実験の無駄について是非を語りたいのでしたら、別記事での展開をご検討ください。その折には、この記事やコメントをリンクいただいて構いません。
よろしくお願いします。
switch 〜 case が条件次第でテーブルジャンプになるのはコンパイラの最適化によるものであることは理解されてますか?