世界最速のBrainfuckインタプリタ

前回作成した BF インタプリタである brust はそれなりに高速であるものの、世界最速ではありません。最後に触れた bffsree は一部のベンチマークで brust 10 倍程度の速度を叩き出します。今回は、前回のインタプリタをベースに、世界最速の座を目指して高速化を行いました。今回のインタプリタは、前回作成した brust の設計をベースにさらなる高速化を行い、多くのプログラムに対して世界最高の性能を得ることができました。

今回作成したインタプリタは以下からアクセスできます。
https://github.com/void-hoge/bropt

本稿は前回の記事を前提としています。この記事の前にご一読いただけるとより楽しめるかと思います。
https://qiita.com/voidhoge/items/a4ca5888a624523906ae

命令書き換えによるオーダーレベル改善

前回のインタプリタは、乗算やリセットなどのイディオムを高レベルな命令に変換することにより、高速化を実現していましたが、その最適化パスの適用範囲は限定的でした。今回のインタプリタは、より積極的にイディオムを適用するため、不要な命令を削除したり、等価性を維持できるような命令列の書き換えを行います。

以下は、今回ベンチマークで使用している Long.b という名前のプログラムです。このプログラムは単にベンチマークのために作られたと思われ、 172 文字の短さでありながらなんの高速化も行っていない場合約 80 億ステップもかかります。

>+>+>+>+>++<[>[<+++>->>>>>>+>+>+>+>++<[>[<+++>->>>
>>>+>+>+>+>++<[>[<+++>->>>>>>+>+>+>+>++<[>[<+++>->
>>>>+++[->+++++<]>[-]<<<<<<]<<]>[-]<<<<<]<<]>[-]<<
<<<]<<]>[-]<<<<<]<<]>.

brust はこのプログラムを約 0.7 秒で実行するのに対して、世界最速のインタプリタである bffsree は約 0.07 秒と、約 10 倍も高速に実行できます。

brust では、ループ最深 1 層の [->+++++<] のみ O(1) で実行可能なのに対し、bffsree は更にもう一層分 [<+++>->>>>>+++[->+++++<]>[-]<<<<<<] を O(1) で実行することができます。今回実装したインタプリタでは、以下の 2 つの最適化パスにより同様の最適化を実現します。

リセットの移動

説明のため、以下のプログラムを考えます。

[->[-]<]

このプログラムは、0 番地 (実行開始番地) の値が 0 になるまで、1 番地の値をリセットし続けます。以下の C と等価です。

while (data[0]--) {
    data[1] = 0;
}

極めて単純な動作をするプログラムですが、前回のインタプリタではどのイディオムにも当てはまらないため、O(data[0]) かけて実行するしかありません。これを O(1) で動くように書き換えます。

まず、リセットを何度も実行するのは無駄なので、ループの後に移動します。

[-><] >[-]<

このプログラムは 0 番地が 0 のときの動作がもとと異なります。もとのプログラムは 0 番地が 0 のときリセットは実行されませんが、変更後のプログラムは実行されます。そこで、全体をループで囲みます。

[[-><] >[-]<]

そして、冗長な移動命令を削除すると、リセットのみのループとなります。0 番地は 1 回目の実行でリセットされるため、このループは O(1) で実行可能です。

[[-]>[-]<]

冗長な書き込みの削除

後にリセットされる書き込みは無意味なので削除します。例えば、+++[-] は単にリセットだけ行うもの [-] と等価です。[-][-] のようなリセットの連続も最後を残して削除します。同様に、後に , で上書きされる命令も削除します。

やや複雑なのが乗算の場合です。以下のコードを考えます。

[->+<]>[-]

[->+<] イディオムは、以下のように開始番地のリセットを内包していると考えると見通しがよくなります。

data[1] += data[0] * 1; data[0] = 0; // [->+<]
data[1] = 0;                         // >[-]

これは、乗算の効果は 2 個目のリセットで打ち消されるため、以下の 2 つのリセットが残ります。

data[0] = 0;
data[1] = 0;

