🚀
[Zig]自作tree-walkerインタプリタでLuaに張合う話

2025/11/04に公開
 はじめに「簡単な言語処理系を作ってみたい」──プログラミングに興味がある人なら、一度はそう思ったことがあるのではないでしょうか。しかし、いざ作ってみると「動くけど遅い」と感じた経験を持つ人も多いはずです。
本記事では、Zigで小さな(1ksteps以内)Joy風のスタック指向言語を実装し、単純なtreewalkerインタプリタでありながら一部ベンチで標準版Luaと同等の性能を達成した方法を紹介します。

 インタプリタの実装方式と性能の関係
 2つの基本的な実装方式プログラミング言語のインタプリタには、大きく分けて2つの実装方式があります。
tree-walkerインタプリタは、プログラムを構文木（AST）として表現し、そのノードを再帰的に辿りながら実行する方式です。実装がシンプルで理解しやすいのが特徴ですが、一般的に性能面不利(後述のバイトコードインタプリタより5〜20倍ほど遅い)とされています。
バイトコードインタプリタは、構文木を一度バイトコード（命令列）にコンパイルしてから実行する方式です。LuaやPythonなど、多くの実用的なインタプリタがこの方式を採用しています。

 tree-walkerの性能課題tree-walkerが遅いとされる主な理由はメモリ局所性の悪さです。
構文木はツリー構造なので、各ノードがメモリ上のバラバラな場所に配置されます。プログラムを実行する際、インタプリタはノードからノードへとポインタを追いかけながら処理を進めますが、このとき次のような問題が発生します。

CPUキャッシュミスの頻発: 次に読むデータがキャッシュになく、遅いメインメモリからの読み込みが必要になる

メモリアクセスパターンの予測困難: CPUの投機実行やプリフェッチが効きにくい
対照的に、バイトコード方式では命令が連続したメモリ領域に配置されるため、次の命令がすでにキャッシュに載っている可能性が高く、効率的に実行できます。

 例外的に高速なtree-walker: PicoLispしかし、すべてのtree-walkerが遅いわけではありません。PicoLispというLisp処理系は、tree-walkerでありながらバイトコードVMに近い性能を発揮します。
筆者が測定したフィボナッチ計算（再帰版、37番目の数）の実行時間は以下の通りです。


処理系
実行時間
備考


Lua(標準版) 5.4.6
1.36秒
バイトコードVM

miniPicoLisp
1.67秒

tree-walker（C実装のPicoLisp）[1]


Ruby 2.5.9
1.90秒
バイトコードVM

Ruby 3.2.3
1.29秒
バイトコードVM（JITコンパイラ無効）

Ruby速…[2]

PicoLispの高速性を支える設計上の特徴は次の通りです。[3]

小さいeval関数: 実行の中核部分が非常にコンパクト

一様なオブジェクトサイズ: すべての値が同じメモリサイズ(2ワード)

専用メモリプール: 構文木を含むオブジェクト用のメモリをまとめて確保し、メモリ局所性を向上

動的スコープ: 環境なし、検索コストなし
ここで重要なのは、型システムがシンプルだからこそ、オブジェクトサイズの統一とメモリ効率が両立するという点です。複雑な型を持つ言語では、各オブジェクトのサイズが異なるため、このような最適化は困難です。

 Joyというアプローチ──変数を持たない言語PicoLispの性能は印象的ですが、さらに改善の余地があります。それは変数束縛のコストです。
一般的にLispインタプリタでは変数を使うたびに環境（変数と値の対応表）を検索する必要があります。動的スコープを採用するPicoLispでは、この検索コストこそ存在しませんが、束縛毎に変数の退避とリストアが必要で、少なくないオーバーヘッドが存在します。
ここで注目したのがJoy[4]という言語です。
JoyはManfred von Thoによって設計されたプログラミング言語です。その最大の特徴は変数を一切持たないことです。

 Joyの基本的な仕組みJoyは所謂スタック指向言語で、すべての操作がデータスタックを介して行われます。
# 通常の言語での計算: (3 + 4) * 5
3 4 + 5 *

