Re: symbols hash table

[Dirk Herrmann]

On Tue, 23 Jan 2001, Martin Grabmueller wrote:

> > 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.
> 
> Have you thought about storing a special value into the table when
> deleting symbols, so that an insertion operation will use a freed slot
> (with that special value) for entering a new symbol, but a search will
> deal with that slot as if it was in use?  That would be a solution to
> the problem you mentioned above.

No, I have not thought about that idea :-)  It's clever.  Since the
proposed hashing technique is probably the fastest, it would make sense to
implement it.  The only disadvantage is, that it is a special solution for
that specific problem, while the solution that I have proposed would be of
more general use (but slower).  Are there any estimates about how much
guile's overall performance would be improved by using one version or the
other?

Best regards,
Dirk Herrmann