Brainf*ck に直すと以下のようになります。

[-]>[-]

最適化の流れ

ここまでに解説した最適化パスを駆使して、本章冒頭で触れたコード片を書き換えます。

[<+++>->>>>>+++[->+++++<]>[-]<<<<<<]

このままではなんのイディオムも適用できず、開始番地の回数だけ実行されてしまいます。

命令を分解し、3 行目の乗算イディオムを含む部分に注目します。

[
    <+++>->>>>>
    +++[->+++++<]>[-]
    <<<<<<
]

3 行目の +++[->+++++<]>[-] は、以下の C と等価です。

data[0] += 3;                         // +++
data[1] += data[0] * 5; data[0] = 0; // [->+++++<]
data[1] = 0;                          // >[-]

いろいろな演算をやっていますが、結局 0 番地と 1 番地はリセットされているため、以下のように書き換えることができます。

data[0] = 0;
data[1] = 0;

[-]>[-]

ここまでで、命令列は以下のように書き換わりました。

[<+++>->>>>>[-]>[-]<<<<<<]

このループの >< を合計すると、開始番地に戻ってきます。そのため、リセットの移動が適用可能です。

[[<+++>->>>>>><<<<<<]>>>>>>[-]<[-]<<<<<]

無意味な移動命令を打ち消すと、以下のように簡単化できます。

[[<+++>-]>>>>>>[-]<[-]<<<<<]

残った部分には乗算イディオムが適用可能であり、全体のループは 1 回だけ回るため、O(1) で実行できます。

while (data[0]) {                     // [
    data[-1] += data[0] * 3; data[0]; // [<+++>-]
    data[6] = 0;                      // >>>>>>[-]
    data[5] = 0;                      // <[-]
}                                     // <<<<<]

定数倍改善

今回のインタプリタの実行部の設計は、ほぼ前回のものを引き継いでいます。命令の構造は以下のようになっており、全体で 8 バイトとなっています。

typedef struct {
    InstType cmd;
    int32_t arg;
    uint8_t inc;
    int16_t delta;
} Inst;

各フィールドは主に以下のように使います。

• cmd: 命令の種類
• arg: シフト量 (>, <) やジャンプ先 ([, ])
• inc: +, - によるインクリメント回数
• delta: 命令後のシフト

副作用付き 0 探索命令

前回 [<<] のような 0 のセルを探索する命令を実装しました。今回は [-<<] のように移動中に 1 箇所のセルを書き換える 0 探索命令を追加しました。各フィールドは以下のように用います。

• arg: 全体のシフト量
• inc: 書き換えセルのインクリメント量
• delta: 書き換えセルのオフセット

さらなる命令の詰め込み

前回の brust では、Set、Output、Input 命令では delta フィールドは使用されていませんでした。しかし今回は命令生成ルーチンを見直し、可能なら使うようにしました。

配列の境界チェックの省略 (unsafe)

Rust では配列のアクセス時に必ず境界がチェックされます。当然これにはオーバーヘッドがあります。
極限までチューンするために、今回は unsafe を甘んじて生のポインタを使うようにしました。

Mul の 0 チェックの省略 (unsafe)

乗算イディオム [-<+>] は、本来以下の C と等価です。

if (*ptr) {
    *(ptr - 1) += *ptr * 1;
    *ptr = 0;
}

しかし、全体の if がなくてもほとんどのプログラムでは問題ありません。

*(ptr - 1) += *ptr * 1;
*ptr = 0;

これが問題になるのは、配列の境界付近の動作です。
例えば、配列の 0 番地の値が 0 であり、データポインタが 0 番地を指しているときに、[-<+>] を実行することを考えます。

Brainf*ck の本来の動作としては、ループの評価が行われる 0 番地は 0 であるため、ループの中には入らず素通りします。
しかし、以下の C にコンパイルされる場合、ptr が 0 番地を指しているとき、ptr - 1 番地は配列の境界外なのでエラーとなります。

