[Haskell-cafe] Optimizing hash array mapped tries

[Edward Z. Yang]

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
    <<ghc: 410718260 bytes, 788 GCs, 19646424/46880276 avg/max bytes residency (9 samples),
      138M in use, 0.00 INIT (0.00 elapsed), 1.14 MUT (1.13 elapsed), 1.88 GC (2.00 elapsed) :ghc>>
    + 0:03.16
    ./IntMapTest 256000 +RTS -t 
    -710684043813
    <<ghc: 172126372 bytes, 329 GCs, 5552955/10483896 avg/max bytes residency (9 samples),
      31M in use, 0.00 INIT (0.00 elapsed), 0.51 MUT (0.51 elapsed), 0.62 GC (0.67 elapsed) :ghc>>
    + 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