高速な動的言語インタプリタを作る方法

 (zef-lang.dev)
6 ポイント 投稿者 GN⁺ 8 일 전 | 1件のコメント | WhatsAppで共有
  • ASTを直接走査するインタプリタでも、値表現、インラインキャッシュ、オブジェクトモデル、watchpoint、反復的な細部最適化だけで大きな性能向上が可能
  • 性能をほとんど考慮していない Zef ベースラインは、CPython 3.10 より35倍、Lua 5.4.7 より80倍、QuickJS-ng 0.14.0 より23倍遅かったが、21段階の最適化の後に 16.646倍の高速化 を達成
  • 最大の飛躍は オブジェクトモデルの再設計とインラインキャッシュの組み合わせ で生まれ、Storage と Offsets ベースのアクセス、キャッシュされた AST 特化、名前オーバーライド監視用 watchpoint の適用により、さらに 4.55 倍改善
  • 追加改善として、文字列ベースのディスパッチ除去、Symbol 導入、引数受け渡し構造の変更、getter と setter の特化、ハッシュテーブル短縮経路、配列リテラルと sqrt・toString の特化まで累積適用
  • Yolo-C++ 移植まで含めると ベースライン比で66.962倍高速 を記録し、CPython 3.10 より 1.889 倍高速、QuickJS-ng 0.14.0 より 2.968 倍高速だが、メモリ解放がないため長時間実行ワークロードには不向き

導入と評価方法論

  • 最適化対象は ASTを直接走査するインタプリタ であり、遊びで作った動的言語 Zef を Lua、QuickJS、CPython と競争可能な水準 まで引き上げることが目標
    • JIT コンパイラや成熟した GC の微調整よりも、基盤のない出発点でも適用できる最適化に集中
    • 扱う手法は 値表現、インラインキャッシュ、オブジェクトモデル、watchpoint、常識的な最適化の反復適用
  • 本文の手法だけで SSA、GC、バイトコード、マシンコードなしでも 大きな性能向上を達成
    • 本文基準で 16倍高速化
    • 未完成の Yolo-C++ 移植 を含めると 67倍高速化
  • 性能評価には ScriptBench1 ベンチマークスイートを使用
    • 含まれるベンチマークは Richards OS スケジューラ、DeltaBlue 制約ソルバ、N-Body 物理シミュレーション、Splay 二分木テスト
    • JavaScript、Python、Lua 向けの既存ポートを使用
    • Splay の Python および Lua ポートは Claude で生成
  • 実験環境は 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 は GitHub releases のバイナリを使用
    • CPython 3.10 は Ubuntu 標準提供版を使用
  • すべての実験は ランダムにシャッフルした30回実行の平均値 を使用
  • ほとんどの比較は Fil-C++ でコンパイルした Zef インタプリタ と Yolo-C コンパイラでビルドした他のインタプリタ群 の間で実施

元の Zef インタプリタ

  • 性能をほとんど考慮せずに書かれており、性能を意識した選択は2つだけだったと明記

  • 値表現

    • 64ビット tagged value を使用
      • 格納できる値は double、32ビット整数、Object*
    • double は 0x1000000000000 オフセット 方式で表現
      • JavaScriptCore から学んだ手法として紹介
      • 文献では NuN tagging と呼ばれる
    • 整数とポインタはネイティブ表現を使用
      • ポインタ値が 0x100000000 より小さくない という仮定に依存
      • 危険な選択だと明言
      • 代替として、整数に 0xffff000000000000 の上位ビットタグを付ける案があったと言及
    • この表現により、数値演算で ビットテストベースの高速経路 を実装可能
    • より重要な利点は、数値に対する ヒープ割り当ての回避
    • 新しくインタプリタを作るときは、基本の値表現を初期段階で適切に選ぶこと が重要で、その後の変更は非常に難しい
    • 動的型付き言語実装の出発点として 32ビットまたは64ビット tagged value を提示

  • 実装言語の選択

    • 最適化を十分に盛り込める言語として C++ 系 を選択
    • Java は低レベル最適化の上限があるため選ばないと明記
    • Rust は GC 言語実装に必要な グローバルな可変状態 と 循環参照 を持つヒープ表現のため選ばないと説明
      • 多言語構成を受け入れるか大量の unsafe コードを許容するなら、一部または全部で Rust を使う可能性には言及

  • 性能エンジニアリング観点での誤った選択

    • Fil-C++ の使用
      • 素早く開発でき、GC をただで提供
      • メモリ安全性違反を診断情報とスタックトレース付きで報告
      • 未定義動作がない
      • 性能コストは通常 約4倍
    • 再帰的 AST ウォーキングインタプリタ
      • 複数箇所でオーバーライドされる virtual Node::evaluate メソッド構造
    • 文字列の乱用
      • Get AST ノードが変数名を表す std::string を保持
      • 変数アクセスのたびにその文字列を使用
    • ハッシュテーブルの乱用
      • Get 実行時に文字列キーで std::unordered_map を検索
    • 再帰呼び出しチェーンに基づくスコープ探索
      • ほぼあらゆる構造のネストとクロージャを許可
      • 関数 F の中のクラス A、クラス B の中の関数 G のようなネストでは、A のメソッドは A のフィールド、F のローカル変数、B のフィールド、G のローカル変数 を見られる
      • 元の実装では、これを異なるスコープオブジェクトへ問い合わせる C++ の再帰関数 群で処理

  • 元の実装の特性

    • 誤った選択にもかかわらず、少ないコードで かなり複雑な言語インタプリタ を実装可能
    • 最大のモジュールは parser
    • それ以外は単純で明快なほう

  • 初期性能

    • 元のインタプリタは CPython 3.10 より35倍遅い

    • Lua 5.4.7 より80倍遅い

      • QuickJS-ng 0.14.0 より23倍遅い

