Olivier Galibert <galibert(a)pobox.com&gt; writes: Ok.. As you are the last person to look in depth at it: How difficult would it be to implement a write barrier? That would make it possible to make a non-copying incremental garbage collector (for this you need 3 colors instead of 1 bit for the garbage collector). In the memory pool idea you would most likely look up the page the object is in the hash table to get an array and then use the offset in the page as an array. That way you could make the set-mark-bit operation independent of the type. i.e. [... woops.. I got carried away. code at end ] are using something like that? I was thinking of a "--naked" argument that makes it behaves like temacs. [here is that code (generalisation well_known bitarray code] /* set_object-color takes the adress of a lisp object and sets is garbage color. Currently only two colors are used: Marked and unmarked. */ /* One must make sure the tables exist for each page with objects to allow these functions to be fast and small */ /* Note I assume that all objects are at least 8 bytes big and aligned on multibles on 8. This holds true for all current lcrecord types. I propose to implement all other types as struct { lrecord_header type_desc; /* 32 bits */ *void real_data; } generic_lisp_object; This needs to be a union for ANSI. That means you can start by making the type pools pages of generic_lisp_object and the type check becomes page_type ( page_for_object(obj) ) == GENERIC && lheader_type (((generic_lisp_object *)obj)->type_desc) == the_type */ #define MINOBJALIGN 8 /* implementation for a typical 32 bit machine */ #define PAGESIZE 4096 #define OBJPERPAGE (PAGESIZE/MINOBJALIGN) #define PAGEMASK 0xFFFFF000 #define FULLWORD_MASK 0xFFFF typedef enum {umarked = 0, marked = 1} gccolors; #define NR_GCCOLBITS 1 #define GCCOL_MASK 0x00000001 #define GCCOLS_PER_WORD (32 / NR_GCCOLBITS) #define GC_WORDSPERPAGE (OBJPERPAGE / GCCOLS_PER_WORD) typedef unsigned int gccol_word_t typedef gccol_word_t[OBJPERPAGE] gccol_page_t static inline addr_t page_for_object (LispObject obj) { return ((addr_t) obj) / PAGESIZE; } static inline unsigned offset_for_object (LispObject obj) { return (((addr_t) obj) % PAGESIZE) / MINOBJALIGN; } static inline *gccol_page_t colorpage_for_page (addr_t page) { return (*gccol_page_t) hash_lookup (gccol_hashtable, (unsigned)page); } inline void set_object_gccolor (LispObj obj, gccolors color) { *gccol_page_t colors = colorpage_for_page (page_for_object (obj)); unsigned offset = offset_for_object(obj); unsigned shift = offset % GCCOLS_PER_WORD; *gccol_word word = &(colors[offset / GCCOLS_PER_WORD]); *word = (*word & ((FULLWORDMASK - GCCOL_MASK) << shift)) + color << shift; } inline gccolors get_object_gccolor (LispObj obj) { *gccol_page_t colors = colorpage_for_page (page_for_object (obj)); unsigned offset = offset_for_object(obj); unsigned shift = offset % GCCOLS_PER_WORD; gccol_word word = (colors[offset / GCCOLS_PER_WORD]); return (word >> shift) & GCCOL_MASK; }