git.iko.soy/typeable/attoparsec
on 0.13.0.1 help sign in
typeable/attoparsec/doc/whats-in-a-parser-1.md
88 lines 4.0 kB history raw
1My goal in working on the
2[new GHC I/O manager](http://www.serpentine.com/blog/2010/01/22/new-ghc-io-manager-first-benchmark-numbers/)
3has been to get the Haskell network stack into a state where it could
4be used to attack high-performance and scalable networking problems,
5domains in which it has historically been weak.
7While it's encouraging to have an excellent networking stack (Johan
8and I now have this thoroughly in hand), the next thing I'd look for
9is libraries to help build networked applications. One of the
10fundamental things that such apps need to do well is parse data, be it
11received from the network or read from files.
13The Haskell parsing library of first resort has for years been
14[Parsec](http://www.haskell.org/haskellwiki/Parsec). While other
15capable libraries exist
16(e.g. [polyparse](http://hackage.haskell.org/package/polyparse) and
17[uu-parsinglib](http://hackage.haskell.org/package/uu-parsinglib)),
18they don't appear to see much use.
20As appealing as Parsec's API is, it has a few problems:
22* Parsec 2 is slow, and it has high memory overhead, due to its use of
23 Haskell's `String` type for tokens. Parsec 3 can use the more
24 efficient `ByteString` type (which is in any case much more
25 appropriate for networked applications that deal in octets), but it
26 achieves this flexibility at the cost of being even slower than
27 Parsec 2.
29* Parsec's API demands that all of a parser's input be available at
30 once. People usually work around this by feeding a Parsec parser
31 with lazily read data, but lazy I/O is at odds with my goal of
32 writing solid networked code.
34What properties should a parsing library for networked applications
35ideally possess? There are a few obvious desiderata that have been
36well known for years. For example, it's important to have an appealing
37API and programming model. Parsec squarely fits this desire.
39Performance is also a big consideration. Ideally, a parsing library
40would be fast enough that you wouldn't feel any real need for either
41of the following:
43* A few weeks to write an insane hand-bummed parser.
45* Mechanical parser generators or lexers
46 (e.g. [happy](http://www.haskell.org/happy/) or
47 [alex](http://www.haskell.org/alex/)).
49There are some additional important constraints on a realistic
50library: it must fit well into a highly concurrent networked world
51full of unreliable, hostile and incompetent clients.
53* High concurrency levels demand a low per-connection memory
54 footprint.
56* The need to cope with poorly behaved clients requires that
57 applications must be able to throttle connections that are too busy,
58 or kill connections that are too slow or attempting to consume too
59 many server resources. A good parsing library will not get in the
60 way of these needs.
62A few years ago, I made a few half-hearted attempts to write a
63specialised version of Parsec, which I eventually named
64[Attoparsec](http://hackage.haskell.org/package/attoparsec).
66I began with a stripped-down Parsec that was specialised to accept
67`ByteString` input. I then extended the API to allow a parser to
68consume small chunks of input at a time.
70Because I wasn't using Attoparsec "in anger" at the time, I made sure
71that my library worked (more or less), but I was not measuring its
72performance.
74In late January of this year, I began to think about using Attoparsec
75as the parser for a simple HTTP server that I could use to benchmark
76our new GHC I/O manager code. Clearly, I'd want the parser to perform
77well, or it would distort my numbers rather badly.
79By coincidence, [John MacFarlane](http://johnmacfarlane.net/) emailed
80me around the same time, with disturbing findings: he'd tried
81Attoparsec, and found its performance to be *terrible*! In fact, it
82was 4 to 20 times _slower_ than plain Parsec with his experimental
83parser and test data. Clearly, I had some hard work to look forward
84to.
86Happily, that work is now almost complete, and I am pleased with the
87results. In the next post, I'll have some details of what this all
88entails.