全体の最適化進行表

  • 表は Zef Baseline から Zef Change #21: No Asserts、そして Zef in Yolo-C++ までの性能変化を整理
    • 比較列は vs Zef Baseline、vs Python 3.10、vs Lua 5.4.7、vs QuickJS-ng 0.14.0
  • 最終行基準で Zef Change #21: No Asserts はベースライン比で 16.646倍高速

    • Python 3.10 より 2.13 倍遅い

    • Lua 5.4.7 より 4.781 倍遅い

      • QuickJS-ng 0.14.0 より 1.355 倍遅い

  • Zef in Yolo-C++** はベースライン比で**66.962倍高速

    • Python 3.10 より 1.889 倍高速

    • Lua 5.4.7 より 1.189 倍遅い

      • QuickJS-ng 0.14.0 より 2.968 倍高速

初期最適化段階

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

    • パーサーはもはや演算子を 演算子名を持つ DotCall ノード として作らず、各演算子ごとの 個別の AST ノード を生成
    • Zef では a + b と a.add(b) は同一
      • もともとは a + b を DotCall(a, "add") と引数 b としてパース
      • すべての算術演算ごとに 演算子メソッド名の文字列参照 が発生
      • DotCall は文字列を Value::callMethod に渡す
      • Value::callMethod は 複数回の文字列比較 を実行
    • 変更後、パーサーは Binary<>、Unary<> ノードを生成
      • テンプレートとラムダを活用し、演算子ごとに 異なる Node::evaluate オーバーライド を提供
      • 各ノードはその演算子に対応する Value の高速パス を直接呼び出す
      • 例として a + b は Binary<add 用ラムダ>::evaluate を呼び出した後、Value::add を呼び出す
    • 性能効果は 17.5% 向上
      • この時点の性能は CPython 3.10 より 30 倍遅い
      • Lua 5.4.7 より 67 倍遅い
      • QuickJS-ng 0.14.0 より 19 倍遅い

  • 最適化 #2: RMW 演算子の直接呼び出し

    • 通常の演算子は高速化されたが、a += b のような RMW 形式は依然として文字列ベースのディスパッチを使用
    • パーサーが各 RMW ケース用の 個別ノード を生成するよう変更
    • パーサーは LValue ノードが makeRMW 仮想呼び出しを通じて自身を RMW に置き換える よう要求
    • RMW に変わる LValue は Get、Dot、Subscript
      • Get は変数読み取り id に対応
      • Dot は expr.id に対応
      • Subscript は expr[index] に対応
    • 各仮想呼び出しは SPECIALIZE_NEW_RMW マクロを使用
      • SetRMW は id += value
      • DotSetRMW は expr.id += value
      • SubscriptRMW は expr[index] += value
    • 変更 #1 の演算子特殊化はラムダディスパッチを使用
    • RMW は enum を使用
      • get、dot、subscript の 3 経路をすべて処理し、enum を複数箇所に渡す必要があるためこの方式を選択
      • 最終的に Value::callRMW<> テンプレート関数 が実際の RMW 演算子呼び出しディスパッチを実行
    • 性能効果は 3.7% 向上
      • この時点の性能は CPython 3.10 より 29 倍遅い
      • Lua 5.4.7 より 65 倍遅い
      • QuickJS-ng 0.14.0 より 18.5 倍遅い
      • 開始時点比で 1.22 倍高速

  • 最適化 #3: IntObject チェックの回避

    • Value の高速パスが isInt() を使い、その内部の isIntSlow() が Object::isInt() 仮想呼び出し を行う点がボトルネック
    • もとの値表現には 4 つのケースが存在
      • tagged int32
      • tagged double
      • int32 で表現できない int64 用の IntObject
      • それ以外のすべてのオブジェクト
    • IntObject の場合でも整数メソッドのディスパッチは Value が担当
      • すべての算術演算の実装を 1 か所、つまり Value に置くため
    • 最適化後、Value の高速パスは int32 と double だけを考慮
      • IntObject 処理ロジックは IntObject 自身に移動
      • メソッドディスパッチのたびに発生していた isInt() 呼び出しを回避
    • 性能効果は 1% 向上
      • この時点の性能は CPython 3.10 より 29 倍遅い
      • Lua 5.4.7 より 65 倍遅い
      • QuickJS-ng 0.14.0 より 18 倍遅い
      • 開始時点比で 1.23 倍高速

  • 最適化 #4: Symbol

    • もとのインタプリタは std::string をほぼあらゆる場所で使用
    • コストの高い文字列使用箇所は Context::get, Context::set, Context::callFunction、Value::callMethod, Value::dot, Value::setDot、Value::callOperator<>、Object::callMethod 系
    • この構造では単純なハッシュテーブル参照ではなく、文字列キーのハッシュテーブル参照 になるため、実行中に 文字列ハッシュ化と比較が繰り返される
    • 最適化では文字列ベースの参照を hash-consed な Symbol オブジェクトポインタ に置き換え
    • 新しい Symbol クラス を追加
      • symbol.h, symbol.cpp に実装
      • Symbol と文字列は相互変換可能
      • 文字列を Symbol に変換する際、グローバルハッシュテーブル で hash consing を実行
      • 結果として Symbol* ポインタの同一性比較 だけで同じシンボルかどうかを判定
    • 文字列リテラルの代わりに 事前に用意されたシンボル を使用
      • 例として "subscript" の代わりに Symbol::subscript
    • 多くの関数シグネチャが const std::string& の代わりに Symbol* を使うよう変更
    • 性能効果は 18% 向上
      • この時点の性能は CPython 3.10 より 24 倍遅い
      • Lua 5.4.7 より 54 倍遅い
      • QuickJS-ng 0.14.0 より 15 倍遅い
      • 開始時点比で 1.46 倍高速

  • 最適化 #5: Value のインライン化

    • 核心は重要な関数群の インライン化を可能にすること
    • ほぼすべての変更の中心は新しいヘッダー valueinlines.h の導入
    • value.h と別ヘッダーに分けた理由は、value.h をインクルードしなければならないヘッダー群 を利用するため
    • 性能効果は 2.8% 向上
      • この時点の性能は CPython 3.10 より 24 倍遅い
      • Lua 5.4.7 より 53 倍遅い
      • QuickJS-ng 0.14.0 より 15 倍遅い
      • 開始時点比で 1.5 倍高速

