11 ms·

"Hand crafted HTTP request parser" - hard to see how this really faster (and less bug prone) than generating one with Ragel.

by hendzen 12y ago

meowface 12y ago
I am fairly ignorant of Ragel, but to my understanding Ragel is better for assuring correctness rather than performance. I don't think Ragel makes any claims regarding performance. I could see a specially written parser outperforming it, just like hand written assembly can still sometimes outperform a compiler. I agree that it's more likely to have bugs, though.
nly 12y ago
Much of the advantage of using a DFA generator like Ragel is lost because the HTTP header grammar is actually ambiguous in several places and can't be streamed. You can use it as a component, but it isn't entirely sufficient on its own. The HTTP 1.1 RFC requires whitespace be stripped at the end of header values, yet also permits (although deprecates) header folding, giving rise to the following ambiguity (using _'s in place of leading spaces): Foo: Hello\r\n ______\r\n ________\r\n ________ world!\r\n Bar: smeg This requires that the parser buffer all the whitespace between 'Hello' and 'world!' (and the RFC doesn't put a standard limit on header value length) just in case 'world!' never comes and the value of the Foo header has to be stripped back to just "Hello" Here's a related observation from a commit[0] by the Joyent guys, who wrote the streaming parser used by NodeJS: "For http-parser itself to confirm[sic] exactly would involve significant changes in order to synthesize replacement SP octets. Such changes are unlikely to be worth it to support what is an obscure and deprecated feature" Another example is parsing the Request and Status lines: GET <uri> HTTP/1.1 Technically <uri> can't contain spaces, but the RFC says you MAY accept them [RFC7230: 3.5. Message Parsing Robustness] ... which then gives rise to the possibility of <uri> containing the literal string " HTTP/1.1", and ultimately opens up bad user agents that send spaces to header injection. Resolving these ambiguities require implementing your own buffering, and dropping down to Ragels 'state charts' feature to avoid your semantic actions being munged... which leaves you to design the top level state machine yourself. [0] https://github.com/joyent/http-parser/commit/5d9c3821729b194eef60f41fcc5f8b4657c3d8ff https://github.com/joyent/http-parser/commit/5d9c3821729b194...
- oever 12y ago
  https://www.ietf.org/rfc/rfc2616.txt https://www.ietf.org/rfc/rfc2616.txt : "All linear white space, including folding, has the same semantics as SP." So only one space need be counted and any subsequent space or horizontal tab can be ignored. Your example simplifies to: Foo: Hello World\r\n Bar: smeg
  - nly 12y ago
    It doesn't matter that the obs-fold can be treated as a single space because you don't know that until you've actually reached the fold. Consider: Foo: Hello_______world\r\n Here the whitespace has to be preserved, as per the field-content production. So RFC2616 allowed: Foo: Hello_______\r\n ____world\r\n to be reduced to: Foo: Hello world\r\n Incidentally RFC7230 (it's successor) says something subtly different: "A server that receives an obs-fold in a request message that is not within a message/http container MUST either reject the message by sending a 400 (Bad Request), preferably with a representation explaining that obsolete line folding is unacceptable, or replace each received obs-fold with one or more SP octets prior to interpreting the field value or forwarding the message downstream." So now it's been loosened to one or more SP octets... useful, except there's no mention of TAB octets, which can follow a CRLF as part of an obs-fold... so you still can't just remove the CRLF and preserve all the whitespace... preserving tabs would be illegal. So the new rules don't help streaming either. Joyents parser did this regardless (not sure if it still does). You'll also notice it says the obs-fold can be replaced with a sequence of SP characters... according to the grammar that's the CRLF and the following whitespace, not any whitespace preceding the CRLF. You'd think that would be helpful because it means any whitespace before the CRLF can always be streamed as part of the field value, right? Except... Foo: Hello_______\r\n ____\r\n would still simplify to: Foo: Hello_______[one or more SP octets]\r\n and then what? Well, presumably you then have to trim off the trailing whitespace to produce a value of just "Hello"... so all the whitespace you buffered before you reached the CRLF (in case you reached another field-vchar like the 'w' in 'world') has to be discarded.
    - Retric 12y ago
      Assuming your reading this from a buffer and most of the time you don't need to count then store an index to the o in hello followed by ignoring space. Then to back and count it only if you need to. Or better yet if whitespace is not need just copy a space but if it's needed then move those bytes to the next stage and don't bother to count them that go around.
quacker 12y ago
hard to see how this really faster (and less bug prone) than generating one with Ragel. Hm, I actually think the opposite (except for the point about bugs). A hand-crafted parser can easily be faster than a generic parser because: * You aren't limited to implementing a regular grammar * You can guarantee no overhead is introduced by the parsing tool * You have complete freedom to optimize at the lowest levels Now, I've never used Ragel, so I'm speaking from my experience with other parser generators (and from the perspective of a programming language implementation). I'd be interested to know if Ragel is different with regard to any of these points.
- nly 12y ago
  > I'd be interested to know if Ragel is different with regard to any of these points. It'll do a better job than you will at reducing DFAs to their optimal representation. Imho, with careful use of its pragmas, it produces pretty much optimal code when using -G2 (goto based code generation). Another really nice feature is being able to dump the DFA to a dot file and render it using Graphviz.

