[Haskell-cafe] Optimizing hash array mapped tries

[Edward Z. Yang]

Hey guys, an update!

It turns out, Clojure is using mutation under the hood during its
initial data structure generation to make populating the hash-map
blazingly fast.  When I force it to use the purely functional
interface, the performance is much closer to Haskell's.

            Haskell     Clojure
    128K    0.56s       0.33s
    256K    1.20s       0.84s
    512K    2.62s       2.80s

There's a large amount of variance in the Java samples, as HotSpot
kicks in; they appear to start off with identical performance and
then the Clojure implementation steadily performs better as the JVM
optimizes away.

I'd be really curious about techniques that permit mutation during
the construction of functional datastructures; this seems like a cool
way to get fast performance w/o giving up any of the benefits of
immutability.  Unfortunately, my (admittedly short) experiments in
this domain ran up against the difficulty that vector didn't let me
unsafely freeze its mutable version. :-)

Cheers,
Edward