Simdjson – Parsing Gigabytes of JSON per Second (opens in new tab)

From “Design Decisions”[1]:

> JSON. The protocol for front-end / back-end communication, as well as between the back-end and plug-ins, is based on simple JSON messages. I considered binary formats, but the actual improvement in performance would be completely in the noise. Using JSON considerably lowers friction for developing plug-ins, as it’s available out of the box for most modern languages, and there are plenty of the libraries available for the other ones.

1: https://github.com/xi-editor/xi-editor/blob/master/README.md...

Because JSON encoding/decoding was not found to be a typical performance bottleneck, and because JSON is supported in virtually every programming language (Xi allows you to write frontends in pretty much any language you want).

After spending most of a year doing deep surgery on systems that used CBOR extensively, I can report that the common CBOR parsers are not faster than common JSON parsers; surprisingly, they are actually slower. CBOR is also not easier; it's much less widely supported, and you need a separate debugging representation. It does have three real advantages over JSON: it supports binary strings, it's a monument to Carsten Bormann's ego, and data encoded in CBOR takes slightly fewer bytes than the same data encoded in JSON. (The second is only an advantage if you're Carsten Bormann.)

While theoretically true, in practice the actual character parsing tends to a small to negligible part of the overall time. Which leads to the measurable fact that on macOS/iOS, the JSON serialization stuff is actually one of their fastest, faster than their binary stuff.

Yeah, I've done some analysis, it's creating a ton of objects to conform to the Codable protocol, and a lot of those objects are for codingPath, which is updated for basically every node in the tree. It's not a mystery, we just don't know the best way to fix it.

Can you see any differences with different levels of optimization? I recall a presentation at some point where the old obj-C style compiled code did a lot of checks before and after calling a method ("does this object listen to this message?"), while with an optimization option enabled (whole module optimization?) these calls could be optimized out. That is, with Swift they can make the resulting machine code less er, "checking for safety", so to speak.

That resonates well with my conclusions that led to the Replicated Object Notation project. [1]. If the parser creates an AST tree or some number of dictionaries or some other bullshit... "now you have two problems", that's it.

I settled on a tabular-log format, which is streamed and immediately consumed most of the time, no intermediate object structures.

Then, that "text vs binary" distinction became mostly moot. The binary is slightly more efficient, but grossly less readable, so no big gain, unless at grand scale.

[1] http://replicated.cc

You might want to check out the benchmark I wrote to compare exactly that.

https://github.com/jeremywiebe/json-performance

Swift has JSONEncoder and JSONDecoder types to do Codable, though internally they have to encode to/decode from the Foundation objects that JSONSerialization produces.

Hadn't seen that particular wrapper, but if we're going to take on an FFI solution, we're more likely to use Rust for this, and implement more logic than just JSON parsing.

I would be extremely surprised if we were somehow accidentally using MMX; it's not our intention. It is my belief that we are using only AVX2, which, like the 19-year old SSE/SSE2 extension, has its own registers that are independent of the x87 floating point set.

If, once you review our codebase and verify that we are not inadvertently using a 22-year-old SIMD extension but still have undefined behavior, please write an issue on github.

I'm admiring Rust from a distance at this stage. I am comfortable enough with writing bare intrinsics and slapping a giant #ifdef around stuff.

> there is great portable SIMD support over there

It's not stable yet. The only stable SIMD stuff Rust supports is access to the raw x86 vendor intrinsics.

reading lots of small files on s3 or local filesystems is tricky. a million devices with one dozen files, so lets say 12 million files.

One thing locally is each file takes up a full block. So even if you only need 500 bytes of data in a file, and a block is 4kb, youve wasted 3.5kb of space and IO. Multiply that by a million and youre wasting gigabytes of space.

In S3, listing 12 million files takes 12 thousand http(max return is 1000 items). So that would take two minutes if you assume its 10ms per round trip. Let's say you wanted to read each file, and again each read takes 10ms.. youre looking at 1.4 days. Obviously this can be parallelized, but when you look at the raw byte size this is a huge overhead, and this is just to read one day of data.

