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

171–180 of 193 posts

Re: Building a high performance JSON parser

#171

Post by riku_iki »

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

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

> RAM pages

I didn't say "RAM pages", well vectorrized code can dump MBs of data preemptively into cache, instead of reading "next keyval sequence" each time.

> And this entire detour has no relevance to what I said in the first place,

or you just don't understand such relevance.

Re: Building a high performance JSON parser

#172

Post by 3cats-in-a-coat »

riku_iki wrote: post #171
3cats-in-a-coat wrote: post #170

Earlier quoted context omitted.

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.

> RAM pages I didn't say "RAM pages", well vectorrized code can dump MBs of data preemptively into cache, instead of reading "next keyval sequence" each time. > And this entire detour has no relevance to what I said in the first place, or you just don't understand such relevance.

I never said the CPU reads one key at a time. I said it can decode hundreds of keys at the time it loads one from memory. This is completely irrelevant of how memory reads are batched. It's about a ratio, like 100:1 get it? Seems like you felt your ego attacked, and you just had to respond in a patronizing way about something, but didn't know about what.

Hashing a string as you read it from memory and jumping to a hash bucket is not an expensive operation. This entire argument sounds like some kindergarten understanding of compute efficiency. This is not a 6052.

Re: Building a high performance JSON parser

#173

Post by riku_iki »

3cats-in-a-coat wrote: post #172
riku_iki wrote: post #171

Earlier quoted context omitted.

> RAM pages I didn't say "RAM pages", well vectorrized code can dump MBs of data preemptively into cache, instead of reading "next keyval sequence" each time. > And this entire detour has no relevance to what I said in the first place, or you just don't understand such relevance.

I never said the CPU reads one key at a time. I said it can decode hundreds of keys at the time it loads one from memory. This is completely irrelevant of how memory reads are batched. It's about a ratio, like 100:1 get it? Seems like you felt your ego attacked, and you just had to respond in a patronizing way about something, but didn't know about what. Hashing a string as you read it from memory and jumping to a ha…

Will ignore you this time )

Re: Building a high performance JSON parser

#174

Post by jensneuse »

romshark wrote: post #157
jensneuse wrote: post #61

I've taken a very similar approach and built a GraphQL tokenizer and parser (amongst many other things) that's also zero memory allocations and quite fast. In case you'd like to check out the code: https://github.com/wundergraph/graphql-go-tools

You might also want to check out this abomination of mine: https://github.com/graph-guard/gqlscan I've held a talk about this, unfortunately wasn't recorded. I've tried to squeeze as much out of Go as I could and I've went crazy doing that :D

It's a bit verbose.

Re: Building a high performance JSON parser

#175

Post by 3cats-in-a-coat »

riku_iki wrote: post #173
3cats-in-a-coat wrote: post #172

Earlier quoted context omitted.

I never said the CPU reads one key at a time. I said it can decode hundreds of keys at the time it loads one from memory. This is completely irrelevant of how memory reads are batched. It's about a ratio, like 100:1 get it? Seems like you felt your ego attacked, and you just had to respond in a patronizing way about something, but didn't know about what. Hashing a string as you read it from memory and jumping to a ha…

Will ignore you this time )

Excellent work. Don't drop to my level where I made a simple factual statement.

Re: Building a high performance JSON parser

#176

Post by chii »

crabbone wrote: post #164
chii wrote: post #140

Earlier quoted context omitted.

> 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 "fi…

you're layering the application semantics into the transport format.

It's fine, in the sense that a JSON with duplicate keys is already invalid - but the parser might handle it, and i suggested a way (just from reading the stackoverflow answer).

It's the same "fine" that you get from undefined C compiler behaviour.

Re: Building a high performance JSON parser

#177

Post by zlg_codes »

nly wrote: post #160
zlg_codes wrote: post #151

Earlier quoted context omitted.

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…

I've seen tens of millions of market data events from a single day of trading encoded in JSON and used in various post-trade pipelines.

Ah, that's a dataset with a size certainly intimidating, and in an environment where performance means money. Thanks for pointing that out!

Re: Building a high performance JSON parser

#179

Post by crabbone »

chii wrote: post #176
crabbone wrote: post #164

Earlier quoted context omitted.

> 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 "fi…

you're layering the application semantics into the transport format. It's fine, in the sense that a JSON with duplicate keys is already invalid - but the parser might handle it, and i suggested a way (just from reading the stackoverflow answer). It's the same "fine" that you get from undefined C compiler behaviour.

Why do you keep inventing stuff... No, JSON with duplicate keys is not invalid. The whole point of streaming is to be able to process data before it completely arrived. What "layering semantics" are you talking about?

This has no similarity with undefined behavior. This is documented and defined.

Re: Building a high performance JSON parser

#180

Post by 3cats-in-a-coat »

alpaca128 wrote: post #63
3cats-in-a-coat wrote: post #46

Earlier quoted context omitted.

JSON is probably the fastest serialization format to produce and parse, which is also safe for public use, compared to binary formats which often have fragile, highly specific and vulnerable encoding as they're directly plopped into memory and used as-is (i.e. they're not parsed at all, it's just two computers exchanging memory dumps). Compare it with XML for example, which is a nightmare of complexity if you actuall…

I prefer msgpack if the data contains a lot of numeric values. Representing numbers as strings like in JSON can blow up the size and msgpack is usually just as simple to use.

Msgpack is nice and simple sure.
Post reply on HN