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 <wi...@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/ > >