ハクソク

世界を動かす技術を、日本語で。

高速な動的言語インタプリタの作り方

16時間前原文(zef-lang.dev)

概要

  • Zefという動的言語のASTウォーク型インタプリタを最適化し、LuaやCPythonに匹敵する速度を達成
  • JITやGC最適化ではなく、基礎部分の工夫で16倍以上の高速化を実現
  • 値表現、インラインキャッシュ、オブジェクトモデル、ウォッチポイントなどの技術を解説
  • ScriptBench1によるベンチマークで他言語と比較
  • 各最適化の具体的な手法と効果を順を追って説明

Zefインタプリタ最適化の旅：基礎からLua/QuickJS/CPython並みの速度へ

  • Zefは筆者が趣味で作った動的言語
  • ASTウォーク型インタプリタの最適化でLuaやQuickJS、CPythonに近い速度を目指す試み
  • 多くの言語実装記事はJITやGC改善が中心だが、本記事は基礎からの最適化に焦点
  • 紹介する最適化はSSAやGC、バイトコード、機械語不要のシンプルなもの
  • 16倍（Yolo-C++移植で67倍）の高速化を達成

評価方法とベンチマーク

  • ScriptBench1という独自ベンチマークを作成
    • Richards（OSスケジューラ）、DeltaBlue（制約ソルバー）、N-Body（物理シミュレーション）、Splay（二分木テスト）
  • 他言語（JavaScript、Python、Lua）版も用意し比較
  • Ubuntu 22.04.5, Intel Core Ultra 5 135U, 32GB RAM, Fil-C++ 0.677で測定
  • Lua 5.4.7（GCC 11.4.0）、QuickJS-ng 0.14.0（公式バイナリ）、CPython 3.10（標準）を使用
  • 各実験は30回ランダムに実行し平均値を利用

オリジナルZefインタプリタの特徴

  • 64ビットタグ付き値（ダブル、32ビット整数、Object*）を使用
    • JavaScriptCore由来のNaNタグ付けで高速パスとヒープ割り当て回避を実現
  • C++ベースで低レベル最適化が可能
  • **Fil-C++**を利用し、GCやメモリ安全性を自動化（ただし4倍程度遅くなる）
  • ASTノードごとに仮想関数evaluateを再帰呼び出しする構造
  • 変数名やキーにstd::string、スコープ管理にunordered_mapを多用
  • クロージャやスコープチェーンもC++で再帰的に管理
  • 設計はシンプルだが、CPythonの35倍、Luaの80倍、QuickJSの23倍遅い

主な最適化とその効果

  • Zef Baseline
    • 他言語に比べて大幅に遅い（例：CPythonの35倍遅い）

最適化 #1: 演算子の直接呼び出し

  • パーサが各演算子ごとに**専用ASTノード（Binary<>やUnary<>）**を生成
  • 文字列比較によるディスパッチを排除し、高速な関数呼び出しに
  • 17.5%高速化
    • まだCPythonの30倍遅いが、一歩前進

最適化 #2: RMW演算子（+=など）の直接呼び出し

  • RMW（Read Modify Write）演算子も専用ノード化
  • enumによる分岐でディスパッチ高速化
  • 3.7%高速化
    • 1.22倍速になり、CPythonの29倍遅い

最適化 #3: IntObject判定の回避

  • isInt()の仮想関数呼び出しを回避し、int32/doubleのみを高速パスに
  • IntObjectの処理はIntObject自身に委譲
  • 1%の高速化
    • 1.23倍速、CPythonの29倍遅い

最適化 #4以降: さらなる高速化と工夫

  • シンボル（Symbol）化による文字列比較の削減
  • 値のインライン化でヒープアクセスを減少
  • オブジェクトモデル刷新とインラインキャッシュ導入で大幅な高速化
  • 引数処理、ゲッター/セッター、callMethodのインライン化
  • ハッシュテーブル最適化、std::optional回避、引数の特殊化
  • 値のスローパス改善、冗長な評価関数の重複排除、sqrtやtoStringの高速化
  • 配列リテラルの特殊化、callOperatorの最適化、C++設定の改善、assertの除去
  • Yolo-C++移植でさらに大幅な高速化（66倍以上）

