Re: rfi: hash set

[Noah Lavine <noah.b.lavine@gmail.com>]

Hello,

I started looking into implementing this, and I ran into something
strange that I'd like clarification on. Am I correct in saying that
currently, hash tables can only shrink by one size index when they are
rehashed?

I think this because of hashtab.c, line 293. This is a part of
scm_i_rehash which looks like this:

 281       /* rehashing is not triggered when i <= min_size */
 290       i = SCM_HASHTABLE (table)->size_index;
 291       do
 292         --i;
 293       while (i > SCM_HASHTABLE (table)->min_size_index
 294              && SCM_HASHTABLE_N_ITEMS (table) < hashtable_size[i] / 4);

The i variable is an int representing the size of the new hash table.
It is an index into hashtable_size, an array of allowed hashtable
sizes. So i will be decremented until it represents a reasonable size
for the table.

However, i is also bounded by the table's min_size_index. Here's the
thing: based on grepping through this file, it seems that
min_size_index is set when a table is first made, to the initial size
index of the table, and never changes. Therefore, any i that
represents a shrink of the table will be <= min_size_index, so the
while's condition will always fail, so the loop can only run once, no
matter how few items are in the hash table, so i will always be the
old size_index - 1.

(This code path is only run in case of a shrink, not when a table
needs to grow.)

Is that right?
Noah

On Wed, Jan 5, 2011 at 10:56 PM, Andy Wingo <wingo@pobox.com> wrote:
> Hello,
>
> Currently the symbol table takes up twice as much memory as it needs to,
> because it is a hash table instead of a set. (The difference being that
> the buckets in a set don't need to be pairs.)
>
> We don't actually have a good set data type implementation, and I'm sure
> people have opinions about this, so if anyone has the time, an
> implementation would be appreciated. Name it hashset.[ch] and make sure
> it handles the weak reference case.
>
> Thanks! :) (Hey, it's worth a try :)
>
> Andy
> --
> http://wingolog.org/
>
>