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

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Sat Dec 13 16:43:59 EST 2008

The lists that you get back from the different hash table
implementations are in different orders.

I changed both programs to return
 
    (sort result > #:key car)

instead of just `result', and the run times ended up about the same.
Sorting with `>' made both run fast, and sorting with `<' made both run
slow.

Matthew

At Fri, 12 Dec 2008 20:59:51 -0800, "Eric Hanchrow" wrote:
> 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:
> http://github.com/offby1/anagrams/tarball/99a7781001b4cebfcf8d91d0c254ffba70e81
> 20e
> 
> And here's the faster version that uses mutable hashes:
> http://github.com/offby1/anagrams/tarball/707635e63e8053705d898a364878b970eeb08
> 602
> 
> (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
> http://github.com/offby1/anagrams/commit/707635e63e8053705d898a364878b970eeb086
> 02
> 
> If you could help explain why the immutable-hash version is three
> times slower than the other, I'd be grateful.  Thanks!
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme


Posted on the users mailing list.