Re: Copy-on-write friendly garbage collector

[Hongli Lai <hongli@plan99.net>]

[-- Attachment #1: Type: text/plain, Size: 713 bytes --]

Daniel DeLorme wrote:
> I believe I managed to close the performance gap to only 6% slower than 
> the current implementation (but I must admit I have trouble getting 
> consistently reproducible benchmarks). The attached patch should be 
> added on top of the one in Matz' email.
> 
> -- 
> Daniel
> 

Great work Daniel. I don't measure the same amount of speedup that you 
claim in your email, but there is definitely a small speedup.

I've added some further further optimizations. 
find_position_in_bitfield() now uses bit operators instead of division 
and modulo operators. This should speed things up a little more.

The attached patch is created against Ruby 1.8, but it shows what I've 
exactly changed.

[-- Attachment #2: gc-optimizations.diff --]
[-- Type: text/x-patch, Size: 2554 bytes --]

diff --git a/gc.c b/gc.c
index cb18a79..3ba5ec5 100644
--- a/gc.c
+++ b/gc.c
@@ -1142,6 +1142,7 @@ gc_sweep()
     int i;
     unsigned long live = 0;
     unsigned long free_min = 0;
+    struct heaps_slot *heap;
 
     for (i = 0; i < heaps_used; i++) {
         free_min += heaps[i].limit;
@@ -1154,9 +1155,11 @@ gc_sweep()
 	/* should not reclaim nodes during compilation
            if yacc's semantic stack is not allocated on machine stack */
 	for (i = 0; i < heaps_used; i++) {
-	    p = heaps[i].slot; pend = p + heaps[i].limit;
+	    heap = &heaps[i];
+
+	    p = heap->slot; pend = heap->slotlimit;
 	    while (p < pend) {
-		if (!rb_mark_table_contains(p) && BUILTIN_TYPE(p) == T_NODE)
+		if (!rb_mark_table_heap_contains(heap, p) && BUILTIN_TYPE(p) == T_NODE)
 		    gc_mark((VALUE)p, 0);
 		p++;
 	    }
@@ -1184,7 +1187,7 @@ gc_sweep()
 		    obj_free((VALUE)p);
 		}
 		if (need_call_final && FL_TEST(p, FL_FINALIZE)) {
-		    rb_mark_table_add(p); /* remain marked */
+		    rb_mark_table_heap_add(heap, p); /* remain marked */
 		    p->as.free.next = final_list;
 		    final_list = p;
 		}
diff --git a/marktable.c b/marktable.c
index 7424633..412616f 100644
--- a/marktable.c
+++ b/marktable.c
@@ -34,10 +34,26 @@ find_position_in_bitfield(struct heaps_slot *hs, RVALUE *object,
                           unsigned int *bitfield_index, unsigned int *bitfield_offset)
 {
 	unsigned int index;
-
 	index = object - hs->slot;
-	*bitfield_index = index / (sizeof(int) * 8);
-	*bitfield_offset = index % (sizeof(int) * 8);
+	
+	/*
+	 * We use bit operators to calculate the position in the bit field, whenever possible.
+	 * This only works if sizeof(int) is a multiple of 2, but I don't know of any platform
+	 * on which that is not true.
+	 *
+	 * The INT_BITS_LOG macro's value must be equal to the base 2 logarithm of sizeof(int).
+	 */
+	#ifdef __i386__
+		#define INT_BITS_LOG 5
+	#endif
+	
+	#ifdef INT_BITS_LOG
+		*bitfield_index = index >> INT_BITS_LOG;
+		*bitfield_offset = index & ((1 << INT_BITS_LOG) - 1);
+	#else
+		*bitfield_index = index / (sizeof(int) * 8);
+		*bitfield_offset = index % (sizeof(int) * 8);
+	#endif
 }
 
 
@@ -81,6 +97,14 @@ rb_mark_table_add(RVALUE *object)
 	}
 }
 
+static inline void
+rb_mark_table_heap_add(struct heaps_slot *hs, RVALUE *object)
+{
+	unsigned int bitfield_index, bitfield_offset;
+	find_position_in_bitfield(hs, object, &bitfield_index, &bitfield_offset);
+	hs->marks[bitfield_index] |= (1 << bitfield_offset);
+}
+
 static inline int
 rb_mark_table_contains(RVALUE *object)
 {