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なども文字列のライブラリとしてあるようです。