# スタックの変化:
# [3]         # 3をプッシュ
# [3 4]       # 4をプッシュ
# [7]         # +で加算
# [7 5]       # 5をプッシュ
# [35]        # *で乗算
関数も同じくスタックを操作します。
# 二乗する関数
DEFINE square == dup * .

# 使用例: 5の二乗
5 square .   # => [25]
このように、変数名を介さず、スタックの位置だけで値を扱います。

 Joyを選んだ理由Joyのアプローチには、性能面で次の利点があります。

環境管理が不要: 変数がないため、環境の検索・更新処理がゼロになる

メモリアクセスの単純化: スタックという連続したメモリ領域だけを操作する

実装の簡潔性: evalループが極めてシンプルになる
理論的には、PicoLisp以上のメモリ局所性とキャッシュ効率を実現できる可能性があります。[5]

 実装の核心技術本実装では、PicoLispの設計思想を参考に以下の最適化を施しました。

 1. 下位ビットタグ付きポインタによる型表現すべての値を64bitのポインタサイズに統一し、下位ビットタグ付きポインタという技法を使って型情報を埋め込みました。
この技法が可能なのは、64bitアーキテクチャにおけるメモリアライメントの性質を利用しているためです。現代のメモリアロケータは、効率的なメモリアクセスのため、ポインタを8バイト（64bit）境界に配置します。これにより、ポインタの下位3ビットは必ず0になります。この「使われていない3ビット」を型タグとして活用するのが下位ビットタグ付きポインタです。
通常のポインタ:    0x7fff1234abcd000  (下位3ビットが0)
タグ付きポインタ:  0x7fff1234abcd001  (下位3ビットで型を表現)
本実装では、最下位の1ビットを整数型の判別に、2ビット目をメモリ管理（線形性フラグ）に使用しました。
// タグ定義
const TAG_INT: Word = 0b1;        // 整数
const TAG_LIST: Word = 0b0000;    // リスト
const TAG_SYM: Word = 0b1000;     // シンボル
const FLAG_LINEAR: Word = 0b0010; // 線形オブジェクトフラグ
const MASK_ADDR: Word = ~@as(Word, 0b1111);
[6]
この方式により次の利点が得られます。

シンプルなメモリアクセス: すべての値が8バイトになり、配列やスタックの操作が高速に

高速な型判定: ビットマスクだけで型を判定可能（分岐予測も効きやすい）

メモリ効率: 別途型情報を保持する必要がない

 2. 型変換不要な整数演算さらに、整数型の表現方法を活かして、四則演算を型変換なしで直接実行できるようにしました。
整数値は (実際の値 << 1) | 0b001 という形式なので、2つの整数を加算すると次のようになります。
  (x << 1) | 0b001
+ (y << 1) | 0b001
= ((x+y) << 1) | 0b010  # タグが0b010になる

# 0b001に戻すため1を引く
= ((x+y) << 1) | 0b001
これにより、算術演算を極めて単純に実装できます。
// 加算: タグを補正するだけ
PRIM_ADD => {
    const b = stack[sp - 1];
    const a = stack[sp - 2];
    if ((a & b & 1) == 0) return error.TypeMismatch;
    sp -= 1;
    stack[sp - 1] = a + b - 1;  // 型変換なし！
},

// 減算
PRIM_SUB => {
    // ...
    stack[sp - 1] = a - b + 1;
},

// 比較演算もそのまま
PRIM_EQ => {
    // ...
    stack[sp - 1] = if (a == b) T else F;
},
関数呼び出しやビット操作による型変換が完全に不要になるため、演算のオーバーヘッドが極小化されます。

 3. メモリプール設計PicoLispの手法を参考に、専用のメモリプールを実装しました。リストのセル（Cons）とシンボルオブジェクトを一度に大量に確保し、連続したメモリ領域に配置することで、キャッシュ効率を高めています。
// メモリプール管理
const POOL_SIZE: usize = 4096;
var mem_pool_head: Word = 0;
var all_pools: std.ArrayList([POOL_SIZE][2]Word) = undefined;

