[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Re: Hash Tables and GC]
- To: ELIOT@cs.umass.edu
- Subject: [Re: Hash Tables and GC]
- From: firstname.lastname@example.org
- Date: Thu, 04 Aug 88 14:55:07 PDT
- Cc: email@example.com
- In-reply-to: ELIOT@cs.umass.edu's message of 2795519880
- Posted-date: Thu, 04 Aug 88 14:55:07 PDT
- Sender: firstname.lastname@example.org
Not only does the GC have to prove that the reference
count for BOTH key and VALUE is one, but the GC also has to prove
that there are no other objects, x, such that:
(<Equality-Predicate> x KEY)
There is no particular concern about whether other pointers to the VALUE
exist; only pointers to members of the KEY's equivalence class. Look at
the problem not as one of GC, but as one of "when is it safe to remove
an entry from a hash table?" [once it has been removed that may make
the value garbage (reduce its reference count to 0)]. It is certainly
SAFE to remove a set of entries Ei= [Ki Vi] if, once the Ei are removed,
there is no way to construct a reference to an object equivalent to any Ki.
If there are references to KEYS from inside VALUES, some schemes may fail
to remove entries that are safe to remove, but this is just like reference
count GCers that fail to reclaim certain circular structures even though
they are garbage. You lose space, but don't get incorrect results.
Even EQ hash tables have problems, in any implementation with
immediate representations for objects. For example the key 57236
(a fixnum) may not be interned and therefor there is no way to tell
how many copies of it exist.
Considering the paragraph of CLTL beginning on pg 77 and continuing to the top
of pg 78, entries in EQ hash tables having integers or characters as the
KEY can serve NO PORTABLE purpose except for usage through
MAPHASH and/or HASH-TABLE-COUNT.