I've implemented a new HTTP/1.1 request and response parser by hand • Hacker News Board

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

#41

Post by viraptor » Tue, Dec 01, 2009, 9:05 PM UTC

bumblebird wrote: post #37

ryah wrote: post #36

Earlier quoted context omitted.

clearly you're unfamiliar with http.

I certainly am. It's a complete mystery to me. Is it like visual basic? The only PITA with HTTP is chunked encoding. Whoever thought that gem up should be shot. The rest is fairly trivial. Certainly parsing headers is. This implementation looks pretty silly. Having individual states for each of the characters in "HTTP" etc? WTF? edit: Instead of just downmodding me, why not explain exactly what part of parsing HTTP h…

The parser correctness is not trivial. The RFC2616 contains the complete grammar you need, so it's fairly simple to implement. OTOH, if you write a parser on your own, you're likely to miss stuff like section 4.2, which explains that header values can be multiline if they include LWS. The parser from this article will fail on (just looking at the source, I'm 99.5% sure of this):

    abc:
     def

It also doesn't like tabs and will not support comma-separated header values. It's not rocket science to write a "good enough" http parser, but writing a fully compliant one is something completely different. There are also cool parts of the spec that you can read 10 times and come to different conclusions - for example what does the "\" CR LF section mean if it's inside a quoted string and does it finish the header value or not. Writing a "correct" parser is a LOT of fun...

Keeping separate states for characters in HTTP saves you a couple of cycles probably, because you match as you go and can reject the message early and with the exact place that didn't match. It's a bit useless for a 4-letter string though.

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

#42

Post by Confusion » Tue, Dec 01, 2009, 9:12 PM UTC

nostrademons wrote: post #6

jerf wrote: post #4

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

The student missed the most important part of the spec: the intent. 99 Out of a 100 times, you aren't implementing a rigorous spec. The ability to understand what is requested is much more important than the ability to be a wise-ass.

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

#43

Post by tyler » Tue, Dec 01, 2009, 10:37 PM UTC

nostrademons wrote: post #35

tyler wrote: post #30

Earlier quoted context omitted.

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 )

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…

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.

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

#44

Post by viraptor » Wed, Dec 02, 2009, 3:37 AM UTC

Confusion wrote: post #42

nostrademons wrote: post #6

Earlier quoted context omitted.

I'm disappointed that the student who hardcoded the results was disqualified. You should get points for finding bugs in your professors' specification.

The student missed the most important part of the spec: the intent. 99 Out of a 100 times, you aren't implementing a rigorous spec. The ability to understand what is requested is much more important than the ability to be a wise-ass.

> 99 Out of a 100 times, you aren't implementing a rigorous spec.

I'd argue that most programmers do, or are supposed to. Either because they are not the designers of the system they build and what they are expected to do is to "fill in the blanks and make it work", or because they implement something that operates with another system and should strictly adhere to the interface/protocol.

The ones who have anything to say about the design are usually the system designers (duh), small project contributors (because there is no spec) and UI people (because they're designers). So yes - if your spec is "1. make it work on this input; 2. make it fast", then making it work in O(1) for this and only this input is basically the best thing you can do (unless you can make it faster for every input in less time of course). Spending time on generalising it is based on second-guessing the intent.

I'd even go as far as saying that specs have absolutely no intent. You have an intent and describe it while writing the spec and you'd better formalise your intent precisely or you will end up with something you didn't request. If you want something on every input, you'd better write it down (when you give a task to someone else).