RustでBrainfuck処理系を高速化して遊んでみる
Brainfuckとは><+-.,[]の8つの命令からなるプログラミング言語である．
実装が簡単であるために，すでに多くの言語によって実装がなされている．
ここでは，
Adventures in JIT compilation: Part 1 - an interpreter
を参考にC++の実装をRustに移植し，そのパフォーマンスを計測し，比較をして遊んでみる．
Brainfuckの実装
実装したBrainfuckは
- simpleinterp
- optinterp
- optinterp2
- optinterp3
の4通りがある．
simpleinterpは素朴な実装であり，高速化はなされていない．
optinterpは[と]の対応表を実行時に作成することにより最適化を図っている．
optinterp2は8つの命令に加えて高水準な命令を定義し，
局所的に実行される命令をそれらの命令に置き換えることで最適化を行う．
optinterp3はさらに実行されるループに使われるパターンを高水準な命令に置き換え，最適化を行う．
実装の概要については BrainFuckの高速化 において解説している．
ベンチマークと計測方法
先に挙げたブログ内では
mandelbrotとfactorの2つのスクリプトをベンチマークに用いている．
ここでもこれらのスクリプトを用いることとする．
実行速度の計測にはtimeを用いる．
計測時には--releaseオプションを指定し，最適化がなされるようにした．
実行環境は
MacBook Air (11-inch, Early 2014)
CPU: 1.7 GHz Intel Core i7
RAM: 8GB 1600 MHz DDR3
OS: macOS High Sierra 10.13.5
cargo: 1.26.0
rustc: 1.26.2
である．
mandelbrot
mandelbrotの場合の比較．
simpleinterp: cargo run --release mandelbrot.bf 47.78s user 0.14s system 99% cpu 48.037 total
optinterp: cargo run --release mandelbrot.bf 25.90s user 0.10s system 99% cpu 26.080 total
optinterp2: cargo run --release mandelbrot.bf 8.30s user 0.08s system 99% cpu 8.443 total
optinterp3: cargo run --release mandelbrot.bf 6.46s user 0.09s system 99% cpu 6.617 total
factor
factorの場合の比較
simpleinterp: cargo run --release factor.bf < prime 17.16s user 0.10s system 99% cpu 17.321 total
optinterp: cargo run --release factor.bf < prime 9.64s user 0.09s system 99% cpu 9.790 total
optinterp2: cargo run --release factor.bf < prime 3.45s user 0.09s system 98% cpu 3.611 total
optinterp3: cargo run --release factor.bf < prime 2.93s user 0.07s system 98% cpu 3.039 total
まとめ
いずれのスクリプトの場合でも simpleinterp > optinterp > optinterp2 > optinterp3 の順の実行時間であった．これは元記事とも一致する． さらに元記事のようにJITなどを用いて最適化することも考えられる．