std::string/pair をやめる & gprof で速度チューニング

自作の String/Pair が出来たのでインタプリタから STL が完全に削除された。
STLを使わなくなって

  • コンパイルが速くなった
  • 継続が安定して動くようになった
  • 実行速度があからさまに遅くなった ★

遅くなった理由を調べる

gprof で調べてみると。

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 95.54      2.57     2.57    99950     0.03     0.03  util::String::operator+=(char)
  0.74      2.59     0.02    67982     0.00     0.00  util::BinaryTree<monash::Object*>::get(util::BinaryTree<monash::Object*>::Node const*, int) const
  0.37      2.60     0.01   315258     0.00     0.00  util::String::at(unsigned int) const
  0.37      2.61     0.01   128896     0.00     0.00  util::String::set(char const*)
  0.37      2.62     0.01    80361     0.00     0.00  util::HashMap<monash::Object*>::hash(char const*)
  0.37      2.63     0.01    72144     0.00     0.00  monash::QuoteFilter::getChar()
  0.37      2.64     0.01    33940     0.00     0.00  monash::SExp::SExp(int)

うは。これは分かりやすいです。

String text = "higepo";
text += 'n';

こういうやつです。
1文字追加するごとに、内部バッファを確保しなおしてコピーを繰り返すのが遅いってことにすぐ気付く。
これは内部バッファのサイズをあらかじめ余分に確保しておけば劇的に改善できます。

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 25.00      0.02     0.02    80361     0.00     0.00  util::HashMap<monash::Object*>::hash(char const*)
 12.50      0.03     0.01   301122     0.00     0.00  util::String::size() const
 12.50      0.04     0.01    99951     0.00     0.00  util::String::operator+=(char)
 12.50      0.05     0.01    67982     0.00     0.00  util::BinaryTree<monash::Object*>::get(util::BinaryTree<monash::Object*>::Node const*, int) const
 12.50      0.06     0.01    39169     0.00     0.00  util::Vector<monash::SExp*>::Vector()
 12.50      0.07     0.01    11617     0.00     0.00  util::BinaryTree<monash::Object*>::add(util::BinaryTree<monash::Object*>::Node*&, int, monash::Object*)
 12.50      0.08     0.01     1932     0.01     0.01  util::String::operator+=(util::String const&)

うんうん。大分良くなりました。