There's really only one thing that's holding me back from releasing the new hash-array mapped trie (HAMT) based implementation of unordered-containers, a fast implementation of
The current released version is implemented in terms of a patricia trie (also known as a radix tree) and it uses a linear time
union algorithm. The new version uses a naive implementation that simply calls
insert repeatedly. This makes
union 378% slower in the new implementation, on my main benchmark. Since I use HAMTs to implement
HashSet in addition to
HashMap, this is less than optimal.
My plan is to try to port the algorithm used on patricia tries to the HAMT implementation. I think this should be possible, due to both data structures being bit tries, but I haven't had time to try this myself. Any Haskellers out there who would like to try? If someone could implement a time complexity efficient version, I could then do the last bit of low-level optimization.
You can find the source of the HAMT-based implementation in the unordered-containers hamt branch on GitHub.
You'll also want to look at the
union implementation used in
The HAMT data structure itself is described in Ideal Hash Trees by Phil Bagwell. Note that we're using a persistent implementation, but most of the ideas (like removing empty nodes by using a bitmask) are still used.
Phil also told me that section 4.5 in A Generic Parallel Collection Framework might be useful in implementing