13 ms·

A fast HTTP request/response parser for Common Lisp

131 points by fukamachi 12y ago

eudox 12y ago
For context, Eitaro Fukamachi has been working on a whole bunch of things relating to the low-level parts of Common Lisp web development: A fast HTTP parser, a fast URI parser[0], a libuv-based web server[1] (That outperforms Node!), and he's also written Clack[2], which is Common Lisp's Rack/WSGI. [0]: https://github.com/fukamachi/quri https://github.com/fukamachi/quri [1]: https://github.com/fukamachi/woo https://github.com/fukamachi/woo [2]: https://github.com/fukamachi/clack https://github.com/fukamachi/clack
- pnathan 12y ago
  Fukamachi has done some stellar work. I've used his code and have generally been very happy with it.
- rgbrgb 12y ago
  > (That outperforms Node!) In what way? All of the benchmarks I'm seeing on that page indicate otherwise.
  - eudox 12y ago
    When he first posted it, it did, it looks like recent changes have brought that down: https://github.com/fukamachi/woo/commit/be4a0db688af05ee204ec37c5c185f13a4fe8e36 https://github.com/fukamachi/woo/commit/be4a0db688af05ee204e...
    - fukamachi 12y ago
      Right. When I added default headers, the score went way down. Probably libevent2 is the bottleneck and no way to make it faster without switching its backend (the cl-async's author is working on rewriting it with libuv now).
      - aidenn0 12y ago
        Out of curiosity did you try basic-binary-ipc? I would expect it would lose out to cl-async, but have never benchmarked the two against each other.
  - thirsteh 12y ago
    It would be quite surprising if it did, since Node's HTTP parser isn't Node/JavaScript, but highly optimized C.
- negativeview 12y ago
  That's quite interesting! I tried to learn Lisp a while back and found the string handling to be horrible, and it's such a huge part of modern development. It sounds like there's someone with a lot of skill working to fix exactly this. Now, do I have time to look into Lisp again...
  - PuercoPop 12y ago
    out of curiosity, what did you found horrible about string handling?
    - negativeview 12y ago
      So I just looked up Common Lisp string handling and none of it looks familiar. It's possible what I was trying to use before wasn't Common Lisp. It's also possible I was trying to learn from a site that was just doing a horrible job of it. It's possible things have gotten much much better since I last tried to learn it. Whatever the cause, I was under the impression that you essentially had to treat strings as lists of characters and that there really weren't any built-in functions to handle strings as strings. It seems that's wrong at least in modern day.
      - PuercoPop 12y ago
        Strings are a simple-array of characters and functions that work sequences work on strings (ej. remove). They are complemented with a some string specific functions like string-equal, string-trim, string-upcase, etc. It has been that way for at least 20 years. It might have been that the site was doing a horrible job at explaining it.
      - aerique 12y ago
        Strings are sequences and functions that work on sequences work on strings as well. So getting substrings etc. is all possible. I've had very little problems operating on strings in Common Lisp (all I missed was starts-with and ends-with functions), could you give some concrete examples so that I might help you?
TheMagicHorsey 12y ago
I've always assumed Clojure was the right choice for a Lisp to do web applications. Perhaps I should revaluate my assumptions.
- apgwoz 12y ago
  If you're assuming this based on some microbenchmarks, you should probably instead reevaluate your evaluation techniques. (This isn't meant as a personal jab, but too many people focus on silly things like microbenchmarks when choosing tools, and not on other more important things like support avenues, tooling, libraries, etc.)
  - aroman 12y ago
    I don't think it's fair to assume that TheMagicHorsey was basing his evaluation on the microbenchmarks themselves. The real story here is that people are working on a number of new libraries/modules/tools for doing web development in CL — the benchmarks (as you correctly point out) are a minor detail.
    - apgwoz 12y ago
      Perhaps you should read more carefully. "If you're assuming ..." It's just not clear from the context we have. But, caution! Microbenchmarks should only be Microtrusted.
  - adrianm 12y ago
    I think this is truly sagely advice. My grand takeaway from Aphyr's Jepsen series (http://aphyr.com/tags/jepsen http://aphyr.com/tags/jepsen) is that the more sophisticated software becomes in the never-ending quest for features and performance, the more likely the fundamentals underlying it have been overlooked, glossed over, or ignored completely.
    - eudox 12y ago
      When you compare the time fukamachi's spent on these libraries to the time spent on Clack, Caveman, etc., it's pretty clear there's obsession with performance. As aroman said, "The real story here is that people are working on a number of new libraries/modules/tools for doing web development in CL".
