From time to time, I have the need to parse relatively small, fixed width binary messages. Like a ITCH 4.1 MoldUDP64 packet from our buddies over there at NASDAQ. Parsing should also be reasonably quick. And I’m lazy. ~~Writing parsers by hand~~ Maintaining handwritten parsers is no fun.
So I’m going to define our parser in Ragel, a parser generator for regular languages (think: regular expressions). It targets C/C++ and some other languages I don’t care about. Like Objective-C, D, Java and Ruby. We’ll focus on C99.
This example parser will handle a cut-down view of the ITCH spec. The full source for this post is available over on GitHub. We’re looking for order executions:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Ragel’s compiler does a bunch of optimization and pumps out a hot mess of GOTOs that regular C compilers like gcc, icc and clang eat for breakfast every day. This parser really isn’t very exciting:
Particularly when compared to a complete, validating ITCH parser:
An autovectorizing compiler can turn these state machines into machine code on par with some of the finest hand-rolled parsers. clang/LLVM does a decent job, adequate for now… but it also has some magic just hidden below the surface for Haskell developers. Namely an LLVM backend.
Typically we’d go ahead and consume parsers like these in GHC with a vanilla foreign import. But even with an unsafe import there is a relatively fixed amount of overhead due to switching calling conventions and loading out parameters. Normally this isn’t such a big deal, but we’re dealing with a lot of packets during simulation, billions and billions, and I’d like to dedicate some CPU to a task more productive than parsing.
To adopt GHC’s calling convention, we need to make our C code look enough like Haskell so they’ll play nice together. The first step is to define a function signature that looks like a regular STG function. The same thing that GHC generates. Like so:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
This is still a ccall function but we’ll fix that later. There is currently no way to define this as cc10 (LLVM’s internal name for GHC’s calling convention) in clang.
Step two is to jump to the return address, which lives on top of the STG stack (the sp argument)… with the desired arguments, like the results of parsing, in tow. This is a regular function call that gets converted to a tailcall later on by llc, LLVM’s native compiler, when using cc10.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Compile it down to LLVM assembly…
And run it through sed to fix up the calling convention for the code generator… this is the magic part. Note: this is also overly general and will break any legit C calls. llc then pumps out an object file that GHC will link with later:
The last bit is to create a foreign primop import in Haskell. Many messages don’t fit within the 5 free registers (R2-R6) that are available here and need to be partially loaded onto the stack. In this example I’m just discarding the ‘printable’ flag to make everything fit in registers. Managing the stack is more involved. Perhaps I’ll cover it in a future post.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
I spent an hour hacking together a simple benchmark suite and posted the results. If you’ve kept reading this far you might find it interesting.