A fast HTTP request/response parser for Common Lisp

by fukamachi • 12 years ago

131 73 12 years ago

eudox9• 12 years 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

[1] https://github.com/fukamachi/woo

[2] https://github.com/fukamachi/clack

pnathan2• 12 years ago

Fukamachi has done some stellar work. I've used his code and have generally been very happy with it.

rgbrgb• 12 years ago

(That outperforms Node!)

In what way? All of the benchmarks I'm seeing on that page indicate otherwise.

eudox9• 12 years ago

When he first posted it, it did, it looks like recent changes have brought that down:

https://github.com/fukamachi/woo/commit/be4a0db688af05ee204e...

thirsteh• 12 years ago

It would be quite surprising if it did, since Node's HTTP parser isn't Node/JavaScript, but highly optimized C.

negativeview3• 12 years 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...

PuercoPop5• 12 years ago

out of curiosity, what did you found horrible about string handling?

bkurtz13• 12 years ago

Try Clojure

TheMagicHorsey• 12 years ago

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

apgwoz2• 12 years 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• 12 years 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.

adrianm2• 12 years ago

I think this is truly sagely advice.

My grand takeaway from Aphyr's Jepsen series (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.

ska• 12 years ago

I'm curious, why would you assume that?

The primary benefit and cost, depending on your point of view, of clojure is that it runs on the JVM. I don't see how that would be a strong argument for or against using this tooling for any problem domain unless you were already committed to or against the JVM for other reasons.

PuercoPop5• 12 years ago

Being able to run on the JVM is not a differentiating factor among lisps. Kawa Scheme and ABCL give you access to Java Libraries.

If you ask me the strengths of Clojure that it is built upon abstraction/interfaces (ie. conj instead of cons) and how it manages hygiene while retaining quasiquotes templates leveraging clj's namespaces. But then again you should probably ask a clojurian instead.

pnathan2• 12 years ago

I've generally been happy with my use of Common Lisp in the web environment - it's had a long-standing presence there. I've personally not found deployment the most happy story, but I expect that with the rise of Docker, shipping a Common Lisp image in a Docker image will be a very popular method of deployment.

147• 12 years ago

Can somebody give arguments for using Racket or CL for web dev? Whenever I evaluate Lisps I end up choosing Clojure because to me it seems to be the most practical to develop web apps in.

jwr• 12 years ago

I don't think you should look for arguments. Just try it. Write something in every one of the environments you are considering and you'll learn more than you ever could from reading online discussions.

As a data point, I moved from Common Lisp to Clojure and never regretted it. But the reason I switched was not because I read something online, but because of Clojure's concurrency support, which means I can create concurrent software that is robust.

wspeirs• 12 years ago

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

easytiger• 12 years 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

haberman5• 12 years 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.

patrickmay• 12 years ago

Possibly, but you might not be able to do that without implementing enough of Lisp to allow the algorithms to be implemented, as per Greenspan's Tenth: http://c2.com/cgi/wiki?GreenspunsTenthRuleOfProgramming

muyuu3• 12 years ago

Not necessarily true, although C compilers are usually very good.

PuercoPop5• 12 years ago

Why do you think that? Is it because most languages compile to C? That is not the case with most CL implementations. (ej. CL & CCL).

Although I agree that it is generally the case, you can read here[0] for an example where CL would gain an advantage over C compilers. Albeit in an implementation specific way.

[0] http://www.pvk.ca/Blog/2014/08/16/how-to-define-new-intrinsi...

haberman5• 12 years 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"

eudox9• 12 years 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?

haberman5• 12 years 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!

gjm11• 12 years 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.)

halayli4• 12 years 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• 12 years ago

assert only runs in debug mode anyway.

haberman5• 12 years 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.

halayli4• 12 years ago

no, that's not correct.

http://pubs.opengroup.org/onlinepubs/009695399/functions/ass...

fukamachi2• 12 years ago

No difference even though I ran the benchmark again after removing the line.

halayli4• 12 years ago

Interesting. I was expecting at least cpu branch improvements given the lack of assert.

halayli4• 12 years ago

Also use gettimeofday() instead of clock(), because you don't know how far into the second you are at the time it's called.

jeffreyrogers• 12 years ago

Any good compiler will optimize that out. (Actually, even a bad compiler will optimize that out... it's a really easy optimization).

Animats2• 12 years 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.

eudox9• 12 years ago

From the Reddit thread: 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).

Animats2• 12 years ago

Yes, that's really important for compatibility with Google Wave.

edsiper2• 12 years 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

best

thu• 12 years 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/ 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• 12 years ago

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

_RPM• 12 years ago

Is Lisp a write-only language?

adwf2• 12 years 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...

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.

aerique2• 12 years 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• 12 years 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• 12 years ago

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

adwf2• 12 years 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

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!

A fast HTTP request/response parser for Common Lisp

Related Stories