Issue #4753: Faster opcode dispatch on gcc

Python gcc optimization

追記: typo修正。テストコードに余計な「r」が含まれてたのと、「PICコード」とか間抜けなこと書いてたのを。

Issue #4753

職場でも話題になったので。

このパッチのコメントによると、threaded codeにしたほうが分岐予測が効果的に働き、15%-20%ほど速くなるとのこと。computed goto自体は、threadedにする都合によるものなので、実はあまり本質的ではない。

要は、分岐予測は分岐命令ごとに、特定の呼び出しパターンを検出することで行われるものなので、ディスパッチする箇所が1カ所になっているよりは複数箇所になっている方が有効に利用できるということらしい。

つまり、

int *op = opcodes;

for (;;) {
    static void *table = { &&OP_ADD, &&OP_LOAD, ... };
    goto table[*op];
OP_ADD:
    ... /* OP_ADDのハンドラ */
    continue;

OP_LOAD:
    ... /* OP_LOADのハンドラ */
    continue;
...
}

よりも、

int *op = opcodes;

for (;;) {
    static void *table = { &&OP_ADD, &&OP_LOAD, ... };
    goto table[*op];
OP_ADD:
    ...  /* OP_ADDのハンドラ */
    goto table[*op];

OP_LOAD:
    ... /* OP_LOADのハンドラ */
    goto table[*op];
...
}

の方がいいということのようだ。

より具体的にいうと、例えば

a.b.c = 5

のようなコードは

LOAD_CONST
LOAD_FAST
LOAD_ATTR
STORE_ATTR

のようなインストラクション列にコンパイラされるわけだけど、このようなコードは随所にあるので、似たようなインストラクション列が同様に何度も実行されることになる。それぞれのインストラクションのハンドラごとにディスパッチを行うことで、特定のインストラクション列の実行に関しては予測がより的確となり、効率よく実行できる、そういった理屈だ。

これが本当かどうかを確かめるため、簡単なVMを書いて実験してみた。

上のようにどちらのケースでもgotoを使うのではなく一方ではswitchを使っている理由は、最適化を行うと、勝手に2番目のようなコードをコンパイラが吐いてしまうからだ。

#include <stdio.h>
#include <string.h>

typedef struct exec_ctx_t {
    int locals[16];
} exec_ctx_t;

#define OP_END   0
#define OP_DUP   1
#define OP_ADD   2
#define OP_SUB   3
#define OP_LOAD  4
#define OP_STORE 5
#define OP_CONST 6
#define OP_PRINT 7
#define OP_BPOS  8

static void exec_ctx_init(exec_ctx_t *ctx)
{
    memset(ctx->locals, sizeof(ctx->locals), 0);
}

static void run(exec_ctx_t *ctx, const int *op)
{
    const int *p = op;
    int stack[16];
    size_t sp = 0;

    for (;;) {
#if USE_COMPUTED_GOTO
        static const void * const op_addr[] = {
            &&op_END, &&op_DUP, &&op_ADD, &&op_SUB, &&op_LOAD, &&op_STORE,
            &&op_CONST, &&op_PRINT, &&op_BPOS
        };
#define OP(label) op_##label
#define DISPATCH \
    if (__builtin_expect(*(unsigned int *)p < sizeof(op_addr) / sizeof(op_addr)[0], 0)) \
        goto *op_addr[*p]; \
    else \
        continue;
#define NEXT DISPATCH
#define SKIP
#else
#define OP(label) case OP_##label
#define DISPATCH switch (*p)
#define NEXT continue
#define SKIP default: continue;
#endif

        DISPATCH
        {
        SKIP
        OP(END):
            ++p;
            break;

        OP(DUP):
            ++p;
            stack[sp] = stack[sp - 1];
            ++sp;
            NEXT;

        OP(ADD):
            ++p;
            stack[sp - 2] = stack[sp - 2] + stack[sp - 1];
            --sp;
            NEXT;

        OP(SUB):
            ++p;
            stack[sp - 2] = stack[sp - 2] - stack[sp - 1];
            --sp;
            NEXT;

        OP(LOAD):
            ++p;
            stack[sp++] = ctx->locals[*p];
            ++p;
            NEXT;

        OP(STORE):
            ++p;
            ctx->locals[*p] = stack[--sp];
            ++p;
            NEXT;

        OP(CONST):
            ++p;
            stack[sp++] = *p;
            ++p;
            NEXT;

        OP(PRINT):
            ++p;
            printf("%d\n", stack[--sp]);
            NEXT;

        OP(BPOS):
            {
                int off;
                ++p;
                off = *p;
                ++p;
                if (stack[--sp] > 0)
                    p += off;
            }
            NEXT;
        }
        break;
    }
}

