Parsing gigabytes of JSON per second | Hacker News Reader

Parsing gigabytes of JSON per second

arxiv.org

139 pointssigna1179 comments

If your dataset is large enough to benefit from such a hyperoptimized parser you might not benefit from the human readability anymore, which is the main reason for the required CPU cycles on the first place. So you should probably use a feature-equivalent binary format that is optimized for parsing speed. The only reason to use json then is that it is the lingua franca. So we as an industry should figure out which of the 100s of binary variants of json-similar formats has the same capabilities and unite around it.

I largely agree, but most modern binary formats are more rigid with schemas and types.

If you want the flexibility of JSON, I'm not sure you'll end up with something massively different from gzipped JSON

That’s an interesting thought. I am now very fascinated by what kind of data would be gigs in size but would need the flexibility of JSON.

Datasets are not always provided by you; if your data source outputs json it doesn't matter why. Also just because your volume of data is measured in gigabytes, that doesn't mean it's a singular stream. As an example you could be handling tens of thousands of small requests.

JSON doesn't allow any custom type, so it is not "flexible" per se. Therefore you only need a format that supports the JSON data model and pretty much nothing else; CBOR [1] for example almost surely fits the bill.

[1] https://cbor.io/

Converting a text format to a compact in-memory data structure takes extra CPU cycles. (de)compression takes extra cycles. The point of using a binary format is to achieve the same result while avoiding that overhead. For some data formats compression also has the downside that it prevents seeking.

Serialized binary encodings don't require a schema. They can have all the expressability of JSON and more.

Well json is everywhere so I think it’s mostly too late for companies to change all their internal protocols and apis to not use it. And note that a big advantage of json is that many applications can process it without a schema—you don’t need to know that the username field is a certain length, type and at a particular place. It is also easier to know if json is valid than a random binary format. The advantage of something like the algorithm here is that you can put it into your shared libraries[1] to get a speed up for free. If you spend (making up numbers) 1% of your cpu time parsing json and this speeds things up 4x (note: possibly more because other parsers get more of an advantage in micro-benchmarks from the branch predictor) then if you have sufficiently many servers you can cut your server bill by 0.75% which can be a large amount of money for the largest companies.

[1] this won’t work for all languages as the OP parses json into a flattish object where fields may be looked up rather than some language-specific data structures (like js objects or python dicts or whatever)

yep. once you’ve had to deal with XMLs that come in without a schema alongside, you start appreciating getting a JSON. at least that properly distinguishes strings, nulls, integers and decimals.

Your dataset could, instead of gigabytes in a single request, also be a very large number of small requests all sent to a server to handle. Each message might be easily human-readable, yet the whole system would benefit from expedient processing.

You could also potentially use plain CSV or TSV files. Not sexy, but they work.

Oh yes, CSV! Sure! Separated with commas or semicolons? With quotes or without? What decimal separator?

No thanks.

Use Protobufs, Parquet, Avro, etc.

I've gotta say, I don't really understand why the industry is so in love with human readability for computer to computer interaction.

It seems like a notion that started in the early internet and just refuses to die.

Everything on the internet is minified and compressed at this point, so the entire idea of "human readability" left the station years ago. Yet I'll still see a primary complaint against the likes of http2+ being "it's a binary format! On NO!".

JSON seems like a similar relic. We use it not because it's fast, but because we like the idea that it's easy to decode (Even if in practice that almost never happens).

I regulary get requests from QA why something is not working. Just watching the dumped request and seeing what is wrong ( eg. Configuration) is a bless.

Makes it easier to troubleshoot.

It's the same idea as designing hardware for repairability. Sure you can repair something that's welded on, but it's much easier if it's bolted through instead.

It's not the same.

You are almost certainly passing these through tools (even built into the browser) that are doing extra processing to make it more readable.

Let's assume, for example, CBOR ends up taking over JSON. Do you not think browsers wouldn't have a CBOR parser to make it more readable?

This isn't bolt vs welding, this is bolt vs bolt with a washer. Yes there's a small extra step, but not some sort of insurmountable hurdle.

The questions about readability when things go wrong. When binary data breaks, mostly your just screwed in figuring out went wrong, especially when it causes your decoder to fall over. When ASCII data breaks often a view of the data can point at something even when tools can't.

Reading a binary file is no different than reading ascii. I experimented with writing a debugger, which meant learning how to parse executable ELF binaries. It really wasn't bad at all. It just takes a bit more time to figure out what the bytes/data are expect at what offsets. The real un-said reason is a) programmers are lazy b) its easier/cheaper to hire people who can read ascii than find someone who is a bit more experienced and can figure out how to debug binary parsing.

Yeah and to b, it really just comes down to a lack of tools and people experienced in those tools (IMO).

There's no reason a binary format couldn't be as easy to read as a JSON format. All you'd really need is a "binary->json" gui and you're off.

