|
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 (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/>
[Prev in Thread] | Current Thread | [Next in Thread] |