wspeirs 12y ago
Just curious what about this parser makes it faster? Can anyone give a basic explanation?
- easytiger 12y ago
  Well if you implemented the c parser with precisely the same algorithms the c one would become faster, so one can assume they have totoally different underlying implementations
  - haberman 12y ago
    That is not necessarily true (and I say this as someone who heavily favors C for parsers). An implementation with a JIT will likely be able to optimize away work by noticing that the table of callbacks is empty. I would be more impressed if the callback table was not empty (and the callbacks actually did something, like increment an integer) and Lisp was still winning. EDIT: I see others saying that SBCL is AOT, not JIT. If so I'd be very interested to look at the disassembly side-by-side and see an explanation for why SBCL is winning.
    - muyuu 12y ago
      SBCL is a compiled Common LISP (even in interpreted mode, it compiles every eval-ed lambda before calling it). On the other hand there is nothing inherently stopping the optimiser from optimising the resulting code as well or better than GCC or any C compiler. Theoretically it could produce optimal machine code.
      - haberman 12y ago
        Correct me if I'm wrong but I was under the impression that Common Lisp is memory-safe (implying guards like bounds-checks), dynamically typed (implying type checks) and garbage collected (implying GC overhead).
        muyuu 12y ago
haberman 12y ago
I was not able to run the benchmark for Lisp. What Lisp implementation is expected? I tried CLISP and got: *** - READ from #<INPUT BUFFERED FILE-STREAM CHARACTER #P"benchmark.lisp" @1>: there is no package with name "SYNTAX"
- deleted 12y ago
  [deleted]
- eudox 12y ago
  I'd recommend SBCL, since a high-performance JIT compiler is likely to give more representative results than a bytecode VM like CLISP. Plus, I'd expect some minor portability errors to arise when you push the envelope like this. By the way, your error seems to be that the cl-syntax library is not being found, as opposed to a portability problem, so maybe you don't have Quicklisp installed and loaded?
  - haberman 12y ago
    > By the way, your error seems to be that the cl-syntax library is not being found, as opposed to a portability problem, so maybe you don't have Quicklisp installed and loaded? Indeed I don't, I didn't know to install it since it wasn't listed as a dependency. Thanks for the info!
    - eudox 12y ago
      Quicklisp is CL's package manager, so that's necessary to install dependencies. You can install it with: $ curl -O http://beta.quicklisp.org/quicklisp.lisp $ sbcl --load quicklisp.lisp \ --eval '(quicklisp-quickstart:install)' \ --eval '(ql:add-to-init-file)' \ --quit
  - gjm11 12y ago
    Pedantic correction: Unless something's changed very radically since I last looked, SBCL's compiler is AOT not JIT. (Though in interactive use it compiles things as you enter them, which I suppose is kinda JIT if you look at it from just the right angle and squint.)
halayli 12y ago
parsed = http_parser_execute(parser, &settings_null, buf, strlen(buf)); assert(parsed == strlen(buf)); He's calling strlen(buf) twice here. There's no guarantee that this is optimized at compile time. Usually len of buf is determined from read/recv system calls and for a fair comparison strlen should be removed here.
- Ono-Sendai 12y ago
  assert only runs in debug mode anyway.
  - haberman 12y ago
    It runs unless NDEBUG is defined, which the author did not do according to his methodology. Anyway I looked at the assembly output and strlen() is optimized away.
    - webreac 12y ago
      I really do not like when bad habits are encouraged by the optimizer.
  - halayli 12y ago
    no, that's not correct. http://pubs.opengroup.org/onlinepubs/009695399/functions/assert.html http://pubs.opengroup.org/onlinepubs/009695399/functions/ass...
    - aidenn0 12y ago
      "Forcing a definition of the name NDEBUG, either from the compiler command line or with the preprocessor control statement #define NDEBUG ahead of the #include <assert.h> statement, shall stop assertions from being compiled into the program"
