引数の組み合わせの数が少ない関数を実装する場合、あらかじめ計算済みの値を配列に埋めておいて返す方法と、 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 というコードに変換されている。
めでたくコンパイラーの最適化を邪魔して、きちんとテーブルから値を読ませることができました。
まとめると、テーブルルックアップによる処理を実装するなら、テーブルはモジュール内にインラインしておくと良い。
その心は、コンパイラーが、テーブル内の値の関係を推測して計算コードに置き換えてくれるかもしれないからです。テーブルのバイト実体を全部削除して、オブジェクトコードのサイズを小さくしてくれるかもしれないし、あるいはテーブルをオフセット参照せずに素早く返すべき値を計算して返すコードを生成してくれるかもしれない。
コンパイラー、恐ろしい子……！（二回目）