オブジェクトモデルとキャッシュ構造の再設計

  • 最適化 #6: オブジェクトモデル、インラインキャッシュ、Watchpoint

    • Object、ClassObject、Context の動作方式を大規模に再構成し、オブジェクト割り当てコストを下げ、アクセス時のハッシュテーブル参照を回避
    • この変更は オブジェクトモデル、インラインキャッシュ、watchpoint の3機能を組み合わせたもの

  • オブジェクトモデル

    • 以前は各レキシカルスコープごとに Context オブジェクトを割り当てていた
      • 各 Context は、そのスコープの変数を格納するハッシュテーブルを保持
    • オブジェクトはさらに複雑な構造だった
      • 各オブジェクトが、自身がインスタンスであるクラス群を Context に対応付けるハッシュテーブルを保持
    • この構造が必要だった理由は継承とネストしたスコープにある
      • Bar が Foo を継承するとき、Bar と Foo がそれぞれ異なるスコープをクロージャとして捕捉する
      • 同名でも異なる private フィールドを持てる
    • 新しい構造では Storage の概念を導入
      • データは Offsets に従って格納される
      • offset はどの Context かによって決まる
    • Context は今も存在するが、オブジェクトやスコープ生成時ではなく、AST の resolve パスで事前に生成される
    • 実際のオブジェクトやスコープ生成時には、その Context が計算したサイズに合わせて Storage だけを割り当てる

  • インラインキャッシュ

    • expr.name のようなコード位置で、最後に見た expr の動的型と、name が解決された直前の offsetを記憶する手法
    • JIT の文脈で説明されることが多い古典的手法だが、ここではインタプリタに適用している
    • 記憶した情報は、通常の AST ノード上に特殊化された AST ノードを placement construct する形で実装

  • インラインキャッシュの構成要素

    • CacheRecipe
      • 特定のアクセスが何を行ったか、キャッシュ可能かどうかを追跡
    • Context、ClassObject、Package の各所に CacheRecipe 呼び出しを挿入
      • アクセス過程の情報を収集
    • Dot::evaluate のような AST 評価関数は、自身が実行した多相演算から得た CacheRecipe を this とともに constructCache<> に渡す
    • constructCache
      • CacheRecipe に応じて新しい AST ノード特殊化をコンパイル
      • テンプレート機構で多様な特殊化 AST ノードを生成
      • ローカル変数アクセスであれば、渡された storage に対する直接ロード
      • 最後に見たクラスと同一か確認する class check
      • その後、最後に見た関数への直接関数呼び出し
      • 必要に応じて chain step と watchpoint を組み合わせる
    • キャッシュ対象の AST ノードはそれぞれ cached variant を保持
      • まず cache オブジェクトで高速呼び出しを試みる
      • cache オブジェクトの型は constructCache<> が決定する

  • watchpoint

    • レキシカルスコープに変数 x があり、その中にクラス Foo があり、Foo のメソッドが x にアクセスする例を示す
    • Foo 内部に x という関数や変数がなければ、すぐ外側の x を読めるように見える
    • しかしサブクラスが getter x を追加できる
    • その場合、アクセス結果は外側の x ではなく getter でなければならない
    • インラインキャッシュはこの変更可能性を処理するため、実行時に Watchpoint を設定する
    • この例では、この名前がオーバーライドされたかどうかを監視する watchpoint を使う

  • 3機能を同時に実装した理由

    • 新しいオブジェクトモデルだけでは、インラインキャッシュがうまく機能しない限り意味のある改善は難しい
    • インラインキャッシュも watchpoint がなければ、多くのキャッシュ条件を安全に扱いにくく、実利が小さい
    • 新しいオブジェクトモデルと watchpoint は一緒にうまく動作する必要がある

  • 実装の進行と難所

    • 開始時点では、単純な CacheRecipe バージョンの作成と、最終形に近い Storage、Offsets の設計から進めた
    • 最も難しい作業の1つは、intrinsic class の実装方式の置き換えだった
    • 配列の例
      • 以前は ArrayObject::tryCallMethod が Object::tryCallMethod の仮想呼び出しを横取りする方式で、すべてのメソッドを実装していた
      • 新しいオブジェクトモデルでは Object に vtable も仮想メソッドもない
      • 代わりに Object::tryCallMethod は object->classObject()->tryCallMethod(object, ...) に委譲する
      • したがって Array メソッドを提供するには、そのメソッドを持つ Array 用クラス自体を生成する必要がある
    • 結果として intrinsic 機能のかなりの部分が、実装全体に散らばっていた構造から makerootcontext.cpp 中心へと移動した
    • これを好ましい結果と評価した理由は、オブジェクトの native/intrinsic 関数にもインラインキャッシュがそのまま適用されるため
    • 性能効果は 4.55倍向上
      • この時点の性能は CPython 3.10 より 5.2 倍遅い
      • Lua 5.4.7 より 11.7 倍遅い
      • QuickJS-ng 0.14.0 より 3.3 倍遅い
      • 開始時点比で 6.8 倍高速
      • Fil-C++ の損失幅は、他のインタプリタと比べて概ね Fil-C のコスト水準まで縮小したと評価している