It would take a little effort to make such a tool and you could have it integrated into every browser.

It's not like something like that is unprecedented even, After all, there's no browser tool out there that's showing you the gzipped resource on a compressed endpoint. It's always already doing the step of gunzipping. binary->Json would similarly be just an additional step the browser could do in the tools.

Indeed, out of all the trillions of HTTP requests that are communicated every day how many get read by a human. Not a lot, yet that's the use-case it's optimised for.

Those on the cloud should compute how much HTTP headers count towards their traffic egress bill.

Everyone is fine with human-readable as long as it's in English.

Binary should be the default. If writing a binary to human decoder is too much for you, you're in the wrong job.

HTTP/2 uses a binary encoding instead of text for performance reasons. I prefer the text version myself as it’s easier to write simple tools for (quick clients, telnet based queries, etc).

Is a custom binary format that much more efficient than a gzipped human-readable format? If not, then it makes all sense to have a mostly universal decoder instead of a hundred different ones, especially since decoders of custom binary formats has traditionally been a major source of security vulnerabilities and other bugs even when those decoders have been written by skilled people and used in production for years.

The answer is in your comment. If you add a step of decompression, then text parsing...it's plain-as-day going to be a lot slower then just pushing bits through a binary parser. Less work = faster

A binary format you understand is easier to parse than a text format, but a binary format you don't understand is harder to learn (from reverse-engineering files) than a text format following certain conventions (HTML/JSON is more familiar to readers than PDF or Punycode). And text formats are easier to extract information out of fragmentary or corrupted documents than binary (or worse yet compressed) formats.

The human readability has to do with developer tooling and ability to work that format. Abstractions are all optimized towards developer productivity the costliest part not compute cycles.

> If your dataset is large enough to benefit from such a hyperoptimized parser

I don't understand that point. Is there an overhead in starting the parsing, which makes regular parsing faster unless you have a large JSON file? If not, why wouldn't you want faster JSON parsing?

Most languages have a built in parser these days, pulling in a c dep can be painful in many build tools and languages. The csimdjson api is sufficiently different to not as idiomatic. Most language json parsers are very fast already.

Personally I’m using csimdjson in a project with 100s of TB of json to burn through. This data should not be json formatted, but migrating away from json would require modifications to hundreds of different systems.

That's a fair point. Though this could probably be used in interpreters/JIT/C++ projects, which is already a lot. And this gives a good template on how to optimize JSON parsing for other projects.

Text is a binary format that just happens to have decoders (ASCII, UTF8 etc) everywhere in order to parse and display it to humans along with more specific parsers for things like JSON.

I wish we could all settle on a binary structured format thats not limited to text encoding and more like JSON (key value) that basically everyone uses with real data types (efficiently encoded numbers, dates, binary , etc).

Text files would just be something like { contentType: "text/plain" content : "text here" } while an image could be { contentType: "image/jpeg", content: <real binary data not base64> } you could also add whatever other metadata you want and all of it is retained and easily parseable. Other more structured formats obviously wouldn't just be a blob for content and every system out there would have a structured binary format viewer/editor just like there are text viewers and editors now.

Sqlite is kinda used this way and has some nice properties like indexes and transactions but is relational instead of hierarchal which can be good and bad, not as straight forward to just view or navigate. Protobuf is another used quite a bit now, honestly I don't care just something everyone agree upon that can encode more structure efficiently but still can be easily inspected everywhere.

Doubt this will any time soon but it does seem inevitable in the long run that we figure out a way to send data between system and what a string, number, date etc is and stop having text encoding and escaping issues.

I don't know why the ASCII characters for record and field separators don't get more love. That is what they are there for. My suspicion is because they aren't type-able, so people rarely encounter them.

Still have the issue of binary data encoding as well since the data will have those bytes in it so they need to be escaped vs a format that defines how to encoding binary as is efficiently (length delimited).

You mean like CBOR?

https://en.wikipedia.org/wiki/CBOR

Sure, looks good, plenty to choose from, just need to get everyone to agree on one.

Although I do like ones that have some concept of a schema to reduce repeated key size and allow validation.

There's also Minecraft NBT. It's a bit obscure but quite nice. https://minecraft.fandom.com/wiki/NBT_format

You should put your NBTs inside of a netstring, https://en.wikipedia.org/wiki/Netstring

Or indeed ASN.1 [0], which started life in 1984 and is still used in a lot of places today.

The idea has been around for almost 40 years in arguably more complete format than any of the above up to and including a standardised schema representation.

It's not the lack of a suitable standard that's holding it back.

[0] https://en.wikipedia.org/wiki/ASN.1

Something like UBF might be interesting to you: https://ubf.github.io/ubf/

