RustのEnumを64ビットワードで置き換えたら、私のインタープリタが17%高速になった

RustのEnumを64ビットワードで置き換えたら、私のインタープリタが17%高速になった 2026年8月25日 この記事は、Plush言語のインタープリタと仮想マシンの構築と最適化に関するシリーズの第6弾です。前回は「Plushのガベージコレクタの高速化」についてでした。前回の記事では、いくつかの簡単な変更でコピーGCが16倍以上高速になり、100万オブジェクトのコレクション時間が約7ミリ秒に短縮されたことを説明しました。 私は単にPlushを最適化することを楽しんでいますが、その目標は、インタープリタ言語でありながら、リアルタイムで3Dアニメーションをレンダリングできるほど言語を高速化することです。PlushはPython、JavaScript、Ruby、Lua、Loxと同じ系統の動的型付け言語です。このような動的言語では、型は変数ではなく値に紐づけられるため、プログラム内で値を伝播させるために、インタープリタは通常、言語に存在するあらゆる値を表現できるValue型を使用します。 Plushの初期バージョンでは、プレーンなRustのタグ付きEnumを使用していました。Rustではタグ付きEnumの扱いは非常に便利で、match文を使って異なるValueサブタイプにディスパッチできます。 // 古いRustのValue型（タグ付きEnum） enum Value { Undef, // 初期化されていない変数またはフィールド、読み取りはエラーを引き起こす Nil, False, True, Int64(i64), Float64(f64), String(*const Str), // 不変文字列 HostFn(&'static HostFn), // ホストVMによって公開された関数 Fun(FunId), // クロージャではないPlush関数 Closure(*mut Closure), // 変数をキャプチャするクロージャ Cell(*mut Value), // クロージャによってキャプチャされた可変変数 Object(*mut Object), // クラスインスタンス Array(*mut Array), // JS/Pythonスタイルの配列/リスト ByteArray(*mut ByteArray), // 高速な生のバイト配列（例: フレームバッファ） Dict(*mut Dict), // JS/Pythonスタイルの辞書 Class(ClassId), } ご覧のように、Plushはまだおもちゃの言語だと考えていますが、多くの異なる値型を持っています。この言語にはクラスインスタンスであるオブジェクトがあり、アクセスは効率的ですが、JSONスタイルの構文を可能にするJS/Pythonスタイルの辞書もあります。また、Int64とFloat64という2つの異なる数値型があります。JavaScriptはすべてがdoubleであるかのように見せかけますが、JSエンジンは実際には整数が何であるかを内部で追跡しているため、この選択をしました。 しかし、最も残念なのは、ここでのEnumバリアントの数ではなく、このEnumが全体で16バイト（128ビット）もあることです。各Enumバリアントは64ビットしか必要とせず、Rustが作成するEnumタグは8ビットしか必要としませんが、メモリのアライメント制約のため、Rustは各値に128ビット全体を使用する必要があるかもしれません。これは大したことではないように思えるかもしれませんが、値の大きな配列がある場合、その配列には大量の空の無駄なバイトが含まれることになります。これはVMエンジニアが夜も眠れなくなるような種類の問題です。 しばらくの間、より効率的な低ビットタグ付けスキームを設計して、Value型が64ビット内に収まるようにできると考えていました。64ビットシステムでは、ヒープオブジェクトのアドレスは通常8バイト境界にアライメントされるため、アドレスの最下位3ビットはゼロである必要があるという事実から派生した古典的なトリックがあります。これは、追加情報をパックするためにこれらのビットを事実上盗むことができることを意味します。また、整数値の最も低い2ビットを借りることもできます。これは、整数値が64ビット範囲全体を必要とする可能性は非常に低いという仮定に基づいています。2^64 ~= 1.84 * 10^19 という非常に大きな値です。例えば、テキストファイルの行数、ゲーム内の敵の数、その他の数値量を示す変数がある場合、その値に到達する可能性は非常に低いです。現代のCPUはクロックサイクルごとに複数の命令をディスパッチできるため、for (uint64_t i = 0; i < UINT64_MAX; ++i) のようなループを実行した場合、そのループは完了するのに10年以上かかるでしょう。 より洗練されたタグ付けスキームは明らかにメモリ使用量を削減できますが、整数、ポインタ、または浮動小数点数が何であるかを判断するためにビット演算を導入する必要があることも意味します。また、一部の値をアンパックして操作するために追加のビット演算も必要になります。これはCPUが実行する必要のある追加の命令を意味します。経験豊富なVMエンジニアが私に言ったのは、整数にゼロをタグビットとして与えるのが賢明だということです。なぜなら、シフトされた2つの整数を加算または減算しても、単純なaddまたはsubマシン命令のままになるからです。しかし、浮動小数点数のパックとアンパックはより複雑で、いくつかの命令が必要です。 パフォーマンスへの影響を少し心配していましたが、メモリ効率とパフォーマンスの低下とのトレードオフになるのではないかと懸念していました。しかし、この記事の後半でわかるように、私の恐れは完全に根拠のないものでした。 効率的な低ビットタグ付けスキーム Claudeと私は、このソースファイルにある値の表現を共同で設計し、改良しました。これは、u64をラップするRustのnewtypeにきれいに収まります。ご覧のように、RustのEnumを失ったことを補うために、扱いやすい多くの便利なメソッドがあります。ほとんどのメソッドは、インタープリタループのどこでも使用されるため、パフォーマンスのために常にインラインとしてマークされています。 下の図は、値の表現がどのように構造化されているかをより詳細に示しています。 タグ付き値表現。 私が選択した低ビットタグ付けスキームは、5種類の値をエンコードします：フィックスナム、フロナム、イミディエイト、および2種類のポインタです。フィックスナムは62ビット範囲に収まる符号付き整数です。フロナムは自己タグ付けスキームを使用してエンコードされた浮動小数点値です（これについては後述）。イミディエイトは、nil、true、false、undef、関数、クラスID、およびPlushから呼び出すことができるRustで記述されたホスト関数などの値です。Plushでは、ドル記号プレフィックス（例: $read_file(file_name)）を使用してホスト関数を呼び出すことができます。イミディエイトには、それがどのような種類のイミディエイトであるかを示す5ビットのサブタグがあります。これは5ビットです。なぜなら、最下位バイトの8ビット比較は最新のCPUでは1つの命令で済むため、必要に応じてタグビットとサブタグを1つの命令で比較できるからです。 この表現に2種類のポインタがある理由は、値間の等価性比較を高速にしたかったからです。これは、ループ条件、if文内のポインタ比較などが頻繁に発生するためです。Plushのほとんどの値は単純な参照等価性で比較されますが、文字列は構造的等価性で比較することを選択しました。これにより、将来的に文字列インターニングテーブルを導入する可能性が可能になります。これはJSのように、同じ値を持つ2つの文字列は等しいとみなされます。浮動小数点数も特別な処理が必要です。符号ビットがあり、+0.0と-0.0は同じでなければならないからです。そのための簡単な方法は、タグに1ビット（ビットインデックス1を選択）を持たせることです。これにより、2つの値が1つの比較命令で直接比較できることがわかります。これにより、整数、ポインタ、ハンドル、およびtrue、false、nil、undefのような小さなイミディエイト定数を単一のマシン比較命令で比較するための高速パスが可能になります。ポインタ型の一部（文字列オブジェクト）は直接ポインタ等価性で比較できないため、そこにはわずかな微妙さがあります。また、整数値または浮動小数点値がタグ付き値に収まる範囲を超えた場合、その値をボックス化するためにヒープオブジェクトを割り当てる必要があります。これは、異なるヒープオブジェクトによって表される同じ値を持つ2つの浮動小数点数が存在する可能性があることを意味しますが、それらの値は==演算子を使用して等しいとテストされなければなりません。 PlushにJITコンパイラが最終的に搭載された場合、if (p != nil) のための生成コードは次のようになります。 ; x0 = テストされる値 ; nil はイミディエイト 0x05 x0 = 値 cmp x0, #5 b.eq .ELSE_BRANCH ; 等しい場合はelseブランチにジャンプ ここには遅いパスはありません。なぜなら、構造的に比較される値がnilと等しくなる可能性はないことを知っているからです。 効率的なフィックスナム操作 状態