呼び出しとアクセス経路の最適化

  • 最適化 #7: 引数受け渡し構造の改善

    • 変更前の Zef インタプリタは関数引数を const std::optional<std::vector<Value>>& で受け渡していた
    • optional が必要だった理由は、一部のコーナーケースで次の 2 つを区別する必要があったため
      • o.getter
      • o.function()
    • Zef ではたいてい両方とも関数呼び出しだが、例外として次のコードが存在する
      • o.NestedClass
      • o.NestedClass()
    • 1 つ目は NestedClass オブジェクトそのもの を返す
    • 2 つ目は インスタンスを生成 する
    • したがって 引数なしの関数呼び出し と getter 系呼び出しとして引数配列が空である場合 を区別しなければならない
    • しかし既存の構造は非効率だった
      • 呼び出し側が vector を割り当て
      • 呼び出される側がそのベクタをコピーした arguments scope を再度割り当てる
    • 変更点は Arguments 型 の導入
      • 形は呼び出される側が作っていた arguments scope と完全に同一
      • これで呼び出し側が直接その形で割り当てるようになった
    • Yolo-C++ でも vector backing store の malloc を除去 して割り当て回数を削減
    • Fil-C++ では std::optional 自体がヒープ割り当て
      • std::optional がなくても const std::vector<>& の受け渡しもやはり割り当て が発生
      • スタック割り当てされるものはヒープ割り当てされると明記
      • 呼び出し側がベクタを事前にサイズ指定していないため 複数回再割り当て していた点にも言及
    • 変更のかなりの部分は関数シグネチャを Arguments* に置き換える作業
    • 性能効果は 1.33 倍向上
      • この時点の性能は CPython 3.10 より 3.9 倍遅い
      • Lua 5.4.7 より 8.8 倍遅い
      • QuickJS-ng 0.14.0 より 2.5 倍遅い
      • 開始時点比で 9.05 倍高速

  • 最適化 #8: Getter の特殊化

    • Zef は Ruby に似て インスタンスフィールドがデフォルトで private
    • 例 class Foo { my f fn (inF) f = inF }
      • コンストラクタで受け取った値を インスタンスにだけ見えるローカル変数 f に保存する
    • 同じ型のインスタンスでも他のオブジェクトの f にはアクセスできない
      • 例 fn nope(o) o.f
      • println(Foo(42).nope(Foo(666)))
      • nope 内の o.f は o の f にアクセスできない
    • 理由は、フィールドが クラスメンバーのスコープチェーンに現れる方式 で動作するため
      • o.f はフィールド読み取りではなく f という名前のメソッド呼び出し要求
    • そのため次のパターンがよく現れる
      • my f
      • fn f f
      • つまり ローカル変数 f を返す、名前が f のメソッド
    • より短い構文として readable f
      • my f と fn f f の短縮形
    • 多くのメソッド呼び出しは実質的に getter 呼び出し
    • すべての getter が AST を評価して動作するのは無駄
    • 最適化は getter の特殊化
      • 中心は UserFunction
      • 新しい Node::inferGetter メソッドで、関数本体が単純な getter かどうかを推論
    • 推論ルール
      • Block::inferGetter は、自身が含むものがすべて getter と推論可能なら getter と推論
      • Get::inferGetter は自分自身を getter と推論し、読み込む offset を返す
      • Context::tryGetFieldOffsets は、getter が実行されるレキシカルスコープにそのフィールドが 確実に存在する場合にのみ、空でない Offsets を返す
      • UserFunction は関数本体が getter と推論可能なら、既知の offset から直接読み取るだけの 特殊な Function サブクラス として resolve される
    • 性能効果は 5.6% 向上
      • この時点の性能は CPython 3.10 より 3.7 倍遅い
      • Lua 5.4.7 より 8.3 倍遅い
      • QuickJS-ng 0.14.0 より 2.4 倍遅い
      • 開始時点比で 9.55 倍高速

  • 最適化 #9: Setter の特殊化

    • setter 推論では fn set_fieldName(newValue) fieldName = newValue のパターンマッチが必要
    • UserFunction の推論段階で setter のパラメータ名 を渡す必要がある
    • Set の推論段階では ClassObject への書き込みではないこと を確認し、setter パラメータが set のソースとして使われているかも合わせて確認する必要がある
    • 性能効果は 3.4% 向上
      • この時点基準で Zef は CPython 3.10 より 3.6 倍遅い
      • Lua 5.4.7 より 8 倍遅い
      • QuickJS-ng 0.14.0 より 2.3 倍遅い
      • 開始時点比で 9.87 倍高速

  • 最適化 #10: callMethod のインライン化

    • 重要な関数を 1 行の変更 でインライン化
    • 性能効果は 3.2% 向上
      • この時点基準で Zef は CPython 3.10 より 3.5 倍遅い
      • Lua 5.4.7 より 7.8 倍遅い
      • QuickJS-ng 0.14.0 より 2.2 倍遅い
      • 開始時点比で 10.2 倍高速

  • 最適化 #11: ハッシュテーブル

    • メソッド呼び出しの inline cache ミス が発生すると ClassObject::tryCallMethod と ClassObject::TryCallMethodDirect をたどる必要があり、どちらの経路も大きく複雑だった
    • 既存の探索コストは 階層の深さに比例する O(hierarchy depth)
      • 階層の各クラスごとに、その呼び出しが メンバ関数として解釈されるか を確認するハッシュテーブル検索を行う
      • 階層の各クラスごとに、その呼び出しが ネストしたクラスとして解釈されるか を確認するハッシュテーブル検索も行う
    • 新しい変更で receiver class と symbol をキーに使うグローバルハッシュテーブルを導入
      • 1 回の検索で callee を直接返す
      • classobject.h では、全体の tryCallMethodSlow に落ちる前にまずこのグローバルテーブルを検索
      • classobject.cpp では、成功した検索結果をグローバルテーブルに記録
      • グローバルハッシュテーブル自体は比較的単純な実装
    • 性能効果は 15% 向上
      • この時点基準で Zef は CPython 3.10 より 3 倍遅い
      • Lua 5.4.7 より 6.8 倍遅い
      • QuickJS-ng 0.14.0 より 1.9 倍遅い
      • 開始時点比で 11.8 倍高速

  • 最適化 #12: std::optional の回避

    • Fil-C++ では union 関連のコンパイラ病理現象 のため std::optional にヒープ割り当てが必要
    • 一般に LLVM は union メモリアクセスの型を緩く扱うが、これが invisicaps と衝突する
      • union 内のポインタが、プログラマ視点では予測しづらい形で capability を失う場合 がある
      • その結果 Fil-C ではプログラマのミスがなくても null capability を持つオブジェクトの逆参照 で panic が発生
    • これを緩和するため、Fil-C++ コンパイラは union 型ローカル変数の処理で LLVM が保守的に動作するよう intrinsics を挿入
    • その後 FilPizlonator パスが独自の escape analysis を行い、union 型ローカル変数をレジスタ割り当て可能にしようと試みる
      • ただしこの分析は一般的な LLVM の SROA 分析ほど完全ではない
    • 結果として std::optional のような union を含むクラスの受け渡し は Fil-C++ ではメモリ割り当てにつながることが多い
    • 今回の変更は hot path で std::optional につながるコードパス を回避
    • 性能効果は 1.7% 向上
      • この時点基準で Zef は CPython 3.10 より 3 倍遅い
      • Lua 5.4.7 より 6.65 倍遅い
      • QuickJS-ng 0.14.0 より 1.9 倍遅い

  • 開始時点比で 12倍高速

  • 最適化 #13: 特化された引数

    • Zef のすべての built-in 関数 は 1 個または 2 個の引数を受け取り、ネイティブ実装ではそれを格納するための Arguments オブジェクトの割り当てが不要
    • setter も常に 1 個の引数 を受け取り、setter 推論が行われた場合は specialized setter 実装 も Arguments オブジェクトなしで値引数だけを直接受け取れば十分
    • 今回の変更で ZeroArguments、OneArgument、TwoArguments の特化引数型を導入
      • callee が必要としない場合、caller は Arguments オブジェクトの割り当てを回避
    • ZeroArguments は (Arguments*)nullptr と区別 するために必要
      • 従来は (Arguments*)nullptr を getter 呼び出しの意味 で使っており、そのロジックを維持
      • これからは ZeroArguments が 引数なし関数呼び出しの意味
    • 多くの変更は、引数を受け取る関数を テンプレート化 する作業で構成
      • ZeroArguments、OneArgument、TwoArguments、Arguments* それぞれについて 明示的インスタンス化 を実行
      • 既存コードのかなりの部分は Value::getArg を引数抽出ヘルパーとして使っており、ここに 特化引数オーバーロード を追加
      • 引数を使うネイティブコードの変更は比較的素直な修正
    • 性能効果は 3.8% 向上
      • この時点で Zef は CPython 3.10 より 2.9 倍遅い
      • Lua 5.4.7 より 6.4 倍遅い
      • QuickJS-ng 0.14.0 より 1.8 倍遅い
      • 開始時点比で 12.4倍高速

