メモリ再確保は遅い - 総合的な学習のお時間

最近メインで使う言語がJavaからC++に変わったので、C++を書く練習に、PKU JudgeOnline（Project Eulerがもっと大規模になったみたいなの）をやってます。

JavaとC++って、構文上の見た目はそれなりに似ているものの、その底流にある考え方はずいぶん異なっていて、コードを書いていての感覚の違いによく戸惑いを覚えます。PKUの問題をやっていて、その一例が出てきたのでメモ。

こんな問題

取り上げるのは、No.1002 「487-3279」。
ここで取り上げたい部分以外の詳細は省略すると、こんな感じの問題です。

入力には、1行に電話番号がひとつずつ入っている。電話番号は7桁。
ただし、数字の間にハイフンが入っていることもある（例：487-3279）。
さらに、ハイフンはどこに何個あるかは分からない（例：1-2-3-4--560-----）。
入力から電話番号を読み取って、指示された処理をせよ。

std::stringへの読み込みが遅い

最初に書いたコードは次のようなものでした。ごく平凡に。

while(入力が続くあいだ){

  std::string str;
  std::cin >> str;
  
  /* strに対していろいろ処理 */
  
}

しかし、これを提出してみたら、時間制限に引っかかって不正解になってしまいました。
どこが遅いのか調べると、どうやらcinからstringに読み込んでいるところが遅いらしい。

どうして遅いのか、考えたりググったりした結果、stringが内部でメモリを動的に確保してるのが原因ではないかなと。

stringに対して、stringが内部で持ってるバッファよりも長いデータを追加しようとした時、stringはバッファ長を現在の2倍とかにしてメモリ再確保しようとするのだろう。たぶん。
1行にハイフンが何百万個も書かれているとても意地悪な入力があった場合、その行をstringに一気に読み込もうとすると、何度もくりかえしstring内部バッファの再確保が行われる。（問題には入力の1行の長さが最大どれだけかは書かれてないので、そんな意地悪な入力もありえる）
メモリ再確保は一般に（四則演算とかに比べて）遅い処理である。
さらにこの状況では、新たに確保した領域に対してこれまでのデータをコピーする処理もある。

まあこのへんは実装依存ではあるんだけど。

std::stringを固定長バッファにしたら速くなったよ

というわけで、入力の読み込みは動的メモリ再確保を行うstringを使うのではなく、最初に固定長のバッファを確保しといて、そこを上書きしつつ使うように書き直しました。

const int BUF_SIZE = 16;
char buf[BUF_SIZE];
std::cin.read(buf, BUF_SIZE);
for(int ind = 0; 入力が続くあいだ; ++ind){
  if(ind == BUF_SIZE){
    std::cin.read(buf, BUF_SIZE);
    ind = 0;
  }
  char c = buf[ind];

  /*
   いろいろ処理

   cがハイフンだったら無視するとか
      数字だったら保存するとか
  */

}

こうすると、今度は正解をもらえました。

手元の環境で簡単に実験すると、以下のような結果でした。

上記両方のコードで、大量のハイフンから成る行を1行読んだ
g++ 3.4.4 (cygwin)
最適化オプションなし

	std::string	固定長バッファ
10万文字	0.12秒	0.09秒
100万文字	0.45秒	0.14秒
1000万文字	3.6秒	0.75秒

感想

Javaで書いてたときは、メモリ確保の遅さを意識するようなことはほとんどなかったけれども、C++ではそれがよりプログラマに近いところに出てきているんだなあ。
上で行った予想通りに、string内部のバッファサイズはメモリ確保するごとに定数倍になっていくのなら、メモリ再確保は文字数の対数に比例する回数しか起こらないはず。
しかし、実際は対数オーダーどころではない早さで性能悪化している。
大きなサイズのメモリを確保するためには長い時間がかかるのが理由だろうか。
まあSTLの実装を読めっちゅう話だけども、テンプレートが使われたコードを読むレベルにはまだ達してない…
ちゃんとしたベンチマークの取り方を知らない。とりあえずtimeコマンドは覚えた。