interpreters

インタープリターとバイトコード VM

目的

C/C++ で効率的なバイトコードインタープリターやシンプルな JIT を実装するためのガイドです。ディスパッチ戦略、VM アーキテクチャの選択肢、パフォーマンスパターンを扱います。

トリガー

• 「高速なバイトコードのディスパッチループを実装するにはどうすればよいですか？」
• 「switch ディスパッチと computed goto の違いは何ですか？」
• 「レジスタベース VM とスタックベース VM はどう実装すればよいですか？」
• 「インタープリターに基本的な JIT コンパイルを追加するにはどうすればよいですか？」
• 「インタープリターの動作が遅いのはなぜですか？」

ワークフロー

1. VM アーキテクチャの選択

方式	説明	例
スタックベース	値スタックにオペランドを格納します。バイトコードはコンパクトです	JVM、CPython、WebAssembly
レジスタベース	仮想レジスタにオペランドを格納します。命令数が少なくなります	Lua 5+、Dalvik
ダイレクトスレッディング	各「命令」が関数呼び出しです	一部の Forth 実装
継続渡し	インタープリター関数が継続を返します	学術用途

スタックベース： 実装しやすく、コンパイルも容易です。コード生成がシンプルになります。式あたりの命令数は多くなります。 レジスタベース： ディスパッチの反復回数は少なくなります。コンパイラーでレジスタ割り当てが必要ですが、複雑な式ではキャッシュ効率が向上します。

2. ディスパッチループの戦略

Switch ディスパッチ（最もシンプルな基本形）

while (1) {
    uint8_t op = *ip++;
    switch (op) {
        case OP_LOAD:  push(constants[*ip++]); break;
        case OP_ADD:   { Value b = pop(); Value a = pop(); push(a + b); } break;
        case OP_HALT:  return;
        // ...
    }
}

問題点：switch はジャンプテーブルからの単一の間接分岐にコンパイルされます。同じ間接分岐がすべてのオペコードで使われるため、最新の CPU では分岐予測を大きく誤る可能性があります。

Computed goto（GCC/Clang 拡張機能 — 移植性の高い最速の方法）

// Table of label addresses
static const void *dispatch_table[] = {
    [OP_LOAD]  = &&op_load,
    [OP_ADD]   = &&op_add,
    [OP_HALT]  = &&op_halt,
    // ...
};

#define DISPATCH() goto *dispatch_table[*ip++]

DISPATCH();  // start

op_load:
    push(constants[*ip++]);
    DISPATCH();

op_add: {
    Value b = pop(); Value a = pop(); push(a + b);
    DISPATCH();
}

op_halt:
    return;

各オペコードは、それぞれ独自の間接分岐で終わります。CPU はオペコードごとに分岐予測器を学習させられるため、予測精度が大幅に向上します。

注： &&label は GCC/Clang の拡張機能であり、標準 C ではありません。ほかのコンパイラーでは #ifdef __GNUC__ を使って条件分岐し、switch にフォールバックしてください。

ダイレクトスレッデッドコード（最も積極的な方式）

各バイトコードワードは関数ポインターまたはラベルアドレスです。VM 自体がフェッチ・デコード・実行ループになります。

typedef void (*Handler)(VM *vm);

// Bytecode is an array of handlers
Handler bytecode[] = { op_load, op_push_1, op_add, op_halt };

for (int i = 0; ; i++) {
    bytecode[i](vm);
}

3. 値の表現

タグ付きポインター： ポインターの下位ビットに型タグを格納します（ポインターのアラインメントにより、2 ビット以上が空いていることが保証されます）。

typedef uintptr_t Value;
#define TAG_INT    0x0
#define TAG_FLOAT  0x1
#define TAG_PTR    0x2
#define TAG_MASK   0x3

#define INT_VAL(v)   ((int64_t)(v) >> 2)
#define FLOAT_VAL(v) (*(float*)((v) & ~TAG_MASK))
#define IS_INT(v)    (((v) & TAG_MASK) == TAG_INT)

NaN ボクシング（64 ビット）： NaN のビットパターンに、double 以外の値を格納します。

