Re:String Interning – Trie vs. Hash Table Deathmatch
by beagle3 on Wednesday July 01, 2015 @10:47AM
(#9812140)
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).
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.