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
<>
+ 0:03.16
./IntMapTest 256000 +RTS -t
-710684043813
<>
+ 0:01.18
IntMap is included for comparison. The HAMT does about x3-5 worse than
IntMap, and uses about x4 more memory (and gets correspondingly
penalized when garbage collection occurs).
My observations/suspicions are as such:
* 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.
* Bagwell suggests that each node in the Array-Mapped Trie should take
only two words. I think I'm losing another two words to storing
bounds information in vector, as well as the costs of boxing (though I
can't tell if GHC is boxing or not). I've done some playing around
with the data declaration, but it's current form seems to result in
the fastest implementation. I wonder if this is what is causing the
x4 ballooning of memory, or if it's something else. I haven't tried
rewriting the code to use GHC's arrays.
* Increasing the heap size seems to generally improve the performance
the HAMT; a 1G heap on a 512K sample set reduces the difference to
about x1.5-2 slower. It's hard to tell if the memory allocation
system is working for or against me.
What bothers me is even if I could magically wave away all GC time in
HAMT, it would only barely win against IntMap. Maybe the algorithm is
simply not as good as a good ole' Patricia Trie; but then again, maybe
not.
Comments and suggestions greatly appreciated.
Thanks,
Edward
