Making Ruby’s garbage collector copy-on-write friendly, part 4
My previous attempt implements the marking table with a set structure. In part 3, Dan42 said that I could use a bit field instead. The idea did occur to me in the past, but I thought it was infeasible because I thought the bit field will have to cover the entire process’s address space. After some thinking, I realized I was wrong. Thanks Dan42. 
Each heap_slot struct now has a bit field, which is used as marking table for objects inside that heap:
-
static struct heaps_slot {
-
void *membase;
-
RVALUE *slot;
-
int limit;
-
int *marks; // added this
-
int marks_size; // and this
-
} *heaps;
The previous marking table implementation had a large overhead: about 8 bytes per marked object. An object (RVALUE) is 20 bytes, so the overhead is 40% in the worst case! And that’s not counting the overhead used by the set structure’s bucket.
The new bit field implementation has a much smaller overhead:
(n / 8 ) / (n * 20) = n / (8 * n * 20) = 1 / (8 * 20) = 1 / 160 = 0.00625
where n is the number of objects on a heap. The bit field only has 0.6% overhead!! 
According to my benchmarks, garbage collection performance has improved by 60% compared to the previous implementation. It’s still 10%-20% slower than normal Ruby, but I think it’s acceptable.
I think a significant amount of time is spent on locating the heap (and thus the marking table bit field) that an object belongs to. Right now it performs a linear search on all heaps. That’s usually OK though. Each heap is 80% larger than the previous. Ruby on Rails fits in 6 heaps. I think the average application needs no more than 7 heaps. So in the average case, looking up the correct heap should take no more than 7 operations. But it still sucks, so next time I’ll investigate whether I can speed this up by sorting the heaps and using a binary search.
And I’m still not done. Running the garbage collector after a fork still makes a lot of pages dirty, and I still haven’t figured out why.
Anyway…
You can download the Ruby 1.8.6 patch here.
This is brought to you by blood, sweat and tears. I poked myself several times today wondering why my code crashes for mysterious reasons.
Koz said,
October 13, 2007 @ 10:51 pm
Thanks again for both a really interesting write-up and a REALLY useful patch. good luck tracking down the dirty pages!
Andrew said,
October 13, 2007 @ 11:57 pm
Thanks for putting all this effort into improving my favorite language/framework!
Roger Pack said,
October 22, 2007 @ 10:13 pm
You might consider a bloom filter to save even more space. Might be slower, tho. Hmm. Maybe every other time or something
I am very interested in this patch and may try to include it in some future enterprise ruby distros. Thank you so much for your work!
Hongli said,
October 22, 2007 @ 10:25 pm
No problem Roger, it was hard work but it was also a fun and educational experience.
Can you inform me when you decide to include my patch? I’m very interested in the usefulness of my patch for other people.
Unfortunately it is not possible to use bloom filters. The Ruby GC needs to be able to unmark objects, and removing items from a bloom filter is impossible. Refactoring the Ruby GC to not rely on unmarking is very hard.
Crystal said,
April 17, 2008 @ 1:33 am
Great job, this is going to be very useful for the new ruby site I am working on.