If you concatenate the files together to get a reasonable size and number of files, raw json on s3 is really powerful. Point athena at it, and you just write sql and it handles the rest, and is serverless. But it does make single row lookups more expensive(supplementing with dynamodb could keep it serverless if single row lookups are frequent).

lots of optimizations will get improvements, like parquet that tobilg mentioned(binary format and columnar), but anything with a decent file size will work.

You may enjoy this:

The best way to not lose messages is to minimize the work done by your log receiver. So we did. It receives the uploaded log file chunk and appends it to a file, and that's it. The "file" is actually in a cloud storage system that's more-or-less like S3. When I explained this to someone, they asked why we didn't put it in a Bigtable-like thing or some other database, because isn't a filesystem kinda cheesy? No, it's not cheesy, it's simple. Simple things don't break.

https://apenwarr.ca/log/20190216

We‘re using AWS Kinesis delivery streams to batch incoming JSON messages from IoT devices to Parquet files in S3. Those can directly be read by different AWS services like Redshift, EMR or Athena...

You’ve kinda just described AWS Athena.

I am replying to you as an engineer at an IoT company that provides SaaS in AWS for the data our devices produce. To solve this problem, we transmit our data in a proprietary "raw" binary format that then gets parsed into a protobuf. All data for a given UTC day is appended to this protobuf file and hosted in S3. Retrieving data requires downloading the protobuf file from S3, unmarshalling the protobuf, and finding the entry you care about.

If you are considering using plain files instead of a DB server, you could try a compromise and use an embedded key-value store like RocksDB, LevelDB, BadgerDB etc.

It's local storage only, limited query capabilities depending on the DB, but should be extremely fast.

Why not use a timeseries database, like http://btrdb.io?

well if you need indexed lookups, then use a database

if you're doing "table scan" processing of entire datasets, sure just-a-bunch-of-files would work too.

Databases can be surprisingly fast for things like that, since high performance file i/o is full of tricky/annoying stuff that databases have already optimized for.

Depending on your size / budget / needs Snowflake may interest you. https://www.snowflake.com/product/architecture/.

I haven't used it but have been given a presentation by them on it, and it was very very good.

They store data in S3 and use FoundationDB for indexes. You can feed it JSON and it'll index it and let you query it on a massive scale shockingly fast.

Obviously they are not aimed at small hobby projects but if your project has money / serious product depending on your needs it's well worth looking at.

On the S3 cheaper / smaller end you can batch up data daily / weekly etc. So the landing bucket acts as a queue that gets processed creating daily batch files from the small files aggregated together. You can then take the daily batches to create weekly batches etc etc, essentially partitioning. This will reduce the total number of files needed to query. If you use deterministic names based on how you plan to query this can also reduce the number of files you need to list / parse. When batching / re-partitioning the data you can also use the Apache Parquet format to compress a little better + also import in some of the querying tools out there.

It's not magic. The things that enable writing this kind of code are essentially practice and specialization. Most people have to write code that works all all architectures and where performance is probably less critical than having a simple, workable codebase - so the opportunities to practice writing SIMD code are rare under those constraints.