まとめ

  • 基礎的な設計や値表現の選択がインタプリタ性能に大きく影響
  • JITやGC以前にできる最適化で、成熟した言語処理系に匹敵する速度が狙える
  • シンプルな工夫の積み重ねで、動的言語のインタプリタでも十分なパフォーマンスを実現可能

参考：最適化ごとの速度比較（抜粋）

| 実装・最適化 | ベース比 | CPython比 | Lua比 | QuickJS比 | |----------------------|---------|----------|---------|-----------| | Zef Baseline | 1x | 35.4x遅 | 79.6x遅 | 22.6x遅 | | Direct Operators | 1.175x | 30.2x遅 | 67.7x遅 | 19.2x遅 | | Object Model & IC | 6.818x | 5.2x遅 | 11.7x遅 | 3.3x遅 | | Array Literal Spec | 15.351x | 2.3x遅 | 5.2x遅 | 1.47x遅 | | Value callOperator | 16.344x | 2.2x遅 | 4.9x遅 | 1.38x遅 | | Yolo-C++ | 66.962x | 1.9x速 | 1.2x遅 | 3x速 |

今後の展望

  • GCやJITの導入前でも、基礎的な設計と地道な最適化で十分な高速化が可能
  • 動的言語インタプリタの実装経験や最適化の勘所を学びたい人に有用な事例

Hackerたちの意見

