# Benchmarks of various trie implementations

**URL:** <https://discourse.haskell.org/t/benchmarks-of-various-trie-implementations/651>\
**Category:** Show and Tell\
**Created:** [May 5, 2019, 8:00am UTC](https://discourse.haskell.org/t/benchmarks-of-various-trie-implementations/651 "2019-05-05T08:00:34Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![ocramz](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ocramz/32/3713_2.png) [@ocramz](https://discourse.haskell.org/u/ocramz)\
**Post date:** [May 5, 2019, 8:00am UTC](https://discourse.haskell.org/t/benchmarks-of-various-trie-implementations/651/1 "2019-05-05T08:00:35Z")

</div>

> **[GitHub - ocramz/trie-perf: Performance shootout of various trie implementations](https://github.com/ocramz/trie-perf)**
>
> Performance shootout of various trie implementations - GitHub - ocramz/trie-perf: Performance shootout of various trie implementations

While studying various approaches to prefix trees (“tries”), I wrote a small memory and time benchmark of four implementations. Long story short, `generic-trie` seems to be the best choice, at least for a `lookup` - `fromList` pair, but I was curious to see how very diverse implementation techniques, notably one based on recursion schemes and another using an arrow type internally, lead to different space and time scaling behaviours.

I would love to hear any feedback regarding for example the use of randomized inputs ([trie-perf/Time.hs at master · ocramz/trie-perf · GitHub](https://github.com/ocramz/trie-perf/blob/master/bench/Time.hs#L21)), and any other improvements.

---

<div class="post-metadata">

**Author:** ![Drezil](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/drezil/32/4989_2.png) [@Drezil](https://discourse.haskell.org/u/Drezil)\
**Post date:** [May 6, 2019, 6:28am UTC](https://discourse.haskell.org/t/benchmarks-of-various-trie-implementations/651/2 "2019-05-06T06:28:40Z")

</div>

Small note: You use `discreteUniform letters` for data-generation. Have you considered other distributions? They could impact runtime a LOT - depending on the algorithm used to insert/lookup.  
For most applications the distribution is closely related to [https://en.wikipedia.org/wiki/Zipf's\_law](https://en.wikipedia.org/wiki/Zipf%27s_law) … i.e. in natural languages (word-frequency, letter-frequency), informatics/statistics/banking (i.e. distribution of digits in an id - in any base!; distribution of the first/last/any digit of wire-transfers, etc.)

Could you also add HashMaps? I made some experiments a week ago (between `HashMap Text Text` from unordered-containers and [Data.Trie.Text](https://github.com/michaeljklein/text-trie) and noticed no difference in performance in my application which just uses this as a big dictionary).

Is there also some implementation of a trie in terms of a finger-tree-like structure with laziness and all? I could imagine that such a thing might exist and offer better armortizes access to the “edges” yielding better performance for left/right-biased data.

---

<div class="post-metadata">

**Author:** ![ocramz](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ocramz/32/3713_2.png) [@ocramz](https://discourse.haskell.org/u/ocramz)\
**Post date:** [May 6, 2019, 6:47am UTC](https://discourse.haskell.org/t/benchmarks-of-various-trie-implementations/651/3 "2019-05-06T06:47:38Z")

</div>

> For most applications the distribution is closely related to [https://en.wikipedia.org/wiki/Zipf’s\_law](https://en.wikipedia.org/wiki/Zipf%27s_law) … i.e. in natural languages (word-frequency, letter-frequency), informatics/statistics/banking (i.e. distribution of digits in an id - in any base!; distribution of the first/last/any digit of wire-transfers, etc.)

This was initially built to test raw performance, not related to any application for now.

> Is there also some implementation of a trie in terms of a finger-tree-like structure with laziness and all? I could imagine that such a thing might exist and offer better armortizes access to the “edges” yielding better performance for left/right-biased data.

PRs open! 😉