Brainfuckのインタプリタの書き方によって、実行速度が変わるのかが気になったため書いてみました。

もちろん、前処理、特にその場でコンパイル (just in time compile) をするなどすれば高速化は容易です。そうではなく、ごく単純なswitch文を使うような、一命令ずつ見ていくタイプのインタプリタでも、書き方によって速度に大きな差が出るかという疑問です。

（余談）ファイル丸ごと読み込み

求めていたものは以下のページに書かれています。適切な検索キーワードを見つけることが難しいですが、「string fstream 一気に読み込み」で見つかりました。

C++ ファイルを全て読み込む - 備忘録

int main( int argc, char* argv[] ) {
    std::ifstream ifs( argv[1] );
    std::string str( (std::istreambuf_iterator<char>(ifs)), std::istreambuf_iterator<char>() );
}

(std::istreambuf_iterator<char>(ifs))とかっこがついているのには意味があります。これがないと、以下のパターンにマッチしてしまうため、関数宣言だと解釈されてしまいます。

ReturnType func_name( Arg1Type (arg1), Type2() );

(arg1)の部分は不自然ですが、このようなかっこをつけることは許されています。

Type2()の部分は、Type2 (*)()、つまり関数ポインタ型（引数なし、返り値型がType2）が第二引数の型であるというように解釈されます。第二引数の名前は省略されています。

丸かっこを使ったコンストラクタ呼び出しが関数宣言と解釈される現象があることは知っていたのですが、引数なしの場合だけだと思っていました。第一引数のように無駄なかっこ扱いされる場合、第二引数のように引数なし関数のかっこ扱いされる場合はどちらも知りませんでした。教育的な例ですね……。

このように丸かっこを使ったコンストラクタ呼び出しは問題が発生しやすいです。こういう場合は統一初期化構文を使うのが良い解決策です。

例えば、std::istreambuf_iterator<char>()ではなく、統一初期化構文を使ってstd::istreambuf_iterator<char>{}とすれば問題が解決します。

自然な実装

普通にインタプリタを書くと以下のようになります。データメモリをスタック上にとるとスタックオーバーフローが発生しうるので避けたほうが賢明ですグローバル領域に確保するのが最も簡単です（よりきれいな書き方は、動的確保する方法でしょう）。

#include <cstdint>
#include <array>

std::array<std::uint8_t, 1000000> data;

#include <iostream>
#include <fstream>
#include <string>
int main( int argc, char* argv[] ) {
    std::ifstream ifs( argv[1] );
    std::string insn( (std::istreambuf_iterator<char>(ifs)), std::istreambuf_iterator<char>() );
    auto ip = insn.begin();
    auto dp = data.begin();
    while (ip != insn.end()) {
        switch(*ip) {
        case '+': ++*dp; break;
        case '-': --*dp; break;
        case '>': ++dp; break;
        case '<': --dp; break;
        case '.': std::cout << *dp; break;
        case ',': std::cin >> *dp; break;
        case ']': if ( *dp) for( int loop = 0; loop += *ip == ']', loop -= *ip == '['; ) --ip; break;
        case '[': if (!*dp) for( int loop = 0; loop += *ip == '[', loop -= *ip == ']'; ) ++ip; break;
        default:;
        }
       ++ip;
    }
}

もっと速い実装

実は、以下のような意味不明なswitch文を書くと、先の実装に比べて1.37倍ほど高速になります。速度の測定は、Intel Core i7-4771 （Haswell）、g++-9.1 -O3 -march=native、動作プログラムはErik Bosman氏作mandelbrot.bです。

#include <cstdint>
#include <array>
std::array<std::uint8_t, 1000000> data;
#include <iostream>
#include <fstream>
#include <string>
#include <cstdio>
int main( int argc, char* argv[] ) {
    std::ifstream i( argv[1] );
    std::string insn( (std::istreambuf_iterator<char>(i)), std::istreambuf_iterator<char>() );
    auto ip = insn.begin();
    auto dp = data.begin();
    while (ip != insn.end()) {
        switch(*ip) {
        case '>': ++dp; break;
        case '<': --dp; break;
        default:;
        switch(*ip) {
        case '+': ++*dp; break;
        case '-': --*dp; break;
        case '.': std::cout << *dp; break;
        case ',': std::cin >> *dp; break;
        case ']': if ( *dp) for( int loop = 0; loop += *ip == ']', loop -= *ip == '['; ) --ip; break;
        case '[': if (!*dp) for( int loop = 0; loop += *ip == '[', loop -= *ip == ']'; ) ++ip; break;
        }
        }
        ++ip;
    }
}

