ruby-dev

初めまして、中村と申します。

RubyGCにLazySweepを取り込んだものを作ってみました。
パッチは添付しています。

詳細は
http://d.hatena.ne.jp/authorNari/20080311/1205242360
に書いております。

あまり性能が劇的に改善されているわけではないのですが、
中々苦労しましたので、一応ご報告させていただきました。(^_^;)

何かの参考になれば幸いです。

--
id:authorNari

Attachments (1)

gc_lazy_sweep_r15749_patch.diff (11.5 KB, text/x-diff)

Index: gc.c
===================================================================
--- gc.c	($B%j%S%8%g%s(B 15749)
+++ gc.c	($B:n6H%3%T!<(B)
@@ -11,6 +11,7 @@
 
 **********************************************************************/
 
+
 #include "ruby/ruby.h"
 #include "ruby/signal.h"
 #include "ruby/st.h"
@@ -131,6 +132,7 @@
     char *file;
     int   line;
 #endif
+    char color;
 } RVALUE;
 
 #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__CYGWIN__)
@@ -140,6 +142,25 @@
 static RVALUE *freelist = 0;
 static RVALUE *deferred_final_list = 0;
 
+/* lazy sweep */
+static int gc_state = 0;
+static int lazy_sweeps_lenght = 0;
+static int sweep_time = 0;
+static int sweeping_slot = 0;
+static int end_sweep_slot = 0;
+static unsigned long lazy_lease_limit = 0;
+static unsigned long lazy_lease_rest = 0;
+static struct heaps_slot *heaps_sort_limit = 0;
+static int heaps_sort_limit_used = 0;
+static int *lazy_brancer = 0;
+static int heap_update = 0;
+#define WHITE 0
+#define BLACK 1
+#define NORMAL_SWEEP_LIMIT 1000000
+//#define NORMAL_SWEEP_LIMIT 0
+#define GC_STATE_NORMAL 0
+#define GC_STATE_LAZY_SWEEP 1
+
 #define HEAPS_INCREMENT 10
 static struct heaps_slot {
     void *membase;
@@ -148,6 +169,7 @@
 } *heaps;
 static int heaps_length = 0;
 static int heaps_used   = 0;
+static int heaps_objs = 0;
 
 #define HEAP_MIN_SLOTS 10000
 static int heap_slots = HEAP_MIN_SLOTS;
@@ -181,6 +203,7 @@
 static void run_final(VALUE obj);
 static int garbage_collect(void);
 
+
 void
 rb_global_variable(VALUE *var)
 {
@@ -435,6 +458,12 @@
 		p = heaps = (struct heaps_slot *)malloc(length);
 	    });
 	if (p == 0) rb_memerror();
+	if (!heaps_sort_limit)
+	    heaps_sort_limit = malloc(length);
+	else
+	    heaps_sort_limit = realloc(heaps_sort_limit, length);
+	if (!heaps_sort_limit)
+	    rb_memerror();
     }
 
     for (;;) {
@@ -484,13 +513,24 @@
     heap_slots *= 1.8;
 
     while (p < pend) {
+	p->color = WHITE;
 	p->as.free.flags = 0;
 	p->as.free.next = freelist;
 	freelist = p;
 	p++;
     }
+
+    //lazy_sweep
+    int i = 0;
+    heaps_objs = 0;
+    for (i = 0; i < heaps_used; i++) {
+	heaps_objs += heaps[i].limit;
+    }
+    heaps_sort_limit[heaps_sort_limit_used] = heaps[hi];
+    heaps_sort_limit_used++;
+    heap_update = 1;
+
 }
-
 #define RANY(o) ((RVALUE*)(o))
 
 static VALUE
@@ -504,10 +544,25 @@
 	}
     }
 
+    //lazy sweep
+    if (lazy_lease_limit) {
+	if (!lazy_lease_rest) {
+	    lazy_lease_rest = lazy_lease_limit;
+	    if (!garbage_collect()) {
+		rb_memerror();
+	    }
+	}
+	lazy_lease_rest--;
+    }
+    
     obj = (VALUE)freelist;
     freelist = freelist->as.free.next;
 
+    /* flags keep */
+    char c = RANY(obj)->color;
     MEMZERO((void*)obj, RVALUE, 1);
+    RANY(obj)->color = c;
+
 #ifdef GC_DEBUG
     RANY(obj)->file = rb_sourcefile();
     RANY(obj)->line = rb_sourceline();
