Lessons from Week One

Summer of Code is on for one week now. I have spent it more reading and thinking than coding but am much clearer about the design for Lush's new memory manager. As I said in my project proposal, Nickle's garbage collector is my primary model, but a few extra requirements force me do some things differently for Lush.

The first requirement is that the collector should utilize a second processor. Keith Packard suggested forking a child process to do the collection. The child would do the mark & sweep and send addresses of non-live heap objects back to the parent process via a pipe. The parent then does the actual reclamation (rebuilding of the free lists) in an incremental fashion (e.g., within the interpreter's idle function or as part of alloc). Creating a child process creates a lazy copy of the parent's address space (copy-on-write), and the cost is that of duplicating the parent's page tables and creating the child's task structure.

So far so good. Now Nickle's GC stores the mark bit just next to the memory object itself. This means that during mark and sweep, the GC needs to do memory writes for all live objects, which are scattered all over the heap. This would throw fork's low cost benefit out of the window. I therefore need to store the mark bits somewhere else, and compactly so in memory. Further, the GC needs to find the mark bit for a given object (address) quickly, or the mark phase will take forever. My solution is to store object address--GC data associations in a dense array, sort the array at the beginning of a collection cycle, and do binary search for the lookup.

Nickle's GC scheme allows very fast (constant time) access to the mark bit. My solution requires O(log n) time per lookup in an array with n addresses. It is a little ironic that utilizing a second processor requires doing much more work. It is quite possible that Nickle's scheme, using only one processor, does actually perform better in practice than the two-processor solution (however, I do not feel inclined to do the experiment and implement both schemes).

More on this later.