最近『コンピュータシステムの理論と実装』(原題 "The Elements of Computing Systems")のHack CPU向けのアセンブラを書いたのだが、異様にパフォーマンスが悪くて解決するのに少し悩んだ話。
結論
std::regex
を何度も呼ぶ関数の中で宣言するのはやめよう
宣言したいならstatic
にすべし
経緯
私の作ったアセンブラは、100行程度のソースならすぐにアセンブルし終わるが、30000行近いソースを入力すると3分近く時間を取られるものであった。
アセンブラの心臓部は、もちろんアセンブリを実際にパースする部分である。
パースは正規表現で行っていたので、初めは正規表現が重いのかと思いstd::regex::optimize
を付けてみるも一切効果なし。
正規表現の動作を除くと、重さの原因となる部分はもはや宣言部しかなかった。
次のようなものだ。
const std::string symbol_match = "([a-zA-Z_.$:][a-zA-Z\\d_.$:]*)";
const std::string dest_match = "([AMD]|A[MD]|[A]?MD)";
const std::string comp_match = "(0|[-]?1|[-!]?[DAM]|D[-+&|][AM]|[AMD][-+]1|[AM]-D)";
const std::string jump_match = "(JGT|JEQ|JGE|JLT|JNE|JLE|JMP)";
const std::regex a_match1("@" + symbol_match);
const std::regex a_match2("@([\\d]*)");
const std::regex c_match1(dest_match + "=" + comp_match + ";" + jump_match + "?");
const std::regex c_match2(dest_match + "=" + comp_match + ";?");
const std::regex c_match3(comp_match + ";" + jump_match + "?");
const std::regex c_match4(jump_match);
const std::regex l_match("\\(" + symbol_match + "\\)");
この宣言は1行読み込むたびに呼ばれる関数内でなされている。
std::regex
の宣言をstatic
にしたところ、たちまちパフォーマンスが向上。
30000行を処理するのに1秒もかからなくなった。
おまけ
元のソースでも、Visual Studioでビルドすると(static
化にはかなわないが)30000行に3秒くらいしかかからなかった。
Visual Studioのことだから何か規格を無視した最適化でもしているのだろうか。