Plush インタプリタと仮想マシン（VM）の最適化：第 6 弾～ロービットタグ付けスキームの実装～

この投稿は、Plush 言語インタプリタと仮想マシン（VM）の構築・最適化に関する作業シリーズの第 6 弾です。前回は「Plush のガベージコレクタの高速化」について報告しました。単なる遊びだけでなく、インタプリタであっても実時間で 3D アニメーションをレンダリングできるほどの高パフォーマンスを実現することを目標にしています。

Value タイプの再設計と背景

従来の Value 型の課題

• 構造: 単純な Rust のタグ付き列挙型（tagged enum）を使用していました。
• メモリ使用量の非効率性:
  • 全体で 16 バイト（128 ビット） を占有していました。
  • 各バリエーションは実質的に 64 ビットしか必要ありませんでした。
  • Rust のタグ自体も 8 ビットで済むはずですが、メモリアルインライン制約により全体を 128 ビットとして確保されていました。
• 結果: 大量の値を持つ配列内部に膨大な空きスペース（メモリロスト）が発生し、VM エンジニアにとっては深刻な問題でした。

解決策：ロービットタグ付けスキーム

より効率的なスキームへの変更により、

Value

設計のポイント

1. 64 ビットシステムでのアラインメント:
   • ヒープオブジェクトのアドレスは 8 バイト境界に揃っているため、最低 3 ビットは必ず

     0

     です。
   • これらのビットを利用して追加情報をパックしました。
2. 整数値の活用:
   • 整数値の最も低い 2 ビットを借りてタグとして使用しました。
   • 稀なケース（

     UINT64_MAX

     に近い値など）はヒープ割り当て（箱詰め）します。

メリットとデメリット

• メモリ効率: 大幅に削減され、キャッシュヒット率向上。
• 演算コスト: 値の区別（整数・ポインタ・浮動小数点）のために追加のビット演算（シフト等）が必要になりましたが、実測では性能低下は発生しませんでした。

効率的なロービットタグ付けスキームの詳細

Claude と共同で設計した新しい値表現は、Rust の

newtype

u64

1. エンコードされる 5 種類の値

00

nil

true

false

undef

• イミディエイトのサブタグ: 5 ビット使用。
  • 理由：8 ビット比較が単一の命令で実行できるため、サブタグ＋タグビットを 1 つの指令で比較可能にするため。
• 等価比較の高速化:
  • 整数・ポインタ・イミディエイトは「直接ポインタ等価性」を使用し、高速に比較できます。
  • 文字列は構造的等価性を意識的に選択し、将来的な文字列インターニングテーブルを可能にしています。
  • 浮動小数点については符号ビットの扱い（

    +0.0

    と

    -0.0

    の等価性）に配慮。

2. 比較命令の最適化

例：

if (p != nil)

• 旧方式: 複雑なタグチェックが必要。
• 新方式:

  nil

  はイミディエート

  0x05

  として定義され、1 つの

  cmp

  命令で完了します。

; x0 = テスト対象の値
; nil はイミディエート 0x05
cmp     x0, #5
b.eq    .ELSE_BRANCH

3. 効率的なフィックスヌム演算

• 保存形式:

  n << 2

  （最低 2 ビットが

  00

  ）。
• オーバーフロー検出: 64 ビットオーバーフローが発生した時点で検出可能（x86-64:

  jo

  , ARM64:

  bvs

  ）。
• 比較 (

  i < n

  ): 3 つのマシン指令で実装。

  orr     x2, x0, x1    ; 演算子を結合
  tst     x2, #3        ; fixnum かチェック（最低 2 ビット）
  b.ne    .Lslow_lt     ; 浮動小数点などは遅いパスへ
  cmp     x0, x1        ; 直接比較（タグビットは無視可）
  

4. 自己タグ付けされたフローヌム表現

既存の「NaN boxing」や「指数ビット借用」ではなく、新しい論文**"Float Self-Tagging"** を採用しました。

• 仕組み:
  • 上位ビットを回転させ、バイアス値を加算してタグ位置に移動させる。
  • シフト・マスク不要で、subnormals/infinity/NaNs も表現可能。
  • 最低 2 ビットを

    10

    に固定（浮動小数点のタグ）。
• 精度維持: 指数ビットを 2 ビットしか失わず、有効数字は損なわない。

フローヌム演算のコスト

加算にはタグ付け・アンタグ付けが必要なため命令数が増えますが、それでも高速パスです。

; 簡易化された説明コード（実装は複雑）
and     x2, x0, #3      ; タグビットを抽出
cmp     x2, #2          ; flonum (10) チェック
ror     x2, x0, #4      ; 回転して復元
sub     x2, x2, x9      ; バイアスを除く（IEEE 754 ビットへ）
fadd    d0, d0, d1      ; 実際の浮動小数点加算
; ... (結果を再タグ付け)

