Earlier quoted context omitted.
Since when are judy arrays synonymous with tries? Judy arrays were only invented and publicized in 2004 and the only public implementation is GPLed.
[deleted]
[deleted]
I've implemented a new HTTP/1.1 request and response parser by hand
21–30 of 44 posts
Re: I've implemented a new HTTP/1.1 request and response parser by hand
#22I thought it was a pretty cool implementation (zero memory alloc is pretty hard most of the time), though I was disappointed how HTTP methods were hard coded in, so adding a new HTTP method (like PROPFIND?) would be adding a ton of code, though I think you could make a few macros for doing HTTP methods and keep the rest of it.
Re: I've implemented a new HTTP/1.1 request and response parser by hand
#23Earlier quoted context omitted.
"I can make it arbitrarily fast if I don't actually have to make it work": http://blogs.msdn.com/larryosterman/archive/2009/09/29/i-can...
I'm disappointed that the student who hardcoded the results was disqualified. You should get points for finding bugs in your professors' specification.
Sounds like red/green/refactor would have come naturally to her.
Re: I've implemented a new HTTP/1.1 request and response parser by hand
#24Earlier quoted context omitted.
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)
Since when are judy arrays synonymous with tries? Judy arrays were only invented and publicized in 2004 and the only public implementation is GPLed.
the only public implementation is GPLed
Actually no. Here's a BSD one: http://hackage.haskell.org/package/judy
Re: I've implemented a new HTTP/1.1 request and response parser by hand
#25At my company we rolled our own too. The hard part was tracking down all the brain-dead servers that seemingly worked fine with browsers, but were off spec.
Are there any good sets of HTTP compatibility tests which test deviations from the spec which show up in existing servers/browsers?
http://coad.measurement-factory.com/
Warning: not free.
Re: I've implemented a new HTTP/1.1 request and response parser by hand
#26Earlier quoted context omitted.
Since when are judy arrays synonymous with tries? Judy arrays were only invented and publicized in 2004 and the only public implementation is GPLed.
the only public implementation is GPLed Actually no. Here's a BSD one: http://hackage.haskell.org/package/judy
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 " 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.
Re: I've implemented a new HTTP/1.1 request and response parser by hand
#27By hand??? As opposed to what exactly? Isn't most code written by hand?
Re: I've implemented a new HTTP/1.1 request and response parser by hand
#28By hand ??? As opposed to what exactly? Isn't most code written by hand?
As opposed to using Ragel, as you'd have known if you'd read the link.
Re: I've implemented a new HTTP/1.1 request and response parser by hand
#29By hand ??? As opposed to what exactly? Isn't most code written by hand?
As opposed to using Ragel, as you'd have known if you'd read the link.
The title is "I've implemented a new HTTP/1.1 request and response parser by hand"
My question was, how do you implement a new HTTP/1.1 request and response parser if it's not by hand. Isn't most code written using hands?
I've written one too... big whoop.
Meh anyway...
Re: I've implemented a new HTTP/1.1 request and response parser by hand
#30Earlier quoted context omitted.
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...
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…
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)