Re: [MIT-Scheme-devel] make-eq-hash-table

[Joe Marshall]

On Sat, Dec 19, 2009 at 9:50 PM, Taylor R Campbell <address@hidden> wrote:
> After I changed the microcode to hold only weak references to interned
> symbols without global bindings, I noticed a number of problems with
> weak hash tables keyed by symbols.  The procedure MAKE-EQ-HASH-TABLE,
> counterintuitively to me, yields hash tables with only weak references
> to their keys.

If the only reference to a key is from within the hash table itself,
there is no need
to keep the entry in the table (no one can generate a new reference).

The exception is, of course, symbols.  Someone can always re-create a
symbol by interning a string.  You probably want to handle this by
strengthening symbols that happen to
be used as keys in hash tables.

> Many uses of MAKE-EQ-HASH-TABLE in MIT Scheme actually
> need key-strong hash tables, not key-weak hash tables, and after going
> through all the uses, I see that the problem is worse than I expected.
> Attached to this message is a summary of all sixty-two uses; here are
> two noteworthy statistics:
>
> - Only eleven, i.e. 17%, of the uses are obviously legitimate uses for
>  key-weak tables.
>
> - Thirteen of the uses are obviously incorrect and require key-strong
>  hash tables.  That is, more than 20% of the uses are bugs.
>
> At the very least, we should make sure that every use of hash tables
> correctly uses key-strong or key-weak hash tables.  However, I'd like
> to go a step further and change the semantics of MAKE-EQ-HASH-TABLE to
> yield strong hash tables, and add a separate MAKE-WEAK-EQ-HASH-TABLE
> which would behave as MAKE-EQ-HASH-TABLE does currently.
>
> I realize that MAKE-EQ-HASH-TABLE has yielded weak hash tables since
> 1993, and that its predecessor MAKE-OBJECT-HASH-TABLE has done so for
> even longer than that, but since even in MIT Scheme itself there are
> more incorrect uses of MAKE-EQ-HASH-TABLE than correct uses (and many
> more ambiguous uses where the intent is not clear), I think that it is
> dangerous to use the name MAKE-EQ-HASH-TABLE, or any name without the
> word `weak' in it, for a constructor of weak hash tables.
>
> If we made this change, existing code using MAKE-EQ-HASH-TABLE
> legitimately would exhibit space leaks only on new versions of Scheme.
> On the other hand, if we don't make this change, I think that more and
> more code will be written that accidentally uses weak hash tables
> where strong ones are at best intended or at worst needed, with subtle
> heisenbugs that show up depending on when garbage collection happens.
>
> Comments?

I think you should re-analyze things.

Ignoring the issue of weak symbols for the moment, there is no need to
have strong
references to the keys *unless* someone is depending upon walking the hash table
to find them.  (and they shouldn't)

Interned objects that can be recreated from their print names (that is symbols,
numbers, and other symbol-like things such as hostnames and/or URLs)
should be treated
as strong keys, but other objects that cannot be re-created (like cons
cells) should
not be strong.

The issues here are subtle, and they have been been gotten wrong many
times before.  However, I seem to recall talking about this with CPH and GJR
many years ago and I know they've given it some hard thought.

-- 
~jrm