int main(int argc, char **argv)
{
    exec_ctx_t ctx;
    static int op[] = {
        /* a = 10000000; */
        OP_CONST, 100000000, OP_STORE, 0,
        /* b = 5; */
        OP_CONST, 5, OP_STORE, 1,
        /* c = 3; */
        OP_CONST, 3, OP_STORE, 2,
        /* b = b + c; */
        OP_LOAD, 1, OP_LOAD, 2, OP_ADD, OP_STORE, 1,
        /* c = c - b; */
        OP_LOAD, 2, OP_LOAD, 1, OP_SUB, OP_STORE, 2,
        /* a = a - 1; */
        OP_LOAD, 0, OP_CONST, 1, OP_SUB,
        OP_DUP,
        OP_STORE, 0,
        OP_BPOS, -32,
        OP_LOAD, 1, OP_PRINT,
        OP_END
    };
    exec_ctx_init(&ctx);

    run(&ctx, op);

    return 0;
}

以下のようにして、

cat /tmp/options | while read opts; do eval "gcc $opts -o test test.c" && echo -n "$opts      " && ( for ((i=0; i < 4; ++i)); do /usr/bin/time -f '%U' ./test 2>&1; done ) | ( sed -e '1 n; s/^/ + &/' | tr -d "\n"; echo) | bc; done

手元のマシン (Core2 Q9550@2.83GHz) で計ってみると

コンパイルオプション 4回繰り返しでの経過時間
-m32 -O0 -DUSE_COMPUTED_GOTO=0 74.65
-m32 -O0 -DUSE_COMPUTED_GOTO=1 75.39
-m32 -O3 -DUSE_COMPUTED_GOTO=0 42.53
-m32 -O3 -DUSE_COMPUTED_GOTO=1 45.98
-m64 -O0 -DUSE_COMPUTED_GOTO=0 74.98
-m64 -O0 -DUSE_COMPUTED_GOTO=1 74.96
-m64 -O3 -DUSE_COMPUTED_GOTO=0 43.61
-m64 -O3 -DUSE_COMPUTED_GOTO=1 45.19
-m32 -fPIC -O0 -DUSE_COMPUTED_GOTO=0 74.73
-m32 -fPIC -O0 -DUSE_COMPUTED_GOTO=1 81.91
-m32 -fPIC -O3 -DUSE_COMPUTED_GOTO=0 44.60
-m32 -fPIC -O3 -DUSE_COMPUTED_GOTO=1 46.50
-m64 -fPIC -O0 -DUSE_COMPUTED_GOTO=0 75.04
-m64 -fPIC -O0 -DUSE_COMPUTED_GOTO=1 75.94
-m64 -fPIC -O3 -DUSE_COMPUTED_GOTO=0 44.88
-m64 -fPIC -O3 -DUSE_COMPUTED_GOTO=1 45.14

どういうわけかほとんどの場合でcomputed gotoのほうが遅いという結果に。
職場の人に「Prescottとかだとパイプラインの段数が多そうだから違う結果になるんじゃないの?」と言われたので試してみました。

Pentium 4 Prescott (model=3) 3.00GHz

コンパイルオプション 4回繰り返しでの経過時間
-O0 -DUSE_COMPUTED_GOTO=0 143.38
-O0 -DUSE_COMPUTED_GOTO=1 113.95
-O3 -DUSE_COMPUTED_GOTO=0 80.06
-O3 -DUSE_COMPUTED_GOTO=1 59.07
-fPIC -O0 -DUSE_COMPUTED_GOTO=0 170.69
-fPIC -O0 -DUSE_COMPUTED_GOTO=1 97.57
-fPIC -O3 -DUSE_COMPUTED_GOTO=0 76.75
-fPIC -O3 -DUSE_COMPUTED_GOTO=1 48.76

はい、ビンゴでした。全然違いますねー。Core i7でも速くなってるのかな。

というわけでまとめ

  • 分岐予測を当てにした最適化は特定のCPUにしか効果がない可能性が高いことを心得るべし。
  • PICではインダイレクションが1段増えるので利用できるレジスタが1つ減る可能性があることを考慮すべし。(とくにx86 32bitで)
  • コンパイラがどのようにコードを最適化するのかを常に観察すべし。

PICの方が速い理由については調べなきゃなあ。