Brainfuckをめちゃくちゃ速くする

はじめに

Brainfuckっていう見るからにヤバイ言語がありまして...。

Brainfuck(ブレインファック)は難解プログラミング言語のひとつ[要出典]。なお名称に卑語が含まれるため、Brainf*ckなどと表記されることがある。

...

開発者Urban Müllerがコンパイラがなるべく小さくなる言語として考案した。 実際、Müllerが開発したコンパイラのサイズはわずか123バイト、インタプリタは98バイトであった。

Brainfuckプログラムは非常に可読性・記述性が低いため実用性は期待できないが、チューリング完全である。その簡潔さから多くの派生言語を生み出すこととなった。

(出典:Wikipedia

Brainfuckはとってもシンプルな言語で、線形メモリ(char *mem;)と、たった8つの命令しかありません!

記号 命令
+ (*mem)++;
- (*mem)--;
> mem++;
< mem++;
[ while(*mem) {
] }
. printf("%c", mem);
. scanf("%c", mem);

そのため、非常に簡単に実装できます。ただ、何も考えずに実装すると

めっちゃくちゃ遅い...

のです。今回はRustでBrainfuck処理系を実装し、様々な手法を使って高速化を図りたいとおもいます。

手法1:LLVMを用いたコード生成

LLVMは、けっこう広く使われているコンパイラミドルウェアです。簡単に言うと、LLVM IRという言語にいちど翻訳してしまえば、あとは勝手に最適化したりネイティブコードを出力してしまうすごいやつです。

llvm.org

RustやSwiftのコンパイラに使用されていることでも知られていますね。

Rust上でLLVMを使うには二種類の方法があって、 llvmをつかう方法と、inkwell を使う方法があります。前者はLLVM C APIをそのままラップしただけでunsafeを使わなければいけないですが、後者は(機能は少ないものの)Rustでさらにラップされているのでunsafeを使わなくて良かったり、Rustの型システムの恩恵を受けることができます。今回は、後者のinkwellを使ってみました。(ただドキュメントは少ないので、LLVM公式のドキュメントに目を通すことになりました...。Swiftがセルフホストできないのもこのへんが理由なのかもしれませんね。)

LLVM IRはテキストで出力するのではなく、Builderを使うと楽です。たとえば、現在のカウンタ位置から値を取り出す(*memのことですね)ためのコードを出力するには、

let counter = self.builder.build_load(counter, "");
let ref_val = unsafe {
    self.builder.build_in_bounds_gep(
        value_table,
        &[
            self.context.i64_type().const_int(0, false),
            counter.into_int_value(),
        ],
        "",
    )
};
self.builder.build_store(ref_val, value);

のように、build_**を使えば命令が追加されていきます。

静的単一代入(Single Static Assignment)

LLVM IRは、静的単一代入とよばれる表現方式を用いています。 静的単一代入では、変数には一度しか代入できず、新しい値を作るには変数を新たに作る必要があります。 どうやら、これが最適化に役立つのだとか。

分岐命令

分岐命令は、BasicBlockを使うことで実装できます。BasicBlockの後にカーソルを移動して、そこに命令を書き込む...、という感じです。ただ、アセンブリやCのラベルとは違って、通り抜け(fallthrough)はしないので明示的にジャンプを行う必要があるようです。

let loop_head = self.context.append_basic_block(function, "");
let loop_body = self.context.append_basic_block(function, "");
let loop_end = self.context.append_basic_block(function, "");

self.builder.build_unconditional_branch(&loop_head); // 明示的なジャンプ
self.builder.position_at_end(&loop_head);

self.builder.build_conditional_branch(
    self.builder.build_int_compare(
        IntPredicate::EQ,
        self.get_current(value_table, counter),
        self.context.i8_type().const_int(0, false),
        "",
    ),
    &loop_end,
    &loop_body,
);
self.builder.position_at_end(&loop_body);

for i in v {
    self.build_operation(function, env, i, value_table, counter)?;
}
self.builder.build_unconditional_branch(&loop_head);
self.builder.position_at_end(&loop_end);

手法2:イディオムの特殊化

LLVMで実装したのはいいですが、これだけではあんまり速くなりません!bf02にすら負けている!

bf02で用いた高速化テクニックを思い出すために、bf02.cppに目を通すことに...。

なんだこのク○コードは...

あの頃は若かったんだよ...。もちろん、今の私よりぜんぜん賢くてこんなことをしていました:

  • 構文木の導入
  • インクリメントの単純化+++++++++なら+×9、という風にパースする)
  • イディオムの特殊化

