Optimizing hash array mapped tries
Hello all,
I spent this weekend attempting to impement Phil Bagwell's Hash
Array Mapped Tries in Haskell. You can view the fruits of this work at
this repository:
http://github.com/ezyang/hamt
Unfortunately, I'm getting pretty abysmal performance out of the
implementation I wrote, so I'm hoping to get some performance tuning
insights here.
My cost centers look about like this:
time% alloc%
i-Full-update HAMT 29.1 31.4
lookup' HAMT 13.7 4.3
main Main 12.8 19.7
subkey HAMT 11.5 10.0
i-Bitmap HAMT 9.4 12.0
i-Full HAMT 8.1 12.9
insert' HAMT 5.1 0.6
popCount PopCount 4.7 1.0
And my GC stats look like:
./HAMTTest 256000 +RTS -t
275576630962922
<
On Feb 22, 2010, at 02:15 , Edward Z. Yang wrote:
* i-Full-update essentially copies a 32-size vector, with a change to one element. I think I am getting brutally punished for this, in terms of both memory usage as well as runtime. What I'm curious is whether or not this is intrinsic to the algorithm, or if it's something special that GHC is doing.
IIRC this is intrinsic to the way GHC modifies and garbage-collects array modifications. There's been discussion on -cafe about it. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
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
Hello Edward, Wednesday, February 24, 2010, 10:32:59 PM, you wrote:
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. :-)
actually, this technique is already used in haskell. look into array library sources, search for freeze -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
Excerpts from Bulat Ziganshin's message of Wed Feb 24 14:48:53 -0500 2010:
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. :-)
actually, this technique is already used in haskell. look into array library sources, search for freeze
Yup, I'm aware of this. In fact, vector has thaw/freeze functions for itself, although it doesn't export them. I'd rather not have to reimplement vector just to get this unsafe mutation capability tough (and since the mutable array GC problem is not fixed for the version of GHC I'm on, I'd likely see no benefit either). What I thought was pretty neat about the Clojure approach was how easy they made it for you to jump into mutation-land and back out again: just a (transient) call and you're off to the races. As far as I can tell, you have to painstakingly write the specific operation you'd like to do via mutation out using all sorts of unsafe calls. Cheers, Edward
ezyang:
Excerpts from Bulat Ziganshin's message of Wed Feb 24 14:48:53 -0500 2010:
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. :-)
actually, this technique is already used in haskell. look into array library sources, search for freeze
Yup, I'm aware of this. In fact, vector has thaw/freeze functions for itself, although it doesn't export them. I'd rather not have to reimplement vector just to get this unsafe mutation capability tough (and since the mutable array GC problem is not fixed for the version of GHC I'm on, I'd likely see no benefit either).
These are exported from vector, though.
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 ()
Excerpts from Don Stewart's message of Wed Feb 24 16:13:18 -0500 2010:
Almost all the vector library generators fill a vector destructively, before doing an unsafeFreeze.
Alright. Is there a standard idiom for filling vectors pointing to vectors destructively, and then unsafely freezing all of them (as you would find in a recursively defined datastructure), or is this something simply not supported by the compiler at this time? Cheers, Edward
participants (4)
-
Brandon S. Allbery KF8NH -
Bulat Ziganshin -
Don Stewart -
Edward Z. Yang