@@ -528,6 +583,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();
@@ -545,6 +601,7 @@
 
     if (v) {
 	RBASIC(v)->flags = 0;
+	RANY(v)->color = WHITE;
 	th->value_cache_ptr++;
     }
     else {
@@ -716,8 +773,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((VALUE)p, 0);
 	    }
 	    p++;
@@ -871,8 +928,8 @@
     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;
 
     if (lev > GC_LEVEL_MAX || (lev == 0 && ruby_stack_check())) {
 	if (!mark_stack_overflow) {
@@ -905,9 +962,9 @@
   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;
 
   marking:
     if (FL_TEST(obj, FL_EXIVAR)) {
@@ -1099,8 +1156,8 @@
 
       case T_OBJECT:
         {
-            long i, len = ROBJECT_NUMIV(obj);
-	    VALUE *ptr = ROBJECT_IVPTR(obj);
+	     long i, len = ROBJECT_NUMIV(obj);
+ 	    VALUE *ptr = ROBJECT_IVPTR(obj);
             for (i  = 0; i < len; i++) {
 		gc_mark(*ptr++, lev);
             }
@@ -1163,6 +1220,7 @@
 	run_final((VALUE)p);
 	if (!FL_TEST(p, FL_SINGLETON)) { /* not freeing page */
             VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
+	    p->color = WHITE;
 	    p->as.free.flags = 0;
 	    p->as.free.next = freelist;
 	    freelist = p;
@@ -1222,7 +1280,7 @@
 
 	p = heaps[i].slot; pend = p + heaps[i].limit;
 	while (p < pend) {
-	    if (!(p->as.basic.flags & FL_MARK)) {
+	    if (p->color != BLACK) {
 		if (p->as.basic.flags) {
 		    obj_free((VALUE)p);
 		}
@@ -1233,6 +1291,7 @@
 		}
 		else {
                     VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
+		    p->color = WHITE;
 		    p->as.free.flags = 0;
 		    p->as.free.next = freelist;
 		    freelist = p;
@@ -1244,7 +1303,7 @@
 		/* do nothing remain marked */
 	    }
 	    else {
-		RBASIC(p)->flags &= ~FL_MARK;
+		p->color = WHITE;
 		live++;
 	    }
 	    p++;
@@ -1280,11 +1339,150 @@
     free_unused_heaps();
 }
 
+static void
+init_lazy_sweep(void) {
+    int i, e, n = 0;
+
+    if (heaps_sort_limit_used > heaps_used) {
+	for (i = 0; i < heaps_sort_limit_used; i++) {
+	    if (!heaps_sort_limit[i].limit) {
+		MEMMOVE(&heaps_sort_limit[i+1], &heaps_sort_limit[i], struct heaps_slot, heaps_sort_limit_used-i-1);
+		heaps_sort_limit_used--;
+	    heap_update = 1;
+	    }
+	}
+    }
+    
+    if (!lazy_brancer)
+	lazy_brancer = malloc(sizeof(int)*heaps_length);
+    else if (heaps_used >= heaps_length)
+	lazy_brancer = realloc(lazy_brancer, sizeof(int) * heaps_length);
+    if (!lazy_brancer)
+	rb_memerror();
+	
+	if(heap_update) {
+    for (i = 0; i < heaps_sort_limit_used; i++) {
+	e = heaps_sort_limit_used - n - 1;
+	lazy_brancer[i] = n;
+	if (n >= e)
+	    break;
+	lazy_brancer[++i] = e;
+	n++;
+    }
+		heap_update = 0;
+	}
+
+    sweeping_slot = 0;
+    end_sweep_slot = heaps_sort_limit_used;
+    sweep_time = heaps_sort_limit_used * 0.25;
+    if (!sweep_time) sweep_time = 1;
+
+    gc_state = GC_STATE_LAZY_SWEEP;
+}
+
+static void
+gc_lazy_sweep(void) {
+    RVALUE *p, *pend, *final_list;
+    int freed = 0, i =0, free_min = 0;
+    unsigned long live = 0;
+
+    if (gc_state == GC_STATE_NORMAL) {
+	init_lazy_sweep();
+	if (source_filenames)
+	    st_foreach(source_filenames, sweep_source_filename, 0);
+	if (freelist) {
+	    during_gc = 0;
+	    return;
+	}
+    }
+    
+    final_list = deferred_final_list;
+    deferred_final_list = 0;
+
+    for (i = 0; i < sweep_time; i++) {
+	int n = 0;
+	int b = lazy_brancer[sweeping_slot];
+	RVALUE *free = freelist;
+	RVALUE *final = final_list;
+
+	p = heaps_sort_limit[b].slot; pend = p + heaps_sort_limit[b].limit;
+	while (p < pend) {
+	    if (p->color != BLACK) {
+		if (RBASIC(p)->flags) {
+		    obj_free((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 if (RBASIC(p)->flags) {
+		    VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
+		    p->color = WHITE;
+		    p->as.free.flags = 0;
+		    p->as.free.next = freelist;
+		    freelist = p;
+		}
+		n++;
+	    }
+	    else if (RBASIC(p)->flags != FL_MARK) {
+		p->color = WHITE;
+		live++;
+	    }
+	    p++;
+	}
+	
+	if (n == heaps_sort_limit[b].limit) {
+	    RVALUE *pp;
+	    heaps_sort_limit[b].limit = 0;
+	    for (pp = final_list; pp != final; pp = pp->as.free.next) p->as.free.flags |= FL_SINGLETON;
+	    freelist = free;
+	}
+	else {
+	    freed += n;
+	}
+	sweeping_slot++;
+	if (sweeping_slot >= end_sweep_slot)
+	    break;
+    }
+
+    if (malloc_increase > malloc_limit) {
+ 	malloc_limit += (malloc_increase - malloc_limit) * ((double)live / (live + freed) / end_sweep_slot);
+ 	if (malloc_limit < GC_MALLOC_LIMIT) malloc_limit = GC_MALLOC_LIMIT;
+    }
+	
+    if (!freelist) {
+	heap_slots = heap_slots * 0.7;
+	add_heap();
+	lazy_lease_limit = heaps_sort_limit[heaps_sort_limit_used-1].limit * 0.20;
+	lazy_lease_rest = lazy_lease_limit;
+    }
+
+    if (sweeping_slot >= end_sweep_slot) { 
+	end_sweep_slot = 0;
+	sweeping_slot = 0;
+    	malloc_increase = 0;
+	gc_state = GC_STATE_NORMAL;
+    }
+
+    during_gc = 0;
+
+    /* clear finalization list */
+    if (final_list) {
+    	deferred_final_list = final_list;
+    	return;
+    }
+	
+    if (!sweeping_slot) free_unused_heaps();
+}
+
 void
 rb_gc_force_recycle(VALUE p)
 {
     VALGRIND_MAKE_MEM_UNDEFINED((void*)p, sizeof(RVALUE));
     RANY(p)->as.free.flags = 0;
+    if (!(gc_state == GC_STATE_LAZY_SWEEP && RANY(p)->color == BLACK))
+    	RANY(p)->color = WHITE;
     RANY(p)->as.free.next = freelist;
     freelist = RANY(p);
 }
@@ -1493,25 +1691,23 @@
 
 void rb_gc_mark_encodings(void);
 
-static int
-garbage_collect(void)
+static void
+rb_mark_freelist(void)
 {
-    struct gc_list *list;
-    rb_thread_t *th = GET_THREAD();
+    RVALUE *p = freelist;
+    while(p) {
+	p->color = BLACK;
+	p = p->as.free.next;
+    }
+}
 
-    if (GC_NOTIFY) printf("start garbage_collect()\n");
 
-    if (!heaps) {
-	return Qfalse;
-    }
 
-    if (dont_gc || during_gc) {
-	if (!freelist) {
-	    add_heap();
-	}
-	return Qtrue;
-    }
-    during_gc++;
+static void
+gc_marks(void)
+{
+    struct gc_list *list;
+    rb_thread_t *th = GET_THREAD();
 
     SET_STACK_END;
 
@@ -1554,11 +1750,73 @@
 	}
     }
 
+}
+
+static int 
+mark_and_sweep(void)
+{
+    if (!heaps) {
+	return Qfalse;
+    }
+
+    if (dont_gc || during_gc) {
+	if (!freelist) {
+	    add_heap();
+	}
+	return Qtrue;
+    }
+    during_gc++;
+
+    if (gc_state == GC_STATE_LAZY_SWEEP) {
+	gc_state = GC_STATE_NORMAL;
+	lazy_lease_limit = 0;
+	lazy_lease_rest = 0;
+    }    
+
+    gc_marks();
+	
     gc_sweep();
-    if (GC_NOTIFY) printf("end garbage_collect()\n");
+	
     return Qtrue;
 }
 
+static int
+mark_and_lazy_sweep(void)
+{
+
+    if (!heaps) {
+	return Qfalse;
+    }
+
+    if (dont_gc || during_gc) {
+	if (!freelist) {
+	    add_heap();
+	}
+	return Qtrue;
+    }
+    during_gc++;
+    if (gc_state == GC_STATE_NORMAL) {
+	gc_marks();
+	if (freelist)
+	    rb_mark_freelist();
+    }
+	
+    gc_lazy_sweep();
+	
+    return Qtrue;
+}
+
+static int
+garbage_collect(void)
+{
+    if (heaps_objs > NORMAL_SWEEP_LIMIT)
+	return mark_and_lazy_sweep();
+
+    return mark_and_sweep();
+}
+
+
+
 int
 rb_garbage_collect(void)
 {
@@ -2017,7 +2275,7 @@
     if (p) {
 	finalize_list(p);
     }
-    free_unused_heaps();
+    if(!sweeping_slot) free_unused_heaps();
     during_gc = 0;
 }
 
@@ -2054,6 +2312,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)));
 		}
@@ -2065,6 +2324,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));
 		}
 	    }

