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

141–150 of 193 posts

Re: Building a high performance JSON parser

#141

Post by nigeltao »

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…

If you want commas and comments, another term to search for is JWCC, which literally stands for "JSON With Commas and Comments". HuJSON is another name for it.

Re: Building a high performance JSON parser

#142

Post by marginalia_nu »

robocat wrote: post #132
marginalia_nu wrote: post #94

Earlier quoted context omitted.

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.

I'm talking about during parsing.

Let's assume I send you a JSON object that is one very long string and nothing else. It's e.g. 1 GB in size. To know you need to allocate a 1GB buffer, you need to first scan it, and then copy it; or keep reallocating the same buffer until it fits.

It's an absurd case, but shorter strings face similar overhead.

Re: Building a high performance JSON parser

#143

Post by forrestthewoods »

shoo wrote: post #114
forrestthewoods wrote: post #87

> Any (useful) JSON decoder code cannot go faster that this. That line feels like a troll. Cunningham’s Law in action. You can definitely go faster than 2 Gb/sec. In a word, SIMD.

we could re-frame by distinguishing problem statements from implementations Problem A: read a stream of bytes, parse it as JSON Problem B: read a stream of bytes, count how many bytes match a JSON whitespace character Problem B should require fewer resources* to solve than problem A. So in that sense problem B is a relaxation of problem A, and a highly efficient implementation of problem B should be able to process b…

Everything you said is totally reasonable. I'm a big fan of napkin math and theoretical upper bounds on performance.

simdjson (https://github.com/simdjson/simdjson) claims to fully parse JSON on the order of 3 GB/sec. Which is faster than OP's Go whitespace parsing! These tests are running on different hardware so it's not apples-to-apples.

The phrase "cannot go faster than this" is just begging for a "well ackshully". Which I hate to do. But the fact that there is an existence proof of Problem A running faster in C++ SIMD than OP's Probably B scalar Go is quite interesting and worth calling out imho. But I admit it doesn't change the rest of the post.

Re: Building a high performance JSON parser

#144

Post by riku_iki »

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

Earlier quoted context omitted.

> 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.

> In a streaming reader you can do your job without ever creating maps or dehydrating objects.

but you need some logic which will check that key is what you want to process, and also do various type transformation (e.g. json string to long).

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

then this shouldn't be called JSON parsing anymore.

Re: Building a high performance JSON parser

#145

Post by dleeftink »

dleeftink wrote: post #58
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…

Somewhat tangentially related, Fabian Iwand posted this regex prefix tree visualiser/generator last week [0], which may offer some inspiration for prototyping auto generated schemas.

Forgot to include the link:

[0]: https://observablehq.com/@mootari/regex-from-strings

Re: Building a high performance JSON parser

#146

Post by tubthumper8 »

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…

Yeah, definitely for small devices. For things like VS Code's configuration file format (the parent comment) or other such use cases, I don't see a problem

Re: Building a high performance JSON parser

#147

Post by c-smile »

beached_whale wrote: post #134
jchw wrote: post #92

Earlier quoted context omitted.

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…

> that most of hte libraries taking a JSON document approach are wasting a lot of time/memory

I agree. That's the same situation as with XML/HTML. In many cases you don't really need to build a DOM or JSOM in memory. If your task is about deserializing some native structures.

This XML scanner of mine does not allocate any memory at all while parsing HTML/XML: https://www.codeproject.com/Articles/14076/Fast-and-Compact-...

It is even simpler than SAX parser.

Re: Building a high performance JSON parser

#149

Post by [deleted] »

c-smile wrote: post #147
beached_whale wrote: post #134

Earlier quoted context omitted.

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…

> that most of hte libraries taking a JSON document approach are wasting a lot of time/memory I agree. That's the same situation as with XML/HTML. In many cases you don't really need to build a DOM or JSOM in memory. If your task is about deserializing some native structures. This XML scanner of mine does not allocate any memory at all while parsing HTML/XML: https://www.codeproject.com/Articles/14076/Fast-and-Compac…

[deleted]

Re: Building a high performance JSON parser

#150

Post by beached_whale »

c-smile wrote: post #147
beached_whale wrote: post #134

Earlier quoted context omitted.

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…

> that most of hte libraries taking a JSON document approach are wasting a lot of time/memory I agree. That's the same situation as with XML/HTML. In many cases you don't really need to build a DOM or JSOM in memory. If your task is about deserializing some native structures. This XML scanner of mine does not allocate any memory at all while parsing HTML/XML: https://www.codeproject.com/Articles/14076/Fast-and-Compac…

For the interesting JSON of a significant size, an interator/range interface that parses to concrete types works really well. Usually they are large arrays or JSONL like things
Post reply on HN