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

In article <[e-mail]>,
  "K.Kosako" <[e-mail]> writes:

> 一度に増加するセルの数はHEAP_SLOTS(10000)で、
> HEAPS_INCREMENT(10)は、一度に増加する管理領域のサイズのようです。

おぉ、なるほど。気がつきませんでした。
# どおりで 10000.times {a << "a"} とするたびに一回 GC がおこるわけだ...

In article <[e-mail]>,
  [e-mail] (Yukihiro Matsumoto) writes:

> |そうなっていれば、Array に要素を追加する操作が平均して定数時間で可能な
> |のと同様に、オブジェクトをアロケートする操作が GC の時間も含めて定数時
> |間で可能になる気がするのですが。
> 
> そうかも。木山くんが調べてくれるかも。^^;;;
> それともVMの方に気持ちが傾いてるかな。

大雑把に変更して調べてみました。
やはり平均して一回あたり定数時間で済むようになりますね。

% ./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.0390625
30000 0.078125
40000 0.1015625
50000 0.1171875
60000 0.140625
70000 0.1953125
80000 0.21875
90000 0.234375
100000 0.2578125
110000 0.28125
120000 0.296875
130000 0.3203125
140000 0.3359375
150000 0.4140625
160000 0.4375
170000 0.453125
180000 0.4765625
190000 0.4921875
200000 0.515625
210000 0.53125
220000 0.5546875
230000 0.5703125
240000 0.5859375
250000 0.609375
260000 0.625
270000 0.6484375
280000 0.6640625
290000 0.6796875
300000 0.703125
310000 0.859375
320000 0.875
330000 0.890625
340000 0.9140625
350000 0.9296875
360000 0.9453125
370000 0.9609375
380000 0.984375
390000 1.0
400000 1.015625
410000 1.0390625
420000 1.0546875
430000 1.078125
440000 1.09375
450000 1.109375
460000 1.1328125
470000 1.1484375
480000 1.1640625
490000 1.1875
500000 1.203125
510000 1.21875
520000 1.234375
530000 1.25
540000 1.2734375
550000 1.2890625
560000 1.3125
570000 1.328125
580000 1.3515625
590000 1.3671875
600000 1.390625
610000 1.40625
620000 1.421875
^C-e:1: Interrupt
        from -e:1:in `times'

Index: gc.c
===================================================================
RCS file: /src/ruby/gc.c,v
retrieving revision 1.70
diff -u -r1.70 gc.c
--- gc.c	2001/06/19 15:41:18	1.70
+++ gc.c	2001/06/26 07:01:43
@@ -267,6 +267,7 @@
 add_heap()
 {
     RVALUE *p, *pend;
+    long heap_slots;
 
     if (heaps_used == heaps_length) {
 	/* Realloc heaps */
@@ -277,9 +278,10 @@
 	if (heaps == 0) mem_error("heaps: can't alloc memory");
     }
 
-    RUBY_CRITICAL(p = heaps[heaps_used++] = (RVALUE*)malloc(sizeof(RVALUE)*HEAP_SLOTS));
+    heap_slots = HEAP_SLOTS << heaps_used;
+    RUBY_CRITICAL(p = heaps[heaps_used++] = (RVALUE*)malloc(sizeof(RVALUE)*heap_slots));
     if (p == 0) mem_error("add_heap: can't alloc memory");
-    pend = p + HEAP_SLOTS;
+    pend = p + heap_slots;
     if (lomem == 0 || lomem > p) lomem = p;
     if (himem < pend) himem = pend;
 
@@ -337,7 +339,7 @@
     /* check if p looks like a pointer */
     for (i=0; i < heaps_used; i++) {
 	heap_org = heaps[i];
-	if (heap_org <= p && p < heap_org + HEAP_SLOTS
+	if (heap_org <= p && p < heap_org + (HEAP_SLOTS << i)
 	    && ((((char*)p)-((char*)heap_org))%sizeof(RVALUE)) == 0)
 	    return Qtrue;
     }
@@ -676,7 +678,7 @@
     if (ruby_in_compile) {
 	/* should not reclaim nodes during compilation */
 	for (i = 0; i < used; i++) {
-	    p = heaps[i]; pend = p + HEAP_SLOTS;
+	    p = heaps[i]; pend = p + (HEAP_SLOTS << i);
 	    while (p < pend) {
 		if (!(p->as.basic.flags&FL_MARK) && BUILTIN_TYPE(p) == T_NODE)
 		    rb_gc_mark((VALUE)p);
@@ -691,7 +693,7 @@
     for (i = 0; i < used; i++) {
 	int n = 0;
 
-	p = heaps[i]; pend = p + HEAP_SLOTS;
+	p = heaps[i]; pend = p + (HEAP_SLOTS << i);
 	while (p < pend) {
 	    if (!(p->as.basic.flags & FL_MARK)) {
 		if (p->as.basic.flags) {
@@ -1045,7 +1047,7 @@
     for (i = 0; i < heaps_used; i++) {
 	RVALUE *p, *pend;
 
-	p = heaps[i]; pend = p + HEAP_SLOTS;
+	p = heaps[i]; pend = p + (HEAP_SLOTS << i);
 	for (;p < pend; p++) {
 	    if (p->as.basic.flags) {
 		switch (TYPE(p)) {
@@ -1078,7 +1080,7 @@
     for (i = 0; i < heaps_used; i++) {
 	RVALUE *p, *pend;
 
-	p = heaps[i]; pend = p + HEAP_SLOTS;
+	p = heaps[i]; pend = p + (HEAP_SLOTS << i);
 	for (;p < pend; p++) {
 	    if (p->as.basic.flags) {
 		switch (TYPE(p)) {
@@ -1245,7 +1247,7 @@
 	    }
 	}
 	for (i = 0; i < heaps_used; i++) {
-	    p = heaps[i]; pend = p + HEAP_SLOTS;
+	    p = heaps[i]; pend = p + (HEAP_SLOTS << i);
 	    while (p < pend) {
 		if (FL_TEST(p, FL_FINALIZE)) {
 		    FL_UNSET(p, FL_FINALIZE);
@@ -1258,7 +1260,7 @@
     }
     /* run data object's finaliers */
     for (i = 0; i < heaps_used; i++) {
-	p = heaps[i]; pend = p + HEAP_SLOTS;
+	p = heaps[i]; pend = p + (HEAP_SLOTS << i);
 	while (p < pend) {
 	    if (BUILTIN_TYPE(p) == T_DATA &&
 		DATA_PTR(p) && RANY(p)->as.data.dfree) {
-- 
[田中 哲][たなか あきら][Tanaka Akira]
「ふえろ! わかめちゃん作戦です$(C⊇」(Little Worker, 桂遊生丸)