Fil-Cの病理回避と詳細な特殊化

  • 最適化 #14: 改良されたValue slow path

    • もう1つのFil-Cの病理現象回避により大きな高速化を確保
    • 変更前のValueのアウトオブラインslow pathはValueのメンバ関数で、暗黙の**const Value*引数**が必要だった
    • この構造ではcallerがValueをスタックに割り当てる必要がある
    • Fil-C++ではすべてのスタック割り当てがヒープ割り当てになる
      • そのためslow pathを呼び出すコードはValueをヒープに割り当てることになる
    • 変更後はこれらのメソッドを**staticにし、Valueを値渡し**するようにした
      • その結果、追加の割り当てが不要になった
    • 性能効果は10%向上
      • この時点でZefはCPython 3.10より2.6倍遅い
      • Lua 5.4.7より5.8倍遅い
      • QuickJS-ng 0.14.0より1.65倍遅い
      • 出発点比で13.6倍高速

  • 最適化 #15: DotSetRMWの重複排除

    • 一部の重複コードを削除
    • constructCache<>によって特殊化されるテンプレート関数では、機械語コードの削減が有利に働く可能性があると期待
    • 実際の結果は性能への影響なし

  • 最適化 #16: sqrtの特殊化

    • inline cacheは目的の関数へ呼び出しをうまくルーティングするが、オブジェクトに対してのみ動作する
    • 非オブジェクトでは、Binary<>、Unary<>、Value::callRMW<>のfast pathが、receiverが**intまたはdoubleかどうかを確認**する方式に依存する
    • この方式はパーサが認識する演算子にしか適用されない
      • value.sqrtのような形には適用されない
    • 今回の変更によりDotが**value.sqrt**に対して特殊化可能になった
    • 性能効果は1.6%向上
      • この時点でZefはCPython 3.10より2.6倍遅い
      • Lua 5.4.7より5.75倍遅い
      • QuickJS-ng 0.14.0より1.6倍遅い
      • 出発点比で13.8倍高速

  • 最適化 #17: toStringの特殊化

    • 前の最適化とほぼ同じ方法で**toStringの特殊化**を適用
    • この変更には、intを文字列に変換する際に発生する割り当て回数を減らすロジックも含まれる
    • 性能効果は2.7%向上
      • この時点でZefはCPython 3.10より2.5倍遅い
      • Lua 5.4.7より5.6倍遅い
      • QuickJS-ng 0.14.0より1.6倍遅い
      • 出発点比で14.2倍高速

  • 最適化 #18: 配列リテラルの特殊化

    • my whatever = [1, 2, 3]のようなコードでは、Zefの配列はエイリアス可能でミュータブルなため、新しい配列の割り当てが必要
    • 変更前は実行のたびにASTをたどって1、2、3を毎回再帰的に評価していた
    • 今回の変更ではArrayLiteralノードを定数配列の割り当てケースに特殊化
    • 性能効果は8.1%向上
      • この時点でZefはCPython 3.10より2.3倍遅い
      • Lua 5.4.7より5.2倍遅い
      • QuickJS-ng 0.14.0より1.5倍遅い
      • 出発点比で15.35倍高速

  • 最適化 #19: Value::callOperatorの改善

    • 以前、Valueを参照渡ししないことで高速化を得たのと同じ最適化を、callOperator slow pathにも適用
    • 性能効果は6.5%向上
      • この時点でZefはCPython 3.10より2.2倍遅い
      • Lua 5.4.7より4.9倍遅い
      • QuickJS-ng 0.14.0より1.4倍遅い
      • 出発点比で16.3倍高速

  • 最適化 #20: より良いC++オプション

    • Fil-C++では不要なRTTIとlibc++ hardeningを無効化
    • C++コード自体の変更はなく、ビルドシステム設定の変更のみを含む
    • 性能効果は1.8%向上
      • この時点でZefはCPython 3.10より2.1倍遅い
      • Lua 5.4.7より4.8倍遅い
      • QuickJS-ng 0.14.0より1.35倍遅い
      • 出発点比で16.6倍高速

  • 最適化 #21: assertの無効化

    • 最後の最適化としてassertionのデフォルト無効化を適用
    • 既存コードはFil-C専用の**ZASSERTマクロ**を使用
      • 常にassertを実行する構造だった
    • 変更後は内部の**ASSERTマクロ**を使用
      • ASSERTS_ENABLEDが設定されている場合にのみassertを実行
    • この変更には、コードがYolo-C++でビルドできるようにする別の修正も含まれる
    • 予想に反して高速化はなかった

