以下の内容はhttps://lpha-z.hatenablog.com/entry/2019/12/08/231500より取得しました。

Brainfuck コードを最適化コンパイルする～C++メタプログラミングで～

この記事は、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++のメタプログラミングを駆使して、これを実現します。

前提

使ったメタプログラミングテクニック

コンパイル時に値を計算するのではなく、プログラムコードを計算すればいいだけなので、困難な点は少ないです。

完成品

#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年ってちょっと特別ですね。

*1:0-origin

*2:左閉右開半区間

*3:分岐予測器の予測的中率が高くなるようなコードが出力されるように書いたコードになっています。



以上の内容はhttps://lpha-z.hatenablog.com/entry/2019/12/08/231500より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14