At the University I am regularly working in Haskell to make certain exercises for the Advanced Algorithms and Datastructures cource. A few days ago, I came across Haskell’s Data.IntMap and Data.IntSet containers. These turn out to be ridiculously fast, running most operations (insert, find, delete, merge) in O(min(n, W)) time, where W is 32 for 32-bit machines and 64 for 64-bit machines.
This sounded very intriguing, since it goes against the understanding I had thus far about Hashmaps, which is that they are usually implemented as Red-Black trees (or similar auto-balancing binary trees) or Finger trees (I believe this is what Erlang’s maps are built on?), which take O(log(n)) time for these operations.
Haskell’s IntMap and IntSet, however, are built on so-called Patrizia trees, which store, in their nodes, the binary representation of (a part of the prefix of) the given key. The ‘drawback’ is of course that you cannot have keys larger than 2^W, but for many applications, this is perfectly fine.
The original paper called Fast Mergeable Integer Maps, written by Chris Okasaki and Andy Gill can be found here.
I don’t have the time in the near future to build an implementation of these in Elixir, but I think it would be an intriguing project, since I expect that maps/sets built on these kinds of trees will be faster than Elixir/Erlang’s built-in maps (even though the latter can be optimized by the BEAM), because of the speed that restricting the key type will bring.
I wanted to share this here because I expect that I’m not the only one who finds this interesting, and maybe someone would like to port this to Elixir .
I might have a go at it myself, but as I already have ten different packages on Hex that I try to maintain and on the side make long days at the university and at work, I expect to have little time to do so in the near future. So if someone else wants to hack away on this: please go ahead!
I would love to look at it, but i am a bit busy too. Additionaly, to really use Patrizia trees properly, i am affraid we would need to go down into NIFs. Otherwise you would need to use binaries to implement them.
I believe you can just use Integers and use Bitwise.band to check if the desired bit of the given node is 1 or 0, which would be faster than binaries (And hopefully the BEAM can optimize this to use word-sized ints).
.