面白いね、シェアしてくれてありがとう。いつか詳しく探ってみたいテーマだな。Githubによると、このリポジトリは99.7%がHTMLで、0.3%がC++なんだって。インタプリタのサイズの証明かな？
└
スタティックに生成したサイトをコミットしたんだけど、コードの生成方法が無駄に大きくなっちゃった。でも、インタプリタ自体はすごく小さいよ。
Fil-Cの使い心地はどう？実際に役立ってる？
└
バイアスがかかってるけど、Filはこのプロジェクトでかなり役立ったよ。 - 複数のメモリ安全性の問題を、いい感じで決定論的にキャッチできたから、オブジェクトモデルの設計が思ったより楽だった。 - 正確なGCを持つC++は、すごく良いプログラミングモデルだと思う。普通のC++に比べて1.5倍くらい速くなった気がするし、他のGC付き言語に対しても1.2倍くらい速いかも（C++のAPIが豊富で、ラムダやテンプレート、クラスシステムが成熟してるからね）。でも、いろんな意味でバイアスがかかってるけどね。 - Fil-C++を作ったし、C++を35年くらいやってるから。
Luaが含まれてるのはいいけど、LuaJITも入ってたらよかったな。
└
LuaJITがZefを圧倒するだろうね！というか、圧倒してほしいな、あれだけエンジニアリングがかかってるんだから。他にもいろんなランタイムを含められたけど、入れなかった。PUC LuaがQuickJSやPythonよりもずっと速いのは本当にすごいよ。
記事で言及されてるYOLO-c++コンパイラって何？ググっても何も出てこないし、ChatGPTも知らないみたい。
└
Fil-Cの作者であり、この言語の作者でもある人が、「Yolo-C/C++」って言うと、Fil-Cなしの普通のC/C++を指してるんだ。
同じような感じで、動的言語Wrenのインタープリタのパフォーマンスについてのページを見てみてね。https://wren.io/performance.html Zefの記事が実装技術について説明しているのに対して、Wrenのページは言語設計がパフォーマンスにどう貢献するかも示してるんだ。特に、Wrenは動的オブジェクトの形状を放棄していて、これがコピー・ダウン継承を可能にして、メソッドの検索をかなり簡素化（つまり加速）してる。個人的には、これはいいトレードオフだと思う。実際、クラスの構築後にメソッドを追加する必要がどれだけあった？
└
これは、モンキーパッチが慣用的に受け入れられている言語、特にRubyでは常に行われていることだね。ただ、Rubyはスピード重視の考え方では知られてないけど。逆に、適用可能な関数の閉じたセットを持つ型って、ちょっと疑問が残るよね。Nim（マクロあり）、Scala（暗黙のクラスと型クラス）、Kotlin（拡張関数）、Rust（トレイト）など、任意の関数を定義して、最初の引数の型に合った変数にドット表記でメソッドとして使える言語もあるよ。
└
うん、言語設計はインタープリタやJITの速度にとって非常に重要な要素だよ。動的言語用の高度に最適化されたVMはたくさんあるけど、LuaJITが王様なのは、Luaがとても小さくて適した言語だからなんだ。いくつか最適化が難しい特徴もあるけど、それは少ないから努力する価値がある。Pythonとは全然違うよ。Pythonは、動的要素が重なり合って、速いJITの可能性を最小限に抑えるように設計されてるって言っても過言じゃない。何年もかけて、CPython 3.15のJITはようやくx86_64の標準インタープリタより約5%速くなったんだ。
└
> 特に、Wrenは動的オブジェクトの形を諦めていて、これがコピー・ダウン継承を可能にし、メソッドの検索を大幅に簡素化（そして加速）するんだ。一般的なルールとして、もし式に静的な型を割り当てられるなら、かなり効率的にコンパイルできるってこと。複雑な動的言語は明らかにこれに対抗する方法をいくつも持っていて、結果的に最適化が難しくなるんだよね。振り返ってみると明らかだね。
変更#5から#6（インラインキャッシュ + 隠れクラスオブジェクトモデル）へのジャンプが、ここでの大部分の作業を担ってるのは、V8/JSCが歴史的に速くなった理由と一致するね。プロパティアクセスの動的ディスパッチは、素朴なインタープリタがつまずくところで、他の部分は比較すると誤差みたいなもんだ。各ステップの貢献が独立して見えるように整理されてるのはいいね。ほとんどのパフォーマンスのレポートは最終的な数字だけを示すから。
└
同意するけど、これは特定のベンチマークに関するもので、実際のコードの大半を反映してないと思う。これは、sqrtを高速化して得られた1.6%の改善に基づいてるんだ。それには驚いたよ。そんな改善を得るには、ベンチマークが最初から1.6%以上の時間をそこに費やしている必要があるからね。gitリポジトリを見た感じ、nbodyシミュレーションでそれが起こったみたいだね。https://github.com/pizlonator/zef/blob/master/ScriptBench/nb...
└
@jiusanzhou 変更#6の面白い実装の詳細は、ASTを歩くインタープリターでのインラインキャッシングのやり方だね。バイトコードインタープリターでは、ICの書き換えは自然なんだ。キャッシュサイトはバイトコードストリーム内の安定したバイトオフセットで、パッチを当てられるからね。ここでは、キャッシュサイトがASTノードだから、@pizlonatorはプレースメントnewを使って、汎用のASTノードの上に特化したASTノードをその場で構築してる（constructCache経由で）。これはASTレベルでの自己修正コードなんだ。ただし、これには可変ASTノードが必要で、ほとんどのコンパイラが依存している不変ASTの仮定と矛盾するんだよね（例えば、部分木を共有したり、コンパイルを並列化したりするために）。シングルスレッドのインタープリターではうまくいくけど、インタープリターがノードを変更している間に同じASTからJITコンパイルしたい場合は問題になるね。
この演習で、fil c自体を良くするために何か学べたと思う？
└
うん、ユニオンの扱い方をもっと良くしないとダメだな。あと、値オブジェクトのメソッドにアウトラインコールを使うのがすごくコストかかるのも問題だよね。
パースと評価の間でASTに対して最適化パスを実行してる？
└
「resolve」パスを実行してるよ。そこで、例えばゲッターの推論が行われるんだ。
└
インタープリターやAST実行環境にとって、最初から効率的なパースが大きな勝利になると思う。特に、式のために優先度パーサーを使うことで、再帰的降下を避けられるし、文法の1:1「ユニット生成」を取り除くためにASTを最適化する必要がなくなるんだよね。
CのメモリエラーをチェックするためにTCCのバウンドチェッカーを使ってるんだけど、コードをデバッグするためにFil-Cに切り替えた方がいいかな？もちろん、yolo-Cがターゲットなんだけど。