c++での文字列最適化
Optimized C++に載っている文字列最適化の手法をgoogle benchmarkでパフォーマンス測定してみました。 www.amazon.co.jp github.com
まず以下の関数の結果を測定してみます。この関数対してパフォーマンス改善をおこなっていきます。
std::string s("\07Now is the time\07 for all good men\r\n to come to the aid of their country. \07"); std::string remove_ctrl(std::string s) { std::string result; for (size_t i=0; i<s.length(); ++i) { if (s[i] >= 0x20) result = result + s[i]; } return result; } static void BM_remove_ctrl(benchmark::State& state) { for (auto _ : state) std::string a = remove_ctrl(s); } BENCHMARK(BM_remove_ctrl);
結果は以下のようになります。
------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------- BM_remove_ctrl 12140 ns 12140 ns 53407
std::stringを使う場合気をつけないと内部的にコピー作成が行われるため性能を悪化させます。今回の例であれば特にresult = result + s[i];のresult + s[i];の部分で毎回一次文字列を作成しresultへの代入となっているためコストがかかっています。
変更文字列演算を使う
では一次文字列を使わないでresult += s[i];で代入するようにしてみます。
std::string s("\07Now is the time\07 for all good men\r\n to come to the aid of their country. \07"); std::string remove_ctrl_mutating(std::string s) { std::string result; for (size_t i=0; i<s.length(); ++i) { if (s[i] >= 0x20) result += s[i]; } return result; } static void BM_remove_ctrl_mutating(benchmark::State& state) { for (auto _ : state) std::string a = remove_ctrl_mutating(s); } BENCHMARK(BM_remove_ctrl_mutating);
結果は以下のように大分改善されているのが確認できます。
------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------- BM_remove_ctrl 12140 ns 12140 ns 53407 BM_remove_ctrl_mutating 1469 ns 1469 ns 502927
次のパフォーマンス改善としてresult += s[i];で変更文字列を行う際に内部的にメモリを確保しているアロケータが追加でメモリを確保する際のコストを削減します。std::stringでは例えば2文字分の文字列を確保している場合に追記で3文字必要な場合4文字分の確保してから文字列の変更を行う動きをしているのですが、文字列の変更のたびにメモリ確保が発生しないよう最初に文字数分のメモリ確保を行うことで性能を改善します。
文字数分確保する
それで事前に文字数分確保する方法として以下のようにresult.reserve(s.length());を実行します。
std::string s("\07Now is the time\07 for all good men\r\n to come to the aid of their country. \07"); std::string remove_ctrl_reserve(std::string s) { std::string result; result.reserve(s.length()); for (size_t i=0; i<s.length(); ++i) { if (s[i] >= 0x20) result += s[i]; } return result; } static void BM_remove_ctrl_reserve(benchmark::State& state) { for (auto _ : state) std::string a = remove_ctrl_reserve(s); } BENCHMARK(BM_remove_ctrl_reserve);
パフォーマンス測定の結果は以下のように改善されていることが確認できます。
------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------- BM_remove_ctrl 12140 ns 12140 ns 53407 BM_remove_ctrl_mutating 1469 ns 1469 ns 502927 BM_remove_ctrl_reserve 1248 ns 1248 ns 559025
次なるパフォーマンス改善として、現在関数の引数の型がstd::string sで渡しており呼び出しの時点でコピーを作成して渡しているのですが、コピーを作成するのが不要なためstd::string const& sにします。
文字列引数のコピーをなくす
関数の引数を変更したものは以下になります。
std::string s("\07Now is the time\07 for all good men\r\n to come to the aid of their country. \07"); std::string remove_ctrl_refs(std::string const& s) { std::string result; result.reserve(s.length()); for (size_t i=0; i<s.length(); ++i) { if (s[i] >= 0x20) result += s[i]; } return result; } static void BM_remove_ctrl_refs(benchmark::State& state) { for (auto _ : state) std::string a = remove_ctrl_refs(s); } BENCHMARK(BM_remove_ctrl_refs);
測定結果は以下のように僅かに改善されています。
------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------- BM_remove_ctrl 12140 ns 12140 ns 53407 BM_remove_ctrl_mutating 1469 ns 1469 ns 502927 BM_remove_ctrl_reserve 1248 ns 1248 ns 559025 BM_remove_ctrl_refs 1170 ns 1170 ns 604706
次なるパフォーマンス改善として、現在戻り値がstd::stringになっているがこれでは戻り値を返す際に毎回コピーコンストラクタが呼ばれているので、これを無くすように結果の代入先をポインタとして渡しておく。
戻り値のコピーをなくす
修正したものは以下になる。
std::string s("\07Now is the time\07 for all good men\r\n to come to the aid of their country. \07"); void remove_ctrl_ref_result( std::string& result, std::string const& s) { result.clear(); result.reserve(s.length()); for (size_t i=0; i<s.length(); ++i) { if (s[i] >= 0x20) result += s[i]; } } static void BM_remove_ctrl_ref_result(benchmark::State& state) { std::string a; for (auto _ : state) remove_ctrl_ref_result(a, s); } BENCHMARK(BM_remove_ctrl_ref_result);
結果は以下のように改善されていっていることが分かる。
------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------- BM_remove_ctrl 12140 ns 12140 ns 53407 BM_remove_ctrl_mutating 1469 ns 1469 ns 502927 BM_remove_ctrl_reserve 1248 ns 1248 ns 559025 BM_remove_ctrl_refs 1170 ns 1170 ns 604706 BM_remove_ctrl_ref_result 1096 ns 1096 ns 649890
std::stringでパフォーマンス改善を行う場合、コピーの作成回数を減らすのが基本的のはずでremove_ctrl_ref_resultでコピーの作成は十分減らすことができています。次なるパフォーマンス改善としてアルゴリズムの改善があり、現状一文字ずつresult += s[i];で変更していっていますが複数文字列まとめて変更するなどの改善があります。今回はそのようなアルゴリズム改善は行はずstd::stringからchar*を使いstd::stringが内部的に持っているアロケータを通さないことで改善されることを確認します。
char*を使う
char*を使う場合、以下のような実装になります。
std::string s("\07Now is the time\07 for all good men\r\n to come to the aid of their country. \07"); void remove_ctrl_cstrings(char* destp, char const* sourcep, size_t length) { for (size_t i=0; i<length; ++i) { if (sourcep[i] >= 0x20) *destp++ = sourcep[i]; } *destp = 0; } static void BM_remove_ctrl_cstrings(benchmark::State& state) { char a[s.length()]; memset(a, 0, sizeof(a)); char* sc = new char[s.size()]; std::strcpy(sc, s.c_str()); for (auto _ : state) remove_ctrl_cstrings(a, sc, s.length()); } BENCHMARK(BM_remove_ctrl_cstrings);
結果を見ると以下のように大分改善されていることが確認できますが、関数のインターフェースがstd::stringの時から修正が必要になります。
------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------- BM_remove_ctrl 12140 ns 12140 ns 53407 BM_remove_ctrl_mutating 1469 ns 1469 ns 502927 BM_remove_ctrl_reserve 1248 ns 1248 ns 559025 BM_remove_ctrl_refs 1170 ns 1170 ns 604706 BM_remove_ctrl_ref_result 1096 ns 1096 ns 649890 BM_remove_ctrl_cstrings 172 ns 172 ns 4144539
今回は単純な文字列の操作だったためcharで問題ありませんでしたが複雑な操作が必要になってくるとcharでは厳しかったりするので、用途に合わせて使用する文字列ライブラリの選定は必要になってくるかと思います。今回はstd::stringとchar*だけでみてましたがstringstreamやboostのstringなども文字列のライブラリとしてあるようです。