Although it's not a format, the closest thing I have found is Postgres. You get well defined types that make life easier. They are stored efficiently in binary. And have a sensible text representation that means you can still read and write them by hand. I can store a PostGIS geometry with millions of verticies and still use text to create a point or read an envelope. Text formatting is hugely useful and benefits from standardisation. But that does not need to be built into the format.

>{ contentType: "image/jpeg", content: <real binary data not base64> }

It would have to be encoded somehow, because what if the "real binary data" included the byte 0x7D which is '}'

Sorry thats not meant to be a literal format but conceptually mapped to text JSON. It would instead be more like CBOR or other JSON like binary formats at the byte level.

protocols have two sides - a producer and a consumer. The consumer often doesn’t have control of the producer, especially in the case of analytics.

I guess an example would be along the lines of protobufs, e.g. Cap’n Proto

https://capnproto.org/

(which I have never used but really enjoy just for its charming website design alone)

If the improvements scale, you can still get benefit for smaller use cases. And even if each json is small, if you have millions of them the tiny improvements add up. We parse quite a bit of json, we fetch and store json regularly from external api's. We can't ask for a different format, and for each of the individual requests json makes sense, the response is only a few hundred kbs. But over time there is a lot of data. We convert them to parquet, but each json needs to be read at least once.

Protobufs would be a good contender here

Protobuf parsing is slower than an optimized json library, e.g. https://jsoniter.com/

I've been hacking with rust & wasm lately and am seeing positive results. Flat buffers are also promising if you are working with larger data.

uh yes that would work perfectly. https://xkcd.com/927/

Why do you think human readable adds appreciable overhead? If you want to create a flexible interchange format, that is going to require some sort of parse step whether the format is text or binary.

That said, probably FlatBuffer would be even an optimized json parser, but json is crazy fast if the parser takes advantage of all modern processor optimizations.

There’s no way reading a series of text is going to beat a machine native byte representation, particularly for things like range limited integers. If you plan things right with proper word alignment, you don’t even have to copy the data to process it as you can directly dereference the byte offsets as machine native ints.

But that isn’t an interchange format given different processors represent such things differently.

How do you debug? Human readability is valuable regardless of the size of the dataset.

"we as an industry" hurts.

It's funny how I feel questioning JSON here on HN is like starting a discussion about politics in a family diner.

I'm forever grateful to Google for demonstrating that all "the industry" is not fully committed to HTTP, JSON and scripting languages. It's honestly a relief to have encountered some sanity somewhere.

Oh god please help me, I just did it, I questioned JSON on HN!

This is pretty great.

Some folks in the thread are suggesting using a binary format, and that's certainly a good idea for some.

My business sells software that collects moderately sized (10-100TB/day) , and this data is collected as PROTOBUF. The format is great, and coordinating the backend and client side stuff with protobuf is bliss.

However, we store the data in various relational and document databases. Neither of those use protobuf...

Most importantly, it's business critical to be able to stream this data to data lakes where it can be read by humans. None of the options are going to support protocol buffers, you're either going to have to write a parser (impossible for some) or transform to JSON before ingest (fairly expensive due to some poor choices in how to represent various fields).

It was a sound technical decision to use protoc , and a terrible choice for the business.

I think it would have been much better to use avro, still benefit from schemas but push the work of marshaling JSON back to clients...

I know it’s utopia, but I still can’t help but ask, why can’t we have protobuffs or some other binary format with readers integrated into normal systems the way everything has a Json reader.

I mean, stuff like “double click on .protobuff file and it opens in notepad and looks like json or whatever. When you click save it gets serialized back to protobuff.

IIRC (I could be wrong on this one) protobuf isn't really a specification, it's a single implementation, and is quite hard to reimplement.

Here's a short comparison of serializing formats: https://drewdevault.com/2020/06/21/BARE-message-encoding.htm...

Regarding the wire format specifically, it's not fully formalized but there's dozen implementations, not all of them from Google. You could hack together a basic serde for a particular language in an afternoon, in some respects much more easily than you could JSON. Most of the engineering work is in the schema compilers.

But in order to semantically read protocol buffer files one needs to compile the schema files…

The degree you "need" to support the full schema format depends entirely on the language you're using. In Go you only need the annotated structures, or in Java you only need a mapping between field number and name, and the languages' own reflection capabilities can handle the rest.

Yes, strings, bytes, and substructures all appear in the same in the wire format. Just like strings, bytes, and dates all appear the same in JSON. If you're trying to write a generic protobuf viewer like wodenokoto suggests, you can make reasonable assumptions about the contents 99% of the time based on the data, and show the user multiple options if you're not sure. There are already lots of tools that do this, but none very well integrated into mainstream development workflows.

Tricky part about implementing that is that the protobuf wire-format alone doesn't contain enough information to unambiguously represent the real data types, it also needs the schema (.proto file) to do that.

