[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Efficiency and flexibility of hash-tables
From: |
Roland Orre |
Subject: |
Re: Efficiency and flexibility of hash-tables |
Date: |
10 Feb 2003 16:00:42 +0100 |
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 <address@hidden>
- Re: Efficiency and flexibility of hash-tables, (continued)
- Re: Efficiency and flexibility of hash-tables, Joris van der Hoeven, 2003/02/08
- Re: Efficiency and flexibility of hash-tables, Roland Orre, 2003/02/08
- Re: Efficiency and flexibility of hash-tables, Joris van der Hoeven, 2003/02/08
- Re: Efficiency and flexibility of hash-tables, Mikael Djurfeldt, 2003/02/08
- Re: Efficiency and flexibility of hash-tables, Joris van der Hoeven, 2003/02/11
- Re: Efficiency and flexibility of hash-tables, Joris van der Hoeven, 2003/02/11
- Re: Efficiency and flexibility of hash-tables, Mikael Djurfeldt, 2003/02/11
- Re: Efficiency and flexibility of hash-tables, Roland Orre, 2003/02/08
- Re: Efficiency and flexibility of hash-tables, Andreas Rottmann, 2003/02/10
- Re: Efficiency and flexibility of hash-tables, Greg Troxel, 2003/02/10
- Re: Efficiency and flexibility of hash-tables,
Roland Orre <=
- Re: Efficiency and flexibility of hash-tables, Mikael Djurfeldt, 2003/02/10
- Re: Efficiency and flexibility of hash-tables, Mikael Djurfeldt, 2003/02/10
- Resizing hash tables in Guile, Mikael Djurfeldt, 2003/02/11
- Re: Resizing hash tables in Guile, Roland Orre, 2003/02/11
- Re: Resizing hash tables in Guile, Marius Vollmer, 2003/02/12
- Re: Resizing hash tables in Guile, Marius Vollmer, 2003/02/12
- Re: Resizing hash tables in Guile, Mikael Djurfeldt, 2003/02/12
- Re: Resizing hash tables in Guile, Roland Orre, 2003/02/12
- Re: Resizing hash tables in Guile, Mikael Djurfeldt, 2003/02/13
- Re: Resizing hash tables in Guile, Harvey J. Stein, 2003/02/13