Faster parser using FFI?

[winterland1989]

Recently we found a bottleneck in our data pipeline which read json from upstream and routing them into downstream, during benchmark aeson show the expected throughtput(5070MB/s), but a nodejs guy in our team showed that v8 can do even better(about 35 time faster on parsing).

I tried many optimization including use multiple ghc thread and Chan, but still can't defeat a single threaded v8 on parsing, on the other hand, encoding seems on pair with v8. it makes me wondering if we can do better by use some fast c code, for example like what json-stream does. Any idea welcomed!

N.B. In benchmark aeson still beat go version, this's not a complaint thread, just want to start a discussion on further optimization possibilities : )

[phadej]

How do you parse the data with aeson. Do you use Generic, TemplateHaskell or manual deriving? Parsing into ADT (with all checks), costs some CPU. Or just parsing into Value? Do you data has a lot of ints, or some other specific characteristics (I'm quite sure, that going thru Scientific slows parsing a bit, but we care about correctness).

I doubt that with current overall architecture/feature set we can get constant factors much lower.

It would be nice to know how json-stream compares to aeson. Do you want to add benchmark (I guess Typed.hs is most interesting, using twitter data)

[winterland1989]

I first designed the ADT version (hand roll instance) which is replaced by nodejs now，during benchmark we directly parse into Value because I think it's not fair to Haskell version if we count addtional ADT construction, but benchmark showed that the ADT construction time is negligible.

I will try to make a bench on json-stream, we did use Twitter sample json actually, the one around 60KB.

[phadej]

If you can share the benchmarks, it would be great!

[winterland1989]

The benchmark code is here, result:

benchmarking twitter10.json/aeson parser
time                 137.3 μs   (135.7 μs .. 138.8 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 138.0 μs   (136.8 μs .. 139.2 μs)
std dev              4.272 μs   (3.694 μs .. 5.045 μs)
variance introduced by outliers: 28% (moderately inflated)

benchmarking twitter10.json/json-stream parser
time                 86.81 μs   (86.16 μs .. 87.51 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 87.34 μs   (86.61 μs .. 88.11 μs)
std dev              2.664 μs   (2.139 μs .. 3.485 μs)
variance introduced by outliers: 29% (moderately inflated)

benchmarking twitter100.json/aeson parser
time                 2.037 ms   (1.998 ms .. 2.089 ms)
                     0.997 R²   (0.996 R² .. 0.999 R²)
mean                 2.008 ms   (1.989 ms .. 2.028 ms)
std dev              63.81 μs   (50.29 μs .. 92.05 μs)
variance introduced by outliers: 18% (moderately inflated)

benchmarking twitter100.json/json-stream parser
time                 1.841 ms   (1.818 ms .. 1.864 ms)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 1.869 ms   (1.854 ms .. 1.887 ms)
std dev              55.99 μs   (41.72 μs .. 84.62 μs)
variance introduced by outliers: 16% (moderately inflated)

Note the larger json, the heavier gc stress, and slower deepseq operation. a conservative approximation in our case where average json size is around 20KB, 30% speed up can be made by just switching to json-stream.

[winterland1989]

An interesting finding is that unescape maybe a key factor, since this is the only heavy weight operation i can think of which may get improved by doing in c.

I push a special benchmark to escape branch in previous repo to compare aeson's jstring parser with json-stream's string parser, here's result:

benchmarking escape.txt/aeson parser
time                 17.48 μs   (17.24 μs .. 17.72 μs)
                     0.998 R²   (0.998 R² .. 0.999 R²)
mean                 17.54 μs   (17.35 μs .. 17.75 μs)
std dev              658.5 ns   (547.3 ns .. 878.9 ns)
variance introduced by outliers: 44% (moderately inflated)

benchmarking escape.txt/json-stream parser
time                 4.879 μs   (4.797 μs .. 5.007 μs)
                     0.996 R²   (0.990 R² .. 0.999 R²)
mean                 4.901 μs   (4.848 μs .. 4.992 μs)
std dev              238.9 ns   (138.9 ns .. 458.5 ns)
variance introduced by outliers: 61% (severely inflated)

benchmarking noescape.txt/aeson parser
time                 7.070 μs   (7.005 μs .. 7.139 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 7.013 μs   (6.940 μs .. 7.100 μs)
std dev              262.5 ns   (216.2 ns .. 336.2 ns)
variance introduced by outliers: 47% (moderately inflated)

benchmarking noescape.txt/json-stream parser
time                 5.106 μs   (5.067 μs .. 5.147 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 5.157 μs   (5.104 μs .. 5.221 μs)
std dev              197.6 ns   (154.6 ns .. 273.4 ns)
variance introduced by outliers: 49% (moderately inflated)

[winterland1989]

So basically i think porting json-stream's c version unescape may make quite big improvement for aeson, @ondrap , would you be interested in making a patch?

[winterland1989]

And from this, it seems v8 switched string to utf8 representation already. In JSON case, v8 has a nature advantage.

[phadej]

Good we find at least one reason.

FWIW, I'd avoid using C, it makes things much more complex than needed (e.g. for windows users). If unescape is slow, i'm sure it can be made faster in pure Haskell. I.e. not use Zepto but manually iterate over both. I'm sure it's doable.

[neongreen]

text itself uses C, so if Windows users had a problem with C they already wouldn't be able to install aeson (which depends on text). I see no problem with using C to implement something C is good at and Haskell isn't.

[phadej]

Hmm, I see. Have to refresh my experience with Haskell + Windoes.

Well, I guess it's maintainers job to decide how they want this to be done. If using json-streams decoding function is ok, why not, it's done.

[winterland1989]

Another problem with current jstring parser is that it tranverse the buffer twice, one for unescape, one for UTF16 decode which is done by text, the c parser in json-stream did these in one pass, while I don't think it easy to achieve with pure code, I will try.

[winterland1989]

Yes, if maintainer thinks okay, reuse c code is better. The Zepto parser is made into transformer due to escape IIRC.

[ondrap]

Json-stream does it in 2 passes too, but differently - and both in C. It first extracts the 'raw' bytestring and then it unescapes & decodes from utf-8. I am not sure how ease would it be to integrate into aeson as I feel it probably parses & decodes on-the-fly (I might be wrong though). Also, there should be some way to handle incremental parsing, which the json-stream function doesn't - in case a string appears over block boundary, it just concatenates the bytestrings and calls the unescape on the whole block.
I think there would be a code review needed for the C function - it is the code where you don't see the obvious bugs... unfortunately I don't see much better way to structure the code.

[winterland1989]

@ondrap, by saying two pass I mean looping the buffer twice, I don't think json-stream's c code do that, the _js_decode_string loop once and direct write into a uint16_t buffer. is that true?

[winterland1989]

Json-stream does it in 2 passes too, but differently - and both in C. It first extracts the 'raw' bytestring and then it unescapes & decodes from utf-8.

I understand what's your point now @ondrap , actually aeson does exactly the same, first extra raw bytestring and then decoding, but aeson traverse the buffer twice during decoding: first with unescape :: ByteString -> Either String ByteString, then with decodeUtf8' :: ByteString -> Either UnicodeException Text, so aeson effectively does a triple loop to decode JSON string.

Note this will hit a lot because the key of JSON object need to be unescaped too, not only the string value, so here is my plan:

1. borrow c code and json-stream's unescape :: ByteString -> Either String Text to aeson.
2. use aeson's existing jstring parser to build a reference test function, then use Quicktest to make sure new unescape are exactly the same one with previous one. (This is a bit tricky because i don't know how to make sure Quickcheck generate proper escaped utf-8 encoded JSON string, maybe we should use QuickTest generate Text and use aeson to encode).
3. after we make sure the new unescape works as expected, we build a new jstring parser based on it, and do benchmark to see if this move make aeson faster, if faster, how much.

I'm pretty sure the result will be postive, since currently aeson's jstring loop more, and call into c via text too, but we have to wait to see if all this actually works.