- fukamachi 12y ago
  No difference even though I ran the benchmark again after removing the line.
Animats 12y ago
Is parsing HTTP headers a major bottleneck? HTML parsing, sure, especially with the horrors of HTML 5 error handling per the spec and the need to back up after guessing the character set. But HTTP headers are not that big or complex.
- eudox 12y ago
  From the Reddit thread: http://www.reddit.com/r/lisp/comments/2klhpn/quri_a_uri_library_for_common_lisp_6x_faster_than/clmsfzd http://www.reddit.com/r/lisp/comments/2klhpn/quri_a_uri_libr... >Right. When I was profiling Wookie, I found URL parsing was the third bottleneck (the first is HTTP request parsing, and the second is libevent2).
  - Animats 12y ago
    Yes, that's really important for compatibility with Google Wave.
- edsiper2 12y ago
  HTTP protocol grammar is pretty simple, but parsing correctly considering the server side and desired performance may be hard. By nature parsing strings is expensive (not sure why they designed HTTP in string format, binary would save a ton of power in processing). So imaging you are receiving a request, most of the time due to Network latency (client or server side), you don't get the full Request at once, most of the time you need to perform a couple of read(2) operations. Now, what do you do on each read ?, did you manage full state ?, how many parsing rounds ?, how to catch the end of the protocol block , etc etc etc. So answering your questions I would say "YES", the HTTP protocol in a Server "may be" a bottleneck if its not well implemented. In our HTTP Server project[0] we are working in a new parser to improve performance, so for real, this is a very important topic. [0] http://monkey-project.com http://monkey-project.com best
thu 12y ago
In the HTTP benchmark game, there is also Bryan O'Sullivan's attoparsec-based parser: http://www.serpentine.com/blog/2014/05/31/attoparsec/ http://www.serpentine.com/blog/2014/05/31/attoparsec/ The important point is that the parser is a few dozen lines of code (i.e. it relies on a general parsing library instead of being custom hand-written code).
verytrivial 12y ago
This reminds me of John Fremlin's work back in 2009 http://john.freml.in/teepeedee2-c10k http://john.freml.in/teepeedee2-c10k . (Hello, John!)
_RPM 12y ago
Is Lisp a write-only language?
- adwf 12y ago
  I'll assume this is an honest question - not a troll (and hence don't deserve the downvotes), but no, Lisp isn't write-only. It's an immensely flexible language that lets you code in a variety of different styles, so you can end up with code spaghetti. But that doesn't mean that you have to, or even that it's the most likely thing to happen. If you compare it to idiomatic Perl, where a lot of the community seem to get obsessed with the famous one-liners, Lisp seems a lot better to me. And if you follow a decent style guide like: https://google-styleguide.googlecode.com/svn/trunk/lispguide.xml https://google-styleguide.googlecode.com/svn/trunk/lispguide... Then there's no particular reason why you should end up with disaster code anymore than in any another language. I'd rather read a single page of Lisp, than the equivalent numerous pages of Java or some other verbose language.
- aerique 12y ago
  Coming from Common Lisp and having tried out Haskell recently I can ask the same about the latter while I find Lisp to be one of the most readable languages out there. It's basically what you're used to and for Lisp it does not take long to get used to.
- wnewman 12y ago
  The old book _Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp_ contains a number of nontrivial programs (like an Othello player and a little symbolic math program). AFAIK, most people think the code is unusually clear, both a good example of how to write clear CL programs and a good example of clear programming period (independent of language). If you are seriously interested in clarity of CL programs, I recommend taking a look at that book.
serbrech 12y ago
Hmm, I can't really write lisp, but, how maintainable is this?? https://github.com/fukamachi/fast-http/blob/master/src/parser.lisp https://github.com/fukamachi/fast-http/blob/master/src/parse...
- adwf 12y ago
  It could do with some comments and doc-strings certainly, but I'd give it a pass for now as it's a new project. As for the code, I imagine that in any language, highly optimised programs can start looking pretty odd after a while. Try understanding "grep" for example: http://git.savannah.gnu.org/cgit/grep.git/tree/src/grep.c http://git.savannah.gnu.org/cgit/grep.git/tree/src/grep.c As a guy not particularly proficient in C, that looks crazy to me. Although it does at least have decent comments, which I'd expect for such a mature project!

