Re: hash tables and GC

[Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>]

> There is also the rather similar "weak pointer" notion, which I believe is
> implemented in T.

Yes, T does have weak pointers.  They were also in RnRS for some n (as
object-hash and object-unhash).

I had thought that weak pointers might be sufficient, but then could
not see any nice way to use them to implement what I really wanted.

> The GC-able hash-table notion unnecessarily complicates the semantics by
> rolling in hash-table semantics when the real issue is with GC.

You're right, to some extent.  But hash tables are the way Common Lisp
provides efficient table-like mappings from keys to values.  You might
use something like a-lists instead, but only if a linear search is
fast enough.  You might implement a new facility of your own, but only
if you wanted it to be significantly different from hash tables.

My feeling is that a new kind of table-like mapping from keys to
values that didn't prevent keys from being collected would be so much
like hash tables that they might as well be hash tables.

Or, we could look at it the other way around.  A hash table is a
mapping from keys to values.  Why should a key be uncollectable just
because it was given a value in a mapping?  When the key is no longer
referenced (except in the mapping), why must it's entry remain?  Well,
in some cases you may want it to remain, but I suspect that those
cases are actually in the minority.

Perhaps a better proposal would be to change hash tables to always
have all entries be "temporary".  But then we have a problem with
backwards compatibility.

> Usually the association capacity of hashtables is unnecessary: instead
> of weak-hashing from A to B, allocate another slot in A to hold the weak
> pointer to B.

Weak pointers are more general.  You can put them in lists, etc., not
just in hash tables.  But: (1) What if you can't add a slot to A?  (2)
What if only a small number of objects of the same type as A need the
slot?  (3) What if what you need is a weak pointer to A, not to B?
That is what I actually want form the tables.  I want the keys to be
collectable.  (But, since a hash table is a mapping from keys to
values, values will be collectable when no longer needed for may key.)

To implement tables with weak pointers to the keys, you need access to
an EQ hash function and you need it to be an efficient hash that works
even when objects might be moved.  I suspect that would be very
difficult.  By having the tables built in, you do not need to provide
the hash function.

Then, once you have the tables, you can easily implement weak pointers
and put them in lists, etc.

-- Jeff