[plt-scheme] A mystery: using immutable hashes slows my program down a lot

From: Eric Hanchrow (eric.hanchrow at gmail.com)
Date: Fri Dec 12 23:59:51 EST 2008

I have a fairly simple program that does lots of computation while
traversing a big list.  It constructs the list by first constructing a
hash table, then calling hash-map on it ... I rewote it a little to
replace the mutable hash with immutable ones -- and to my great
surprise, the program as a whole slowed down by a factor of three.
What's odder is that, as far as I can tell, the hash is unreferenced
as soon as we return from hash-map -- and that happens very quickly in
the life of the program; it's the subsequent computation, using the
list, that is slow.

Anyway, enough blather; you'll want to see what I'm talking about.
Here's the slower version that uses immutable hashes:

And here's the faster version that uses mutable hashes:

(Unfortunately both those links require a Javascript-enabled browser;
"wget" doesn't seem to work)

Unpack 'em and, in each, cd to the unpacked directory and type "make"
to see the program run and print a little timing report.  (You'll need
GNU Make, and of course mzscheme.)

The difference between the two versions is at

If you could help explain why the immutable-hash version is three
times slower than the other, I'd be grateful.  Thanks!

Posted on the users mailing list.