ruby-dev

authorNariです。

バグが取れてRVALUEのフィールドを削る事ができました。
修正版を添付します。
バグだと思われていた箇所は私のコードによるものでした。。。


2008/05/20 16:50 authorNari <authornari@gmail.com>:
> authorNariです。
>
>> ざっとみたところRVALUEにフィールドが追加されているのだけが残
>> 念ですね。たった１バイトですが、アラインメントの関係でおそら
>> く１オブジェクトあたり4バイトはメモリ消費が増えるでしょう。
>
> これは本当は必要ないはずなので消したいのですが、
> FL_MARKを使ってflagにMARKを付けておくと、どこかのタイミングで
> MARKが消されてしまって、そのslotをsweepする際に生きているObjectが消されてしまう
> バグが発生しました。
> それを回避するためにRVALUEにフィールドを追加しています。
> （この前のパッチも同じ理由でフィールドが追加されています）
>
> 本当は消せるはずですし、僕も消したくてたまりませんので
> 頑張ってみます。
>
> 2008/05/20 14:48 Yukihiro Matsumoto <matz@ruby-lang.org>:
>> まつもと ゆきひろです
>>
>> In message "Re: [ruby-dev:34768] Improvement of lazy sweep patch"
>>    on Tue, 20 May 2008 13:23:16 +0900, authorNari <authornari@gmail.com> writes:
>>
>> |前に作成していたLazySweepを、現在のHeap構造に合うように修正しました。
>> |といってもほぼ書き直してしまいましたが。
>> |
>> |性能は手持ちのベンチマークでためした所、さほど変化はありませんでした。
>> |http://d.hatena.ne.jp/authorNari/20080520/1211251926
>>
>> すばらしい。
>>
>> ざっとみたところRVALUEにフィールドが追加されているのだけが残
>> 念ですね。たった１バイトですが、アラインメントの関係でおそら
>> く１オブジェクトあたり4バイトはメモリ消費が増えるでしょう。
>>
>> こちらでもいろいろ試してみます。
>>
>>
>
> ---
> nari
>
>

---
nari

Attachments (1)

rb_gc_lazy_sweep_r_16491.diff (13.2 KB, text/x-diff)