Thread

Prev Next

In This Thread

Prev Next

[#33946] Symbol#inspect should use rb_str_inspect — sheepman <sheepman@...>

[#33947] Ruby 1.9.0-1 snapshot released — Yukihiro Matsumoto <matz@...>

[#33948] Schedule for the 1.8.7 release — "Akinori MUSHA" <knu@...>

[#33950] Ruby 1.9.0-1 build failure: error: `r15660' undeclared — "Hiroshi Ichikawa" <gimite@...>

[#33952] Float('1__1') — Tadayoshi Funaba <tadf@...>

[#33954] Mac OS X 10.5.2でruby-1.9.0-1のmake testが失敗 — 高尾 宏治 <kouji@...>

[#33955] --encoding affects script encoding — sheepman <sheepman@...>

[#33962] Ruby1.9.0でのインタプリタ組み込みについての質問 — Masayuki Yamaguchi <Yamaguchi.Masayuki@...>

[#33966] Re: [ruby-cvs:22881] Ruby:r15644 (trunk): * test/ruby/test_m17n_comb.rb (TestM17NComb::test_str_chomp): test — Tanaka Akira <akr@...>

[#33967] $SAFE=1でLoadErrorではなくInsecure operationになる — "Ken Date" <itacchi@...>

[#33972] なぜ transcode.c の transcode_loop で from_utf8 が特別扱い — Martin Duerst <duerst@...>

[#33974] Test::Unit::Collector::Dirがtest_*.rb以外集めてくれない — "Ken Date" <itacchi@...>

[#33983] Re: [ruby-cvs:22913] Re: Ruby:r15674 (trunk): * gc.c (add_heap): sort heaps array in ascending order to use — Yukihiro Matsumoto <matz@...>

[#33989] Hash#compare_by_identity breaks commutativity of Hash#== — Tanaka Akira <akr@...>

[#33991] Maybe IRB bug!! by 09 — Tanaka Akira <akr@...>

[#33992] debug.rb:221:in `debug_command': undefined method `callcc' for #<DEBUGGER__::Context:0xb7a85914> (NoMethodError) — Tanaka Akira <akr@...>

[#33993] Re: [ruby-cvs:22935] Ruby:r15695 (trunk): * string.c (is_utf8_lead_byte, count_utf8_lead_bytes_with_ulong): — Tanaka Akira <akr@...>

[#33994] printf "[%08f]\n", 0.0/0.0 — Tanaka Akira <akr@...>

[#33996] No definition for sym_succ など — Martin Duerst <duerst@...>

[#34000] --program-suffix option of configure.bat(mswin32) — KIMURA Koichi <kimura.koichi@...>

[#34002] sprintf("% e", Inf) — Tanaka Akira <akr@...>

[#34005] Array#slice! may be too slow and allocate memory too much — "Yusuke ENDOH" <mame@...>

[#34006] 11.divmod(3.5) — Tanaka Akira <akr@...>

[#34008] local_variables contains strings — Tanaka Akira <akr@...>

[#34010] RUBY_*定数のencoding — Kazuhiro NISHIYAMA <zn@...>

[#34011] Should --verbose be equal to -v ? — Yugui <yugui@...>

[#34019] DelegateClassのバックトレース — "GO Noguchi" <gonoguti@...>

[#34020] MurmurHash problem — Nobuyoshi Nakada <nobu@...>

[#34021] singleton class extended by a module with module_function — Tanaka Akira <akr@...>

[#34022] patch of lazy sweep gc — authorNari <authornari@...>

[#34030] uint32_t — KIMURA Koichi <kimura.koichi@...>

[#34033] ruby coding guideline — "NARUSE, Yui" <naruse@...>

[#34037] Ruby performance gains on SPARC — Yukihiro Matsumoto <matz@...>

[#34042] IOはこれからもEnumerableなのか — rubikitch@...

[#34048] CGI::Cookie.new を高速化するバッチ — "Makoto Kuwata" <kwa@...>

[#34052] IO should provide #each_char and #chars — Yugui <yugui@...>

[#34059] putsでSEGV — rubikitch@...

[#34066] Bignum#div — Tadayoshi Funaba <tadf@...>

[#34067] Array#take,take_while,drop,drop_whlie — "Yusuke ENDOH" <mame@...>

[#34068] lgamma_r requires _REENTRANT on Solaris — "Yusuke ENDOH" <mame@...>

[#34071] procを組み合わせた再帰呼び出しで例外が投げられない — wanabe <s.wanabe@...>

[#34072] rb_memsearch optimization — "NARUSE, Yui" <naruse@...>

[#34077] 異なるエンコーディングだと同じバイト列でも==にならない件 — rubikitch@...

[#34086] extend spawn to change attributes of child process. — Tanaka Akira <akr@...>

[#34093] 拡張ライブラリ初期化中でのmodule_eval — Kouhei Sutou <kou@...>

[#34094] tempfile.unlink 後に tempfile.close — SATOH Fumiyasu <fumiyas@...>

[#34095] (再送) Cygwin で Resolv.getaddress が失敗する — Kouhei Yanagita <yanagi@...>

[#34100] delegate Kernel#{gets,readline,readlines} to ARGF — Nobuyoshi Nakada <nobu@...>

[#34105] rational.rb, complex.rb and mathn.rb — Tadayoshi Funaba <tadf@...>

[#34109] LP64: date.rb:321:in `convert': integer 86400000000000 too big to convert to `int' (RangeError) — Tanaka Akira <akr@...>

[#34112] Module#define_methodがprivateなわけ — rubikitch@...

[#34114] Is 'Class.new(Class)' valid? — rucila <rucila@...>

[#34116] Improving Fixnum#gcd(Fixnum) — "Akinori MUSHA" <knu@...>

[#34117] backporting features from 1.9 to 1.8 — "Akinori MUSHA" <knu@...>

[#34119] Process.daemon kills other threads — Tanaka Akira <akr@...>

[#34122] --disable=all --enable=gems — Kazuhiro NISHIYAMA <zn@...>

[#34128] enumerator with certain built-in methods dumps core — "Yusuke ENDOH" <mame@...>

[#34136] thread.c (fastthread)の状況 — Daigo Moriwaki <techml@...>

[#34144] [質問２点] C からの定数参照 & thread switching コストの低減 — Hidetoshi NAGAI <nagai@...>

[#34150] sigsetjmp significantly slower on OSX. — Yukihiro Matsumoto <matz@...>

[#34158] Complex組み込み — Masahiro TANAKA <masa16.tanaka@...>

[#34159] ruby-trunk Marshal.dump bug — nagachika <rucila@...>

[#34162] GC heap size less patch — authorNari <authornari@...>

[#34163] Array#shift/unshift の高速化 — wanabe <s.wanabe@...>

[#34180] メソッドにクラスを定義させるとprivateになる？ — rubikitch@...

[#34184] Re: [ruby-cvs:23097] Ruby:r15858 (trunk): * io.c: IO.copy_stream implemented. — "U.Nakamura" <usa@...>

[#34189] Re: [ruby-cvs:23106] Re: Ruby:r15866 (trunk): * numeric.c (num_quo): should convert its operand to Rational. — Tadayoshi Funaba <tadf@...>

[#34191] Object#singleton_class — rubikitch@...

[ruby-dev:34022] patch of lazy sweep gc

Attachments (1)

Thread

In This Thread

[#33954] Mac OS X 10.5.2でruby-1.9.0-1のmake testが失敗 — 高尾宏治 <kouji@...>

[#34072] rb_memsearch　optimization — "NARUSE, Yui" <naruse@...>