メモリ使用量への影響

ベンチマーク結果比較

ac75356

6b71f8c

• 教訓: メモリ使用量がベースラインより多いベンチマークほど、削減効果が大きいです。
• トレードオフ: 左シフトや乱数生成など特定のパターンでは箱詰めが必要になりますが、コピー型 GC とバンプアロケータによって割当コストは低く抑えられています。

アセンブリコードの比較（

add

指令）

❌ 旧方式：Rust enum + match

• 問題点:

  • match

    で多数のサブタイプを判定（スパイリングが必要）。
  • インタプリタスタックからポインタを取り出し、C/Rust スタックに吐き出す操作が多く。
  • コードが膨大になり、キャッシュ不友好。

; 旧方式のディスアセンブル（抜粋）
ldr   x12, [x19, #0x58]       ; スタックベースポインタ
add   x13, x12, x11, lsl #4   ; スパイルアドレス計算
ldr   w9,  [x13]              ; タグ読み出し
str   w9,  [sp, #0x2b8]       ; スタックへ吐き出す（スプール）
... (多数のスタック操作) ...
cmp   w10, #4                 ; 整数判定
b.eq  .Lv0_int
cmp   w10, #5                 ; 浮動小数点判定
; ...

✅ 新方式：単一レジスタ + if 分岐

• 改善点:
  • 値が単一レジスタに収まるため、スパイルなし。
  • LLVM のトリックを活用し、2 つの型テストを 1 つの分岐へ融合。
  • メモリ操作と命令数的大幅削減。

; 新方式のディスアセンブル（抜粋）
ldr   x9, [x16]               ; v1 (8 バイトストライド)
ldr   x2, [x9, x10, lsl #3]   ; v0 (8 バイトストライド)
and   x11, x2, #3             ; v0 のタグチェック
cmp   x11, #2                 ; 浮動小数点？
b.ne  .Lcheck_fixnum          ; いいえなら、整数判定へ

.Lcheck_fixnum:
cmp   x11, #0                 ; 固定整数？
ccmp  x11, #0, #0, eq         ; 両方を同時チェック
b.ne  .Lslow
adds  x11, x2, x3             ; タグ付きワード上で直接加算！
b.vc  .Lpush                  ; オーバーフロー検出

• 比較:
  • 旧方式：52 命令、24 メモリ操作、4 つの分岐
  • 新方式：36 命令、9 メモリ操作、1 つの分岐

パフォーマンスへの影響（全体的な成果）

ベンチマークごとの速度向上

すべてのベンチマークが速くなり、驚くべき結果となりました。

• メモリ効率向上による恩恵:

  • binary_tree

    ,

    linked_list

    など：大量のオブジェクト・ポインタ追跡があるため、約半分のキャッシュ/メモリトラフィックとなり劇的に高速化。
• 浮動小数点演算の意外な速度:

  • mlp

    ,

    nbody

    : 従来の認識ではアンボックス・再ボックスのコストが懸念されましたが、新スキームは極めて速く動作。
  • JIT コンパイルがあればさらに加速される可能性があります。

なぜこれほど速いのか？

1. キャッシュフレンドライン: オブジェクトサイズが半分になり、キャッシュミスが大幅に減少。
2. 命令ディスパッチの最適化:

   match

   の代わりとなる高速な

   if

   チェックにより、CPU ピパイプ効率向上。
3. レジスタ利用効率: 値を単一のレジスタで扱い、スタックへの吐き出しが不要。

結論と今後の展望

まとめ

• リファクタリングは成功: メモリ削減に加え、すべてのベンチマークで速度向上を実現しました。
• Rust コンパイラの限界: 旧方式ではコンパイラに効率的なコードを生成させられなかったため、手動最適化（新スキーム）が必要でした。
• 設計の自由度: 言語設計において「箱詰め整数」の問題は、32 ビット整数や明示的な BigInteger ライブラリの使用などで回避可能なトレードオフです。

実績：3D グラフィックスでの活用

• 成果: Plush では交互なフレームレートで約 10,000 個のフラットシェーディングポリゴンをレンダリングできます。
• 実装例: 「無限の街並みを通る高速道路を走行するモーターサイクル」ゲームを実装済み。
• 試す方法:

  git clone <plush-repo>
  cargo run --release examples/night_ride.psh
  

次のステップ

1. レジスタベースインタプリタへの移行: スタックベースからレジスタベースへ設計を変更し、さらなる性能向上を目指す。
2. JetLISP の開発: Plush VM を利用した最小限の LISP 方言を構築し、新しい言語設計を探求する。

続報: Plush の新しいレジスタベースインタプリタは現在完了しており、信じられないほど速いです！

著作権 © 2011–2026 マキシム・シェヴァリエ＝ブワズベルト。全権利 Reserved。