Unfortunately, the fragmentation of SIMD standards and various pitfalls in implementation (the much ballyhoo'ed "running AVX will make your processor clock to half its speed or something" exaggerations, for example) make a lot of people nervous about putting in the time to commit to developing expertise, which is a shame.

Not really a question, but if you ever get to the point of wondering what a good next challenging project would be, consider generalizing some of these techniques into a next generation Yacc / Bison replacement.

Something that can take generic grammer rules and turn it into a high performance parsing engine.

It wouldn't have to support every possible grammar or option. Json isn't that complex of a language, but even a limited set of grammar options in exchange for a performant parser could be of benefit for a very large set of problems.

Probably not too hard. It would come down to how easy it is to detect quoting conventions so you don't accidentally parse () chars in strings. JSON is medium-easy. I don't know where the canonical definition of s-expressions you're using comes from (is it just Common Lisp?) so I don't know how this works.

We'd like to have some more examples of formats people care about - I'm interested in generalizing this work. So if you want to followup with more detail please do.

Thank you. More description of the work will be forthcoming but please be patient (for non-sinister reasons).

Jsmn it's already pretty fast and simple. How the hell can be a lot faster than that? I'm very curious.

More performance details beyond what's on the site will follow (in a while).

We use RapidJSON in the high-performance mode not the funky mode that minimizes FP error (which is some astounding work - I had no idea that strtof was so involved!). Number conversion is not our #1 focus - doing it well is nice, but all implementations have access to the same FP tricks, so you don't really learn much by going wild on this aspect.

At least, you don't unless FP conversion is your focus, in which case you should share your FP conversion code with everyone!

I'm not aware of an article that covers a actual implementation or that has a benchmark of performance. As for GPGPU: it's possible. Our first stage of matching is very parallel. But Amdahl's law would, of course, suggest that the serial parsing step would dominate.

I'm interested in this: some aspects of our very serial 'stage 2' (the parsing step) could be made parallel. This would be very interesting. Unfortunately I personally cannot be made parallel, so working on this needs to go into a big queue with a lot of other work.

Daniel Lemire did most of the work on the number handling, but our general approach was to try to do work that's similar to what the bulk of other libraries do. I believe pretty much everyone throws oversize numbers on the floor.

I don't think it would be hard at all; it would just be extra effort that wasn't needed to run obvious comparisons.

Honestly? I was trolled into it. :-) Unemployed people do weird things.

I can't speak for Daniel's motivation.

This would imply an ARM port, I guess, as x86 android isn't much of a thing anymore AFAIK.

I don't think either of us know much about android - not enough to do that. But an ARM port is very interesting.

Since I'm no longer an Intel employee I don't see why I shouldn't skill up and do a Neon port (I got interested in SVE, but since ARM doesn't seem to want to bother releasing cores that run SVE, I'm not going to go too far down that path right now). Neon, on the other hand, is in tons of places. As far as I know all the required permutes, carryless multiplies and various other SIMD bits and pieces are there on Neon. So it's a simple matter of porting.

Parsing itself doesn't need jitting but as soon as you start to use the parsed data to interface with some typed containers the data plumbing consumes much more time than parsing does and drags down all the optimization. For parsing to interact well with static languages jitting is a possible solution to look at.

For node.js, I wrote a lib that can selectively parse JSON subtrees:

https://gitlab.com/philbooth/bfj

The specific function of interest here is `bfj.match`, which takes a readable stream and a selector as arguments:

https://gitlab.com/philbooth/bfj#how-do-i-selectively-parse-...

It still walks the full tree like a regular parser, but just avoids creating any data items unless the selector matches. Though there is an outstanding issue to support JSONPath in the selector, currently it only matches individual keys and values.

It’s not exactly the lazy parser you describe, but Sparser[1] builds filters to exclude json lines/files that can’t contain what you’re looking for, and only parses those that might.

The Morning Paper’s writeup[2] from last year provides a good summary

[1]: http://www.vldb.org/pvldb/vol11/p1576-palkar.pdf [2]: https://blog.acolyer.org/2018/08/20/filter-before-you-parse-...

That's what our first stage does, pretty much. I would imagine we do it way faster than re2c would do it.

Parsing the entire document lock stock and barrel is an easier thing to write about and benchmark. The problem is with skipping around and pulling out bits of JSON from a benchmarking framework is that attempting to present such data often amounts to "hey, we asked ourselves a question and then we got a really good answer for it!". It's hard to picture what a 'typical' query for some field over a JSON document would look like. Conversely, it's pretty easy to know when you finished parsing the Whole Thing.

I'm not sure what you mean by arbitrary? What parsing in this case means e.g. turning a string of digits into a ieee754 float number in memory. I think this project is meant to accelerate this part with SIMD, but a greater improvement can be obtained by simply not doing this for as much data as possible. If the actual materialized data constitutes a small part of the original, there should be ways to do minimum work for the rest.

In jvm-land circe-fs2[1] is a streaming Parser.

[1]: https://github.com/circe/circe-fs2/blob/master/README.md

