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

[Ed Watkeys]

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.

Ed

--
Transmogrify, LLC * <http://xmog.com/>