brainf*ckのインタプリタを書いて高速化したかった

sxclij

なんだこれは

rui氏のchibiccとか好きなので、まあ、そういうことです。
また、これは以下の記事をC言語で追ったものになります。（実質的なパロディ）
brainf*ckのインタプリタを書いて高速化しよう #Go - Qiita

できたもの

そしてこちらがbfインタプリタになります。
愚直に書いて68sだったものが最終的に0.5sまで短縮できました。
sxclij/sxcbf (github.com)

内容について

元記事にも書いていますが、以下のルールに基づいて遊びました。

素直に実装: 68s

元記事より1.5倍ぐらい時間がかかってます。Cなのに元記事のGo相手に惨敗して悲しいね。というかGo（と元記事の人）すごいね。

#pragma GCCを追加: 24s

３行で爆速になりました。やったね。

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

__attribute__(aligned(16)): 20s

メモリ配置のキリを良くしました。なぜ速くなるのかは、謎です。

__attribute__((aligned(bfalign))) char bf_mem[bfsize];
__attribute__((aligned(bfalign))) struct bfinst bf_insts[bfsize];

ループのジャンプ先を事前に計算: 12s

以前は対応するジャンプ先まで一つずつプログラムカウンタ（？）を動かしていましたが、遅いので事前に場所の計算をしました。
ついでにお手製の命令に切り替えました。（この部分は遅くなってるはずなので測らず）

連続する加減算、ポインタ移動を圧縮: 5.341s

1ずつ足し引きするのは遅いので一気にやってしまおうということです。

if (itr->value.inst == bfinst_kind_add_val && itr->next->value.inst == bfinst_kind_add_val) {
　　itr->value.val += itr->next->value.val;
    itr->next = itr->next->next;
}

[-]を圧縮: 4.967s

「[-]」は「while(*ptr) (*ptr)--」であるので、
「*ptr = 0」に書き換えます。

[->>+<<]系を圧縮: 4.398s

このパターンは値の移動（吸収？）を意味しているので以下のように書き換えます。

// while(*ptr) {
//     (*ptr)--;
//     (*ptr)--;
//     ptr++;
//     (*ptr)++;
//     (*ptr)++;
//     ptr--;
// }
*(ptr+2) += *ptr;
*ptr = 0;

複数の[-]を圧縮: 4.861s

逆に遅くなりました。悲しいね。memsetを使ったのが原因かも？

ifからswitchに切り替え: 4.072s

uchijo（元記事の人）さん曰く、gccはswitchの最適化が強いとのこと。

[>>]専用の命令を追加: 2.646s

ポインタ先の値が０になるまでn個飛ばしでポインタを移動させる専用の命令を追加しました。まさかここまで速くなるとは…

Linuxで実行する: 2.291s

WSLからLinuxに切り替えることでオーバーヘッドが無くなるはず…ということでUSBに入れたNobaraOSで実行してみました。さすがネイティブ環境、強い。

[追記] [->>+<-<]系を圧縮: 1.983s

解説できそうにないので雰囲気だけ読み取っていただければ。

擬似コード
*(ptr+pc[0]) += *ptr * pc[1]
*(ptr+pc[2]) += *ptr * pc[3]
*ptr = 0

if (itr0.inst == bfinst_kind_while_start &&
            itr1.inst == bfinst_kind_add_val &&
            itr2.inst == bfinst_kind_add_ptr &&
            itr3.inst == bfinst_kind_add_val &&
            itr4.inst == bfinst_kind_add_ptr &&
            itr5.inst == bfinst_kind_add_val &&
            itr6.inst == bfinst_kind_add_ptr &&
            itr7.inst == bfinst_kind_while_end &&
            itr1.data == -1 &&
            itr2.data + itr4.data + itr6.data == 0) {
    itr->value.inst = bfinst_kind_pseq2;
    itr->value.data = itr2.data;
    itr = itr->next;
    itr->value.data = itr3.data;
    itr = itr->next;
    itr->value.data = itr2.data + itr4.data;
    itr = itr->next;
    itr->value.data = itr5.data;
    bfnode_skip(itr, 4);
}

[追記] .bfを.cへ変換: 0.554s

gccが最強すぎてもう、多分最適化とか意味なかったんだと思います（何かあった顔）

終わりに

これ以上最適化の方法が思いつかないので一先ず終わりにしようと思います。C使ってるくせに元記事に負けていいものかという疑問もありますが、まあ、CPUとか環境が違いますしお寿司（）
bfインタプリタの高速化、めちゃくちゃ楽しいです。おすすめです。

いいなと思ったら応援しよう！