これらを全て取り入れようと思います。

Brainfuckのイディオム

イディオムとは何かっていうと、Brainfuckは命令が少ない分、効率的に書くための頻繁に多用される定石のようなものが存在します。

イディオム 意味
[-] 値のクリア
[>>>+++++++<<<-] 乗算
[----->>>+<<<] 除算

など...

これらを特殊化することによって、コードを高速化します。

無理矢理パターンマッチしちゃいましょう。

f:id:kabanchan:20191215231607p:plain
Don't repeat yourself...

ああ○ソコード...。

比較

これまでの手法を盛り込んで、bf-rsを実装しました。

では、bf-rs (v1.0.1)、bfc、 過去作のbf01(最適化一切なし)およびbf02[-]の高速化)と比較してみましょう。 (FUJITSU CELSIUS J520(RAM 8GB、Xeon E3-1275v2)で計測。--optLLVMによる最適化オン・オフのオプションです。)

bf-rs bf-rs (--opt) bfc bf02 bf01
mandelbrot 3.50 sec 3.08 sec 5.13 sec 10.88 sec 52.40 sec
hanoi 0.48 sec 1.91 sec 0.42 sec 1.01 sec 19.46 sec
long 2.11 sec 0.82 sec 2.44 sec 9.78 sec -
bench 0.14 sec 0.08 sec 0.42 sec 0.5 sec 3.59 sec
factor 0.81 sec 0.65 sec 1.26 sec 4.37 sec -

(追記:MacBook Pro (Late 2016)、i7-6700HQでの測定結果を追加しました。)

bf-rs (v1.0.1) bf-rs (opt) bfc bf02
mandelbrot 3.56 sec 3.22 sec 5.26 sec 9.82 sec
hanoi 0.44 sec 1.79 sec 0.38 sec 1.06 sec
long 2.07 sec 0.87 sec 2.51 sec 7.30 sec
bench 0.16 sec 0.10 sec 0.41 sec 0.58 sec
factor 0.83 sec 0.67 sec 1.19 sec 4.00 sec

bf01では遅すぎて話にならないですね...(ちなみに-は遅すぎて測定不可です)。 bf-rsの計測結果はビルド時間も含むので、hanoiではbf02にすら負けてしまってます...。ただ、他のプログラムではインタプリタベースの実装よりも速くなっていることがわかります。

結論:LLVMは偉大

現時点では、いちばん高速な処理系だと思っていますが実際どうなのでしょうかねえ...?

余談:インタプリタの高速化について

今回はインタプリタでの実装は行いませんでしたが、せっかくなのでいくつかの高速化テクニックについて調べてみました。

VM

抽象構文木を直接実行するのではなく、オペコードに一度落とすことで高速化します。Pythonでも同様の手法が利用されています。

Direct Threaded VM

ふつうのVM方式のインタプリタだと、

命令のフェッチ→分岐→命令に対して処理→くりかえし

という感じで実行されます。このとき、命令のフェッチと分岐は先頭でしか行われず、ほとんどの場合CPUの分岐予測が失敗してしまいます。

そこで、それぞれの命令の最後で直接次の命令に対する処理にジャンプできるようにします。

命令に対して処理→命令のフェッチ→次の命令のアドレスをジャンプテーブルから取得→ジャンプ

見た目では殆ど変わりませんが、これだけで高速になるらしいです(ためしたことはない)。

JITコンパイル

元も子もないですが...。

VMも結局のところは遅いです。ネイティブコードのほうが速く動きます。

ただ、ぜんぶ丸ごとコンパイルしてしまうのはどうしても時間が掛かります(かつてのGoogle V8はそれをやってのけたらしいですが...)。それを軽減するために、必要なときだけコンパイルする、という手法が存在します(適応的コンパイル)。JavaのHotSpot VMはこの方式ですね。

さいごに

成果物は、こちらに公開してあります。LLVMをインストールしてからビルドしてくださいね♥

github.com