"Unforgivable" is a bit strong. I don't think this is something which invalidates our entire approach - nothing in the algorithm depends on this behavior as the \0 chars don't appear until quite late. Even then, we are not dependent on sighting a \0 in our string normalization and as such we can probably just store a offset+length in our 'tape' structure rather than assuming we have null terminated strings.

Please add an issue on Github.

Edit: I went ahead and added an issue. Seems like something we should fix.

The parsed format in tape.md is quite close to the flatbuffer format. Flatbuffer can encode any json file just fine. The parse time is immediate and requires no extra memory.

It’s a great way to store big json files where you only want to access a subset of data very quickly and not load the whole file into memory.

https://google.github.io/flatbuffers/

> either your binary format ends up not much better than JSON or you end up reencoding old comments because the API changed

Those are other options too, eg, storing the schema separately from the records (then batching records with identical schemas in compact binary files) and defining migration rules between different schemas (eg, if schema A has required field "foo" while schema B has required field "foo" and optional field "bar" then data which follows schema A can be trivially migrated to schema B at read time without needing to reencode on disk).

https://avro.apache.org/docs/current/

Yeah not everyone, I’d even say the majority of people, are using software parsing libraries where they are in control of the input data format.

The readme specifies that it’s not optimized for reading a large number of small files.

Is there a reason these fast json libraries seem to favor doing linear scan for object representation?

That header mentions a tape.md describing the format. It's really interesting:

https://github.com/lemire/simdjson/blob/master/tape.md

Isn't that just lexing?

iirc, it's complicated. Some instructions don't reduce the frequency; some reduce it a little; some reduce it a lot.

I'm not sure AVX2 is as ubiquitous as the README says: "We assume AVX2 support which is available in all recent mainstream x86 processors produced by AMD and Intel."

I guess "mainstream" is somewhat subjective, but some recent Chromebooks have Celeron processors with no AVX2:

https://us-store.acer.com/chromebook-14-cb3-431-c5fm

https://ark.intel.com/products/91831/Intel-Celeron-Processor...

I doubt someone using CSV for big data is going to follow that rule...

https://en.wikipedia.org/wiki/JSON#Data_portability_issues :

> Although Douglas Crockford originally asserted that JSON is a strict subset of JavaScript, his specification actually allows valid JSON documents that are invalid JavaScript. Specifically, JSON allows the Unicode line terminators U+2028 LINE SEPARATOR and U+2029 PARAGRAPH SEPARATOR to appear unescaped in quoted strings, while ECMAScript 2018 and older does not.

Agree.

This is another useful resource, discussed here already - http://seriot.ch/parsing_json.php - which lists relevant standards. But "the" standard is static, so divergence, is any, is with other standards (different from json.org) vs. evolving JavaScript.

> People complain about the lack of comments and trailing commas,

Yeah, I don't think JSON should include those things. I think the lack of comments makes JSON a poor format for config files, but that just means you should use another format for config files. JSON is good for machine-to-machine communication.

This is a dangerous assumption to make, and one that bit us a while ago when using trigger.io for an app.

We had a lot of user supplied data in the strings of our API responses, some of it copied from Word documents and were ridden with U+2028 and U+2029 whitespace. Turns out that on iOS, the trigger.io library makes the all too popular assumption that any well-formated JSON can be interpreted as JS, and parses the responses with "eval", thus turning all those unicode characters _within JSON strings_ into newlines!

Thank you!

Though from the readme on that module the dev says "it turns out that you’re better off using the normal Node.js/V8 implementation unless you’re operating on huge JSON.

... the bridging from V8 to C++ is a bit too costly at this stage."

I'm not aware of any SIMD-capable Arduino chips; even when Quark was a thing, it didn't support SIMD.

It's possible to do SWAR (SIMD Within A Register) tricks to try to substitute, but on a 32-bit processor (or even a 64-bit processor) I doubt our techniques would look good. In Hyperscan, my regex project, we used SWAR for simple things (character scans) but I doubt that simdjson would work well if you tried to make it into swarjson. :-)