Optimizing Hash-Array Mapped Tries for Fast Immutable JVM Collections (2015) [pdf]

What is the real world use case for a HAMT data structure? Tree based associative arrays (like c++'s std::map) tend to have poor real world performance

chongli• 9 years ago

They are used to implement Clojure's immutable map and set structures. They are absolutely critical to the philosophy of the language.

FreakLegion2• 9 years ago

Depending on the use case, of course. Sometimes you need a structure that's both associative and ordered, for example, in which case std::map is handy.

masklinn3• 9 years ago

HAMT are not intrinsically ordered or sorted.

jcdavis2• 9 years ago

Immutable maps that have efficient update semantics

gshayban• 9 years ago

std::map and red-black trees are associative & sorted (by key); HAMTs are just plain associative. HAMTs have generally excellent performance: the typical implementations use 32-way branching, which allows for the top levels to be likely in cache.

The best thing about HAMTs is passing immutable ones around, which have free update costs and multi-thread safe. Clojure uses these to represent information that flows through a program. (By free update costs I mean: they are free enough to never rise to the programmer's attention. Obviously ops have costs.)

masklinn3• 9 years ago

More efficient (in both CPU and memory) immutable/persistent collections, which have the advantage that they're intrinsically thread-safe. They can also be used to implement lock-free concurrent maps (Ctrie)

Tree based associative arrays (like c++'s std::map) tend to have poor real world performance

That's something HAMT significantly improve upon. You're not going to get linear performances out of them but basic operations are generally O(ln N) where N is usually 32.

wfunction2• 9 years ago

Is there any research on the tradeoff between this kind of thread safety and the penalties incurred on the memory management side (specifically the fact that now you have far more heap allocations with immutable data and they have to synchronize too)?

mrkgnao• 9 years ago

Um, isn't that "constant-time in practice"? (Something like log-star.) Am I missing some matter of convention here?

dmichulke• 9 years ago

I think it's for an array of size N:

- O(1) - standard array (regardless of N)

- O(log_b(N)) - HAMT (b is 32 in clojure)

Since b is big, log_b(N) is quite small even for big numbers, e.g. log_32(2^20) = 4

didibus• 9 years ago

Does this add something that the Clojure implementation doesn't?

zokier• 9 years ago

So would this be a good structure to store the recently discussed password hash dump, basically a fixed set of 300 million SHA1-sums where the only interesting operation is checking if the sum is or is not contained in the set?

lord_jim• 9 years ago

It would probably be better to use a trie directly, maybe a radix trie or a b-trie.

Optimizing Hash-Array Mapped Tries for Fast Immutable JVM Collections (2015) [pdf]

Related Stories