[Haskell-cafe] Optimizing hash array mapped tries

[Don Stewart]

ezyang:
> 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. :-)

Almost all the vector library generators fill a vector destructively,
before doing an unsafeFreeze.

Here's an example of filling a buffer with randoms,

   random g n = do
    v  <- GM.new n
    fill v 0
    G.unsafeFreeze v
      where
        fill v i
            | i < n = do
                x <- R.random g
                GM.unsafeWrite v i x
                fill v (i+1)
            | otherwise = return ()