131 points by fukamachi 12y ago

eudox 12y ago

For context, Eitaro Fukamachi has been working on a whole bunch of things relating to the low-level parts of Common Lisp web development: A fast HTTP parser, a fast URI parser[0], a libuv-based web server[1] (That outperforms Node!), and he's also written Clack[2], which is Common Lisp's Rack/WSGI. [0]: https://github.com/fukamachi/quri https://github.com/fukamachi/quri [1]: https://github.com/fukamachi/woo https://github.com/fukamachi/woo [2]: https://github.com/fukamachi/clack https://github.com/fukamachi/clack

pnathan 12y ago
Fukamachi has done some stellar work. I've used his code and have generally been very happy with it.
rgbrgb 12y ago
> (That outperforms Node!) In what way? All of the benchmarks I'm seeing on that page indicate otherwise.
- eudox 12y ago
  When he first posted it, it did, it looks like recent changes have brought that down: https://github.com/fukamachi/woo/commit/be4a0db688af05ee204ec37c5c185f13a4fe8e36 https://github.com/fukamachi/woo/commit/be4a0db688af05ee204e...
  - fukamachi 12y ago
    Right. When I added default headers, the score went way down. Probably libevent2 is the bottleneck and no way to make it faster without switching its backend (the cl-async's author is working on rewriting it with libuv now).
    - aidenn0 12y ago
      Out of curiosity did you try basic-binary-ipc? I would expect it would lose out to cl-async, but have never benchmarked the two against each other.
- thirsteh 12y ago
  It would be quite surprising if it did, since Node's HTTP parser isn't Node/JavaScript, but highly optimized C.
negativeview 12y ago
That's quite interesting! I tried to learn Lisp a while back and found the string handling to be horrible, and it's such a huge part of modern development. It sounds like there's someone with a lot of skill working to fix exactly this. Now, do I have time to look into Lisp again...
- PuercoPop 12y ago
  out of curiosity, what did you found horrible about string handling?
  - negativeview 12y ago
    So I just looked up Common Lisp string handling and none of it looks familiar. It's possible what I was trying to use before wasn't Common Lisp. It's also possible I was trying to learn from a site that was just doing a horrible job of it. It's possible things have gotten much much better since I last tried to learn it. Whatever the cause, I was under the impression that you essentially had to treat strings as lists of characters and that there really weren't any built-in functions to handle strings as strings. It seems that's wrong at least in modern day.
    - PuercoPop 12y ago
      Strings are a simple-array of characters and functions that work sequences work on strings (ej. remove). They are complemented with a some string specific functions like string-equal, string-trim, string-upcase, etc. It has been that way for at least 20 years. It might have been that the site was doing a horrible job at explaining it.
    - aerique 12y ago
      Strings are sequences and functions that work on sequences work on strings as well. So getting substrings etc. is all possible. I've had very little problems operating on strings in Common Lisp (all I missed was starts-with and ends-with functions), could you give some concrete examples so that I might help you?

TheMagicHorsey 12y ago

I've always assumed Clojure was the right choice for a Lisp to do web applications. Perhaps I should revaluate my assumptions.

apgwoz 12y ago
If you're assuming this based on some microbenchmarks, you should probably instead reevaluate your evaluation techniques. (This isn't meant as a personal jab, but too many people focus on silly things like microbenchmarks when choosing tools, and not on other more important things like support avenues, tooling, libraries, etc.)
- aroman 12y ago
  I don't think it's fair to assume that TheMagicHorsey was basing his evaluation on the microbenchmarks themselves. The real story here is that people are working on a number of new libraries/modules/tools for doing web development in CL — the benchmarks (as you correctly point out) are a minor detail.
  - apgwoz 12y ago
    Perhaps you should read more carefully. "If you're assuming ..." It's just not clear from the context we have. But, caution! Microbenchmarks should only be Microtrusted.
