symbols hash table

[Dirk Herrmann]

On 17 Dec 2000 19:45:22 +0100 Mikael Djurfeldt wrote:

> Dirk Herrmann <address@hidden> writes:
>
> > BTW:  an optimization would be to replace the weak-key hash table for the
> > symbols by some specialized hash table that does not store (<symbol> . #f)
> > pairs, but only weak symbols.  Maybe it could also be auto-resizing, but I
> > am not sure about that.
>
> Yes, this is exactly the kinds of things I was referring to when
> talking about "representation".  The fastest thing we could possibly
> have is a weak vector (with resizing).  (A hash miss simply means
> checking next entry (increment by one), and next etc until hit or free
> slot is found, or up to a limit where the table needs growth and
> rehashing.  More advanced hash techniques exist if this causes the
> table to grow too large.)

I have thought about such a representation, but I think that it is
probably not the best solution for our case:  The hash table for symbols
should be a weak hash table.  That means, that entries from that table may
disappear.  In other words, when looking for a symbol in the hash table,
the fact that you stumble across an empty slot does not mean that you can
finish your search:  The symbol you are looking for may have been added to
the hash table when the slot was in use.

Thus, when looking for a symbol you will always have to search a
predefined number of slots before you can be sure that a symbol is not
contained in the table.  Alternatively, the code that removes unreferenced
symbols from the table during gc will have to do some clever rehashing.
However, this will complicate things a lot since you must handle the case
that the hash table was in the process of being resized just when the gc
was issued.

Therefore, I think that a better representation would be a vector where
each slot holds a list of symbols, which are stored weakly.  Currently,
there is no such type of a weak vector in guile, but it should be easy to
extend the code in weaks.[ch] to also provide such a "weak-hash-set".  
The existence of such a weak hash set could also be of use in other parts
of guile:  I remember to have used a weak-key hash table as a workaround
instead to store environment observers weakly.

Compared to the current implementation of the symbol hash table, this will
already halven the number of cells required to store a given number of
symbols.

Best regards,
Dirk Herrmann