[plt-scheme] Weak hash tables

From: Bradd W. Szonye (bradd+plt at szonye.com)
Date: Thu Sep 9 17:04:43 EDT 2004

Bradd wrote:
>> You normally wouldn't use a hash table to create a trie -- it's a lot
>> more work and overhead than you really need.

Robby Findler wrote:
> Perhaps surprisingly, I had an opportunity to implement a trie a few
> months ago and populated it with a 264k word dictionary. I found it
> went about twice as fast if the children were held in a hash-table,
> rather than in 26-element array (in mzscheme and I heard from others
> that the same was true in Java). I was surprised ....

I'm surprised too! However, I'll concede that you can't really judge
performance without measuring it.

> ... but I guess it just reminds us that there are a lot of factors
> that go into performance. I have no idea what they are in this case,
> tho. :)

Sounds like it might be a hardware cache/swap effect -- perhaps the hash
table happened to hit hardware lines better than the array did?
Bradd W. Szonye

Posted on the users mailing list.