[ruby-dev:13652] very long array and GC.

ふと、とても長い配列を使う機会があったのですが、なんとなく遅いことに気がつきました。

% ./ruby -e 't1 = Process.times; a=[]; loop {10000.times {a << "a"}; t2 = Process.times; print a.length, " ", t2.utime - t1.utime, "\n"};'
10000 0.0234375
20000 0.0546875
30000 0.0859375
40000 0.125
50000 0.171875
60000 0.2109375
70000 0.2578125
80000 0.3125
90000 0.375
100000 0.4296875
110000 0.5
120000 0.5625
130000 0.6328125
140000 0.7109375
150000 0.7890625
160000 0.8828125
170000 0.96875
180000 1.0625
190000 1.15625
200000 1.2578125
210000 1.359375
220000 1.4609375
230000 1.578125
240000 1.6953125
250000 1.8125
260000 1.9375
270000 2.0625
280000 2.1953125
290000 2.328125
300000 2.4609375
310000 2.6015625
320000 2.75
330000 2.8984375
340000 3.0546875
350000 3.2109375
360000 3.375
370000 3.5390625
380000 3.7109375
390000 3.8828125
400000 4.0625
410000 4.2421875
420000 4.421875
430000 4.609375
440000 4.8046875
450000 4.9921875
460000 5.1796875
470000 5.390625
480000 5.6015625
490000 5.796875
500000 6.0078125
510000 6.234375
520000 6.453125
530000 6.6875
540000 6.9140625
550000 7.1484375
560000 7.390625
570000 7.6328125
580000 7.875
590000 8.1328125
600000 8.3828125
^C-e:1: Interrupt
        from -e:1:in `times'
        from -e:1
        from -e:1:in `loop'
        from -e:1

plot してみれば一目瞭然ですが、線形になっていません。配列が長ければ長
いほど要素の追加に時間がかかっています。

最初は Array の実装を疑ったのですが、Array では領域が足りない場合には
1.5倍の領域を確保しており、要素の追加一回あたりのコストは平均して定数
時間に抑えられるようになっていることがわかりました。

そこで、profile をとってみたところ、時間がかかっているのは GC であるこ
とがわかり、実際 GC.disable すると線形になることが確認されました。

で、gc.c をすこし眺めてみたのですが、ひとつ疑問が出てきました。

heap は一度に定数個(HEAPS_INCREMENT)しか増やさない気がするのですが、な
ぜ(Array のように)その時点での大きさに比例して増やさないんでしょうか?

そうなっていれば、Array に要素を追加する操作が平均して定数時間で可能な
のと同様に、オブジェクトをアロケートする操作が GC の時間も含めて定数時
間で可能になる気がするのですが。
-- 
[田中 哲][たなか あきら][Tanaka Akira]
「ふえろ! わかめちゃん作戦です$(C⊇」(Little Worker, 桂遊生丸)