なんだこれは
少し前に、Goのプログラムをチューニングして遊びたいなと思い、brainf*ckインタプリタを作って高速化しました。
忘れないうちにそのときのことを書いておこうという記事になります。
高速化！高速化！うおおおおお！
できたもの
こちらが最終的に完成したものになります。
ベンチマークにはbfでマンデルブロ集合を描画するプログラムを利用しています。
それを私の手元のPCでインタプリタに食わせたときの実行時間を減らしていくという形で高速化を進めました。
始めた当初は描画に42.36sかかったところ、最終的には2.271sで描画できるようになりました。ついでにbfをllvm irにトランスパイル？するプログラムも書いていて、それを使ってコンパイルした場合は0.466sでマンデルブロ集合を描画することができます。
皆さんもぜひ高速化を…
途中からは以下のようなルールを設け、友人らと速度を競いながら遊んでいました：
- https://github.com/pablojorge/brainfuck/blob/master/programs/mandelbrot.bf が動けば他は何でも良い
- 言語もなんでもok
- readmeが充実してるとみんなが嬉しい
私は速いコードの書き方に飢えています。
ぜひ皆さんもbf高速化で遊んで、私の記録をぶっつぶしてください。
そしてリポジトリを教えて下さい‥！
高速化のためにやったこと
ここからは、どういったステップで高速化を進めていったのかを順を追って見ていきたいと思います。
コミットも載せておくので、気になる方はぜひ実際のコードの変更箇所も眺めてみてください。
そんなに効果を感じられなかったものや自信のないものに関しては一部割愛しています。
1. 素直に実装: 42.36s
とりあえず何もしていない状態で速度を測りたいと思い、何も最適化を施していない素直な実装を行いました。
非常にシンプルですね。1ファイルにほぼ全ておさまっています。
メモリのポインタとプログラムカウンタがあって、プログラムカウンタが生のプログラム上を動きます。
2. パーサを追加: 38.07s
パーサを追加しました。読み込むファイルにはbfの命令8種以外にも、スペースや関係のない文字、改行などが含まれています。
bfの文法上これらは無視してよいのですが、実行時にこれらを無視するとループが増えるたびに無駄な処理が増えます。ということで、入力に前処理を施して無視すべき文字を全て最初に消してしまいます。
3. ループ時のジャンプ先を事前に計算: 33.59s
bfでは、[, ]が出てきた際に、対応するカッコにジャンプする処理が発生する場合があります。
これまでの実装では、これらのカッコが出てきた場合には毎回プログラムカウンタをどこまで動かせば良いのか計算していました。しかし、プログラム自体は実行中には変わらず、したがってジャンプ先も毎回同じはずです。
そのため実際の実行中に計算せずとも、先にジャンプ先を計算しておけば良いはずです。
整備編. プロファイルができるようにする
ここまではtimeコマンドに頼って計測を行ってきました。しかしこの方法は言ってしまえば当てずっぽうで、「推測するな、計測せよ」の精神からは程遠いものです。今後はより詳細にどこがボトルネックなのかといったところを洗い出しながら作業を進めていきたいため、ここで一旦高速化の手を止めてpprofを導入しました。
コマンド一発でプロファイルのデータが生成されるため、後で利用するときに非常に便利でした。
4. [-]を圧縮: 31.74s
詳細は割愛しますが、bfにおいて[-]のパターンは「今見ているメモリの値を0にする」という処理と等価です。
しかし実際に処理を行う上では、毎回今見ているメモリが0かどうかを確認して1つ減らし‥という手順でこの処理が行われています。結果が分かっているのであれば、この無駄な処理をスキップして、一気に現在のメモリを0にしてしまっても良いはずです。
具体的な実装方法としては、パース処理後に[-]のパターンを見つけてそれを0に置き換えるという処理を追加しました。
そのうえで、実際に動作させる際に0という命令に当たったら今見ているメモリを問答無用で0にするという処理を行っています。
5. 仮想命令の導入: 48.71s
さて、ここで記録は大きく後退します。仮想命令を導入したためです。
これまでは+,-,...といったbfの命令をruneで表現したものを使ってそのままswitchで分岐していたところを、Op構造体とそこに定義されている命令の種類のenumで判別することにしました。
当然ながら、これにより以前は必要なかった構造体のメンバへのアクセスといったオーバーヘッドが発生します。結果として記録は悪化し、スタート時より遅くなってしまいました。
しかし仮想命令に移行したには狙いがあります。それは、+や-、<や>をランレングス圧縮するためです。
bfのプログラムを眺めていると、これらの命令は大量に同じものが複数個並んでいる事が大変多く、これまでの愚直な実装ではこれら複数の命令を1回のループで1個ずつ実行していました。
これを圧縮し、例えば1回の命令で一気に現在のメモリに10足すことができるようになれば、それによる時間短縮は計り知れません。
このあとこれを行うための下地として、一旦重いコストを支払ってでも仮想命令に移行したかったというわけです。
6. 出力のバッファリング: 47.95s
このあたりで出力をバッファリングしていないことを思い出しました。多少は速くなるかなと思って試してみましたが、あまり速くはなっていないですね‥
ちゃんと計測してから試すべきだったと少し後悔しましたが、一応は実行速度が速くなっていると判断しそのまま先に進むことにします。
7. <, >, +, - をランレングス圧縮: 27.80s
先ほど仮想命令を導入しましたが、それによるアドバンテージを使って実際にシフト命令を圧縮しました。やはり効果はてきめんで、これだけで仮想命令を導入する前の最高記録を上回ることに成功しました。
整備編. 改変したプログラムをダンプ可能にする
ここまでで、シフトとプラスマイナス、[-]のパターンを発見し、元のプログラムに改変を加えるといった処理を追加しました。このまま進めても良いのですが、brainf*ckのコードのさらなる最適化を目指すためには処理が完了したあとのコードを観察することも必要です。
ということで、ある程度きれいに改変後のプログラムを見れるようなツールを作成しました。
ついでにリファクタリングなどもこのタイミングの別のコミットで行っています。
8. コピー命令の追加: 27.32s
ダンプしたプログラムを観察すると、以下のようなパターンが多く見つかりました：
LoopStart
Decr 1
ShiftRight n
Incr 1
ShiftLeft n
LoopEnd
これをさらによく分析すると、現在のポインタ位置の値をn個右のセルに足す操作と等価であるということが分かるかと思います。この性質を利用し、OpCopyという命令を追加しました。
9. ジャンプ先の結果保持にスライスを利用する: 19.33s
段々アイデアが尽きてきたので、プロファイル結果をしっかり見てみることにしました。するとどうやらマップアクセス用のハッシュの計算にかなり時間がかかっているようです。
とりあえず一箇所思い当たる点としてジャンプ先を事前に計算する部分が怪しかったので、ここをマップからスライスに置き換えてみました※。結果としては大正解で、一気に7秒ほど実行時間を短縮することができました。
※スライスだとハッシュの計算が不要になるため高速化が見込める
10. メモリを保持する際、マップでなくスライスを使う: 8.09s
こちらも上と同様です。メモリもマップを使って保持していたのですが、これをスライスに置き換えました。メモリアクセスも全体の実行時間のかなりを占めるため、この処置によって実行時間は半分以下となりました。
11. 仮想命令にパディングを追加: 5.98s
以前、構造体の配列を舐める際は、ワードサイズを意識するとメモリのオフセットの計算などによるオーバーヘッドを減らすことができる、というテクニックを聞いたことがありました。
ここまでくればそのテクニックも光ってくるだろうと思い、仮想命令の各フィールドが16bitの倍数に乗るように変更してみました：
type Instruction struct {
Op Op // Opはuint8
pad uint8 // この行を追加
Data int16
}
するとこれも効果はてきめんで、結果としては実行時間をおよそ0.79倍に縮めることができました。
このテクニックに関しては割と都市伝説だと思っていた節があったので、こういった最適化が実際に効果的な場面に出くわすことができて非常に感動したのを覚えています。
ちなみにこの記事を書いたのは、パディングの追加で高速化ができたということを自慢するためというのが非常に大きいです。
12. シフト命令の最適化: 4.047s
再び生成されたコードを観察していると、次は以下のようなパターンが多くあることに気づきました:
LoopStart
ShiftLeft 9
LoopEnd
この処理では、右か左いずれかの方向に指定した数だけ注目するメモリをずらしていき、その値が0であるところで止まるという処理です。
これに対応するコードを書き計測したところ、およそ2秒程度実行時間を縮めることに成功しました。
13. キャストを取り除く: 3.753s
キャストにもある程度はオーバーヘッドがあるだろうということで、できる限りキャストを取り除きました。
数字にすると0.3秒未満とインパクトは小さいのですが、これにより実行時間は3秒の大台に乗りました。
14. 番外編：mattnさんからPR
nostrで実況しながら作業していたところ、ちょうどそこにいらしたmattnさんからpull requestをいただけました。誠にありがとうございます。
内容としては出力周りをさらに調整するといったもので、fmtを取り除くことでさらなる高速化が図れるそうです。
結果0.2秒ほど実行速度の短縮につながっています。
15. switchをやめる: 2.271s
さらに高速化できないかとプロファイル結果を眺めていたところ、switchに非常に時間がかかっているということが判明しました。nostrでつぶやいていたところ、switchは重い場合が多いというアドバイスをいただけたので、試しにこれをifとgotoで置き換えてみました。するとさらに1秒程度実行速度が速くなり、2.271秒でマンデルブロ集合の描画が行えるようになりました。
終わりに
bfインタプリタの高速化、めちゃくちゃ楽しいです。
皆さんのご参加もお待ちしております！
おまけ：他の方々の実装
大学の友人らや、そのまた友人が作ったリポジトリになります。