[ruby-dev:34768] Improvement of lazy sweep patch
From:
authorNari <authornari@...>
Date:
2008-05-20 04:23:16 UTC
List:
ruby-dev #34768
authorNariです。 前に作成していたLazySweepを、現在のHeap構造に合うように修正しました。 といってもほぼ書き直してしまいましたが。 性能は手持ちのベンチマークでためした所、さほど変化はありませんでした。 http://d.hatena.ne.jp/authorNari/20080520/1211251926 --- nari
Attachments (1)
rb_gc_lazy_sweep_r_16484.diff
(15.8 KB, text/x-diff)
Index: gc.c
===================================================================
--- gc.c ($B%j%S%8%g%s(B 16484)
+++ gc.c ($B:n6H%3%T!<(B)
@@ -91,6 +91,7 @@
int ruby_gc_debug_indent = 0;
#undef GC_DEBUG
+#define GC_NOTIFY 0
#if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__CYGWIN__)
#pragma pack(push, 1) /* magic for reducing sizeof(RVALUE): 24 -> 20 */
@@ -123,20 +124,25 @@
char *file;
int line;
#endif
+ char color;
} RVALUE;
#if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__CYGWIN__)
#pragma pack(pop)
#endif
+#define WHITE 0x00
+#define BLACK 0x01
+#define GRAY 0x02
+
struct heaps_slot {
void *membase;
RVALUE *slot;
int limit;
+ char color; // white : garbage, black : used, gray : not sweep
};
#define HEAP_MIN_SLOTS 10000
-#define FREE_MIN 4096
struct gc_list {
VALUE *varptr;
@@ -156,10 +162,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 +203,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 +270,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 +335,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 +400,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,11 +555,13 @@
heaps_length = next_heaps_length;
}
+#define RANY(o) ((RVALUE*)(o))
+
static void
assign_heap_slot(rb_objspace_t *objspace)
{
RVALUE *p, *pend, *membase;
- size_t hi, lo, mid;
+ size_t hi, lo, mid, i;
int objs;
objs = HEAP_OBJ_LIMIT;
@@ -570,6 +591,7 @@
hi = mid;
}
else {
+ printf("membase = %p : mid_membase = %p\n", membase, mid_membase);
rb_bug("same heap slot is allocated: %p at %ld", membase, mid);
}
}
@@ -579,6 +601,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 +613,9 @@
freelist = p;
p++;
}
+ if (hi < heaps_sweep_index) {
+ heaps_sweep_index++;
+ }
}
static void
@@ -632,15 +658,14 @@
return Qfalse;
}
-#define RANY(o) ((RVALUE*)(o))
-
-static VALUE
+VALUE
rb_newobj_from_heap(rb_objspace_t *objspace)
{
VALUE obj;
+ rb_thread_t *th = GET_THREAD();
if (ruby_gc_stress || !freelist) {
- if (!heaps_increment(objspace) && !garbage_collect(objspace)) {
+ if (!garbage_collect(objspace)) {
rb_memerror();
}
}
@@ -671,6 +696,7 @@
th->value_cache[i] = v;
RBASIC(v)->flags = FL_MARK;
+ RANY(v)->color = BLACK;
}
th->value_cache_ptr = &th->value_cache[0];
rv = rb_newobj_from_heap(objspace);
@@ -693,6 +719,7 @@
if (v) {
RBASIC(v)->flags = 0;
+ RANY(v)->color = WHITE;
th->value_cache_ptr++;
}
else {
@@ -824,8 +851,8 @@
for (i = 0; i < heaps_used; i++) {
p = heaps[i].slot; pend = p + heaps[i].limit;
while (p < pend) {
- if ((p->as.basic.flags & FL_MARK) &&
- (p->as.basic.flags != FL_MARK)) {
+ if ((p->color == BLACK) &&
+ (p->as.free.flags != FL_MARK)) {
gc_mark_children(objspace, (VALUE)p, 0);
}
p++;
@@ -865,8 +892,8 @@
while (lo < hi) {
mid = (lo + hi) / 2;
heap = &heaps[mid];
- if (heap->slot <= p) {
- if (p < heap->slot + heap->limit)
+ if (RANY(heap->slot) <= p) {
+ if (p < RANY(heap->slot) + heap->limit)
return Qtrue;
lo = mid + 1;
}
@@ -1005,8 +1032,9 @@
obj = RANY(ptr);
if (rb_special_const_p(ptr)) return; /* special const not marked */
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;
+ if (obj->color & BLACK) return; /* already marked */
+ obj->color = BLACK;
+ live++;
if (lev > GC_LEVEL_MAX || (lev == 0 && ruby_stack_check())) {
if (!mark_stack_overflow) {
@@ -1039,9 +1067,10 @@
again:
obj = RANY(ptr);
if (rb_special_const_p(ptr)) return; /* special const not marked */
- 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;
+ if (obj->as.free.flags == 0) return; /* free cell */
+ if (obj->color & BLACK) return; /* already marked */
+ obj->color = BLACK;
+ live++;
marking:
if (FL_TEST(obj, FL_EXIVAR)) {
@@ -1292,12 +1321,15 @@
static void
finalize_list(rb_objspace_t *objspace, RVALUE *p)
{
+ rb_thread_t *th = GET_THREAD();
+
while (p) {
RVALUE *tmp = p->as.free.next;
run_final(objspace, (VALUE)p);
if (!FL_TEST(p, FL_SINGLETON)) { /* not freeing page */
VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
p->as.free.flags = 0;
+ p->color = WHITE;
p->as.free.next = freelist;
freelist = p;
}
@@ -1305,124 +1337,102 @@
}
}
-static void
-free_unused_heaps(rb_objspace_t *objspace)
-{
- size_t i, j;
- RVALUE *last = 0;
+void rb_gc_abort_threads(void);
- for (i = j = 1; j < heaps_used; i++) {
- if (heaps[i].limit == 0) {
- if (!last) {
- last = heaps[i].membase;
+static int
+slot_sweep(rb_objspace_t *objspace, struct heaps_slot *target) {
+ RVALUE *p, *pend, *free;
+ RVALUE *final;
+ int freed = 0;
+
+ 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->color != BLACK) {
+ 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->color = WHITE;
+ 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->color = WHITE;
+ 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)
-{
- RVALUE *p, *pend, *final_list;
- size_t freed = 0;
- size_t i;
- size_t live = 0, free_min = 0, do_heap_free = 0;
+heap_sweep(rb_objspace_t *objspace) {
- 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
@@ -1431,8 +1441,7 @@
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);
+ RANY(p)->color = WHITE;
}
static void
@@ -1589,8 +1598,6 @@
#endif /* __human68k__ or DJGPP */
#endif /* __GNUC__ */
-#define GC_NOTIFY 0
-
void rb_vm_mark(void *ptr);
static void
@@ -1636,30 +1643,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 (p->color != BLACK) {
+ 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->color = WHITE;
+ }
+ 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 +1749,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 +2147,6 @@
if (p) {
finalize_list(objspace, p);
}
- free_unused_heaps(objspace);
during_gc = 0;
}
@@ -2092,6 +2190,7 @@
DATA_PTR(p) && RANY(p)->as.data.dfree &&
RANY(p)->as.basic.klass != rb_cThread) {
p->as.free.flags = 0;
+ p->color = WHITE;
if ((long)RANY(p)->as.data.dfree == -1) {
RUBY_CRITICAL(free(DATA_PTR(p)));
}
@@ -2103,6 +2202,7 @@
else if (BUILTIN_TYPE(p) == T_FILE) {
if (rb_io_fptr_finalize(RANY(p)->as.file.fptr)) {
p->as.free.flags = 0;
+ p->color = WHITE;
VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
}
}
@@ -2116,8 +2216,8 @@
rb_gc(void)
{
rb_objspace_t *objspace = &rb_objspace;
+ gc_finalize_deferred(objspace);
garbage_collect(objspace);
- gc_finalize_deferred(objspace);
}
/*