Re: Efficiency and flexibility of hash-tables

[Roland Orre <orre@nada.kth.se>]

On Mon, 2003-02-10 at 15:24, Greg Troxel wrote:
>   Maybe one could re-use the GLib code, they have resizing hash tables.
> 

Wouldn't glib's implementation cause gc problems? 

Today there are three different types of hash tables: vectors, weak hash
tables and double weak hash tables. The only real difference between 
them is how their content is handled by gc, "tag wise" they are close.

My idea (which I haven't revealed yet) about resizing hash tables may be
considered a little "dirty" but when thinking about it I don't really
see a problem with it.

My idea was to modify the routines 
scm_c_make_hash_table in hashtab.c,
scm_make_weak_key_hash_table and scm_make_weak_value_hash_table in 
weaks.c so they allocate three extra items in the mallocated block
but hides this to the gc by setting the actual vector length to the
ordinary one. These extra items will contain the actual size in
number of items stored in the table and current upper and lower
thresholds for resizing the table.

Then modify the routines:
scm_hash_fn_create_handle_x and scm_hash_fn_remove_x in hashtab.c
to do resizing when needed, using a table of prime numbers for next
and previous size.

The advantage with this solution is that it's minimalistic, i.e. all 
routines working with hash tables will behave exactly the same. Only
the routines changing the number of items in the table will be affected.

The reason why I don't see a problem with this solution is that the
free() routine uses information which is independent from guile's view
about the size of the allocated memory block.

The only disadvantage I see is the risk that someone are not using
the routine "make-hash-table" in their code. If they use "normal"
vectors as hash tables it may cause segmentation fault, but this is
not a serious one as I see it.

Comments?

	Best regards
	Roland Orre


> This prompted a few questions:
> 
>   Would it be reasonable for guile to depend on glib?
>   I wouldn't mind, but I suspect others would view this as a problem.
> 
>   If not, would a 'guile-glib' package that has interfaces to the glib
>   functions be appropriate.  The new guile-gobject might support this
>   already.
> 
>   Didn't Jay Glascoe have auto-resizing hash tables implemented before?
> 
> Using glib's implementation (in glib, not copying the code) really
> seems preferable, either natively in guile or via (possibly enhanced)
> guile-gobject.
> 
>         Greg Troxel <gdt@ir.bbn.com>




_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user