4 ms·

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 s

by 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).

by beagle3 11y ago

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).