fn expand_mem_pool() !void {
    const new_pool = try all_pools.addOne();
    
    // フリーリストを構築
    var i: usize = 0;
    while (i < POOL_SIZE - 1) : (i += 1) {
        const next_addr = @intFromPtr(&new_pool[i + 1]);
        new_pool[i][0] = next_addr;
    }
    new_pool[POOL_SIZE - 1][0] = mem_pool_head;
    mem_pool_head = @intFromPtr(&new_pool[0]);
}

fn alloc_obj() !*[2]Word {
    if (mem_pool_head == 0) {
        try expand_mem_pool();
    }
    const obj: *[2]Word = @ptrFromInt(mem_pool_head);
    mem_pool_head = obj[0];  // フリーリストから取り出し
    return obj;
}
すべてのオブジェクトが2ワード（16バイト）固定サイズなので、フリーリストによる単純な管理が可能です。メモリプールを使うことで、次の効果が得られます。

アロケーションの高速化: システムのmallocを頻繁に呼ばずに済む

メモリ局所性の向上: セルが連続したメモリ領域に配置される

キャッシュミスの削減: 次のオブジェクトがすでにキャッシュに載っている可能性が高い

 4. 線形型システムによるメモリ管理本実装では、独自の線形型システムを導入しました。これは、パース時に生成される永続的なオブジェクト（構文木）と、実行時に生成される一時的なオブジェクトを区別するための仕組みです。
const FLAG_LINEAR: Word = 0b0010;  // 線形オブジェクトフラグ

inline fn is_linear(w: Word) bool {
    return !is_int(w) and !is_prim(w) and w != 0 and 
           (w & FLAG_LINEAR) != 0;
}

// 線形オブジェクトのみを解放
inline fn discard(w: Word) void {
    if (!is_linear(w)) return;
    discard_linear(w);
}
この設計により次の利点があります。

参照カウント不要: 線形オブジェクトは即座に解放可能

GCのオーバーヘッド排除: ガベージコレクションが不要

不要なコピーの抑止: 構文木上の永続的なオブジェクトはコピー不要

 5. evalループの最適化最も効果が大きかったのは、evalループの設計です。
標準的なインタプリタでは、要素ごとに型を判定して関数を呼び出します。
// 一般的な実装（簡略化）
fn eval(expr: Value) void {
    var current = expr;
    while (isCons(current)) {
        const elem = getCar(current);
        
        // 型によって処理を分岐
        if (isBuiltin(elem)) {
            callBuiltin(elem);
        } else if (isNumber(elem)) {
            stack.push(elem);
        }
        // ...
        current = getCdr(current);
    }
}
この実装には次の問題がありました。

関数呼び出しのオーバーヘッド: 各要素ごとに関数を呼び出し、スタックフレームを作成・破棄

分岐予測の失敗: 次にどの型が来るかわからないため、CPUの分岐予測器が効きにくい

間接ジャンプの多用: 型判定→分岐→関数呼び出しという間接的なジャンプが頻発
これを解決するため、ループを展開し、型判定と処理をすべてインライン化[7]しました。
fn eval(prog: Word) anyerror!void {
    //...
    while (true) {
        //...
        // ループを9回分展開
        inline for (0..9) |_| {
            if (cursor == NIL) return;
            const obj = get_ptr(cursor);
            const op = obj[0];
            cursor = obj[1];
            
            // すべてインライン展開
            if (is_symbol(op)) {
                const op_val = symbol_op(op);
                if (is_int(op_val)) {
                    const code = @as(u64, op_val);
                    try execute_primitive(code);
                } else {
                    try eval(op_val);
                }
            } else if (is_linear(op)) {
                const copied = try deep_copy(op);
                try push(copied);
            } else {
                try push(op);
            }
        }
    }
    //...
}
Zigのinline forを使うことで、コンパイラが8回分のループを完全に展開します。この変更により次の効果が得られました。

ジャンプ命令の削減: ループの終端判定が8分の1に

分岐予測の改善: 展開されたコードが単純な直線的実行になる

命令キャッシュの効率化: 連続した命令列がCPUの命令キャッシュに効率的に載る

 6. スタック境界チェックの最適化スタック操作の境界チェックを効率化するため、チェックの頻度を大幅に削減しました。
