1.概要
Rustで少し凝ったBrainfuckインタプリタを実装してみたので，やってみたことについてメモがてら書きます．2.経緯
プログラミング好きの友人とともに内輪でハッカソンみたいなものをやろうという話になった．1日で実装できてしかもそこそこ面白いプログラムはないかと考えた結果Brainfuckインタプリタを実装しようという話に．どうせやるならなるべく早いインタプリタを実装しようとのことで，マンデルブロ集合を表示するプログラムの実行時間を計測した．
結果はともかくとしてそこそこ速いインタプリタができたので満足してる．
・作成したプログラムのGitHubレポジトリ
3.制約
Rustの勉強目的もあったので，以下の制約の下で実装した- 安全性や信頼性に重きを置いて書く(unwrapやunsafeとか使わない)
- panicで殺さずにResult/Optionでエラーハンドリングする
- ポインタが負の値となったらエラーを吐く
- 括弧の対応がないなどinvalidなコードはエラーを吐く
- Brainfuckのメモリは動的にallocationする(固定長にしない)
3・5の制約からポインタを動かすたびにポインタが負になってないかや配列サイズより大きくなってないかなどを確認することになるので，きちんと確認したわけじゃないけれどこの２つがネックになっている気がする(試しに固定長にしてみたら10%ぐらいは改善していた)．
4.やったこと
パース→最適化→実行という形で実行させた．主にOptimizing brainfuck compilerを参考にしつつ，実行速度が早くなるような工夫をした．4.1.メモリをu8ではなくi32で扱う
Vector<u8>で持つよりVector<i32>で持って255との論理積を取るほうが早かった．B1のときに先生が言ってたキャストは遅いは真だったんだなぁ．メモリをたくさん使うプログラムでベンチマークをとったらまた変わるとは思うが．4.2.括弧の対応は実行前にとっておく
書くほどではないが毎回対応する括弧を探すのは時間がかかるのでパースした際にプログラムをリストの形で持っておいた．4.3.連続する+や>は圧縮する
これもまた定番だが+++++はAddMemory(5)，<<<<はAddPointer(-4)という内部命令に変換することで高速化した4.4.[-]は0を代入するというコードに変換した
Assign(v)というメモリに値vを代入する内部命令を作って[-]は0を代入するようにした．4.5.[->+++>++<<]系のコードを最適化した
[->+++>++<<]は意味的にはmem[1] += mem[0]*3,mem[1] += mem[0]*2, mem[0] = 0というコードであるので，MultAdd([(1,3),(2,2)])という内部命令を作り実行する形にした．それ以外に工夫はしてみたものの，かえって遅くなったり，実装した当時は早くなったがいろいろ書き換えた今はむしろボトルネックになっていそうだったりするので割愛した．
とりあえずこれらの最適化をかけた結果，一番最初にインタプリタとして動作したとき(4.1～4.3のみ実装)と比較して半分の時間で実行できるようになった．
5. ベンチマーク
比較対象はbfとbff．bfはaptで入るBrainfuck処理系で，bffはideoneなどで使われている処理系．どちらもC言語製．コード: mandelbrot.bf
Version: 1.0.0
CPU: Core i3 3220
OS: Ubuntu16.04(Bash on Windows)
| program | time |
|---|---|
| chetah_bf(release build) | 0m6.686s |
| cheeta_bf(optimized build)※1 | 0m5.652s |
| bf | 0m7.604s |
| bff | 0m5.330s |
bfには勝ったけどbffには負けてますね……(いやきっとメモリアクセスをunsafeにすれば勝ってた←ホントか？)
少し悔しいですが僕のRust力ではこれが限界でした．
6.その他
Bash on Windowsでlldb(rust-lldb)を実行するとrunしたときにフリーズするという問題にぶち当たった．友人も同様だったのでおそらくBoW特有の問題っぽい．解決策は持っておらず，単にrust-gdbを使ってごまかした．7.参考
- 実装したプログラムのリポジトリ
- Brainfuckの最適化が詳しく書いてあるサイト Optimizing brainfuck compiler
- bffのコード apankrat/bff: Moderately-optimizing brainfuck interpreter
- Wikipedia Brainfuck - Wikipedia
0 件のコメント:
コメントを投稿