"Hand crafted HTTP request parser" - hard to see how this really faster (and less bug prone) than generating one with Ragel.

by hendzen 12y ago

"Hand crafted HTTP request parser" - hard to see how this really faster (and less bug prone) than generating one with Ragel.

meowface 12y ago

I am fairly ignorant of Ragel, but to my understanding Ragel is better for assuring correctness rather than performance. I don't think Ragel makes any claims regarding performance. I could see a specially written parser outperforming it, just like hand written assembly can still sometimes outperform a compiler. I agree that it's more likely to have bugs, though.

nly 12y ago

Much of the advantage of using a DFA generator like Ragel is lost because the HTTP header grammar is actually ambiguous in several places and can't be streamed. You can use it as a component, but it isn't entirely sufficient on its own. The HTTP 1.1 RFC requires whitespace be stripped at the end of header values, yet also permits (although deprecates) header folding, giving rise to the following ambiguity (using _'s in place of leading spaces): Foo: Hello\r\n ______\r\n ________\r\n ________ world!\r\n Bar: smeg This requires that the parser buffer all the whitespace between 'Hello' and 'world!' (and the RFC doesn't put a standard limit on header value length) just in case 'world!' never comes and the value of the Foo header has to be stripped back to just "Hello" Here's a related observation from a commit[0] by the Joyent guys, who wrote the streaming parser used by NodeJS: "For http-parser itself to confirm[sic] exactly would involve significant changes in order to synthesize replacement SP octets. Such changes are unlikely to be worth it to support what is an obscure and deprecated feature" Another example is parsing the Request and Status lines: GET <uri> HTTP/1.1 Technically <uri> can't contain spaces, but the RFC says you MAY accept them [RFC7230: 3.5. Message Parsing Robustness] ... which then gives rise to the possibility of <uri> containing the literal string " HTTP/1.1", and ultimately opens up bad user agents that send spaces to header injection. Resolving these ambiguities require implementing your own buffering, and dropping down to Ragels 'state charts' feature to avoid your semantic actions being munged... which leaves you to design the top level state machine yourself. [0] https://github.com/joyent/http-parser/commit/5d9c3821729b194eef60f41fcc5f8b4657c3d8ff https://github.com/joyent/http-parser/commit/5d9c3821729b194...

oever 12y ago
https://www.ietf.org/rfc/rfc2616.txt https://www.ietf.org/rfc/rfc2616.txt : "All linear white space, including folding, has the same semantics as SP." So only one space need be counted and any subsequent space or horizontal tab can be ignored. Your example simplifies to: Foo: Hello World\r\n Bar: smeg
- nly 12y ago
  It doesn't matter that the obs-fold can be treated as a single space because you don't know that until you've actually reached the fold. Consider: Foo: Hello_______world\r\n Here the whitespace has to be preserved, as per the field-content production. So RFC2616 allowed: Foo: Hello_______\r\n ____world\r\n to be reduced to: Foo: Hello world\r\n Incidentally RFC7230 (it's successor) says something subtly different: "A server that receives an obs-fold in a request message that is not within a message/http container MUST either reject the message by sending a 400 (Bad Request), preferably with a representation explaining that obsolete line folding is unacceptable, or replace each received obs-fold with one or more SP octets prior to interpreting the field value or forwarding the message downstream." So now it's been loosened to one or more SP octets... useful, except there's no mention of TAB octets, which can follow a CRLF as part of an obs-fold... so you still can't just remove the CRLF and preserve all the whitespace... preserving tabs would be illegal. So the new rules don't help streaming either. Joyents parser did this regardless (not sure if it still does). You'll also notice it says the obs-fold can be replaced with a sequence of SP characters... according to the grammar that's the CRLF and the following whitespace, not any whitespace preceding the CRLF. You'd think that would be helpful because it means any whitespace before the CRLF can always be streamed as part of the field value, right? Except... Foo: Hello_______\r\n ____\r\n would still simplify to: Foo: Hello_______[one or more SP octets]\r\n and then what? Well, presumably you then have to trim off the trailing whitespace to produce a value of just "Hello"... so all the whitespace you buffered before you reached the CRLF (in case you reached another field-vchar like the 'w' in 'world') has to be discarded.
  - Retric 12y ago
    Assuming your reading this from a buffer and most of the time you don't need to count then store an index to the o in hello followed by ignoring space. Then to back and count it only if you need to. Or better yet if whitespace is not need just copy a space but if it's needed then move those bytes to the next stage and don't bother to count them that go around.

quacker 12y ago

hard to see how this really faster (and less bug prone) than generating one with Ragel. Hm, I actually think the opposite (except for the point about bugs). A hand-crafted parser can easily be faster than a generic parser because: * You aren't limited to implementing a regular grammar * You can guarantee no overhead is introduced by the parsing tool * You have complete freedom to optimize at the lowest levels Now, I've never used Ragel, so I'm speaking from my experience with other parser generators (and from the perspective of a programming language implementation). I'd be interested to know if Ragel is different with regard to any of these points.

nly 12y ago
> I'd be interested to know if Ragel is different with regard to any of these points. It'll do a better job than you will at reducing DFAs to their optimal representation. Imho, with careful use of its pragmas, it produces pretty much optimal code when using -G2 (goto based code generation). Another really nice feature is being able to dump the DFA to a dot file and render it using Graphviz.