From ... From: Erik Naggum Subject: Re: hash tables with a copying memory gc Date: 1999/11/19 Message-ID: <3151988077875646@naggum.no>#1/1 X-Deja-AN: 550452274 References: mail-copies-to: never X-Complaints-To: newsmaster@eunet.no X-Trace: oslo-nntp.eunet.no 942999295 15777 193.71.66.49 (19 Nov 1999 08:14:55 GMT) Organization: Naggum Software; +47 8800 8879 or +1 510 435 8604; fax: +47 2210 9077; http://www.naggum.no NNTP-Posting-Date: 19 Nov 1999 08:14:55 GMT Newsgroups: comp.lang.lisp * "David Betz" | 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.