Re: [Chicken-users] Re: Better algorithm for growing hash tables

[Nelson Castillo]

On 8/1/05, Ed Watkeys <address@hidden> wrote:
> 
> On Aug 1, 2005, at 4:52 PM, Alejandro Forero Cuervo wrote:
> 
> >> That explains Chicken's pathetic performance in the spellcheck
> >> benchmark in the alioth shootout (
> >> http://shootout.alioth.debian.org/benchmark.php?
> >> test=spellcheck&lang=all&sort=fullcpu
> >> ) - dead last, at 35.4 seconds, compared to 16.9 seconds for the next
> >> slowest language.  It's writing and reading ~39000 entries into a
> >> 10000 size hash table, with this dumb algorithm.
> >>
> >
> > That's probably right.  I suppose currently it performs (39000 -
> > 500) / 101 = 337 resizes, whereas with the change it would resize
> > the table from 10000 to 39709 and then to 79423, just 3 resizes. :)
> 
> _The Practice of Programming_ (Kernighan & Pike) deals with a
> situation analgous to this; they grow storage for a string by powers
> of two. This works well because it heavily tests the algorithm --
> from 1 to 2 to 4 to 8... -- but also causes a grow for every log n
> inserts i.e. rarely.

Yup. But you really should use prime numbers for hash tables.