Hello, everyone.

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 .