LoginSignup
4
3

More than 5 years have passed since last update.

@ryohji(亮志 池邉)

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

Last updated at Posted at 2018-02-17

引数の組み合わせの数が少ない関数を実装する場合、あらかじめ計算済みの値を配列に埋めておいて返す方法と、 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 というコードに変換されている。

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

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

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

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

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

  3. 大雑把に比較できれば十分だと考え time コマンドを利用した。 ↩

  4. なぜ引いたのかは、よくわからない……。 ↩

  5. 実際に LBB0_2 に飛ぶことはない。というのは引数は x, y とも int8_t なので switch 文の式の値が 65536 以上には決してならないから。 ↩

4
3
12

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
3