For example, in the wire-format, a string and a sub-message are encoded as the same type (a blob - varint + sequence of bytes), but using the schema they are clearly interpreted differently.

Sure, it is possible to make a self-describing protobuf message which includes the schema in protobuf representation, but that is a special-case.

What about Avro then?

Json schema has a similar challenge, there is no header, in the json files themselves, indicating which schema is used.

The slightly dirty solution is https://www.schemastore.org/json/, where the IDE looks up schema from a global registry, using a fileMatch pattern.

I've written translation layers for such systems and it's not too bad. See this project from $job - 1: https://github.com/CaperAi/pronto

It allowed us to have a single model for storage in the DB, for sending between services, and syncing to edge devices.

This is great work! I've done similar stuff (not as nice) for some relational and document stores.

But if you're talking about data lakes, like splunk, or various other similar systems - there's no standard way for writing a parser like this across all of them and you end up implementing the same thi ng a ton of different times.

The project described in the paper is https://simdjson.org/.

Thank you for the link! Much nicer to browse this than an arxiv paper

Source: https://github.com/simdjson/simdjson

PyPI: https://pypi.org/project/pysimdjson/

There's a rust port: https://github.com/simd-lite/simd-json

... From ijson https://pypi.org/project/ijson/#id3 which supports streaming JSON:

> Ijson provides several implementations of the actual parsing in the form of backends located in ijson/backends: [yajl2_c, yajl2_cffi, yajl2, yajl, python]

I think there is some room for "object predictor" optimization. In real world cases, 99% of objects in array will have the same keys over and over. Smart parser can potentially exploit that.

Having some trouble figuring out how to benefit from this.

I can't think of a scenario where JSON handling is our bottleneck; almost all of the massive-data-handling tasks in my entire career have usually been handled by our database of choice.

Largest individual JSONs we've had to handle like on import tasks and such were about 300mb, which proved extremely easy to manage with stuff like JSONStream -I think we used a hand-rolled analogue back then but JSONStream is actually pretty cool, check it out-

What is the use case here? data lakes?

I've dealt with hundreds of gigabytes of JSON data like that in the fintech world

And yeah I just streamed the data thru the processor and avoid malloc at all costs and it works in seconds

I bet this method works even faster though somehow if they felt compelled to throw research money at all at it

If you're at a very large scale, maybe the reduced server cost by parsing JSON this way can "finance" an engineer? If you're starting to reach the limits of JSON, maybe it could also help you avoid a transition for a while longer? At least those are the obvious cases for me.

If it's a drop-in replacement for other JSON parsers, I think this could have a huge impact. There is a lot of value to gain by optimizing the fundamentals

I worked for small(ish) music supplier of Spotify, not a major label like Universal etc. at all - they were receiving a daily 3-4 Gb JSON file (uncompressed) of yesterday's activity. Things get big, fast, nowadays.

I worked on a database engine that uses JSON as communication protocol. Sure, most messages are small, but for a system processing JSONs 24/7 it quickly sums a lot.

The main issues see had with our codec was memory allocation and the big number of "if" in the code.

I tried to use simdjson, but there were concerns at that time about portability and long term support. It's nice to see that in retrospective we were wrong.

I'm working on an embedded vision/navigation system. The core app itself generates about 50mb a minute of metadata alone in the simplest scenario. It's supposed to be long running system. There is one case that generates just over a TB.

Now you may say we should optimize this or that but I'm not an architect and I have no say, and it's just what I gotta deal with:(

Yeah if you have a situation where JSON gets into the megabytes you should definitely stop using JSON! I recommend SQLite for large datasets that you need to put in a file.

I guess if you don't have a choice then it might become a bottleneck. Parsing 300 MB of data can be very slow.

But even with small JSON messages it can become a bottleneck, e.g. check out the Xi editor's issues. They thought it wouldn't be a bottleneck and then found that sound languages don't have insanely optimised JSON parsers like this. Boom. Bottleneck.

We receive market data formatted as JSON and use it to make trading decisions. So we would like to make those decisions quickly.

The use-case for a more efficient JSON parser is exactly the same as the use-case for a less efficient one. They're doing the same thing.

Daniel Lemire does a ton of performance research like this. He's an unusual case of a professor who publishes fully working source code.

There's a good chance that your database of choice uses some of his stuff or was influenced by his research.

Fast JSON parsers are all fine and good, but take such benchmarks with a grain of salt. JSON, like any format, is useless unless you do something meaningful with it - populate a database, verify the result, or transform it in some useful way for the task at hand. Many of these faster JSON DOM-style parsing libraries store key/value pairs in lists or arrays because it's the most efficient way to do so. But they aren't great at lookup speed. If the JSON parse library is event based, i.e. SAX-style, you have to store it somewhere, and this takes CPU as well.

(2019)

Reply on news.ycombinator.com