Brainf*ck interpreter 高速化そのに
http://d.hatena.ne.jp/janus_wel/20100920/1284973323 でまともに見えるオレオレ命令列を作ることができたけどもう少し何とかなりそう。具体的には [ と ] 。ちなみに今回の内容は元ネタの http://d.hatena.ne.jp/hogelog/20100914/p1 のまんまパクリ。
前回までの loop に関する挙動は実行時に対応する括弧を探すような形、たとえば LOOP_END 命令から LOOP_START 命令に戻るときにひとつずつさかのぼりながら対応する LOOP_START かどうかを確かめていたんだけどこれは無駄が大きい。 loop っては一回だけじゃなくて複数回まわすから loop なわけで、何度も cost のかかる同じ事やらせてるわけだ。
というわけでそれぞれ対応する '[' と ']' の位置を覚えておいて直接そこへ飛んじゃえばいいじゃんというハナシになるわけだね。具体的に LOOP_START と LOOP_END の operand 部分に jump 方向と距離をいれてやる。方向てのは正が命令列後方、負が命令列前方。距離はオレオレ命令列いくつ分飛ばすかってことね。
で、実装では元ネタと同じく std::stack を使って頑張ってる。 stack を使うと nest した loop をうまく捌けるんだよね。例えば >>++++[<++++[<++++>-]>-]<<. みたいな script があったとして、
初期状態は stack に何も積まれてない。で、 '[' が出てきたらその位置を stack に積む。
| 1st stack | (position of first '[') |
ふたつめの '[' でも同じように積む。
| 2nd stack | (position of second '[') |
| 1st stack | (position of first '[') |
']' は stack から対応する '[' の位置を取り出して処理する。対応するってつまり直前のってことだよな。
| 1st stack | (position of first '[') |
そしてふたつめの ']' はひとつめの '[' と対応して最終的に stack が空になる、とまぁこういう感じ。
ちなみに上記の script をつっこむと以下のオレオレ命令列を吐く。ちゃんと loop 時に跳ぶ方向と距離が書かれてるね。
ADD_POINTER 2 ADD_CONTENT 4 LOOP_START 11 ADD_POINTER -1 ADD_CONTENT 4 LOOP_START 5 ADD_POINTER -1 ADD_CONTENT 4 ADD_POINTER 1 ADD_CONTENT -1 LOOP_END -6 ADD_POINTER 1 ADD_CONTENT -1 LOOP_END -12 ADD_POINTER -2 OUTPUT_CONTENT 0
さて恒例の mandelbrot 集合描画での time 測定。前回の約 1/2 、最初の 1/5 程度。
./a.out ../../scripts/mandelbrot.bf 24.52s user 0.02s system 99% cpu 24.700 total
