Brainf*ck interpreter 高速化そのいち
http://d.hatena.ne.jp/janus_wel/20100919/1284908467 でとりあえず brainf*ck interpreter を書いたわけだけどあまりに仕様どおりで正直に文字列処理してるもんだからどうやったって速度なんかでねぇよ ! ってのはまぁ普通に気付く。とりあえずどの方向に対しても一文字でひとつしか加算・減算できないのは無駄だよねー、ということでじゃあまとめてしまおうという方向。
先にできたものおいておこう。
変更点を言葉で説明すると以下の 2 点。
+-<>の四文字は連なってたら一気に計算すればいいんじゃね ?++++++++という code 片があったとして "+8" みたいに解釈する。
+と-は memory 内容に対する演算なので一緒くたにできる。++++++----てのはつまり "+2" だよねとかそういうこと。- 同様に
<と>もまとめてしまえる。
で、これをそのまま実装、の前に命令集合を決めないといけない。というのも上記の "+8" ってのはちゃんと説明すると「 8 」を「現在位置に足せ」ということであってどっちかひとつだけでは成り立たない。つまり何か指示するときに「現在位置に足せ」みたいな動詞部分と「 8 」みたいな目的語部分が必要になるわけで、動詞部分にあたる命令を定義してやらないといけないわけだ。命令集合ってのは単純に複数あるよってだけで。
でまぁ別に brainf*ck と同じ文字集合をそのまま命令にしてもいいんだけどせっかく自分で定義するわけだし switch するときに文字どうしを比較するのはどうなんだろうと思って以下のように定義しなおしてみる。名前が長いとは思うけど省略しすぎてパッと見わからないというのよりはいいと思う。
// operator definitions enum operator_type { ADD_CONTENT, // +- ADD_POINTER, // <> OUTPUT_CONTENT, // . INPUT_CONTENT, // , LOOP_START, // [ LOOP_END // ] };
これを上記の目的語部分にあたる被演算 data とあわせてひとつの命令を作るわけだ。以下の定義では operand_type にあたる部分が目的語部分ね。
// instruction definition struct instruction_type { operator_type op; operand_type operand; };
ちなみに operand_type は以下のように定義してて、 int 型なのはたとえば "ADD_CONTENT -3" みたいなことをするため。あと ADD_CONTENT と ADD_POINTER 以外は operand を固定で 0 としてる。
// operand definition typedef int operand_type;
で、ここまでの定義を使って brainf*ck script からオレオレ命令列に変換する code を書けばいいわけだね。冒頭に挙げた github の code はちょっと泥臭いけどきちんと変換してくれる。たとえば "A" を出力する以下の script を食わせると、
++++++++[>++++++++<-]>+. # 0x41 A: 8 * 8 plus 1
以下のようなオレオレ命令列をはき出す。
ADD_CONTENT 8 LOOP_START 0 ADD_POINTER 1 ADD_CONTENT 8 ADD_POINTER -1 ADD_CONTENT -1 LOOP_END 0 ADD_POINTER 1 ADD_CONTENT 1 OUTPUT_CONTENT 0
最後に mandelbrot 集合を演算させると今回の time は 44 秒弱。前回と比べて約 1/3 になった。けっこう縮むもんだなぁ。
./a.out ../../scripts/mandelbrot.bf 43.69s user 0.04s system 98% cpu 44.271 total
