brainfxxk処理系を最適化した話

といった現象が私の中で化学反応を起こした結果､BF処理系の最適化にゴールデンウイークを費やすという残念な結果となった｡

処理系概要

hogelog氏のfast-bfにいくつか最適化を加えました｡プロジェクトは以下｡

https://github.com/hogelog/fast-bf

処理系はC++で書かれており､BFのソースを読んでその都度最適化しながら中間コードに変換､それをx86の機械語に変換してから実行します｡

BF概要

レジスタ:
p: 操作対象のメモリ位置を示す

命令:
>: pの値を+1する
<: pの値を-1する
+ pが指すメモリの内容を+1する
-: pが指すメモリの内容を-1する
[: pが指すメモリの内容が0なら､対応する]にジャンプ｡0でなければ何もしない｡
]: ↑のジャンプ先
,: 標準入力から1文字読み､pが指すメモリにセット
.: pが指すメモリの内容を標準出力に出力

これだけでチューリング完全らしいですよ｡すごいですね｡

中間コードの最適化について

CALC,MOVE

>>>>>>>>>>>>>や++++++++++などの命令はBFに頻出しますが､これをいちいち一個ずつ実行していると効率が悪いのでまとめる｡新しく､CALC(x)とMOVE(n)という命令を定義します｡

CALC(x): pが指すメモリの内容を+xする
MOVE(n): pの値を+nする

中間コード変換時には､

  • <や>が来たら､MOVE(-1),MOVE(+1)に変換
  • +や-が来たら､CALC(-1),CALC(+1)に変換
  • CALCやMOVEが連続していたら､合成する

という処理をしている｡

LOAD

BFにおける

[-]

というプログラムは､pが指す内容が0になるまでpが指す内容を1引く､つまりpが指す内容を0にするという動作を行う(まわりくどい)｡
まわりくどい上にループを無駄に回して遅いので､LOAD(x)という命令を導入､

LOAD(x): pが指すメモリの内容をxで上書きする

[-]というパターンをLOAD(0)に置き換える｡

また､

LOAD(a)
CALC(b)

は

LOAD(a+b)

に､

LOAD(a)
LOAD(b)

は

LOAD(b)

に置き換えることで無駄な処理が減ります｡

SEARCH_ZERO
[>>>>>]

のような命令もBFでは頻出します｡これは､指定された個数おきにメモリの内容をチェックして､最初に発見したゼロの位置まで移動するという処理｡このパターンを発見したらSEARCH_ZERO(n)という命令に置き換えて､専用に最適化した処理を使用します｡

SEARCH_ZERO(n): 指す先が0になるまで､pをnずつ移動する
SET_MULTIPLIER, CALC_MULT
[->>>++<<<]

のようなパターンもよくある｡意味としては

p[3] += p[0]*2;
p[0] = 0;

です｡
複数のメモリ位置を同時に操作するパターンもあったり｡

[->++>>>+++++>++>+<<<<<<]

これは

p[1] += p[0]*2;
p[4] += p[0]*5;
p[5] += p[0]*2;
p[6] += p[0];
p[0] = 0;

という意味になる｡

こういった処理をループせずに実現するために､SET_MULTIPLIER､CALC_MULTという命令を定義する｡

SET_MULTIPLIER: 現在pが指す値を､倍率として設定｡
CALC_MULT(x): CALC(x)と同様だが､足される値はxに現在の倍率を掛けたもの｡
入力
  [->++>>>+++++>++>+<<<<<<]

MOVE,CALCの変換後
  [
    CALC(-1)
    MOVE(1)
    CALC(2)
    MOVE(3)
    CALC(5)
    MOVE(1)
    CALC(2)
    MOVE(1)
    CALC(1)
    MOVE(-6)
  ]

SET_MULTIPLIER, CALC_MULTの適用後
  SET_MULTIPLIER
  LOAD(0)
  MOVE(1)
  CALC_MULT(2)
  MOVE(3)
  CALC_MULT(5)
  MOVE(1)
  CALC_MULT(2)
  MOVE(1)
  CALC_MULT(1)
  MOVE(-6)

まとめとか

  • 私が実施した最適化､最後のSET_MULTIPLIERだけなんですが(他にもいくつかやったけど最後のに吸収されて消滅した)､hogelog氏のオリジナル実装に比べて17%くらい高速化することができました｡
  • 多重ループに対しても同じような最適化ができそうだが､コードの解析が複雑化するので断念｡
  • 低水準言語の最適化､頻出パターンを見つけては潰すみたいなことになりがちで残念感が強い｡言語の表現能力は高いほうが良い｡
  • 高速化すべきアプリケーションがないというのが一番の問題｡
    • fast-bfという高速な処理系が登場したことで､実用的なアプリケーションが増えることが期待されます｡
  • 有意義ななゴールデンウイークだった……