*(ptr - 1) += *ptr * 1; // 境界外 (-1 番地) へのアクセスでエラー
*ptr = 0;

しかし、このような秘孔をつくプログラムは多くないため、多くのインタプリタでは無視されており、今回もそれに従って if なしで実行しています。

前節のものも含めた unsafe な最適化を行っていない場合、パフォーマンスは 5 ~ 10 % 低下するようです。

実験結果

前回と同様の手法で以下 12 種類のプログラムでベンチマークを行いました。比較対象は以下の通りです。

• Tritium
  • 様々な最適化を行う Brainf*ck 環境
  • 今回は Non-JIT インタプリタモードを使用 (JIT モードは更に数倍速い)
• bffsree
  • Non-JIT では最速のインタプリタ
  • ソースコードは非公開
• brust
  • 前回作成したインタプリタ
• bropt
  • 本稿で解説したもの

結果を以下の表に示します。

	brust [s]	Tritium [s]	bffsree [s]	bropt [s]
awib	0.0197	0.350	SIGSEGV	0.0233
Collatz	1.71	1.51	1.41	1.29
Counter	2.27	1.92	2.49	1.96
EasyOpt	0.0308	0.0200	0.0353	0.0308
Factor	1.66	2.24	1.98	1.58
Hanoi	0.112	0.0711	0.0159	0.0177
Life	0.0114	0.0285	0.0117	0.0119
Long	0.664	0.652	0.0654	0.0552
Mandelbrot	1.52	1.95	1.44	1.38
Prime	1.12	0.102	0.115	0.124
SelfInt	2.05	2.59	1.89	1.64
Sudoku	0.724	0.741	1.03	0.692

図にすると以下のようになります。brust が紫、Tritium が緑、bffsree が水色、今回作成した bropt が黄色です。

bropt は 12 種類中 6 種類のベンチマークで最速でした。特に Long と Prime を高速に実行できているのは bffsree と bropt のみであり、命令の書き換えを伴う最適化の効果が現れていることがわかります。なお、Prime はリセットの移動が実装できていれば高速に実行できるため、Tritium はリセットの移動だけ実装されているのかもしれません。

また、bropt は実行に時間のかかる Collatz、 Counter、Factor、Mandelbrot、SelfInt、Sudoku ではほぼ全て最速となっており、今回行ったチューニングの効果が現れています。

まとめ

本稿では、前回作成したインタプリタに、さらなる最適化パスとチューニングを加えたものを実装しました。命令列の等価な変換、副作用付き 0 探索命令の追加、さらなる命令の詰め込みに加え、一部の unsafe な高速化を許すことで世界最高の性能が得られました。

実験結果がかなりのデッドヒートとなっていることからわかるように、Non-JIT のインタプリタの性能はこのあたりが限界だと思われます。

今回のインタプリタでは深さ 1 のループはほぼすべてカバーされており、これ以上オーダーレベル改善を狙うためには深さ 2 以上のループに手を出す必要があると思われます。しかし深さ 2 以上のループはかなり状態が多く、実行時命令の拡張が必要でしょう。さらに、深さ 2 以上のループは [>] のように、ループを実行することによりポインタ位置が変わるものが多いため、最適化の際にはメモリの状態を考慮することが求められます。

また、bropt は毎秒 6 億命令程度を実行することが可能ですが、すでに命令フェッチ以外の分岐を極限まで減らしているので Non-JIT でこれを大幅に改善するのは難しいでしょう。これ以上命令の発行速度を上げるためには、JIT コンパイルを行うことで命令フェッチを省略することが必要でしょう。Tritium などの高度な最適化を行う JIT コンパイラは bropt よりも数倍高速です。

参考文献 (全て 2025 年 5 月閲覧)

• 前回の記事 (https://qiita.com/voidhoge/items/a4ca5888a624523906ae) で触れたものに加えて以下
• rdebath: Brainfuck (Tritium, test suite)
  • https://github.com/rdebath/Brainfuck
• Mugi Noda: brust
  • https://github.com/void-hoge/brust