単純なインタプリタでは、pushやpopのたびにスタックの上限・下限をチェックします。しかし、これは大きなオーバーヘッドになります。
本実装では、次の観察に基づいて最適化しました。
リテラルやプリミティブがスタックに追加する要素は高々1個
プリミティブの引数チェックで下限は保証できる
スタックの上限を実際よりも小さく設定することで、evalループの展開数である約9回に1回のチェックで十分
fn eval(prog: Word) anyerror!void {
    //...
    while (true) {
        // 上限チェック: 9回に1回まとめてチェック
        if (sp >= STACK_MAX) return error.StackOverflow;
        
        // ループを9回分展開（各操作は高々1要素を追加）
        inline for (0..9) |_| {
            if (cursor == NIL) {
                if (sp >= STACK_MAX) return error.StackOverflow;
                // 再帰呼び出し時でも9回に1回以上を保証
                return;
            }
            //...
        }
    }
}
プリミティブ関数側では、必要な引数分の下限チェックを最初にまとめて実行します。
inline fn execute_primitive(code: u64) anyerror!void {
    switch (code) {
        PRIM_ADD => {
            // 下限チェック: 引数2個分をまとめてチェック
            if (sp < btm + 2) return error.StackUnderflow;
            const b = stack[sp - 1];
            const a = stack[sp - 2];
            if ((a & b & 1) == 0) {
                discard(pop());
                discard(pop());
                return error.TypeMismatch;
            }
            // 直接スタック操作（チェック不要）
            sp -= 1;
            stack[sp - 1] = a + b - 1;
        },
        
        PRIM_CONS => {
            // 引数2個分のチェック
            if (sp < btm + 2) return error.StackUnderflow;
            const car_val = pop();
            errdefer discard(car_val);
            const cdr_val = pop();
            errdefer discard(cdr_val);
            const new_list = try make_list(car_val, cdr_val, true);
            // 上限チェック不要（evalループでチェック済み）
            push(new_list);
        },
        // ...
    }
}
この最適化により、次の効果が得られます。

チェック回数の削減: 従来はpush時とpop時だったチェックが、約4回に1回（上限）+ プリミティブごとに1回（下限）に

分岐予測の改善: チェックの分岐が減り、CPUの分岐予測が効きやすくなる

 7. その他の細かい最適化
インライン関数の徹底活用: 型判定、スタック操作、リスト操作など、すべての小さな関数をinline展開。また、evalなどの再帰関数や大きめの関数でも引数チェックの部分だけinline化して関数呼出しを減らすと効果があります。

スタックの静的配列化: 動的メモリ確保を避け、固定サイズの配列をスタックとして使用[8]
地味ですがif文とswitch文の選択、判定順序もCPUの分岐予測に影響を与えます。

 最終的なベンチマーク結果すべての最適化を適用した結果、次の性能を達成しました。

 フィボナッチ数列（37番目の数、再帰版）20回実行の平均値:


処理系
実行時間
備考


Lua(標準版) 5.4.6
1.36秒
バイトコードVM

本実装
1.35秒
tree-walker

miniPicoLisp
1.67秒

tree-walker（C実装のPicoLisp）

Ruby 2.5.9
1.90秒
バイトコードVM

Ruby 3.2.3
1.29秒
バイトコードVM（JITコンパイラ無効）

tree-walkerインタプリタでありながら、Luaのバイトコードインタプリタとほぼ同等の性能を実現しました。
測定環境:
CPU: Intel Core i5-12400
OS: Ubuntu 24.04.1
コンパイラ: Zig 0.11.0[9]（ReleaseFastモード）

 まとめ本記事では、ZigでJoy風のスタック指向言語を実装し、tree-walkerインタプリタでLuaのバイトコードVMと同等の性能を達成するまでの取り組みを紹介しました。

 得られた知見実装を通じて、以下の点を確かめることができました。