- adrianm 12y ago
  I think this is truly sagely advice. My grand takeaway from Aphyr's Jepsen series (http://aphyr.com/tags/jepsen http://aphyr.com/tags/jepsen) is that the more sophisticated software becomes in the never-ending quest for features and performance, the more likely the fundamentals underlying it have been overlooked, glossed over, or ignored completely.
  - eudox 12y ago
    When you compare the time fukamachi's spent on these libraries to the time spent on Clack, Caveman, etc., it's pretty clear there's obsession with performance. As aroman said, "The real story here is that people are working on a number of new libraries/modules/tools for doing web development in CL".

wspeirs 12y ago

Just curious what about this parser makes it faster? Can anyone give a basic explanation?

easytiger 12y ago
Well if you implemented the c parser with precisely the same algorithms the c one would become faster, so one can assume they have totoally different underlying implementations
- haberman 12y ago
  That is not necessarily true (and I say this as someone who heavily favors C for parsers). An implementation with a JIT will likely be able to optimize away work by noticing that the table of callbacks is empty. I would be more impressed if the callback table was not empty (and the callbacks actually did something, like increment an integer) and Lisp was still winning. EDIT: I see others saying that SBCL is AOT, not JIT. If so I'd be very interested to look at the disassembly side-by-side and see an explanation for why SBCL is winning.
  - muyuu 12y ago
    SBCL is a compiled Common LISP (even in interpreted mode, it compiles every eval-ed lambda before calling it). On the other hand there is nothing inherently stopping the optimiser from optimising the resulting code as well or better than GCC or any C compiler. Theoretically it could produce optimal machine code.
    - haberman 12y ago
      Correct me if I'm wrong but I was under the impression that Common Lisp is memory-safe (implying guards like bounds-checks), dynamically typed (implying type checks) and garbage collected (implying GC overhead).
      - muyuu 12y ago

haberman 12y ago

I was not able to run the benchmark for Lisp. What Lisp implementation is expected? I tried CLISP and got: *** - READ from #<INPUT BUFFERED FILE-STREAM CHARACTER #P"benchmark.lisp" @1>: there is no package with name "SYNTAX"

deleted 12y ago
[deleted]
eudox 12y ago
I'd recommend SBCL, since a high-performance JIT compiler is likely to give more representative results than a bytecode VM like CLISP. Plus, I'd expect some minor portability errors to arise when you push the envelope like this. By the way, your error seems to be that the cl-syntax library is not being found, as opposed to a portability problem, so maybe you don't have Quicklisp installed and loaded?
- haberman 12y ago
  > By the way, your error seems to be that the cl-syntax library is not being found, as opposed to a portability problem, so maybe you don't have Quicklisp installed and loaded? Indeed I don't, I didn't know to install it since it wasn't listed as a dependency. Thanks for the info!
  - eudox 12y ago
    Quicklisp is CL's package manager, so that's necessary to install dependencies. You can install it with: $ curl -O http://beta.quicklisp.org/quicklisp.lisp $ sbcl --load quicklisp.lisp \ --eval '(quicklisp-quickstart:install)' \ --eval '(ql:add-to-init-file)' \ --quit
- gjm11 12y ago
  Pedantic correction: Unless something's changed very radically since I last looked, SBCL's compiler is AOT not JIT. (Though in interactive use it compiles things as you enter them, which I suppose is kinda JIT if you look at it from just the right angle and squint.)

halayli 12y ago

parsed = http_parser_execute(parser, &settings_null, buf, strlen(buf)); assert(parsed == strlen(buf)); He's calling strlen(buf) twice here. There's no guarantee that this is optimized at compile time. Usually len of buf is determined from read/recv system calls and for a fair comparison strlen should be removed here.

Ono-Sendai 12y ago
assert only runs in debug mode anyway.
- haberman 12y ago
  It runs unless NDEBUG is defined, which the author did not do according to his methodology. Anyway I looked at the assembly output and strlen() is optimized away.
  - webreac 12y ago
    I really do not like when bad habits are encouraged by the optimizer.
- halayli 12y ago
  no, that's not correct. http://pubs.opengroup.org/onlinepubs/009695399/functions/assert.html http://pubs.opengroup.org/onlinepubs/009695399/functions/ass...
  - aidenn0 12y ago
    "Forcing a definition of the name NDEBUG, either from the compiler command line or with the preprocessor control statement #define NDEBUG ahead of the #include <assert.h> statement, shall stop assertions from being compiled into the program"