// IEEE 754 quiet NaN: exponent all 1s, mantissa != 0
// Use high mantissa bits as type tag, low 48 bits as payload
// Allows pointer/int/bool/nil to fit in a double-sized slot

V8（旧方式）、LuaJIT、JavaScriptCore で使用されています。

4. スタック管理

#define STACK_SIZE 4096
Value stack[STACK_SIZE];
Value *sp = stack;  // stack pointer

#define PUSH(v) (*sp++ = (v))
#define POP()   (*--sp)
#define TOP()   (sp[-1])
#define PEEK(n) (sp[-(n)-1])

// Check for overflow
#define PUSH_SAFE(v) do { \
    if (sp >= stack + STACK_SIZE) { vm_error("stack overflow"); } \
    PUSH(v); \
} while(0)

5. インラインキャッシュ（IC）

インラインキャッシュは、各呼び出しサイトで最後に観測した型をキャッシュすることで、プロパティ検索とメソッドディスパッチを高速化します。

struct CallSite {
    Type   cached_type;      // Last observed receiver type
    void  *cached_method;    // Cached function pointer
    int    miss_count;       // Number of misses
};

void invoke_method(VM *vm, CallSite *cs, Value receiver, ...) {
    Type t = GET_TYPE(receiver);
    if (t == cs->cached_type) {
        // Cache hit: direct call, no lookup
        cs->cached_method(vm, receiver, ...);
    } else {
        // Cache miss: look up, update cache
        void *method = lookup_method(t, name);
        cs->cached_type = t;
        cs->cached_method = method;
        cs->miss_count++;
        method(vm, receiver, ...);
    }
}

多相 IC（PIC）：最大 N 個（通常は 4 個）の型とメソッドのペアをキャッシュします。

6. シンプルな JIT（mmap + マシンコード）

x86-64 の場合：実行可能メモリーを割り当て、マシンコードのバイト列を書き込み、それを呼び出します。

#include <sys/mman.h>
#include <string.h>

typedef int (*JitFn)(int a, int b);

JitFn jit_compile_add(void) {
    // x86-64: add rdi, rsi; mov rax, rdi; ret
    static const uint8_t code[] = {
        0x48, 0x01, 0xF7,   // add rdi, rsi
        0x48, 0x89, 0xF8,   // mov rax, rdi
        0xC3                 // ret
    };

    void *mem = mmap(NULL, sizeof(code),
                     PROT_READ | PROT_WRITE | PROT_EXEC,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (mem == MAP_FAILED) return NULL;

    memcpy(mem, code, sizeof(code));

    // On some systems (macOS Apple Silicon): must use mprotect
    // mprotect(mem, sizeof(code), PROT_READ | PROT_EXEC);

    return (JitFn)mem;
}

macOS の Apple Silicon（M シリーズ）では、pthread_jit_write_protect_np() または MAP_JIT フラグを使用します。

7. パフォーマンスのヒント

1. ディスパッチ： GCC/Clang では switch より computed goto を使用します
2. 値： NaN ボクシングまたはタグ付きポインターを使用し、ホットパスでのボクシング／アンボクシングを避けます
3. スタック： スタックポインターを呼び出し先保存レジスターに保持します（register Value *sp asm("r15") — GCC のグローバルレジスター変数）
4. ローカル変数へのアクセス： 頻繁にアクセスするローカル変数はスタックではなく、VM のレジスター（構造体フィールド）に保持します
5. プロファイリング： perf またはサンプリングを使って、ディスパッチのオーバーヘッドと実際の処理を特定します
6. 特化： よくある型の組み合わせに対して、特化したハンドラーのバリエーションを生成します（int+int の加算と汎用的な加算など）
7. トレース記録： トレース JIT（LuaJIT の方式）は、関数全体ではなくホットトレースをコンパイルします

ディスパッチ戦略のベンチマークについては、references/benchmarks.md を参照してください。

関連スキル

• インタープリターのディスパッチループをプロファイリングするには、skills/profilers/linux-perf を使用します
• JIT の出力を理解するには、skills/low-level-programming/assembly-x86 を使用します
• バイトコードパーサー／ローダーをファジングするには、skills/runtimes/fuzzing を使用します
• LLVM IR ベースの JIT（MCJIT / ORC JIT）には、skills/compilers/llvm を使用します