メモリ局所性の重要性: 専用メモリプールと固定サイズオブジェクトの採用により、tree-walkerでもバイトコードインタプリタに匹敵する性能を実現できる
変数管理のコスト: 変数束縛を排除したスタック指向アプローチはダイナミックスコープによるO(1)の解決アルゴリズムよりも高速
バイトコードVM技術の応用可能性: スタック境界チェックの最適化などはtree-walkerにも有効に適用できる
本実装はベンチマーク特化型の最適化が含まれているため、より汎用的な言語機能を追加した場合の性能維持が今後の課題です。
「tree-walkerは遅い」という定説は、条件次第で覆すことができます。本記事が、言語処理系の実装に興味を持つ方々の参考になれば幸いです。

 参考文献PicoLisp公式サイト: https://picolisp.com/
Joy言語: https://www.kevinalbrecht.com/code/joy-mirror/
Zig言語公式ドキュメント: https://ziglang.org/documentation/

 付録各言語のコードは以下の通り
Lua
function fib(n)
    if n < 2 then
        return n
    else
        return fib(n - 1) + fib(n - 2)
    end
end

fib(37)
Ruby
def fib(num)
  if num < 2
    return num
  end
  fib(num - 1) + fib(num - 2)
end

fib(37)
miniPicoLisp
(de fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
(fib 37)
本記事で実装した言語
DEFINE fib == dup 2 < [] [dup 1 - fib swap 2 - fib +] ifte .
37 fib

脚注
なぜminiの方を載せているかというと私の測定環境だと本家より(なぜか)速いから ↩︎
一昔前だとPicoLispの方がRuby、Pythonより断然速かったんですが、、、ちなみに起動は他の言語の方が圧倒的に速いのでLuaのバランスの良さが光ります。なおJITとは本当に勝負にならないので割愛します ↩︎
詳細はリファレンスを参照。個人的には単純な型システムとダイナミックスコープを持つ言語はここくらいまでは(構文木の設計を頑張れば)最適化できると思います。シェルとか ↩︎
何でスタック指向言語の中でもJoyかと言うと単純で動的言語と表現力が近いから。Joyの仕様でもifteのように明らかに性能を下げるものは後発のFactor等に近い意味論に変えてあります(なのであくまでJoy風) ↩︎
もうここまで来るとバイトコードインタプリタと何が違うのかよく分からない気もしますが、評価対象が結合リストでもまとめに書いた工夫でどこまでいけるか検証するというのが実際のモチベーションでした ↩︎
4ビット目が使われているのはオブジェクトのメモリを16バイト境界で獲得しているため。オブジェクトサイズが一様な場合、サイズが2の倍数なら大きいほど使えるビット数が増えます ↩︎
ほんとはダイレクトスレッディングをやりたいんですが第一級ラベルがないのでinline forでお茶を濁しました。展開数は今回のベンチマークにチューニングしているので一般的な最適解は別である可能性があります ↩︎
ヒープに取って境界チェックをOSにやらせる案もありましたが、実測したらやや遅でした。 ↩︎
AIに得意なバージョンを聞いたら0.11だったため。今回の取り組みは言語とAIの学習を兼ねており、最適化ついてもAIの出力を取り入れています。なお0.14に対応したら遅くなった。謎… ↩︎
処理系	実行時間	備考
Lua(標準版) 5.4.6	1.36秒	バイトコードVM
miniPicoLisp	1.67秒	tree-walker（C実装のPicoLisp）^[1]
Ruby 2.5.9	1.90秒	バイトコードVM
Ruby 3.2.3	1.29秒	バイトコードVM（JITコンパイラ無効）
はじめに

インタプリタの実装方式と性能の関係

2つの基本的な実装方式

tree-walkerの性能課題

例外的に高速なtree-walker: PicoLisp

Joyというアプローチ──変数を持たない言語

Joyの基本的な仕組み

Joyを選んだ理由

実装の核心技術

1. 下位ビットタグ付きポインタによる型表現

2. 型変換不要な整数演算

3. メモリプール設計

4. 線形型システムによるメモリ管理

5. evalループの最適化

6. スタック境界チェックの最適化

7. その他の細かい最適化

最終的なベンチマーク結果

フィボナッチ数列（37番目の数、再帰版）

まとめ

得られた知見

参考文献

付録

Discussion
