Tuning tries (IntSet, hashmap, bytestring-trie, etc.)

Jim Apple jbapple+haskell-lib at gmail.com
Sat Jun 26 16:04:46 EDT 2010

Given the recent faster trie implementations (hooray!), I thought it
would be worth pointing out that a pretty thorough discussion of the
tradeoffs of functional trie design is available at


An experimental study of compression methods for functional tries
Jukka-Pekka Iivonen, Stefan Nilsson, and Matti Tikkanen

FWIW, apparently clojure uses a 32-ary hashtrie:


Because it is only binary, Data.IntSet is sometimes quite deep. All of
that pointer chasing makes Data.Set actually faster than Data.IntSet
for looking up 0 in the set 0:[2^i | i <-[0..30]].

More information about the Libraries mailing list