Re:I've implemented a new HTTP/1.1 request and response pars...
by tyler on Tuesday December 01, 2009 @06:45AM
(#969587)
I've had the opposite experience with Tries v. Hash tables. Though that could be a result of the Trie implementation. Dual array tries have really impressive lookup times, especially compared to the naive implementation... Insertion is pretty bad though. (Though that can be mitigated: http://www.gongcaichun.info/PPT/21.pdf)
Re:I've implemented a new HTTP/1.1 request and response pars...
by nostrademons on Tuesday December 01, 2009 @11:15AM
(#969975)
The structure of your data matters a lot. If one will fit in cache but the other won't, the one that fits in cache will almost always win. Then they have different big-O characteristics: binary searching an array is O(log N) where N is the number of items, a trie is O(k) where k is the length of the key, a hashtable is O(1), but this is misleading because the hash function is usually O(k) and performance can degrade to O(n) if you have lots of hash collisions.
I thought that an autocompletion widget for stock tickers would be the perfect application for tries: short, dense key space, lots of elements, and a fair likelihood of hash collisions. But apparently not, because our data size just happened to be one where cache effects dominate. I talked to one of the GMail guys later and he was quite surprised, from which I inferred (but it was not stated) that GMail probably uses tries to good effect.
Re:I've implemented a new HTTP/1.1 request and response pars...
by tyler on Tuesday December 01, 2009 @05:37PM
(#970972)
Right on. My point was simply that the type of Trie you use has an effect on the data's size in memory. A dual-array setup is pretty good at keeping the data small... There's very little pointer overhead and proximity is fairly good as well.
(Yeah, I do have some data to back that up - I wrote & benchmarked an autocomplete implementation for a financial software firm. String tries were roughly 10x slower than binary searching an array for a 20k word corpus, which is probably around the size you're dealing with here. They have terrible cache locality - each character makes you follow a pointer, which is probably a cache miss, and the total size of the trie is on the order of 26 * 8 * 20k = 4M. They become a bit better if the number of distinct words in the corpus is small (so that everything fits into cache) or if the number of words is huge (so that your hashtable or array blows the cache anyway).