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

[Edward Kmett]

On Sat, Jun 26, 2010 at 4:04 PM, Jim Apple
<jbapple+haskell-lib at gmail.com<jbapple%2Bhaskell-lib at gmail.com>
> wrote:

> 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
>
>
> http://www.nada.kth.se/~snilsson/publications/Functional-trie-compression-experiment/
>
> An experimental study of compression methods for functional tries
> Jukka-Pekka Iivonen, Stefan Nilsson, and Matti Tikkanen
> WAAAPL'99
>
> FWIW, apparently clojure uses a 32-ary hashtrie:
>
> http://blog.ezyang.com/2010/03/the-case-of-the-hash-array-mapped-trie/
>
> http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice/
>
> 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]].
> _______________________________________________
>


To be fair that particular set is quite literally the worst case scenario
for a patricia trie.

-Edward Kmett
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100626/31abcd50/attachment.html