Index: gc.c
===================================================================
--- gc.c	($B%j%S%8%g%s(B 16491)
+++ gc.c	($B:n6H%3%T!<(B)
@@ -91,6 +91,9 @@
 int ruby_gc_debug_indent = 0;
 
 #undef GC_DEBUG
+#ifndef GC_NOTIFY
+#define GC_NOTIFY 0
+#endif
 
 #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__CYGWIN__)
 #pragma pack(push, 1) /* magic for reducing sizeof(RVALUE): 24 -> 20 */
@@ -129,14 +132,20 @@
 #pragma pack(pop)
 #endif
 
+enum slot_color {
+    WHITE = 0x00,  /* garbage */
+    BLACK = 0x01,  /* used */
+    GRAY  = 0x02,  /* not sweep */
+};
+ 
 struct heaps_slot {
     void *membase;
     RVALUE *slot;
     int limit;
+    enum slot_color color;
 };
 
 #define HEAP_MIN_SLOTS 10000
-#define FREE_MIN  4096
 
 struct gc_list {
     VALUE *varptr;
@@ -156,10 +165,16 @@
 	RVALUE *freelist;
 	RVALUE *range[2];
 	RVALUE *freed;
+	size_t live;
+	size_t dead;
+	size_t do_heap_free;
+	size_t sweep_index;
+	size_t sweep_increment;
     } heap;
     struct {
 	int dont_gc;
 	int during_gc;
+	int during_sweep;
     } flags;
     struct {
 	int need_call;
@@ -191,8 +206,14 @@
 #define himem			objspace->heap.range[1]
 #define heaps_inc		objspace->heap.increment
 #define heaps_freed		objspace->heap.freed
+#define live			objspace->heap.live
+#define dead			objspace->heap.dead
+#define do_heap_free		objspace->heap.do_heap_free
+#define heaps_sweep_index	objspace->heap.sweep_index
+#define heaps_sweep_inc 	objspace->heap.sweep_increment
 #define dont_gc 		objspace->flags.dont_gc
 #define during_gc		objspace->flags.during_gc
+#define during_sweep		objspace->flags.during_sweep
 #define need_call_final 	objspace->final.need_call
 #define finalizer_table 	objspace->final.table
 #define deferred_final_list	objspace->final.deferred
@@ -252,6 +273,7 @@
 
 static void run_final(rb_objspace_t *objspace, VALUE obj);
 static int garbage_collect(rb_objspace_t *objspace);
+static int garbage_collect_force(rb_objspace_t *objspace);
 
 void
 rb_global_variable(VALUE *var)
@@ -316,11 +338,11 @@
     if (size == 0) size = 1;
 
     if (ruby_gc_stress || (malloc_increase+size) > malloc_limit) {
-	garbage_collect(objspace);
+	garbage_collect_force(objspace);
     }
     RUBY_CRITICAL(mem = malloc(size));
     if (!mem) {
-	if (garbage_collect(objspace)) {
+	if (garbage_collect_force(objspace)) {
 	    RUBY_CRITICAL(mem = malloc(size));
 	}
 	if (!mem) {
@@ -381,10 +403,10 @@
     }
     if (!ptr) return ruby_xmalloc(size);
     if (size == 0) size = 1;
-    if (ruby_gc_stress) garbage_collect(objspace);
+    if (ruby_gc_stress) garbage_collect_force(objspace);
     RUBY_CRITICAL(mem = realloc(ptr, size));
     if (!mem) {
-	if (garbage_collect(objspace)) {
+	if (garbage_collect_force(objspace)) {
 	    RUBY_CRITICAL(mem = realloc(ptr, size));
 	}
 	if (!mem) {
@@ -536,6 +558,8 @@
     heaps_length = next_heaps_length;
 }
 
+#define RANY(o) ((RVALUE*)(o))
+
 static void
 assign_heap_slot(rb_objspace_t *objspace)
 {
@@ -570,7 +594,8 @@
 	    hi = mid;
 	}
 	else {
-	    rb_bug("same heap slot is allocated: %p at %"PRIuVALUE, membase, (VALUE)mid);
+	    rb_bug("same heap slot is allocated: %p, %p at %"PRIuVALUE,
+		   membase, mid_membase, (VALUE)mid);
 	}
     }
     if (hi < heaps_used) {
@@ -579,6 +604,7 @@
     heaps[hi].membase = membase;
     heaps[hi].slot = p;
     heaps[hi].limit = objs;
+    heaps[hi].color = BLACK;
     pend = p + objs;
     if (lomem == 0 || lomem > p) lomem = p;
     if (himem < pend) himem = pend;
@@ -590,6 +616,9 @@
 	freelist = p;
 	p++;
     }
+    if (hi < heaps_sweep_index) {
+	heaps_sweep_index++;
+    }
 }
 
 static void
@@ -632,15 +661,13 @@
     return Qfalse;
 }
 
-#define RANY(o) ((RVALUE*)(o))
-
 static VALUE
 rb_newobj_from_heap(rb_objspace_t *objspace)
 {
     VALUE obj;
 	
     if (ruby_gc_stress || !freelist) {
-    	if (!heaps_increment(objspace) && !garbage_collect(objspace)) {
+   	if (!garbage_collect(objspace)) {
 	    rb_memerror();
 	}
     }
@@ -1007,6 +1034,7 @@
     if (obj->as.basic.flags == 0) return;       /* free cell */
     if (obj->as.basic.flags & FL_MARK) return;  /* already marked */
     obj->as.basic.flags |= FL_MARK;
+    live++;
 
     if (lev > GC_LEVEL_MAX || (lev == 0 && ruby_stack_check())) {
 	if (!mark_stack_overflow) {
@@ -1042,6 +1070,7 @@
     if (obj->as.basic.flags == 0) return;       /* free cell */
     if (obj->as.basic.flags & FL_MARK) return;  /* already marked */
     obj->as.basic.flags |= FL_MARK;
+    live++;
 
   marking:
     if (FL_TEST(obj, FL_EXIVAR)) {
@@ -1305,134 +1334,112 @@
     }
 }
 
-static void
-free_unused_heaps(rb_objspace_t *objspace)
+void rb_gc_abort_threads(void);
+
+static int
+slot_sweep(rb_objspace_t *objspace, struct heaps_slot *target)
 {
-    size_t i, j;
-    RVALUE *last = 0;
+    RVALUE *p, *pend, *free;
+    RVALUE *final;
+    int freed = 0;
 
-    for (i = j = 1; j < heaps_used; i++) {
-	if (heaps[i].limit == 0) {
-	    if (!last) {
-		last = heaps[i].membase;
+    if (target->color == BLACK || target->color == WHITE) {
+	return Qfalse;
+    }
+
+    final = deferred_final_list;
+    free = freelist;
+    p = target->slot; pend = p + target->limit;
+    while (p < pend) {
+	if (!(p->as.basic.flags & FL_MARK)) {
+	    if (p->as.basic.flags) {
+		obj_free(objspace, (VALUE)p);
 	    }
+	    if (need_call_final && FL_TEST(p, FL_FINALIZE)) {
+		p->as.free.flags = FL_MARK; /* remain marked */
+		p->as.free.next = deferred_final_list;
+		deferred_final_list = p;
+	    }
 	    else {
-		free(heaps[i].membase);
+		VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
+		p->as.free.flags = 0;
+		p->as.free.next = freelist;
+		freelist = p;
 	    }
-	    heaps_used--;
+	    freed++;
 	}
+	else if (RBASIC(p)->flags == FL_MARK) {
+	    /* objects to be finalized */
+	    /* do nothing remain marked */
+	}
 	else {
-	    if (i != j) {
-		heaps[j] = heaps[i];
-	    }
-	    j++;
+	    p->as.basic.flags &= ~FL_MARK;
+	    dead += freed;
 	}
+	p++;
     }
-    if (last) {
-	if (last < heaps_freed) {
-	    free(heaps_freed);
-	    heaps_freed = last;
+    if (freed == target->limit && dead > do_heap_free) {
+	RVALUE *pp;
+	
+	target->limit = 0;
+	target->color = WHITE;
+	for (pp = deferred_final_list; pp != final; pp = pp->as.free.next) {
+	    pp->as.free.flags |= FL_SINGLETON; /* freeing page mark */
 	}
-	else {
-	    free(last);
+	freelist = free;	/* cancel this page from freelist */
+    }
+    else {
+	target->color = BLACK;
+    }
+    return Qtrue;
+}
+
+static void
+heap_sweep_increment(rb_objspace_t *objspace)
+{
+    int i = 0;
+
+    while (i < heaps_sweep_inc && heaps_sweep_index < heaps_used) {
+	if (slot_sweep(objspace, &heaps[heaps_sweep_index])) {
+	    i++;
 	}
+	heaps_sweep_index++;
     }
 }
 
-void rb_gc_abort_threads(void);
-
 static void
-gc_sweep(rb_objspace_t *objspace)
+heap_sweep(rb_objspace_t *objspace)
 {
-    RVALUE *p, *pend, *final_list;
-    size_t freed = 0;
-    size_t i;
-    size_t live = 0, free_min = 0, do_heap_free = 0;
 
-    do_heap_free = (heaps_used * HEAP_OBJ_LIMIT) * 0.65;
-    free_min = (heaps_used * HEAP_OBJ_LIMIT)  * 0.2;
-    if (free_min < FREE_MIN) {
-	do_heap_free = heaps_used * HEAP_OBJ_LIMIT;
-        free_min = FREE_MIN;
+    while (!freelist && heaps_sweep_index < heaps_used) {
+	slot_sweep(objspace, &heaps[heaps_sweep_index]);
+	heaps_sweep_index++;
     }
+}
 
-    freelist = 0;
-    final_list = deferred_final_list;
-    deferred_final_list = 0;
-    for (i = 0; i < heaps_used; i++) {
-	int n = 0;
-	RVALUE *free = freelist;
-	RVALUE *final = final_list;
+static int
+gc_lazy_sweep(rb_objspace_t *objspace, rb_thread_t *th)
+{
 
-	p = heaps[i].slot; pend = p + heaps[i].limit;
-	while (p < pend) {
-	    if (!(p->as.basic.flags & FL_MARK)) {
-		if (p->as.basic.flags) {
-		    obj_free(objspace, (VALUE)p);
-		}
-		if (need_call_final && FL_TEST(p, FL_FINALIZE)) {
-		    p->as.free.flags = FL_MARK; /* remain marked */
-		    p->as.free.next = final_list;
-		    final_list = p;
-		}
-		else {
-                    VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
-		    p->as.free.flags = 0;
-		    p->as.free.next = freelist;
-		    freelist = p;
-		}
-		n++;
-	    }
-	    else if (RBASIC(p)->flags == FL_MARK) {
-		/* objects to be finalized */
-		/* do nothing remain marked */
-	    }
-	    else {
-		RBASIC(p)->flags &= ~FL_MARK;
-		live++;
-	    }
-	    p++;
-	}
-	if (n == heaps[i].limit && freed > do_heap_free) {
-	    RVALUE *pp;
-
-	    heaps[i].limit = 0;
-	    for (pp = final_list; pp != final; pp = pp->as.free.next) {
-		p->as.free.flags |= FL_SINGLETON; /* freeing page mark */
-	    }
-	    freelist = free;	/* cancel this page from freelist */
-	}
-	else {
-	    freed += n;
-	}
+    if (heaps_increment(objspace)) {
+	heap_sweep_increment(objspace);
     }
-    if (malloc_increase > malloc_limit) {
-	malloc_limit += (malloc_increase - malloc_limit) * (double)live / (live + freed);
-	if (malloc_limit < GC_MALLOC_LIMIT) malloc_limit = GC_MALLOC_LIMIT;
+    else {
+	heap_sweep(objspace);
     }
-    malloc_increase = 0;
-    if (freed < free_min) {
-    	set_heaps_increment(objspace);
-	heaps_increment(objspace);
+    
+    if (!freelist) {
+	return Qfalse;
     }
-    during_gc = 0;
-
-    /* clear finalization list */
-    if (final_list) {
-	deferred_final_list = final_list;
-	return;
-    }
-    free_unused_heaps(objspace);
+    
+    return Qtrue;
 }
 
 void
 rb_gc_force_recycle(VALUE p)
 {
-    rb_objspace_t *objspace = &rb_objspace;
     VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
     RANY(p)->as.free.flags = 0;
-    RANY(p)->as.free.next = freelist;
-    freelist = RANY(p);
 }
 
 static void
@@ -1589,8 +1596,6 @@
 #endif /* __human68k__ or DJGPP */
 #endif /* __GNUC__ */
 
-#define GC_NOTIFY 0
-
 void rb_vm_mark(void *ptr);
 
 static void
@@ -1636,30 +1641,71 @@
 
 void rb_gc_mark_encodings(void);
 
-static int
-garbage_collect(rb_objspace_t *objspace)
+static void
+gc_mark_all_clear(rb_objspace_t *objspace)
 {
+    RVALUE *last = 0;
+    size_t i, j;
+    
+    for (i = j = 0; j < heaps_used; i++) {
+	if (heaps[i].color == WHITE && !deferred_final_list) {
+	    if (!last) {
+		last = heaps[i].membase;
+	    }
+	    else {
+		free(heaps[i].membase);
+	    }
+	    heaps_used--;
+	}
+	else {
+	    if (heaps[i].color == GRAY) {
+		RVALUE *p, *pend;
+		p = heaps[i].slot; pend = p + heaps[i].limit;
+		while (p < pend) {
+		    if (!(RBASIC(p)->flags & FL_MARK)) {
+			if (p->as.basic.flags && !FL_TEST(p, FL_FINALIZE)) {
+			    obj_free(objspace, (VALUE)p);
+			    VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
+			    p->as.free.flags = 0;
+			}
+		    }
+		    else if (RBASIC(p)->flags != FL_MARK) {
+			p->as.basic.flags &= ~FL_MARK;
+		    }
+		    p++;
+		}
+	    }
+	    else {
+		heaps[i].color = GRAY;
+	    }
+	    if (i != j) {
+		heaps[j] = heaps[i];
+	    }
+	    j++;
+	}
+    }
+    if (last) {
+	if (last < heaps_freed) {
+	    free(heaps_freed);
+	    heaps_freed = last;
+	}
+	else {
+	    free(last);
+	}
+    }
+}
+
+static void
+gc_marks(rb_objspace_t *objspace, rb_thread_t *th)
+{
     struct gc_list *list;
-    rb_thread_t *th = GET_THREAD();
+    size_t free_min = 0;
 
-    if (GC_NOTIFY) printf("start garbage_collect()\n");
+    live = 0;
+    freelist = 0;
 
-    if (!heaps) {
-	return Qfalse;
-    }
+    gc_mark_all_clear(objspace);
 
-    if (dont_gc || during_gc) {
-	if (!freelist) {
-            if (!heaps_increment(objspace)) {
-                set_heaps_increment(objspace);
-                heaps_increment(objspace);
-            }
-	}
-	return Qtrue;
-    }
-    during_gc++;
-    objspace->count++;
-
     SET_STACK_END;
 
     init_mark_stack(objspace);
@@ -1701,9 +1747,60 @@
 	}
     }
 
-    gc_sweep(objspace);
+    dead = 0;
+    heaps_sweep_index = 0;
+    heaps_sweep_inc = (heaps_used / 10) + 1;
+    do_heap_free = (heaps_used * HEAP_OBJ_LIMIT) * 0.65;
+    free_min = (heaps_used * HEAP_OBJ_LIMIT)  * 0.2;
+    if (free_min < FREE_MIN) free_min = FREE_MIN;
+    if (free_min > (heaps_used * HEAP_OBJ_LIMIT - live)) {
+	set_heaps_increment(objspace);
+	heaps_sweep_inc = (heaps_used + heaps_sweep_inc) / heaps_sweep_inc + 1;
+    }
+}
 
+static int
+garbage_collect_force(rb_objspace_t *objspace)
+{
+    if (malloc_increase > malloc_limit) {
+	malloc_limit += (malloc_increase - malloc_limit) * (double)live / (heaps_used * HEAP_OBJ_LIMIT);
+	if (malloc_limit < GC_MALLOC_LIMIT) malloc_limit = GC_MALLOC_LIMIT;
+    }
+    malloc_increase = 0;
+    gc_marks(objspace, GET_THREAD());
+    return garbage_collect(objspace);
+}
+
+static int
+garbage_collect(rb_objspace_t *objspace)
+{
+    rb_thread_t *th = GET_THREAD();
+
+    if (GC_NOTIFY) printf("start garbage_collect()\n");
+
+    if (!heaps) {
+	return Qfalse;
+    }
+
+    if (dont_gc || during_gc) {
+	if (!freelist) {
+            if (!heaps_increment(objspace)) {
+                set_heaps_increment(objspace);
+                heaps_increment(objspace);
+            }
+	}
+	return Qtrue;
+    }
+    during_gc++;
+    objspace->count++;
+
+    while (!gc_lazy_sweep(objspace, th)) {
+	gc_marks(objspace, th);
+    }
+
     if (GC_NOTIFY) printf("end garbage_collect()\n");
+    during_gc = 0;
+
     return Qtrue;
 }
 
@@ -2048,7 +2145,6 @@
     if (p) {
 	finalize_list(objspace, p);
     }
-    free_unused_heaps(objspace);
     during_gc = 0;
 }
 
@@ -2116,8 +2212,8 @@
 rb_gc(void)
 {
     rb_objspace_t *objspace = &rb_objspace;
+    gc_finalize_deferred(objspace);
     garbage_collect(objspace);
-    gc_finalize_deferred(objspace);
 }
 
 /*

Thread

Prev Next

In This Thread

Prev Next