[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Ed Watkeys
Subject: Re: [Chicken-users] Re: Better algorithm for growing hash tables
Date: Mon, 1 Aug 2005 18:23:36 -0400

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 ( 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.


Transmogrify, LLC * <>

reply via email to

[Prev in Thread] Current Thread [Next in Thread]