Yolo-C++の結果と限界

  • コードを**Yolo-C++**でコンパイルした結果、4倍の高速化を確保
  • ただしこの方式はsoundではなくsuboptimal
    • soundでない理由は、既存のFil-C++ GC呼び出しが**calloc呼び出し**に置き換わるため
    • その結果メモリが解放されず、十分に長く実行されるワークロードではインタプリタがメモリ枯渇に達する
    • ScriptBench1ではテスト時間が短いためメモリ枯渇は発生しない
  • suboptimalである理由は、実際のGCアロケータがglibc 2.35の**callocより高速**だから
  • したがってYolo-C++ポートに実際のGCを追加すれば、4倍を超える高速化の可能性があると述べている
  • この実験ではGCC 11.4.0を使用
  • この時点でZefは

    • CPython 3.10より1.9倍高速

    • Lua 5.4.7より1.2倍遅い

    • QuickJS-ng 0.14.0より3倍高速

      • 出発点比で67倍高速

生ベンチマークデータ

  • ベンチマーク実行時間の単位は 秒
  • 表には各インタプリタごとの nbody、splay、richards、deltablue、geomean を含む

  • Python 3.10

    • nbody 0.0364
    • splay 0.8326
    • richards 0.0822
    • deltablue 0.1135
    • geomean 0.1296

  • Lua 5.4.7

    • nbody 0.0142
    • splay 0.4393
    • richards 0.0217
    • deltablue 0.0832
    • geomean 0.0577

  • QuickJS-ng 0.14.0

    • nbody 0.0214
    • splay 0.7090
    • richards 0.7193
    • deltablue 0.1585
    • geomean 0.2036

  • Zef ベースライン

    • nbody 2.9573
    • splay 13.0286
    • richards 1.9251
    • deltablue 5.9997
    • geomean 4.5927

  • Zef 変更 #1: Direct Operators

    • nbody 2.1891
    • splay 12.0233
    • richards 1.6935
    • deltablue 5.2331
    • geomean 3.9076

  • Zef 変更 #2: Direct RMWs

    • nbody 2.0130
    • splay 11.9987
    • richards 1.6367
    • deltablue 5.0994
    • geomean 3.7677

  • Zef 変更 #3: IntObject を回避

    • nbody 1.9922
    • splay 11.8824
    • richards 1.6220
    • deltablue 5.0646
    • geomean 3.7339

  • Zef 変更 #4: Symbols

    • nbody 1.5782
    • splay 9.9577
    • richards 1.4116
    • deltablue 4.4593
    • geomean 3.1533

  • Zef 変更 #5: Value Inline

    • nbody 1.4982
    • splay 9.7723
    • richards 1.3890
    • deltablue 4.3536
    • geomean 3.0671

  • Zef 変更 #6: Object Model and Inline Caches

    • nbody 0.3884
    • splay 3.3609
    • richards 0.2321
    • deltablue 0.6805
    • geomean 0.6736

  • Zef 変更 #7: Arguments

    • nbody 0.3160
    • splay 2.6890
    • richards 0.1653
    • deltablue 0.4738
    • geomean 0.5077

  • Zef 変更 #8: Getters

    • nbody 0.2988
    • splay 2.6919
    • richards 0.1564
    • deltablue 0.4260
    • geomean 0.4809

  • Zef 変更 #9: Setters

    • nbody 0.2850
    • splay 2.6690
    • richards 0.1514
    • deltablue 0.4072
    • geomean 0.4651

  • Zef 変更 #10: callMethod のインライン化

    • nbody 0.2533
    • splay 2.6711
    • richards 0.1513
    • deltablue 0.4032
    • geomean 0.4506

  • Zef 変更 #11: Hashtable

    • nbody 0.1796
    • splay 2.6528
    • richards 0.1379
    • deltablue 0.3551
    • geomean 0.3906

  • Zef 変更 #12: std::optional を回避

    • nbody 0.1689
    • splay 2.6563
    • richards 0.1379
    • deltablue 0.3518
    • geomean 0.3839

  • Zef 変更 #13: Specialized Arguments

    • nbody 0.1610
    • splay 2.5823
    • richards 0.1350
    • deltablue 0.3372
    • geomean 0.3707

  • Zef 変更 #14: Improved Value Slow Paths

    • nbody 0.1348
    • splay 2.5062
    • richards 0.1241
    • deltablue 0.3076
    • geomean 0.3367

  • Zef 変更 #15: DotSetRMW::evaluate の重複排除

    • nbody 0.1342
    • splay 2.5047
    • richards 0.1256
    • deltablue 0.3079
    • geomean 0.3375

  • Zef 変更 #16: Fast sqrt

    • nbody 0.1274
    • splay 2.5045
    • richards 0.1251
    • deltablue 0.3060
    • geomean 0.3322

  • Zef 変更 #17: Fast toString

    • nbody 0.1282
    • splay 2.2664
    • richards 0.1275
    • deltablue 0.2964
    • geomean 0.3235

  • Zef 変更 #18: Array Literal Specialization

    • nbody 0.1295
    • splay 1.6661
    • richards 0.1250
    • deltablue 0.2979
    • geomean 0.2992

  • Zef 変更 #19: Value callOperator Optimization

    • nbody 0.1208
    • splay 1.6698
    • richards 0.1143
    • deltablue 0.2713
    • geomean 0.2810

  • Zef 変更 #20: Better C++ Configuration

    • nbody 0.1186
    • splay 1.6521
    • richards 0.1127
    • deltablue 0.2635
    • geomean 0.2760

  • Zef 変更 #21: No Asserts

    • nbody 0.1194
    • splay 1.6504
    • richards 0.1127
    • deltablue 0.2619
    • geomean 0.2759

  • Yolo-C++ 上の Zef

    • nbody 0.0233
    • splay 0.3992
    • richards 0.0309
    • deltablue 0.0784
    • geomean 0.0686

