4 ms·

Tries ain't easy. It's no surprise that a naive trie is bested by a naive hashtable, especially where the number of entries is dwarfed by the capacity of the ha

Tries ain't easy. It's no surprise that a naive trie is bested by a naive hashtable, especially where the number of entries is dwarfed by the capacity of the hashtable. The gold standard for a trie is probably the Judy array[1], which I've heard has some patents on it, but I can't confirm. Judy arrays obtain their performance by using a myriad range of possible leaf and branch nodes. The goal is to fit as much data that could be used for decision making and branching in the first cache line that would be read. And in the case of very sparse tries this pays off handsomely. That said, hash tables are really hard to beat. They are susceptible to denial of service attacks though. [1] http://judy.sourceforge.net/application/shop_interm.pdf http://judy.sourceforge.net/application/shop_interm.pdf [2] http://loup-vaillant.fr/projects/string-interning/intern_trie.c http://loup-vaillant.fr/projects/string-interning/intern_tri...

jamii 11y ago
These are not patented, and are reasonably simple - http://www3.informatik.tu-muenchen.de/~leis/papers/ART.pdf http://www3.informatik.tu-muenchen.de/~leis/papers/ART.pdf
beagle3 11y ago
Also, critbit trees: http://cr.yp.to/critbit.html http://cr.yp.to/critbit.html - they are a binary patricia trie. They might beat both Judy and Hash tables in specific input distributions: e.g., if all strings have a long common prefix such as: AbstractFactoryFactoryFactoryCreator_x where x is different in each string; hash and judy would need to scan through the entire string, but critbit trees would start by comparing the 'x'. Somewhat similar to how a Boyer-Moore search doesn't need to scan the whole haystack while looking for needles.
- kryps 11y ago
  For critbit trees the entire string _up to_ the critical bit where the string differs from all others already in the datastructure needs to be scanned. critbit trees degenerate badly if you store strings and their prefixes, e.g. storing a, aa, aaa, ...
  - beagle3 11y ago
    True, but that's not worse than "standard" tries, and big O()-wise, not even worse than hashing - you do have to scan through the string to hash it. Worst case data for a critbit tree is also worst case for any other kind of trie, and better than worst case for a classic hash (which is O(items in table) and can often be triggered by an adversary). Constants are different, though.
- aidenn0 11y ago
  I hacked in support for critbits from this repository: https://github.com/jgehring/critbit89 https://github.com/jgehring/critbit89 I modified it to use something like the pool allocator that TFA's hash table implementation used (testing later with and without showed only small performance differences). I couldn't replicate the dataset from TFA, since it wasn't provided, so I downloaded the java corpus and just took the first 3M symbols in it. Relative performance of the 3 benchmarks from the article were similar. The result was that it was much more space-efficient than the trie implementation from TFA (only slightly larger than the hash table), but about 1.8x slower than the trie implementation. A quick -pg run showed 98% of the CPU time in cb_tree_insert which isn't useful for determining why this was so slow, since it's the monolithic function that does all of the insert work other than allocation.
  - beagle3 11y ago
    Thanks, I wanted to do that but didn't have the time. Probably the usual tradeoff - critbit does log2(fan_out) branches per location (it branches per bit ) whereas a regular trie branches per location (it branches per byte ). That it is only x1.8 times slower is actually good. I guess it's mostly the less predictable branches of the critbit (and the fact that there's more of them).

jamii 11y ago

These are not patented, and are reasonably simple - http://www3.informatik.tu-muenchen.de/~leis/papers/ART.pdf http://www3.informatik.tu-muenchen.de/~leis/papers/ART.pdf

beagle3 11y ago

Also, critbit trees: http://cr.yp.to/critbit.html http://cr.yp.to/critbit.html - they are a binary patricia trie. They might beat both Judy and Hash tables in specific input distributions: e.g., if all strings have a long common prefix such as: AbstractFactoryFactoryFactoryCreator_x where x is different in each string; hash and judy would need to scan through the entire string, but critbit trees would start by comparing the 'x'. Somewhat similar to how a Boyer-Moore search doesn't need to scan the whole haystack while looking for needles.

kryps 11y ago
For critbit trees the entire string _up to_ the critical bit where the string differs from all others already in the datastructure needs to be scanned. critbit trees degenerate badly if you store strings and their prefixes, e.g. storing a, aa, aaa, ...
- beagle3 11y ago
  True, but that's not worse than "standard" tries, and big O()-wise, not even worse than hashing - you do have to scan through the string to hash it. Worst case data for a critbit tree is also worst case for any other kind of trie, and better than worst case for a classic hash (which is O(items in table) and can often be triggered by an adversary). Constants are different, though.
aidenn0 11y ago
I hacked in support for critbits from this repository: https://github.com/jgehring/critbit89 https://github.com/jgehring/critbit89 I modified it to use something like the pool allocator that TFA's hash table implementation used (testing later with and without showed only small performance differences). I couldn't replicate the dataset from TFA, since it wasn't provided, so I downloaded the java corpus and just took the first 3M symbols in it. Relative performance of the 3 benchmarks from the article were similar. The result was that it was much more space-efficient than the trie implementation from TFA (only slightly larger than the hash table), but about 1.8x slower than the trie implementation. A quick -pg run showed 98% of the CPU time in cb_tree_insert which isn't useful for determining why this was so slow, since it's the monolithic function that does all of the insert work other than allocation.
- beagle3 11y ago
  Thanks, I wanted to do that but didn't have the time. Probably the usual tradeoff - critbit does log2(fan_out) branches per location (it branches per bit ) whereas a regular trie branches per location (it branches per byte ). That it is only x1.8 times slower is actually good. I guess it's mostly the less predictable branches of the critbit (and the fact that there's more of them).