Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

four.livejournal.com

Post reply on HN
Print view View original

31–40 of 44 posts

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

#31

Post by Frazzydee »

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.

Well the specs say that the program must "calculate the 10 most common words". The disqualified program doesn't really calculate the 10 most common words– it simply outputs the answer.

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

#32

Post by viraptor »

bumblebird wrote: post #29
ionfish wrote: post #28

Earlier quoted context omitted.

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

Most parsers nowadays are generated via yacc and others. You write the structure, yacc generates the parser (and flex the lexer). It's something completely different if you write the parser yourself.

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

#33

Post by bumblebird »

viraptor wrote: post #32
bumblebird wrote: post #29

Earlier quoted context omitted.

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

Most parsers nowadays are generated via yacc and others. You write the structure, yacc generates the parser (and flex the lexer). It's something completely different if you write the parser yourself.

It was just a bit surprising to me. Parsing HTTP isn't exactly complex.

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

#34

Post by ricree »

andreyf wrote: post #12
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.

Not to mention the "winning" entry did exactly the same thing: found an `n' # of words which works for this input only , then created a fast algorithm that works for this input only , but is incorrect in general.

Especially since the other solution that got docked for breaking the rules actually performed the calculation that was requested.

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

#35

Post by nostrademons »

tyler wrote: post #30
nostrademons wrote: post #17

Earlier quoted context omitted.

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 )

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 parser by hand

#36

Post by ryah »

bumblebird wrote: post #33
viraptor wrote: post #32

Earlier quoted context omitted.

Most parsers nowadays are generated via yacc and others. You write the structure, yacc generates the parser (and flex the lexer). It's something completely different if you write the parser yourself.

It was just a bit surprising to me. Parsing HTTP isn't exactly complex.

clearly you're unfamiliar with http.

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

#37

Post by bumblebird »

ryah wrote: post #36
bumblebird wrote: post #33

Earlier quoted context omitted.

It was just a bit surprising to me. Parsing HTTP isn't exactly complex.

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 headers is non trivial?

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

#38

Post by jimbokun »

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.

I'm stunned that this was not for seen by the professor. Wasn't it obvious that the best way to do this was to give some sample documents for development, but keep the text that the program would be judged on a secret?

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

#39

Post by eru »

Frazzydee wrote: post #31
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.

Well the specs say that the program must " calculate the 10 most common words". The disqualified program doesn't really calculate the 10 most common words– it simply outputs the answer.

It doesn't say they have to be calculated from the input.

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

#40

Post by davisp »

pquerna wrote: post #22

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

Hacked together an on_method callback last night for the Python bindings I'm writing:

http://github.com/davisp/http-parser/commit/50e54f95fd4c2eac...

Post reply on HN