関連記事

1件のコメント

 
GN⁺ 8 일 전
Hacker Newsのコメント

  • 似た文脈で、Wrenインタプリタの性能を扱ったこのページもかなり興味深かった
    Zefの記事が実装手法中心だとすると、Wrenの方は言語設計そのものが性能にどう寄与するかも示していると感じた
    特にWrenはdynamic object shapesを捨てることでcopy-down inheritanceを可能にし、メソッド探索をはるかに単純化している点がよさそうだった
    個人的にはかなり妥当なトレードオフだと思う。クラスが作られた後でメソッドを付け足す必要が実際どれほど頻繁にあるのか、という気がする

    • インタプリタやJITの速度は言語設計にものすごく大きく左右されると思う
      動的言語向けに非常に最適化されたVMは多いが、LuaJITが強いのはLuaが非常に小さく、最適化に向いた言語だからだと感じる
      最適化しにくい機能も多少はあるが、数が少ないので力を注ぐ価値があるのが大きい
      一方でPythonはまったく別物だと思う。少し大げさに言えば、高速なJITの可能性を最小化するように設計されたレベルで、何層もの動的性が重なって最適化が本当に難しそうだ
      これだけ長い期間取り組んだ後でも、CPython 3.15 JITがx86_64でデフォルトのインタプリタより約5%速い程度だという点が、それをよく示していると感じる
    • このアプローチは、monkey patchingが慣用的に受け入れられている言語、とくにRubyでいつもやっていることに近いと思う
      もちろんRubyは速度最優先の言語として知られているわけではない、という点も同時に思い浮かぶ
      逆に、ある型が適用可能な関数集合を閉じた形で持つという発想には、少し疑問も感じる
      世の中には任意の関数を定義しておいて、最初の引数の型が合う変数にドット記法のメソッドのように付けて使える言語がかなりある
      たとえばNimのマクロ、Scalaのimplicit classesとtype classes、Kotlinのextension functions、Rustのtraitsのような方式だ
    • 私の経験では、たいてい何らかの式に静的型を付けられるなら、かなり効率よくコンパイルできる
      複雑な動的言語はさまざまな形でその可能性を積極的に壊してくるので、最適化が難しくなりがちだと感じる
      振り返ってみると、かなり当たり前の話にも思える

  • 変更 #5 から #6 に移るところで、inline cachesとhidden-class object modelが性能向上の大半を生み出している点は、歴史的にV8やJSCが高速化したやり方と本当に似ていると感じた
    素朴なインタプリタが死ぬポイントは結局プロパティアクセスの動的ディスパッチで、残りは比較的rounding errorに近いという印象だ
    各段階がどれだけ寄与したのかを個別に見られるよう整理されているのもよかった。たいていの性能記事は最終的な数値だけ投げて終わることが多い

    • #6で特に興味深い実装ディテールは、ASTを直接たどるインタプリタでinline cachingをどうやるかという点だった
      バイトコードインタプリタならバイトコード列の安定したオフセットをパッチすればよいので、ICの書き換え位置は自然だ
      ところがここではキャッシュ位置がASTノードなので、@pizlonatorがconstructCache<>を通じてgenericノードの上にspecialized ASTノードをin-placeで構築する方式を取っていた点が印象的だった
      結局のところ、ASTレベルのself-modifying codeのように見えた
      その代わりこの方式はmutable AST nodesを要求するため、サブツリー共有や並列コンパイルのように多くのコンパイラが期待するimmutable ASTという前提と衝突する
      単一スレッドのインタプリタならきれいだが、同じASTをバックグラウンドスレッドでJITコンパイルしている間にインタプリタがノードを書き換える状況だと問題になりそうだ
    • 全体的な方向性には同意するが、これはあくまで特定のベンチマーク1つに対する結果だという小さな注記はあると思う
      私の考えでは、実際の業務コードの大半をうまく代表していない可能性もある
      そう感じた理由は、sqrt最適化で1.6%改善したというくだりだった
      その程度の改善が出るなら、そもそもベンチマーク時間の1.6%以上がそこに費やされているはずで、かなり驚いた
      git repoを見ると、実際にnbodyシミュレーションでそうなっていたようだった

  • 私も最近、自分のAST-walking interpreterの最初のバージョンを公開したばかりだったので、なおさら興味深く読めた
    目標は、インタプリタ言語を作るのに何が必要かを基礎レベルで理解することだった
    最適化の複雑さは入れたくなくて、単に自分のRustコードを自分で理解できるようにすることに集中していた
    それでも好きな言語であるRustを使ったというだけで、性能がかなり良く出たのには驚いた
    しかもRustがownershipとlifetimeを面倒見てくれるので、別途garbage collectorが不要だという点もボーナスのように感じた
    もちろん今はclosureのような部分でlifetime地獄を避けるためにcloneにかなり保守的に頼っているが、それでも速度とメモリプロファイルは十分良好だと感じる
    シンプルで理解しやすいRustベースのtree-walking interpreterに興味があるなら、私のインタプリタgluonscriptを見るとよい

  • 記事は本当に素晴らしかった
    特にArgumentsアーク、つまり#7から#13へ進む流れが、自分の経験ととてもよく重なった
    以前Rustでasync step evaluatorを作っていたとき、普段はborrowが得になると信じてCow<'_, Input>に深く入り込んだことがあった
    マイクロベンチではよく見えたが、実ワークロードではCowのdiscriminantとlifetime周りの複雑さが最初のawait以降のすべてのcombinatorに広がり、インライン化が大きく崩れてCowを使う理由そのものが失われた
    結局、evaluatorの境界でNoInput / OneInput / MultiInput(Vec)に切り替えたが、見た目は無骨でも結果的にはここでのZeroArguments / OneArgument / TwoArguments分離とほぼ同じ地点にたどり着いた
    1つずっと気になっているのは、native経路でarity specializationの上にtype specializationまで重ねてみたかどうかだ
    たとえばbinaryスタイルにすると、isIntチェック自体をなくせるかもしれない
    推測するに、コードサイズの計算が合わなかったか、オブジェクト側はICがすでにホットパスを十分に食っていてnative fast pathの影響が大きくなかったのかもしれない
    どちらなのか気になった

  • これは本当に興味深く、よくできた仕事だと感じた
    私も似たようなことをやったことがあるが、もっと関数型寄りの言語であるSchemeの方だった
    ここではオブジェクト最適化が最大の利益をもたらしたが、私の場合はclosures最適化が最大の勝負どころだった
    面白いことに、最適化のやり方自体はかなり似ていた
    Schemeを十分に速くする答えはThree implementation models for schemeにほとんど全部入っていると思う
    ただしこちらはある程度コンパイル段階を経るので、元のASTをそのままインタプリタ実行するモデルではないという違いはある

  • 興味深かったし、共有してくれてありがたかった
    私もいつかこのテーマを詳しく掘り下げてみたいと思った
    それとGithub上ではrepoが99.7% HTMLで0.3% C++という点もかなり面白くて印象的だった
    インタプリタが本当に小さい証拠のように見えた

    • 静的生成したサイトをコミットしてあるのでそう見えるだけだ
      ブラウザ向けコードを生成する都合で、サイト側が無駄に大きくなっている面がある
      それでもインタプリタ自体は本当にとても小さい

  • この作業を通じて、fil c自体をより良くできそうなことを学んだのか気になった

    • たしかにunionsを扱うやり方には、より良い解法が必要だと感じた
      それとvalue objectのメソッドをoutline callで処理するコストがかなり大きいということも学んだ

  • Luaが入っているのは見たが、LuaJITも一緒にあってほしかったと思った

    • 私の予想ではLuaJITがZefに完勝すると思う
      いや、そのくらいのエンジニアリングが投入されていることを考えれば、むしろそうであるべきだという期待だ
      入れられたランタイムは多かったが、全部は含めなかった
      そしてPUC LuaがQuickJSやPythonよりかなり速いという点も相当に印象的だった

  • Fil-Cを実際に使ってみた経験がどんなものか、実務で実質的な有用性があるのか気になった

    • 私がFil本人なので偏っていることは先に言っておく
      それでもこのプロジェクトではかなり実質的に役立った
      メモリ安全性の問題をいくつも決定論的に捕まえてくれて、オブジェクトモデル設計がそうでなかった場合よりずっと簡単になった
      さらに正確なGC付きのC++は本当に良いプログラミングモデルのように感じられた
      普通のC++と比べて生産性が1.5倍くらい上がる感覚があり、他のGC言語と比べても1.2倍くらいは速く開発できる感じだった
      理由はC++のAPIエコシステムが豊富で、lambdas、templates、class systemが非常に成熟しているからだと思う
      もちろん多くの点で偏っていることも認める
      Fil-C++を自分で作ったし、C++も35年ほど使ってきた

  • 記事で触れられていた**YOLO-C/C++**コンパイラが何なのか気になった
    検索してもあまり出てこないし、chatgptも知らないようだった

    • Fil-Cの作者でありこの言語の作者でもある人が、**Yolo-C/C++**という表現でFil-Cのない普通のC/C++を指して使っていたものだ