Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building a high performance JSON parser

dave.cheney.net

Post reply on HN
Print view View original

131–140 of 193 posts

Re: Building a high performance JSON parser

#131

Post by debugnik »

mananaysiempre wrote: post #104
tubthumper8 wrote: post #97

Earlier quoted context omitted.

Does JSONC have a specification or formal definition? People have suggested[1] using JSON5[2] instead for that reason [1] https://github.com/microsoft/vscode/issues/100688 [2] https://spec.json5.org/

Unfortunately, JSON5 says keys can be ES5 IdentifierName[1]s, which means you must carry around Unicode tables. This makes it a non-option for small devices, for example. (I mean, not really, you technically could fit the necessary data and code in low single-digit kilobytes, but it feels stupid that you have to. Or you could just not do that but then it’s no longer JSON5 and what was the point of having a spec again…

Or take the SQLite route, if you don't need to reject strictly invalid JSON5. When they extended SQLite's JSON parser to support JSON5, they specifically relaxed the definition of unquoted keys (in a compatible way) to avoid Unicode tables[1]:

> Strict JSON5 requires that unquoted object keys must be ECMAScript 5.1 IdentifierNames. But large unicode tables and lots of code is required in order to determine whether or not a key is an ECMAScript 5.1 IdentifierName. For this reason, SQLite allows object keys to include any unicode characters greater than U+007f that are not whitespace characters. This relaxed definition of "identifier" greatly simplifies the implementation and allows the JSON parser to be smaller and run faster.

[1]: https://www.sqlite.org/json1.html

Re: Building a high performance JSON parser

#132

Post by robocat »

marginalia_nu wrote: post #94
diarrhea wrote: post #26

Earlier quoted context omitted.

I wonder: can fast, special-case JSON parsers be dynamically autogenerated from JSON Schemas? Perhaps some macro-ridden Rust monstrosity that spits out specialised parsers at compile time, dynamically…

A fundamental problem with JSON parsing is that it has variable length fields that don't encode their length, in a streaming scenario you basically need to keep resizing your buffer until the data fits. If the data is on disk and not streaming you may get away with reading ahead to find the end of the field first, but that's also not particularly fast. Schemas can't fix that.

Only if you are using pointers/slices into the buffer as an optimisation.

Otherwise there is no need to keep a buffer of anything after it has been parsed.

Re: Building a high performance JSON parser

#133

Post by crabbone »

mannyv wrote: post #77
mgaunard wrote: post #55

"It’s unrealistic to expect to have the entire input in memory" -- wrong for most applications

If you're building a library you either need to explicitly call out your limits or do streaming. I've pumped gigs of jaon data, so a streaming parser is appreciated. Plus streaming shows the author is better at engineering and is aware of the various use cases. Memory is not cheap or free except in theory.

Here people confidently keep repeating "streaming JSON". What do you mean by that? I'm genuinely curios.

Do you mean XML SAX-like interface? If so, how do you deal with repeated keys in "hash tables"? Do you first translate JSON into intermediate objects (i.e. arrays, hash-tables) and then transform them into application-specific structures, or do you try to skip the intermediate step?

I mean, streaming tokens is kind of worthless on its own. If you are going for SAX-like interface, you want to be able to go all the way with streaming (i.e. in no layer of the code that reads JSON you don't "accumulate" data (esp. not possibly indefinitely) until it can be sent to the layer above that).

Re: Building a high performance JSON parser

#134

Post by beached_whale »

jchw wrote: post #92
coldtea wrote: post #82

Earlier quoted context omitted.

What line of work are you in that you've "written far too many JSON parsers already" in your career?!!!

Reasons differ. C++ is a really hard place to be. It's gotten better, but if you can't tolerate exceptions, need code that is as-obviously-memory-safe-as-possible, can parse incrementally (think SAX style), off-the-shelf options like jsoncpp may not fit the bill. Handling large documents is indeed another big one. It sort-of fits in the same category as being able to parse incrementally. That said, Go has a JSON scan…

The large documents are often fixed by using mmap/virtualalloc of the file, but Boost.JSON has a streaming mode and is reasonably fast and the license is good for pulling into anything. It's not the fastest, but faster than rapid with the interface of nlohmann JSON. For most tasks, it does seem that most of hte libraries taking a JSON document approach are wasting a lot of time/memory to get to the point that we want normal data structures, not a JSON document tree. If we pull that out and parse straight to the data structures there is a lot of win in performance and memory with less/no code, just mappings. That's how I approached it at least.

Re: Building a high performance JSON parser

#135

Post by crabbone »

suzzer99 wrote: post #81

Can someone explain to me why JSON can't have comments or trailing commas? I really hope the performance gains are worth it, because I've lost 100s of man-hours to those things, and had to resort to stuff like this in package.json: "IMPORTANT: do not run the scripts below this line, they are for CICD only": true,

There's no real reason for that. It just happened like that. These aren't the only bad decisions made by JSON author, and not the worst either.

What you can do is: write comments using pound sign, and rename your files to YAML. You will also get a benefit of a million ways of writing multiline strings -- very confusing, but sometimes useful.

Re: Building a high performance JSON parser

#136

Post by beached_whale »

craigching wrote: post #85
coldtea wrote: post #82

Earlier quoted context omitted.

What line of work are you in that you've "written far too many JSON parsers already" in your career?!!!

Probably anywhere that requires parsing large JSON documents. Off the shelf JSON parsers are notoriously slow on large JSON documents.

There are several that are into the GB/s of performance with various interfaces. Most are just trash for large documents and sit in the allocators far too long, but that's not required either

Re: Building a high performance JSON parser

#137

Post by gnuvince »

kaladin_1 wrote: post #116
lylejantzi3rd wrote: post #20

Earlier quoted context omitted.

Andreas Fredriksson demonstrates exactly that in this video: https://vimeo.com/644068002

I really enjoyed this video even though he lost me with the SIMD code.

I like this video because there's a lot of a good actionable advice before he gets into SIMD code.

Re: Building a high performance JSON parser

#138

Post by suzzer99 »

coldtea wrote: post #83
suzzer99 wrote: post #81

Can someone explain to me why JSON can't have comments or trailing commas? I really hope the performance gains are worth it, because I've lost 100s of man-hours to those things, and had to resort to stuff like this in package.json: "IMPORTANT: do not run the scripts below this line, they are for CICD only": true,

It can't have comments because it didn't originally had comments, so now it's too late. And it originally didn't have comments, because Douglas Cockford thought they could be abused for parsing instructions. As for not having trailing commas, it's probably a less intentional bad design choice. That said, if you want commas and comments, and control the parsers that will be used for your JSON, then use JSONC (JSON wit…

Yeah if you could get NPM to allow JSONC in package.json, that'd be great.

Re: Building a high performance JSON parser

#139

Post by 3cats-in-a-coat »

riku_iki wrote: post #56
3cats-in-a-coat wrote: post #47

Earlier quoted context omitted.

I think people say that as they give disproportional weight to the fact it's text-based, while ignoring how astoundingly simple and linear it is to write and read. The only way to nudge the needle is to start exchanging direct memory dumps, which is what ProtoBuff and the like do. But this is clearly only for very specific use.

> while ignoring how astoundingly simple and linear it is to write and read. code maybe simple, but you have lots of performance penalties: resolving field keys, you need to construct some complicated data structures through memory allocations, which is expensive. > to start exchanging direct memory dumps, which is what ProtoBuff and the like do Protobuff actually is doing parsing, it is just binary format. What you…

Resolving what keys? JSON has keyval sequences ("objects") but what you do with them is entirely up to you. In a streaming reader you can do your job without ever creating maps or dehydrating objects.

Plus no one makes people use objects in JSON. If you can send a tuple of fields as an array... then send an array.

Re: Building a high performance JSON parser

#140

Post by chii »

crabbone wrote: post #133
mannyv wrote: post #77

Earlier quoted context omitted.

If you're building a library you either need to explicitly call out your limits or do streaming. I've pumped gigs of jaon data, so a streaming parser is appreciated. Plus streaming shows the author is better at engineering and is aware of the various use cases. Memory is not cheap or free except in theory.

Here people confidently keep repeating "streaming JSON". What do you mean by that? I'm genuinely curios. Do you mean XML SAX-like interface? If so, how do you deal with repeated keys in "hash tables"? Do you first translate JSON into intermediate objects (i.e. arrays, hash-tables) and then transform them into application-specific structures, or do you try to skip the intermediate step? I mean, streaming tokens is kin…

> If so, how do you deal with repeated keys in "hash tables"?

depending on the parser, behaviour might differ. But looking at https://stackoverflow.com/questions/21832701/does-json-synta... , it seems like the "best" option is to have 'last key wins' as the resolution.

This works fine under a SAX like interface in a streaming JSON parser - your 'event handler' code will execute for a given key, and a 2nd time for the duplicate.

Post reply on HN