この記事は、Brainf*ck Advent Calendar 2019 - Adventarの八日目の記事です。
Brainfuckをインタプリタで実行するとかなり遅いです。
高速に実行する一つの簡単な方法に、「C言語に変換する」という方法があります。 Wikipediaにも書いてありますが、以下の簡単な文字列置換によって、C言語に変換できます。
>
→++ptr;
<
→--ptr;
+
→++*ptr;
-
→--*ptr;
,
→*ptr=getchar();
.
→putchar(*ptr);
[
→while(*ptr){
]
→}
あとは、適当な“おまじない”をくっつければコンパイルできるC言語ソースコードになります。
#include <stdio.h> int main() { char data[30000] = {}; char* ptr = data; 【ここに変換したコード本体】 }
さて、この方法では変換という手順が入るのが気になります。何とか変換せずに、“おまじない”をくっつけるだけでコンパイルできるようにできないでしょうか?
それ自体は簡単で、単にインタプリタのソースコードとくっつければ、コンパイルできるC言語ソースコードになります(第1二村射影)。 しかし、これは結局インタプリタと同程度の速度でしか動作せず、高速化したいという当初の目的を達成できていません。
「変換せず、“おまじない”をくっつけるだけでコンパイル可能」と「コンパイルして高速なバイナリを得たい」の両立はできないのでしょうか?
前提
- “おまじない”部分はC++17で記述する
- Brainfuckソースコードは、
"
でくくった文字列として別ファイルに記述する。これを#include
でC++ソースコードに取り込む - コンパイルして得られるバイナリがなるべく高速に動作するようにする
使ったメタプログラミングテクニック
- 文字列を型の世界に持っていくためにラムダ式でくるむ
- コンパイラの最適化を助けるループアンローリングを目的としてパック展開を使う
- 特殊化によるディスパッチ
- テンプレートの再帰展開制御に
if constexpr
を使う
コンパイル時に値を計算するのではなく、プログラムコードを計算すればいいだけなので、困難な点は少ないです。
完成品
#include <cstdio> #include <string> #include <utility> using Byte = int; constexpr std::size_t find_open( const char* bf_code, std::size_t begin, std::size_t end ) { for( std::size_t i = begin; i != end; ++i ) { if( bf_code[i] == '[' ) { return i; } } return end; } constexpr std::size_t find_close( const char* bf_code, std::size_t begin, std::size_t end ) { std::size_t depth = 0; for( std::size_t i = begin; i != end; ++i ) { if( bf_code[i] == '[' ) { ++depth; } if( bf_code[i] == ']' ) { --depth; } if( depth == 0 ) { return i; } } return end; } template<char C> Byte* action( Byte* ptr ) { static_assert( C != ']', "Unmatched ']'" ); return ptr; } template<> Byte* action<'+'>( Byte* ptr ) { ++*ptr; return ptr; } template<> Byte* action<'-'>( Byte* ptr ) { --*ptr; return ptr; } template<> Byte* action<'>'>( Byte* ptr ) { return ptr+1; } template<> Byte* action<'<'>( Byte* ptr ) { return ptr-1; } template<> Byte* action<','>( Byte* ptr ) { *ptr = std::getchar(); return ptr; } template<> Byte* action<'.'>( Byte* ptr ) { std::putchar(*ptr); return ptr; } template<std::size_t Begin, class Code, std::size_t... Indeces> Byte* ExecuteSimple( Byte* ptr, Code bf_code, std::index_sequence<Indeces...> ) { ((ptr = action<bf_code()[Begin+Indeces]>( ptr )), ...); return ptr; } template<std::size_t Begin, std::size_t End, class Code> Byte* ExecuteRange( Byte* ptr, Code bf_code ) { constexpr std::size_t Open = find_open( bf_code(), Begin, End ); ptr = ExecuteSimple<Begin>( ptr, bf_code, std::make_index_sequence<Open-Begin>() ); if constexpr( Open != End ) { constexpr std::size_t Close = find_close( bf_code(), Open, End ); static_assert( Close != End, "Unmatched '['" ); while( *ptr ) { ptr = ExecuteRange<Open+1, Close>( ptr, bf_code ); } ptr = ExecuteRange<Close+1, End>( ptr, bf_code ); } return ptr; } int main() { constexpr auto bf_code = []{return #include "mandelbrot.bf" ;}; constexpr std::size_t CodeSize = std::char_traits<char>::length( bf_code() ); Byte data[30000] = {}; Byte* ptr = data; ExecuteRange<0, CodeSize>( ptr, bf_code ); }
解説
using Byte = int;
Brainfuckデータメモリ一要素を表す型の定義です。後述しますが、char
とするよりもint
としたほうが高速です。ただし、ラップアラウンドを前提としているBrainfuckプログラムは正しく動作しなくなります。
find_open
とfind_close
find_open(bf_code, begin, end)
は、Brainfuck命令列bf_code
を受け取り、そのbegin
文字目*1以上end
文字目未満の間で最も近い位置にある[
を探し、その位置を返します。見つからなかった場合は、end
を返します。
find_close(bf_code, begin, end)
は、Brainfuck命令列bf_code
を受け取り、そのbegin
文字目以上end
文字目未満の間で最も近い位置にある[
と対応の取れた]
の位置を返します。該当しない場合、end
を返します。
以上の二つの関数は、自明に副作用がない純粋な関数であり、また単純型のみで型付けできるため、constexpr
関数として実装しています。
action
Brainfuck命令をテンプレート引数として受け取り、その動作をする関数に実体化されるテンプレートです。 全ての動作は、現在のデータメモリを指し示すポインタを受け取り、目的の動作を行い、更新されたデータメモリを指し示すポインタを返す関数として実装します。
6つの命令+
、-
、>
、<
、,
、.
について特殊化することでディスパッチを実現しています。
[
と]
の命令動作は、ローカルには完結しないため、ここでは取り扱いません(]
が来た場合、対応が取れていない]
であるため、コンパイルエラーにするstatic_assert
を入れています)。
ExecuteSimple
ExecuteSimple
はテンプレートで、ExecuteSimple<Begin, Code, Indeces...>
は、Brainfuck命令列を返す関数の型Code
、その中で[
と]
を含まない非負整数区間の始点を指定するBegin
、区間と同じ要素数の初項0公差1の数列を指定するIndeces
を受け取り、その一連の動作をする関数に実体化されます。
テンプレート引数を推論する都合上、受け取る順番が変則的です。
Indeces
は、0, 1, 2, 3, 4, 5
のような非負整数列になっており、((【Indecesを使った式】), ...);
の形で使うことで、【Indecesが0の時の式】, 【Indecesが1の時の式】, ……, 【Indecesが5の時の式】;
のように展開されます。
このように展開されることは、ループアンローリングを強制していることに相当します。このループアンローリングは、コンパイラの最適化を助けます。
ExecuteRange
ExecuteRange
はテンプレートで、ExecuteRange<Begin, End, Code>
は、Brainfuck命令列を返す関数の型Code
、その中で実行すべき非負整数区間*2を指定するBegin
、End
を受け取り、その動作をする関数に実体化されるテンプレートです。
このテンプレートの実体化の際、再帰的にこのテンプレートを、異なるテンプレート引数で実体化することがあります。
まず、find_open
で実行すべき区間の中に[
があるかを確認します。もし[
がなければ、ExecuteSimple
を呼び出すだけで仕事は完了です。
もし、[
が含まれていれば、対応する]
をfind_close
で探します。これは正しいBrainfuckプログラムであればあるはずです(もしなければ、対応が取れていない[
であり、コンパイルエラーにします)。
[
と]
で囲まれている区間は、そのBrainfuckプログラムを、while
文の中で再帰的にExecuteRange
を呼び出すことで変換します。
また、残りのBrainfuckプログラムも、再帰的にExecuteRange
に渡し、変換します。
if constexpr
を使うことにより、テンプレートの再帰的展開が無限ループに陥らないようにすることができます(使わない場合、実行されないif
文の中身も展開されてしまって無限ループになります)。
main
ゼロ初期化されたデータメモリの確保、Brainfuckデータメモリを指し示すポインタの確保、変換されたプログラムの呼び出しを行うだけです。
bf_code
がへんてこな書き方になっているのは以下の理由です。
action
、ExecuteSimple
、ExecuteRange
はいずれもテンプレート引数により動作を変化させる必要があります。
そのため、異なるBrainfuck命令列には、異なる型がつかないとうまくいきません。
C++のラムダ式は、すべて異なる型がつくことになっているので、定数を返すラムダ式を書くことで、これを実現できます。
ExecuteSimple
やExecuteRange
が、Brainfuck命令列ではなく、それを返す関数を受け取るような関数になっているのもこれが原因です。
速度測定
- ベンチマークとしてErik Bosman氏作mandelbrot.bを使用
- 環境:Windows10 (1903), WSL (Microsoft 4.4.0-18362.476-Microsoft 4.4.35), Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz(実際には、Intel(R) Turbo Boost Technology 2.0により3.50GHzで稼働しているはずです)
- C++コンパイラ:g++-9 (Ubuntu 9.2.1-17ubuntu1~16.04) 9.2.1 20191102
- C++コンパイル方法:
g++-9 -std=c++17 -O3 -march=native
- 実行速度の計測:
time ./a.out >/dev/null
を20回実行し、最も速かったものを採用
何も工夫しないインタプリタの場合
Brainfuckのインタプリタを書いた - よーるで、ナイーブなインタプリタと、g++-9
以降向けに最適化した*3ナイーブなインタプリタを実装しました。
これらを使った場合、前者では約40秒、後者では約27秒かかりました。
C言語に変換した場合
最初に述べた方法でC言語に変換したソースコードをコンパイルすると、その実行時間は0.953秒でした。
データメモリ用の配列をchar
ではなくint
で宣言した場合、実行時間はわずかに縮まり、0.906秒ほどになりました。
今回作った、C++メタプログラミングによる方法
実行速度は0.844秒まで高速化されました。
Byte
としてchar
を使った場合、0.875秒とほんのわずかですが劣ります。これは、コンパイラがchar
を取り扱うのが苦手であることに起因します。
x86は1Byteレジスタを持つため本来は4Byteレジスタとの間で転送する必要はないのですが、コンパイラがそれを読み切れず、不要な変換命令を挟んでしまうことが原因のようです。
ちなみに、clang++-9を用いた場合は、0.953秒でした。
ところで、言うまでもないことですが、32倍もの高速化が行われる理由は、そのほとんどがC++コンパイラの最適化能力にあります。 今回書いたコードは、Brainfuckのコードをちょっとパースして、C++コンパイラにわかりやすい形に変換したにすぎず、実際に最適化を行っているわけではありません。
なぜC言語に変換するよりC++メタプログラミングを使ったほうが高速なのか
謎です。
C++メタプログラミング版では、ループ内部が関数化されている影響で生存解析等の最適化が行いやすくなった結果のようにも思われますが、確定的なことはよくわかりません。
もっと高速化することは可能か
Brainfuckプログラムに頻出のパターンをとらえ、それを高速化するようなコンパイラ(あるいはメタプログラミングを駆使した“おまじない”)を書くことは可能です。
例えば、Brainfuck のプログラムを C に変換してコンパイルしてみる実験 - Qiitaで行われているようなC言語変換をしてからコンパイルしたバイナリを実行した場合、その実行時間は0.609秒と、今回作った方法を上回ります。
Brainfuckプログラムに頻出のイディオムを、今回作った方法で最適化できているか確認してみます。 結論から言うと、簡単なテストプログラムの場合、全部最適化できてしまいました。 上記記事のC言語変換ではできているが、コンパイラの汎用的な最適化では見抜けないというパターンは見つけられませんでした。
[-]
ゼロ代入イディオムです。今回作った方法では、ちゃんと最適化されます。
入力Brainfuckプログラム,[-].
とした場合、コンパイル結果は以下のようになりました。
mov rdi, QWORD PTR stdin[rip] # 第一引数=stdin call _IO_getc mov rsi, QWORD PTR stdout[rip] # 第二引数=stdout xor edi, edi # 第一引数 call _IO_putc
xor edi, edi
はx86のゼロ代入イディオムで、確かに最適化されていることがわかります。
[->+<]
破壊的加算イディオムです。-
と+
の位置が違ったり、<
と>
の個数が異なったり入れ替わっていたりするような場合もありますが、すべて同じです。,>,[-<+>]<.
のようなごく単純な例では、多少見抜いて最適化されるようです。
mov rdi, QWORD PTR stdin[rip] call _IO_getc mov rdi, QWORD PTR stdin[rip] mov ebp, eax # 一回目のgetcharで返ってきた値をebpに保存 call _IO_getc test eax, eax # 二回目のgetcharで返ってきた値が0であるかチェック mov edx, ebp # 一回目のgetcharで返ってきた値をedxにコピー lea ebp, [rbp+0+rax] # 二回目のgetcharで返ってきた値とebpに保存した値を足し算 cmove ebp, edx # 二回目のgetcharで返ってきた値が0の時はedx、そうでないときは加算結果 mov rsi, QWORD PTR stdout[rip] mov edi, ebp # ……をputcharの引数に渡す call _IO_putc
getc
で返ってきた値が0
の場合でも足し算した値をそのまま使えばいいのに、そこは見抜けなかったようです。
ちなみに、clangでコンパイルした場合、この部分を以下のように完全に最適化してくれます。
mov rdi, qword ptr [rip + stdin] call _IO_getc mov ebx, eax # 一回目のgetcharで返ってきた値をebxに保存 mov rdi, qword ptr [rip + stdin] call _IO_getc lea edi, [rax + rbx] # 二回目のgetcharで返ってきた値とebxに保存した値を足し算し、 # putcharの引数に渡す mov rsi, qword ptr [rip + stdout] call _IO_putc
gccは、この手の「結局同じになるのだから分岐しなくていい」というのを見抜けませんが、clangは見抜いてくれます。 総合的な最適化能力はgccのほうが上のようですが……。
まとめ
C++メタプログラミングを使い、Brainfuckのソースコードにちょっと“おまじない”をくっつけたソースコードをコンパイルするだけで高速なバイナリを得る方法を示しました。
それによって得られるバイナリは、従来の「C言語に変換する」手法を超える最適化がかかったものになっていました。
また、この手の別言語コンパイラを流用した最適化を行う場合、Brainfuckイディオムを特別扱いせずとも単純な例であればコンパイラ最適化が働くこと、 データメモリ用の配列を4Byteなどコンパイラが得意としている語長にすると更なる高速化が行われるということがわかりました。
明日は、roodni さんが1993年のbrainfuckについて書かれるそうです。1993年ってちょっと特別ですね。