Hacker News Reader

Comment by beagle3 | Hacker News Reader

Also, critbit trees: 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.

View on HN

I hacked in support for critbits from this repository: 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.

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

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

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.

Reply on news.ycombinator.com