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

161–170 of 193 posts

Re: Building a high performance JSON parser

#161

Post by lifthrasiir »

debugnik wrote: post #131
mananaysiempre wrote: post #104

Earlier quoted context omitted.

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…

Or take the XML route. Unicode offers several strategies to avoid continuously updating the Unicode table [1] which has been adapted by XML 1.1 and also later editions of XML 1.0. The actual syntax can be as simple as the following (based from XML, converted to ABNF as in RFC 8295):

    name = name-start-char *name-char
    name-start-char =
        %x41-5A / %x5F / %x61-7A / %xC0-D6 / %xD8-F6 / %xF8-2FF / %x370-37D /
        %x37F-1FFF / %x200C-200D / %x2070-218F / %x2C00-2FEF / %x3001-D7FF /
        %xF900-FDCF / %xFDF0-FFFD / %x10000-EFFFF
    name-char = name-start-char / %x30-39 / %xB7 / %x300-36F / %x203F-2040
In my opinion, this approach is so effective that I believe every programming language willing to support Unicode identifiers but nothing more complex (e.g. case folding or normalization or confusable detections) should use this XML-based syntax. You don't even need to narrow it down because Unicode explicitly avoided identifier characters outsides of those ranges due to the very existence of XML identifiers!

[1] https://unicode.org/reports/tr31/#Immutable_Identifier_Synta...

Re: Building a high performance JSON parser

#162

Post by mxmlnkn »

zlg_codes wrote: post #151
craigching wrote: post #85

Earlier quoted context omitted.

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

What on Earth are you storing in JSON that this sort of performance issue becomes an issue? How big is 'large' here? I built a simple CRUD inventory program to keep track of one's gaming backlog and progress, and the dumped JSON of my entire 500+ game statuses is under 60kB and can be imported in under a second on decade-old hardware. I'm having difficulty picturing a JSON dataset big enough to slow down modern hardw…

Chrome trace format files also use JSON and can also become large and are a pain to work with.

Re: Building a high performance JSON parser

#163

Post by rurban »

This is a very poor and overly simplified text to write basic JSON parsers, not touching any topic of writing actually fast JSON parsers. Such as not-copying tokenizers (e.g. jsmn), word-wise tokenizers (simdjson) and fast numeric conversions (fast_double_parser at al).

Re: Building a high performance JSON parser

#164

Post by crabbone »

chii wrote: post #140
crabbone wrote: post #133

Earlier quoted context omitted.

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…

> This works fine

This is a very strange way of using the word "fine"... What if the value that lives in the key triggers some functionality in the application that should never happen due to the semantics you just botched by executing it?

Example:

    {
      "commands": {
        "bumblebee": "rm -rf /usr",
        "bumblebee": "echo 'I have done nothing wrong!'"
      }
    }
With the obvious way to interpret this...

So, you are saying that it's "fine" for an application to execute the first followed by second, even though the semantics of the above are that only the second one is the one that should have an effect?

Sorry, I have to disagree with your "works fine" assessment.

Re: Building a high performance JSON parser

#165

Post by CyberDildonics »

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…

If you have files that are large enough that json is a problem, why use json in the first place? Why not use a binary format that will be more compact and easier to memory map?

Re: Building a high performance JSON parser

#166

Post by httgp »

CyberDildonics wrote: post #165
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…

If you have files that are large enough that json is a problem, why use json in the first place? Why not use a binary format that will be more compact and easier to memory map?

Chances are they can’t control that; they’re perhaps provided by a vendor.

Re: Building a high performance JSON parser

#167

Post by 3cats-in-a-coat »

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

Earlier quoted context omitted.

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.

The "logic" to match a key is not slow. Your CPU can parse hundreds of keys while waiting for the next keyval sequence to be loaded from RAM.

As for whether you must stuff everything in objects for it to be JSON, I mean that makes no sense. JSON arrays are also JSON. And JSON scalars are also JSON.

If this argument requires we deliberately go out of our way to be dumb, then it's a bad argument.

I'm writing a platform which has a JSON-like format for message exchange and I realized early on that in serialized data, maps are at best nominal. You process everything serially (hence the word serialization). It's a stream of tokens. The fact some tokens are marked as keys and some as values is something that can be useful to communicate intent, but it doesn't mandate how you utilize it.

Everything else is just prejudices and biases, such as "maps take resources to allocate". JSON doesn't force you to build maps when you have an object. Point in the spec where JSON mandates how you must store the parsed results of a JSON object. Should it be a hashmap? A b-tree? A linked list? A tuple? Irrelevant.

Re: Building a high performance JSON parser

#168

Post by riku_iki »

3cats-in-a-coat wrote: post #167
riku_iki wrote: post #144

Earlier quoted context omitted.

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

The "logic" to match a key is not slow. Your CPU can parse hundreds of keys while waiting for the next keyval sequence to be loaded from RAM. As for whether you must stuff everything in objects for it to be JSON, I mean that makes no sense. JSON arrays are also JSON. And JSON scalars are also JSON. If this argument requires we deliberately go out of our way to be dumb, then it's a bad argument. I'm writing a platform…

> The "logic" to match a key is not slow. Your CPU can parse hundreds of keys while waiting for the next keyval sequence to be loaded from RAM.

RAM on my computer works with pages loaded into CPU cache.

Rants, personal attacks, handwavings are ignored.

Re: Building a high performance JSON parser

#170

Post by 3cats-in-a-coat »

riku_iki wrote: post #168
3cats-in-a-coat wrote: post #167

Earlier quoted context omitted.

The "logic" to match a key is not slow. Your CPU can parse hundreds of keys while waiting for the next keyval sequence to be loaded from RAM. As for whether you must stuff everything in objects for it to be JSON, I mean that makes no sense. JSON arrays are also JSON. And JSON scalars are also JSON. If this argument requires we deliberately go out of our way to be dumb, then it's a bad argument. I'm writing a platform…

> The "logic" to match a key is not slow. Your CPU can parse hundreds of keys while waiting for the next keyval sequence to be loaded from RAM. RAM on my computer works with pages loaded into CPU cache. Rants, personal attacks, handwavings are ignored.

No, pages are not loaded in cache. Cache lines are. RAM pages are typically 4kb, and cache lines are most commonly 64 bytes. This means you have 64 cache lines per RAM page. And this entire detour has no relevance to what I said in the first place, which still stands. But you know, someone was wrong on the Internet.
Post reply on HN