I've implemented a new HTTP/1.1 request and response parser by hand

Re:I've implemented a new HTTP/1.1 request and response pars... by viraptor on Monday November 30, 2009 @11:26PM (#969228)

After reading that, I wonder if trie-s (i.e. judy arrays) would beat hash tables in this exercise... (and I also think that hardcoding the results wasn't cheating)

[ Parent | on HN ]

Re:I've implemented a new HTTP/1.1 request and response pars... by codexon on Tuesday December 01, 2009 @12:26AM (#969283)

Since when are judy arrays synonymous with tries?

Judy arrays were only invented and publicized in 2004 and the only public implementation is GPLed.

[ Parent | on HN ]

[deleted]

Re:I've implemented a new HTTP/1.1 request and response pars... by weaksauce on Tuesday December 01, 2009 @01:08AM (#969328)

For the record, and I am sure it's what you meant, a more specific description of Judy arrays is that they are a specific type of trie(though a trie is a specialization of a tree a trie is more rigorous.)

[ Parent | on HN ]

Re:I've implemented a new HTTP/1.1 request and response pars... by andreyf on Tuesday December 01, 2009 @01:13AM (#969333)

Judy Arrays are all Tries are all Trees, but only some Trees are Tries, and only some Tries are Judy Arrays.

[ Parent | on HN ]

Re:I've implemented a new HTTP/1.1 request and response pars... by pstuart on Tuesday December 01, 2009 @01:13AM (#969332)

This of i.e. as 'that is' and e.g. as "example given'.

[ Parent | on HN ]

Re:I've implemented a new HTTP/1.1 request and response pars... by ramchip on Tuesday December 01, 2009 @01:35AM (#969352)

the only public implementation is GPLed

Actually no. Here's a BSD one: http://hackage.haskell.org/package/judy

[ Parent | on HN ]

Re:I've implemented a new HTTP/1.1 request and response pars... by codexon on Tuesday December 01, 2009 @02:05AM (#969378)

Actually no. That's only a binding if you look at the source code.

The sole C source code is only about 2-3 lines long with a "#include <Judy.h>" which isn't even included while the haskell source is littered with foreign function calls.

I discussed this issue with Don on my website a couple of months ago: http://www.codexon.com/posts/why-arent-functional-languages-...

and believe me, he would have told me if he really did have a completely reimplemented Judy array.

[ Parent | on HN ]

Re:I've implemented a new HTTP/1.1 request and response pars... by andreyf on Tuesday December 01, 2009 @12:28AM (#969286)

With some pointer arithmetic, I would imagine so (with tries, not sure what judy arrays are)... although it might depend into how quickly memory can be allocated/accessed. Assuming the text is a set of lower-case alphabet character strings, you could define a 26-ary trie with very few instructions to do each characters' lookup...

[ Parent | on HN ]

Re:I've implemented a new HTTP/1.1 request and response pars... by nostrademons on Tuesday December 01, 2009 @12:46AM (#969310)

I would be willing to bet that that implementation is slower than a hash table.

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

[ Parent | on HN ]

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)

[ Parent | on HN ]

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.

[ Parent | on HN ]

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.

[ Parent | on HN ]