Tuning tries (IntSet, hashmap, bytestring-trie, etc.)
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-ex... 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-persistenthas... 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]].
On Sat, Jun 26, 2010 at 4:04 PM, Jim Apple
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-ex...
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-persistenthas...
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
participants (2)
-
Edward Kmett -
Jim Apple