2009年2月11日
C++ の string と vector の reserve() の挙動
C++ の string と vector には前もって容量を確保するための reserve() というメンバ関数があります。何気なく使っていた関数ですが最近になって興味深い挙動に気づきました。
reserve() の基本
string と vector の reserve() は前もって容量 (capacity) を確保しておくためのメンバ関数です。前もって容量を確保 (reserve) しておけば、データの追加時に発生する再割り当て (reallocation) を防ぐことができ、効率的です。
たとえば、何もしないで文字列に 1,000文字追加した場合、（内部的に倍々で容量を増やしていくため）10回程度の再割り当てが発生しますが、 s.reserve(1000) のように容量を確保しておけば 1回の割り当て (allocation) だけで済みます。
以下は Mac OS X 10.5 の gcc version 4.0.1 (Apple Inc. build 5465) での実行結果です。
何もしない場合
% cat reserve0.cc
#include <string>
const int N = 1000;
int main() {
std::string s;
for (int i = 0; i < N; ++i) {
s.append("a");
}
return 0;
}
% g++ -g reserve0.cc
% gdb ./a.out
(gdb) start
...
Breakpoint 1, main () at reserve0.cc:5
5 std::string s;
(gdb) b malloc
Breakpoint 2 at 0x954f825b
(gdb) c
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 1回
(gdb) bt
#0 0x954f825b in malloc ()
#1 0x97009598 in operator new ()
#2 0x96ff0fd2 in std::string::_Rep::_S_create ()
#3 0x96ff129a in std::string::_Rep::_M_clone ()
#4 0x96ff2a8f in std::string::reserve ()
#5 0x96ff2d21 in std::string::append ()
#6 0x96ff2da5 in std::string::append ()
#7 0x00001f61 in main () at reserve0.cc:7
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 2回
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 3回
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 4回
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 5回
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 6回
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 7回
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 8回
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 9回
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 10回
(gdb)
Continuing.
Breakpoint 2, 0x954f825b in malloc () ← 11回
(gdb)
Continuing.
Program exited normally.
(gdb)
たしかに 10回ほどの再割り当てが行われていることが確認できました。再割り当て時には元の領域から新しい領域への文字列のコピーも行われます。
reserve() した場合
% cat reserve1.cc
#include <string>
const int N = 1000;
int main() {
std::string s;
s.reserve(N);
for (int i = 0; i < N; ++i) {
s.append("a");
}
return 0;
}
% g++ -g reserve1.cc
% gdb ./a.out
(gdb) start
...
Breakpoint 1, main () at reserve1.cc:6
6 s.reserve(N);
(gdb) b malloc
Breakpoint 2 at 0x954f825b
(gdb) c
Continuing.
Breakpoint 2, 0x954f825b in malloc () ←1回
(gdb) bt
#0 0x954f825b in malloc ()
#1 0x97009598 in operator new ()
#2 0x96ff0fd2 in std::string::_Rep::_S_create ()
#3 0x96ff129a in std::string::_Rep::_M_clone ()
#4 0x96ff2a8f in std::string::reserve ()
#5 0x00001f42 in main () at reserve1.cc:6
(gdb) c
Continuing.
Program exited normally.
(gdb)
reserve() すると確かに 1回だけの割り当てで済むことが確認できました。
reserve() の間違った使い方
それでは reserve() を間違って使うとどうなるでしょうか。以下のコードではループの中で、現在のサイズ + 1 を reserve しています。
% cat reserve2.cc
#include <string>
const int N = 1000;
int main() {
std::string s;
for (int i = 0; i < N; ++i) {
s.reserve(s.size() + 1);
s.append("a");
}
return 0;
}
これをさきほどと同じようにデバッガで追いかけると 1,000回もの再割り当てが起きることがわかります。毎回文字列のコピーが行われていることを考えると、これは O(n^2) の計算量になります。実際、 N の数を 100000 くらいに増やすと、プログラムが終了するまでに 7秒もかかりました。
reserve() の不思議な挙動
さきほどのプログラムの挙動をもう少し追ってみると、容量の増え方が予想外の動きをしていることがわかりました。以下のコードでは reserve() の直後に容量を表示しています。
% cat reserve3.cc
#include <string>
#include <iostream>
const int N = 1000;
int main() {
std::string s;
for (int i = 0; i < N; ++i) {
s.reserve(s.size() + 1);
std::cout << s.capacity() << " ";
s.append("a");
}
return 0;
}
% g++ -g reserve3.cc
% ./a.out
1 2 4 4 8 6 12 8 16 10 20 12 24 14 28 16 32 ... 1988 996 1992 998 1996 1000
このように、容量が 1 2 4 4 8 6 12 8 16 10 20 12 24 14 28 ... のように増えたり減ったりしていることがわかりました。増えるだけで減ることはないと思っていたので、意外でした。2倍に増えたかと思えばまたすぐに小さくなっています。なぜこんな挙動をするのでしょうか。
謎を調べるため、デバッガで追ってみることにします。 Mac OS X の場合 /usr/lib/libstdc++-static.a にデバッグ情報つきの C++ のライブラリがあるので、これを使います。これを使うには g++ に -lstdc++-static を渡す必要があります。
% g++ -g -lstdc++-static reserve3.cc
% gdb ./a.out
(gdb) start
Breakpoint 1 at 0x3c400: file reserve3.cc, line 6.
...
Breakpoint 1, main () at reserve3.cc:6
6 std::string s;
(gdb) n
7 for (int i = 0; i < N; ++i) {
(gdb) n
8 s.reserve(s.size() + 1);
(gdb) s
std::string::size (this=0xbffff578) at bits/basic_string.h:584
584 bits/basic_string.h: No such file or directory.
in bits/basic_string.h
おっと、ソースコードが見当たらないといって怒られてしまいました。こういうときは dir コマンドでソースコードの場所を教えてあげれば OK です。
(gdb) dir /usr/include/c++/4.0.0/bits
Source directories searched: /usr/include/c++/4.0.0/bits:$cdir:$cwd
(gdb) s
585 { return _M_rep()->_M_length; }
が、デバッガで追いかけるより basic_string.h を直接読んだほうが早そうなので、そうすることにします。ざーっと読んでいくと basic_string.tcc の次のコードにたどり着きます。reserve() から間接的に呼ばれている _S_create() という関数内です。
// The below implements an exponential growth policy, necessary to
// meet amortized linear time requirements of the library: see
// http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
// It's active for allocations requiring an amount of memory above
// system pagesize. This is consistent with the requirements of the
// standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
__capacity = 2 * __old_capacity;
コメントには「ここでは償却線形時間要求を満たすために指数的な成長ポリシーを実装する」といった旨のことが書かれています。コードの方を見ると、「指定された新しい容量が現在よりも大きく、かつ、現在より2倍未満の場合は、新しい容量を現在の２倍にする」という処理が行われています。
文字列追加のために「指数的な成長ポリシー」が必要なことはわかりますが、reserve() したときに行わなくてもいいような気がします。
ともあれ、これで、現在の容量に 1しか足していないのに、容量が2倍になる謎が解けました。では減るほうはどうでしょうか。SGI の string のマニュアルを読むと次のように書かれています (C++ の仕様書は確認していません)。
Requests that the string's capacity be changed; the postcondition for this member function is that, after it is called, capacity() >= n. You may request that a string decrease its capacity by calling reserve() with an argument less than the current capacity. (If you call reserve() with an argument less than the string's size, however, the capacity will only be reduced to size(). A string's size can never be greater than its capacity.) reserve() throws length_error if n > max_size().
太字のところに「現在の容量 (capacity) よりも小さい値で reserve() を呼ぶことで、容量を減らすことができる 」と書かれています。つまり、string の reserve() で容量を減らせるのは仕様です。
というわけで、「指数的な成長ポリシー」と「現在の容量より減らせる」の2つが組み合わせると、容量が増えたり減ったりするという挙動が説明できます。
reserve() のアンチパターン
上のような一目で非効率とわかるコードを書くことはないと思いますが、複雑なコードでは reserve() の呼び出しが思わぬところに埋もれている可能性があるので注意が必要です。せっかく前もって適切に reserve() していても、処理の途中で余計な reserve() が入ってしまったら台無しになります。
たとえば、次の関数は、よかれと思って reserve() を行っていますが、余計なお世話になります。前述のとおり、reserve() には容量を縮める効果があるので下手に reserve() するとせっかく前もって確保していた容量が台無しになってしまうためです。
void AppendTwice(const string& stuff, string* output) {
output->reserve(output->size() + stuff.size() * 2);
output->append(stuff);
output->append(stuff);
}
余計なお世話をしないためには次のように書く必要があります。
void AppendTwice(const string& stuff, string* output) {
// 容量が足りていないときだけ reserve する
string::size_type new_size = output->size() + stuff.size() * 2;
if (output->capacity() < new_size) {
output->reserve(new_size);
}
output->append(stuff);
output->append(stuff);
}
処理の最初に前もって reserve() することは効果的ですが、文字列を連結していく途中で reserve() が入ると逆効果になることがあります。下手に reserve() を入れるくらいなら何もしないで「指数的な成長ポリシー」に任せたほうがましです。あるいは Rope のような内部的に非連続な文字列を使う手もあります。
vectorの場合
では vector の reserve() の方はどうでしょうか。結論からいうと、 vector の reserve() は容量を減らすことはありません。SGI の vector のマニュアルに次のように書かれています。
If n is less than or equal to capacity(), this call has no effect. Otherwise, it is a request for allocation of additional memory. If the request is successful, then capacity() is greater than or equal to n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
つまり、capacity() より小さい値を reserve() した場合、何も起きない仕様です。string もこの仕様なら、前述のコードで容量が増えたり減ったりするという不思議な挙動に悩まされることはなかったはずです。
また、vector.tcc の reserve() のコードは比較的シンプルで、素直に指定されたサイズで reallocation します。その代わり、「指数的な成長ポリシー」は _M_insert_aux() の中で実装されています。
size_type __len = __old_size != 0 ? 2 * __old_size : 1;
reserve() の中で「指数的な成長ポリシー」を実装している string より、 vector のやり方の方が好ましいように思います。
まとめ
長くなりましたが、まとめると次のようになります。
- reserve() を間違って使うと非常に非効率
- string の reserve() は現在より容量を減らせる
- vector の reserve() は現在より容量を減らせない
- string の reserve() は「指数的成長ポリシー」を発動する
- vector の reserve() は「指数的成長ポリシー」を発動しない
- string の reserve() するときは余計なお世話にならないように気をつけるべし
- Mac OS X でデバッグ情報つき C++ ライブラリを使うときは -lstdc++-static
- gdb にソースコードの場所を教えるときは dir コマンド
なお、この記事で取り上げた string と vector の挙動は GCC 4.0.3 に付属する STL での挙動です。他の STL の実装では挙動が異なると思います。
p.s.
これを書いた後で、Effective STL の「reserve を使って不必要な割り当てを避けよう」のところを確認してみると、string の reserve() が 容量を減らす件について軽く触れていました。以前に読んだのにすっかり忘れていました。
string では size() か n の小さい方の値に容量を「減らすことがある」が、string のサイズは常に変わらない。筆者の経験では、 string から余分な容量を減らすには「swap」技法を使ったほうが成功することが多い。