Subject: Re: Implementing Lisp in C?
From: rpw3@rpw3.org (Rob Warnock)
Date: Fri, 09 Apr 2004 05:59:02 -0500
Newsgroups: comp.lang.lisp
Message-ID: <7vednTOErMZrHOvd4p2dnA@speakeasy.net>
Ray Dillinger  <bear@sonic.net> wrote:
+---------------
| Jeff Dalton wrote:
| > Garbage collection can also be tricky, with obscure bugs.
| 
| Actually, a simple and reasonably efficient generational 
| garbage collector can be written in under a hundred lines 
| of C.  I know, because I wrote one. 
| 
| It requires a 3-word "header" for all boxed objects, though, 
| so even cons cells wind up occupying 5 32-bit words.
+---------------

If you allocate memory in "hunks", as the Train Algorithm does or
classic BiBoP (or a number of others), you can store the generation
information in the per-hunk metadata, and the per-object overhead
goes away. You should be able to get back to a 1-word header for
most heap objects, and if you use a low-bits pointer-tagging method
a small class of heap objects (cons cells are a obvious type to include)
will need *no* header [while the rest will still need a 1-word header].

Also note that card-marking software write barriers co-exist nicely
with "hunk" allocation (e.g., 256-byte cards in 64 KB hunks).


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607