Subject: Re: hash tables with a copying memory gc From: Erik Naggum <firstname.lastname@example.org> Date: 1999/11/19 Newsgroups: comp.lang.lisp Message-ID: <email@example.com> * "David Betz" <firstname.lastname@example.org> | I'm sure this must be obvious but I'm having trouble with it anyway. I | have built a system based on a copying garbage collector and I would like | to add hash table support. In a system where objects never move an | obvious choice for a hash key is the address of the object. Of course, | this doesn't work with a copying collector since objects can potentially | move at every collection. How are hash tables usually implemented in a | copying environment? this applies to an EQ hash table as EQUAL and beyond cannot use the address of the object for the obvious reasons. so for some objects that are likely to be stored in an EQ hash table, the typical example being a symbol, you store a hash key with the object, but not in all objects. for the rest, you have to change the key in the hashtable as you move the objects. this may not be a huge cost, but if you have a generational garbage collector, the hashtable itself will at least become old enough not to move around all the time, and most of its keys probably will, too. | What is the good solution that I'm overlooking. you _could_ move the keys outside the standard garbage collector's reach -- it's not like they're going away unless the hashtable releases them, and you pretty much have full control over that. during the first GC after a key had been inserted in or deleted from the table, you would take care of this and would then not have to traverse the keys at all otherwise. if allocating memory that doesn't move around is bad for other reasons, the solutions I can think of only moves the problems out of hash tables and into other similar constructs, such as using indices into arrays instead of addresses, which doesn't really help any. perhaps memory that moves around less often (like only when it's full) is a good compromise, in which case we're talking about a sort of generational garbage collector if not the whole nine yards. #:Erik -- Attention Microsoft Shoppers! MS Monopoly Money 6.0 are now worthless.