Edited at

std::regexの構築は意外と重い

More than 3 years have passed since last update.

最近『コンピュータシステムの理論と実装』(原題 "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のことだから何か規格を無視した最適化でもしているのだろうか。