Subject: Re: hash tables with a copying memory gc
From: Erik Naggum <erik@naggum.no>
Date: 1999/11/19
Newsgroups: comp.lang.lisp
Message-ID: <3151988077875646@naggum.no>

* "David Betz" <dbetz@mediaone.net>
| 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.