fukamachi 12y ago
No difference even though I ran the benchmark again after removing the line.

Animats 12y ago

Is parsing HTTP headers a major bottleneck? HTML parsing, sure, especially with the horrors of HTML 5 error handling per the spec and the need to back up after guessing the character set. But HTTP headers are not that big or complex.

eudox 12y ago
From the Reddit thread: http://www.reddit.com/r/lisp/comments/2klhpn/quri_a_uri_library_for_common_lisp_6x_faster_than/clmsfzd http://www.reddit.com/r/lisp/comments/2klhpn/quri_a_uri_libr... >Right. When I was profiling Wookie, I found URL parsing was the third bottleneck (the first is HTTP request parsing, and the second is libevent2).
- Animats 12y ago
  Yes, that's really important for compatibility with Google Wave.
edsiper2 12y ago
HTTP protocol grammar is pretty simple, but parsing correctly considering the server side and desired performance may be hard. By nature parsing strings is expensive (not sure why they designed HTTP in string format, binary would save a ton of power in processing). So imaging you are receiving a request, most of the time due to Network latency (client or server side), you don't get the full Request at once, most of the time you need to perform a couple of read(2) operations. Now, what do you do on each read ?, did you manage full state ?, how many parsing rounds ?, how to catch the end of the protocol block , etc etc etc. So answering your questions I would say "YES", the HTTP protocol in a Server "may be" a bottleneck if its not well implemented. In our HTTP Server project[0] we are working in a new parser to improve performance, so for real, this is a very important topic. [0] http://monkey-project.com http://monkey-project.com best

thu 12y ago

In the HTTP benchmark game, there is also Bryan O'Sullivan's attoparsec-based parser: http://www.serpentine.com/blog/2014/05/31/attoparsec/ http://www.serpentine.com/blog/2014/05/31/attoparsec/ The important point is that the parser is a few dozen lines of code (i.e. it relies on a general parsing library instead of being custom hand-written code).

verytrivial 12y ago

This reminds me of John Fremlin's work back in 2009 http://john.freml.in/teepeedee2-c10k http://john.freml.in/teepeedee2-c10k . (Hello, John!)

_RPM 12y ago

Is Lisp a write-only language?

adwf 12y ago
I'll assume this is an honest question - not a troll (and hence don't deserve the downvotes), but no, Lisp isn't write-only. It's an immensely flexible language that lets you code in a variety of different styles, so you can end up with code spaghetti. But that doesn't mean that you have to, or even that it's the most likely thing to happen. If you compare it to idiomatic Perl, where a lot of the community seem to get obsessed with the famous one-liners, Lisp seems a lot better to me. And if you follow a decent style guide like: https://google-styleguide.googlecode.com/svn/trunk/lispguide.xml https://google-styleguide.googlecode.com/svn/trunk/lispguide... Then there's no particular reason why you should end up with disaster code anymore than in any another language. I'd rather read a single page of Lisp, than the equivalent numerous pages of Java or some other verbose language.
aerique 12y ago
Coming from Common Lisp and having tried out Haskell recently I can ask the same about the latter while I find Lisp to be one of the most readable languages out there. It's basically what you're used to and for Lisp it does not take long to get used to.
wnewman 12y ago
The old book _Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp_ contains a number of nontrivial programs (like an Othello player and a little symbolic math program). AFAIK, most people think the code is unusually clear, both a good example of how to write clear CL programs and a good example of clear programming period (independent of language). If you are seriously interested in clarity of CL programs, I recommend taking a look at that book.

serbrech 12y ago

Hmm, I can't really write lisp, but, how maintainable is this?? https://github.com/fukamachi/fast-http/blob/master/src/parser.lisp https://github.com/fukamachi/fast-http/blob/master/src/parse...

adwf 12y ago
It could do with some comments and doc-strings certainly, but I'd give it a pass for now as it's a new project. As for the code, I imagine that in any language, highly optimised programs can start looking pretty odd after a while. Try understanding "grep" for example: http://git.savannah.gnu.org/cgit/grep.git/tree/src/grep.c http://git.savannah.gnu.org/cgit/grep.git/tree/src/grep.c As a guy not particularly proficient in C, that looks crazy to me. Although it does at least have decent comments, which I'd expect for such a mature project!