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

111–120 of 193 posts

Re: Building a high performance JSON parser

#111

Post by marcosdumay »

coldtea wrote: post #82
jchw wrote: post #72

Looks pretty good! Even though I've written far too many JSON parsers already in my career, it's really nice to have a reference for how to think about making a reasonable, fast JSON parser, going through each step individually. That said, I will say one thing: you don't really need to have an explicit tokenizer for JSON. You can get rid of the concept of tokens and integrate parsing and tokenization entirely . This…

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

I've seen "somebody doesn't agree with the standard and we must support it" way too many times, and I've written JSON parsers because of this. (And, of course, it's easy to get some difference with the JSON standard.)

I've had problems with handling streams like the OP on basically every programing language and data-encoding language pair that I've tried. It looks like nobody ever thinks about it (I do use chunking any time I can, but some times you can't).

There are probably lots and lots of reasons to write your own parser.

Re: Building a high performance JSON parser

#112

Post by mannyv »

jjeaff wrote: post #99
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.

I guess it's all relative. Memory is significantly cheaper if you get it anywhere but on loan from a cloud provider.

RAM is always expensive no matter where you get it from.

Would you rather do two hours of work or force thousands of people to buy more RAM because your library is a memory hog?

And on embedded systems RAM is a premium. More RAM = most cost.

Re: Building a high performance JSON parser

#113

Post by mannyv »

e12e wrote: post #90
mgaunard wrote: post #55

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

If you can live with "fits on disk" mmap() is a viable option? Unless you truly need streaming (early handling of early data, like a stream of transactions/operations from a single JSON file?)

In general, JSON comes over the network, so MMAP won't really work unless you save to a file. But then you'll run out of disk space.

I mean, you have a 1k, 2k, 4k buffer. Why use more, because it's too much work?

Re: Building a high performance JSON parser

#114

Post by shoo »

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 bytes much more efficiently than an "optimal" implementation of problem A.

So in this sense, we can probably all agree with the author that counting whitespace bytes is an easier problem than the full parsing problem.

We're agreed that the author's implementation (half a page of go code that fits on a talk slide) to solve problem B isn't the most efficient way to solve problem B.

I remember reading somewhere the advice that to set a really solid target for benchmarking, you should avoid measuring the performance of implementations and instead try to estimate a theoretical upper bound on performance, based on say a simplified model of how the hardware works and a simplification of the problem -- that hopefully still captures the essence of what the bottleneck is. Then you can compare any implementation to that (unreachable) theoretical upper bound, to get more of an idea of how much performance is still left on the table.

* for reasonably boring choices of target platform, e.g. amd64 + ram, not some hypothetical hardware platform with surprisingly fast dedicated support for JSON parsing and bad support for anything else.

Re: Building a high performance JSON parser

#115

Post by jbiggley »

marcosdumay wrote: post #111
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?!!!

I've seen "somebody doesn't agree with the standard and we must support it" way too many times, and I've written JSON parsers because of this. (And, of course, it's easy to get some difference with the JSON standard.) I've had problems with handling streams like the OP on basically every programing language and data-encoding language pair that I've tried. It looks like nobody ever thinks about it (I do use chunking a…

This reminds me of my favourite quote about standards.

>The wonderful thing about standards is that there are so many of them to choose from.

And, keeping with the theme, this quote may be from Grace Hopper, Andrew Tanenbaum, Patricia Seybold or Ken Olsen.

Re: Building a high performance JSON parser

#116

Post by kaladin_1 »

lylejantzi3rd wrote: post #20
vjerancrnjak wrote: post #9

Earlier quoted context omitted.

If your JSON always looks the same you can also do better than general JSON parsers.

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.

Re: Building a high performance JSON parser

#117

Post by ahoka »

mgaunard wrote: post #55

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

Most applications read JSONs from networks, where you have a stream. Buffering and fiddling with the whole request in memory increases latency by a lot, even if your JSON is smallish.

Re: Building a high performance JSON parser

#118

Post by 1vuio0pswjnm7 »

"But there is a better trick that we can use that is more space efficient than this table, and is sometimes called a computed goto."

From 1989:

https://raw.githubusercontent.com/spitbol/x32/master/docs/sp...

"Indirection in the Goto field is a more powerful version of the computed Goto which appears in some languages. It allows a program to quickly perform a multi-way control branch based on an item of data."

Re: Building a high performance JSON parser

#119

Post by duped »

vlovich123 wrote: post #45
duped wrote: post #30

Earlier quoted context omitted.

> The user only had to Memory Map the file (or equivalent) Having done this myself, it's a massive cheat code because your bottleneck is almost always i/o and memory mapped i/o is orders of magnitude faster than sequential calls to read(). But that said it's not always appropriate. You can have gigabytes of JSON to parse, and the JSON might be available over the network, and your service might be running on a small n…

> memory mapped i/o is orders of magnitude faster than sequential calls to read() That’s not something I’ve generally seen. Any source for this claim? > You can have gigabytes of JSON to parse, and the JSON might be available over the network, and your service might be running on a small node with limited memory. Memory mapping here adds quite a lot of latency and cost to the system Why does mmap add latency? I would…

Experience? Last time I made that optimization it was 100x faster, ballpark. I don't feel like benchmarking it right now, try yourself.

The latency comes from the fact you need to have the whole file. The use case I'm talking about is a JSON document you need to pull off the network because it doesn't exist on disk, might not fit there, and might not fit in memory.

Re: Building a high performance JSON parser

#120

Post by mgaunard »

ahoka wrote: post #117
mgaunard wrote: post #55

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

Most applications read JSONs from networks, where you have a stream. Buffering and fiddling with the whole request in memory increases latency by a lot, even if your JSON is smallish.

On a carefully built WebSocket server you would ensure your WebSocket messages all fit within a single MTU.
Post reply on HN