先日のvectorの伸長度合いの記事に関して
という反応をいただきました。とても興味深い。みんな読みましょう。
自分の理解メモ：
「再利用ができるから嬉しい」等の議論をするなら、
今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、
有効に使えてるメモリ r^{k-1} (バッファ拡大直後)
や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。
まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、
(r-1)/r になります（途中計算略）。
この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、
という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2
で最大(25%)となることがわかります。
平均 (r^2-1)/2r^2 や利用率最高時 (r-1)/r は r が大きければ大きいほど良いので、
いずれにせよ r=2 が r=1.5 を上回る。
じゃあ再利用まで考えるとどうなるか、とシミュレーションで実験してみると、
再利用がハマる瞬間は確かに r=1.5 の最高利用率が上回るのだけど、
前回の記事で例示したような流れで5回に1回程度しか再利用が起きることはないので、
結局、r=2 を下回ってる普通の場合と平均するとだいたい 35～40% に落ち着いて、
r=2 の場合の 37.5% と変わらないじゃない！
ですねえ。納得しました。再利用云々は1.5倍説をサポートするには不足だ。
もちろん、vector単体で見れば最悪50%(r=2) vs
最悪66%(r=1.5) なので依然として"メモリ効率"がいいのには変わらないのだけど、
そこはある意味当たり前なので、 それに追加する議論として今までに確保したメモリ
(1 + r^1 + ... + r^k) を持ち出すわけですけど、
そこでは結局大差ないという結論が出てくる。なるほど。
C++ の std::vector や Java の ArrayList、
Ruby の Array、Python の list などなど、
多くの手続き型言語には、実行時にサイズを変更できる動的配列が実装されています。
動的なサイズ変更は、最初は適当なサイズのメモリを使っておいて、
足りなくなったら裏でもっと大きいサイズのメモリを確保し直してそっちに移動、
を繰り返すことで実現されてます。
こんな風にちょくちょくメモリの確保やデータの移動を繰り返すのに、 配列へのデータ追加コストは、 「平均すると」 配列サイズによらず一定の時間で終わるように実装されています。 なぜ？どうやって？ については、工藤拓さんによる素晴らしい解説記事があります。 ご一読あれ：
さて、こちらの記事では、「足りなくなったら配列を2倍にしていく」
というよくある実装を例にとって、
ならし計算量の解析をされていました。「一般的に配列サイズを指数的に増やしていけば O(1) になります」
と触れられているように、2倍でなくても、1より大きい倍数で増やしていく実装なら、同じ議論ができます。
やってみましょう。「足りなくなったら r 倍にしていく」場合、再配置によるコピー回数は…
1 + r + r^2 + ... + r^logr(n)
＝ (r^(logr(n)+1) - 1) / (r-1) // 等比数列の和の公式（公比r、初項1、項数logr(n)+1）。
＝ (rn-1) / (r-1) // r^logr(n) = n なので。
≒ r/(r-1) ・ n // 定数部分は無視できる。
これに再配置が起きない分の回数 n-logr(n)≒n を足して
n で割ると、１要素追加の平均計算量は (2r-1)/(r-1)、n が消えました。定数です。
というわけで、定数時間にしたいというだけなら、
r の値はどう選んでも問題ありません。
といっても、あんまり大きすぎるとメモリの無駄遣いになってしまいますし、
逆に小さすぎると、理論的には定数オーダとはいえども馬鹿にならないコストにふくれあがります。
実際に使われている動的配列の実装は、その辺りのバランスをとって、たとえば
「r=2 くらいなら丁度バランスいいんじゃない？」
と、適切な値を選んでいるわけです。
このチョイスは、どう取るのが一番バランスいいかは難しいところ。
統一見解は、ありません。2倍以外の増やし方をする処理系もたくさんあります。
調べてみました。
// include/bits/stl_vector.h : 1235行目～
const size_type __len = size() + std::max(size(), __n);
return (__len < size() || __len > max_size()) ? max_size() : __len;// include/vector : 1273行目～
_Capacity = max_size() - _Capacity / 2 < _Capacity
? 0 : _Capacity + _Capacity / 2; // try to grow by 50%// Objects/listobject.c : 24行目～
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);// array.c : 176行目～
ary_double_capa(VALUE ary, long min)
{
long new_capa = ARY_CAPA(ary) / 2;
...
new_capa += min;// java/util/ArrayList.java : 199行目～
int newCapacity = oldCapacity + (oldCapacity >> 1);// java/util/Vector.java : 251行目～
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);// av.c : 66行目～
if (AvALLOC(av) != AvARRAY(av)) {
...
if (key > AvMAX(av) - 10) {
newmax = key + AvMAX(av);
goto resize;
}
}
else {
...
newmax = key + AvMAX(av) / 5;
resize:// Zend/zend_dynamic_array.c : 43行目～
if (da->current == da->allocated) {
da->allocated *= 2;// rt/lifetime.d : 1414行目～
long mult = 100 + (1000L * size) / log2plus1(newcap);
// testing shows 1.02 for large arrays is about the point of diminishing return
if (mult < 102)
mult = 102;
newext = cast(size_t)((newcap * mult) / 100);// builtins.cc : 406行目～
int capacity = new_length + (new_length >> 1) + 16;// System.Collections.Generic/List.cs : 94行目～
Capacity = Math.Max (Math.Max (Capacity * 2, DefaultCapacity), minimumSize);どうも、1.5 倍と 2 倍が人気があるようです。 1.5 の方がメモリ効率はいいけどコピー回数は多い、2 の方がメモリ効率は悪いけど、コピー回数は少なくて済む。 どちらを好むかの趣味の問題にも見えますけど、調べてみると、2 の方はわかりませんが、 1.5 を好むのには理由がある という主張がしばしば見つかります。 正確には、黄金比 1.618... より小さくするのには理由がある、らしい。
私が最初にこの話を聞いたのは、以下のスレッドでの Andrew Koenig 氏の発言でした：
comp.lang.c++.moderated: vector growth factor of 1.5
理由はこうです。
stackoverflow: What is the ideal growth rate for a dynamically allocated array?
に具体例での解説があったので引用させてもらいます。まず r=2 倍の場合…
- 16バイト割り当てた状態から始めましょう。
- もっとメモリが必要になったら、32バイト割り当ててコピーし、16バイト解放します。すると16バイトの穴が残ります。
- もっとメモリが必要になったら、64バイト割り当ててコピーし、32バイト解放します。48バイトの穴が残ります (16と32が隣接してたとすれば)。
- もっとメモリが必要になったら、128バイト割り当ててコピーし、64バイト解放します。112バイトの穴が残ります (隣接を仮定)。
- 以下同様
つまり、2倍で進んでいくと、いつまで経っても、一度使ったメモリ領域を再利用する機会がありません。
メモリを使い捨てて突き進んでいきます。一方で、r=1.5 倍の場合…
- 16バイト割り当てた状態から始めましょう。
- もっとメモリが必要になったら、24バイト割り当ててコピーし、16バイト解放します。すると16バイトの穴が残ります。
- もっとメモリが必要になったら、36バイト割り当ててコピーし、24バイト解放します。40バイトの穴が残ります。
- もっとメモリが必要になったら、54バイト割り当ててコピーし、36バイト解放します。76バイトの穴が残ります。
- もっとメモリが必要になったら、81バイト割り当ててコピーし、54バイト解放します。130バイトの穴が残ります。
- もっとメモリが必要になったら、122バイト…は、さっきできた130バイトの穴を再利用できます！！！
ね？素晴らしいでしょう？
議論を一般化すると、
「1 + r + r^2 + ... + r^(k-1) バイトの穴」
「r^k バイト使っている」
「次 r^(k+1) バイト欲しい」
という状況で再利用が可能なためには、
「1 + r + r^2 + ... + r^(k-1) ≧ r^(k+1)」
が成り立たないといけません。r が黄金比未満なら、
k を大きくしていけば、そのうちこの再利用可能状態になります。
ところが黄金比以上では、絶対にそんな状態には辿り着けません。
だから、黄金比より少し小さい 1.5 が良い、とのこと。
あまり黄金比に近づけてしまうと、実際のマシンのメモリを食いつぶすくらい大きい
k の後で再利用可能になっても意味ないですし、
1.5倍というのは右シフトと足し算で表現できて高速、というのもあるでしょう。
連続して確保→解放した穴が隣接してくっつくかどうかはメモリアロケータの実装依存の話でしょうし、
動的配列の拡大以外に他のメモリ確保が割り込まない、
という簡単化した状況での議論なので、
実際のアプリケーションではもっと状況は複雑になっているはずです。
つまり、上の議論だけをもって一概に「1.5 倍が良い」と言い切れるかどうかは微妙なところ。
とはいえとはいえ、「r は大きすぎず小さすぎずならなんでもいい」
と比べれば、一つの指針としては有効な値なんじゃないかと思います。
Python の 9/8 倍や、 D の log N を使った複雑な倍率調整にもきっと技術的な根拠があるんじゃないかと思うんですが、 私が今日調べた範囲ではちょっとわかりませんでした。 識者の意見を待ちたいところです。
というか反応集。 realloc や mremap を頼って後ろに領域をノーコストで延ばせる状況を考慮に入れると、 また違った結論が出てくるのではなかろうか、という意見が。 shinhさん。 methaneさん。 repeatedlyさんに教えて頂いた D での議論もそういう方向に向かってました。 確かにそうですねえ。 どうなるんだろう。 どこかに定量的な議論ないかなあ。
※別記事で追記： "それでも２倍だ" 興味深い反論。みなさま読むべし。