なぜ速度に違いが出るのか

観察

各case文を"上側"または"下側"のswitch文に移動した場合のコンパイル結果を観察します。すると、以下のような違いがあることがわかります。

case '['とcase ']'に対応する文は、どちらに入れても大きく変わらない
- case '['とcase ']'に対応する文はループのある長いコードであり、コンパイラはこれを別立てで考えている？
その他のcase文6つのうち、5つ以上が片方に入ると、ジャンプテーブルを使った実装になる
- 各case式の値が狭い範囲に分布しているかとは無関係にジャンプテーブルになる
- 各case式の値が狭い範囲に分布していると、ジャンプテーブルのサイズは小さくなる
ジャンプテーブルにならない場合、高速に実行される
case '<'とcase '>'のみを"上側"のswitch文に入れると最高速
- <と>は出現頻度が最も高い二つ
- 一般に、出現頻度の高い事象から検討するのが最適

速度に差が出る原因

一般にジャンプテーブルを使った間接分岐でswitch文を構成する場合、分岐予測が当たりにくくなります。

分岐予測器は条件分岐（if文）が成立するか否かを当てることには強いです。一方、その分岐が飛ぶ先を当てることは苦手であり、前に飛んだアドレスにもう一度飛ぶだろうくらいの予測しかしてくれません（最近は間接分岐用の分岐予測器も研究されているようです。この前、パーセプトロンを使ったような間接分岐予測器が発表されていました）。

ジャンプテーブルを使う場合、そのswitch文を処理するためには分岐予測ミスは高々一回しか起こりません。一方、ジャンプテーブルを使わない場合、（おそらく二分探索的な）if文のツリーになるため、分岐予測ミスは複数回起こりえます。

こう聞くとジャンプテーブルのほうがよさそうに思えますが、今回作ったBrainfuckのインタプリタは以下の条件が効いてくるため、if文のツリーの分岐予測ミス率は意外と低いものとなり、ジャンプテーブルを使った場合の性能を上回ります。

インタプリタを動かす場合、同じような命令列が流れてくることが多い。よってswitch文の引数に来る値の系列には法則性があり、過去の分岐方向履歴を活用した分岐予測は当たりやすい
一見256方向分岐だが、実行時間のほとんどを占めているのは+-<>[]の6文字だけである（,は現れず、.もほとんど現れない）。しかもほとんどの部分が<か>の連続である。つまり、「前回と同じ方向に行く」という雑な分岐予測器でさえ、かなりの精度で当てることができる

g++-9ではコード生成エンジンが大幅に変わっており、特にswitch文の最適化を強化したとうたっていました。今回のような結果になったのは、g++-9を使ったことも原因の一つでしょう。

g++-8との違い

g++-8を使った場合、case文を4つずつに分けたときだけはif文のツリーになりました。つまり、「4つ以下ならif文のツリーにする」というルールは変わっていないようです。一方、g++-9では、case '['とcase ']'に対応する文のような長いコードを特別扱いするようです。長いコードの場合は分岐予測ミスによる損失が相対的に小さいとみなしているのでしょうか……？

まとめ

g++-9ではswitch文の最適化が強化されており、小型のswitch文をif文のツリーに分解する最適化をしてくれることがあります。よって、switch文を二つに分解するという一見意味の分からないコード変形を行うことで、if文のツリーへの変形を行ってほしいということをコンパイラに伝えることができます。

インタプリタを実装するときは、ジャンプテーブルではなくif文のツリーを使ったほうが高速な場合もあります。よって、このようなコード変形は、インタプリタの高速実装に役立てられるかもしれません。