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

Simdjson – Parsing Gigabytes of JSON per Second

github.com

Post reply on HN
Print view View original

21–30 of 202 posts

Re: Simdjson – Parsing Gigabytes of JSON per Second

#21

Post by chubot »

eesmith wrote: post #14
chubot wrote: post #11

Earlier quoted context omitted.

The JSON spec [1] never had any updates, so it couldn't have diverged. Kudos to Douglas Crockford for keeping it simple. I wish more standards committees would take a cue from him. (Looking at ECMAScript [2] and C++.) There's been a tremendous amount of growth and value around JSON precisely because it's so simple and easy to implement. People complain about the lack of comments and trailing commas, but I think those…

https://en.wikipedia.org/wiki/JSON#Data_portability_issues : > Although Douglas Crockford originally asserted that JSON is a strict subset of JavaScript, his specification actually allows valid JSON documents that are invalid JavaScript. Specifically, JSON allows the Unicode line terminators U+2028 LINE SEPARATOR and U+2029 PARAGRAPH SEPARATOR to appear unescaped in quoted strings, while ECMAScript 2018 and older doe…

Yeah I remember that quirk, and that's why I said it's "as much of a subset as it ever was". :) Because of this issue, it was technically never a subset.

But almost all real JSON documents are subsets of JavaScript, unless they happen to have those characters.

And the salient point is that if JSON never changes, then no further divergence from JavaScript is possible.

Re: Simdjson – Parsing Gigabytes of JSON per Second

#22

Post by glangdale »

chubot wrote: post #13
xfs wrote: post #10

If you're working with json objects with sizes on the higher end quite often you're not going to need the entirety of them, just a small part of them. If that is the workload what then to do is simply parse as little data as possible: skip the validation, locate the relevant bits, and then start parsing, validation and all the stuff. In this optimizing the json scanner/lexer gives much greater improvement than optimi…

I agree that's a good strategy for big JSON. Do you know of any such "lazy" parsers? I think the problem is that to extract arbitrary keys, you really need to parse the whole thing, although you don't need to materialize nodes for the whole thing. But if you have big JSON with a given schema, you may be able to skip things lexically. You basically need to count {} and [], while taking into account " and \ within quot…

That's what our first stage does, pretty much. I would imagine we do it way faster than re2c would do it.

Parsing the entire document lock stock and barrel is an easier thing to write about and benchmark. The problem is with skipping around and pulling out bits of JSON from a benchmarking framework is that attempting to present such data often amounts to "hey, we asked ourselves a question and then we got a really good answer for it!". It's hard to picture what a 'typical' query for some field over a JSON document would look like. Conversely, it's pretty easy to know when you finished parsing the Whole Thing.

Re: Simdjson – Parsing Gigabytes of JSON per Second

#23

Post by xfs »

chubot wrote: post #13
xfs wrote: post #10

If you're working with json objects with sizes on the higher end quite often you're not going to need the entirety of them, just a small part of them. If that is the workload what then to do is simply parse as little data as possible: skip the validation, locate the relevant bits, and then start parsing, validation and all the stuff. In this optimizing the json scanner/lexer gives much greater improvement than optimi…

I agree that's a good strategy for big JSON. Do you know of any such "lazy" parsers? I think the problem is that to extract arbitrary keys, you really need to parse the whole thing, although you don't need to materialize nodes for the whole thing. But if you have big JSON with a given schema, you may be able to skip things lexically. You basically need to count {} and [], while taking into account " and \ within quot…

I'm not sure what you mean by arbitrary? What parsing in this case means e.g. turning a string of digits into a ieee754 float number in memory. I think this project is meant to accelerate this part with SIMD, but a greater improvement can be obtained by simply not doing this for as much data as possible. If the actual materialized data constitutes a small part of the original, there should be ways to do minimum work for the rest.

Re: Simdjson – Parsing Gigabytes of JSON per Second

#24

Post by Falell »

kccqzy wrote: post #5

I guess the question is, what do you parse it to? I'm guessing definitely not turning objects into std::unordered_map and arrays into std::vector or some such. So how easy it is to use the "parsed" data structure? How easy is it to add an element to some deeply nested array for example?

The ParsedJson type is immutable and accessed mutating iterators (up and down the tree, forward and backward through members and indices).

My immediate thought is to compare it to rapidjson, which I've used before. The paradigm of mutating iterators seems awkward at first but should be just as powerful as rapidjson's Value. For example, both approaches end up doing a linear scan to find an object member by name.

The fact that rapidjson supports mutation of Values and simdjson does not has huge implications (as mentioned in the simdjson README scope section), I suspect this tradeoff explains most of the performance differences as I know rapidjson also uses simd internally.

Re: Simdjson – Parsing Gigabytes of JSON per Second

#25

Post by glangdale »

xfs wrote: post #10

If you're working with json objects with sizes on the higher end quite often you're not going to need the entirety of them, just a small part of them. If that is the workload what then to do is simply parse as little data as possible: skip the validation, locate the relevant bits, and then start parsing, validation and all the stuff. In this optimizing the json scanner/lexer gives much greater improvement than optimi…

Jitting is a common tool that people seem to reach for whenever they are parsing or lexing anything at any time. It's really not necessary; there are plenty of fast search methods out there.

JIT approaches make a lot of sense for lex/yacc and their numerous descendants, as these typically need to put a lot of extra logic into the process of parsing. You don't need to JIT just to look up some strings and/or parse a fairly simple hierarchical structure.

Re: Simdjson – Parsing Gigabytes of JSON per Second

#26

Post by scottlamb »

saagarjha wrote: post #9
kccqzy wrote: post #5

I guess the question is, what do you parse it to? I'm guessing definitely not turning objects into std::unordered_map and arrays into std::vector or some such. So how easy it is to use the "parsed" data structure? How easy is it to add an element to some deeply nested array for example?

The data is put into a "ParsedJson" object: https://github.com/lemire/simdjson/blob/master/include/simdj...

That header mentions a tape.md describing the format. It's really interesting:

https://github.com/lemire/simdjson/blob/master/tape.md

Re: Simdjson – Parsing Gigabytes of JSON per Second

#27

Post by xfs »

glangdale wrote: post #22
chubot wrote: post #13

Earlier quoted context omitted.

I agree that's a good strategy for big JSON. Do you know of any such "lazy" parsers? I think the problem is that to extract arbitrary keys, you really need to parse the whole thing, although you don't need to materialize nodes for the whole thing. But if you have big JSON with a given schema, you may be able to skip things lexically. You basically need to count {} and [], while taking into account " and \ within quot…

That's what our first stage does, pretty much. I would imagine we do it way faster than re2c would do it. Parsing the entire document lock stock and barrel is an easier thing to write about and benchmark. The problem is with skipping around and pulling out bits of JSON from a benchmarking framework is that attempting to present such data often amounts to "hey, we asked ourselves a question and then we got a really go…

> It's hard to picture what a 'typical' query for some field over a JSON document would look like.

Exactly. A "query" would have to define not only the path, type of the field in the source data but also the type/interface of where you want to put that data. Combining dynamic queries and typed data you get a fairly tricky problem, which is why I said this is tricky. I worked on a similar thing for protobuf and jitting was a solution I looked into (in that project libllvm was too unwieldy to use).

Re: Simdjson – Parsing Gigabytes of JSON per Second

#28

Post by SoSKatan »

glangdale wrote: post #20

One of the two authors here. Happy to answer questions. The intent was to open things but not publicize them at this stage but Hacker News seems to find stuff. Wouldn't surprise me if plenty of folks follow Daniel Lemire on Github as his stuff is always interesting.

I've written my fare share of performant code over the years, but this is some next level shit. I've been reading it the last few hours. The only question I have is what is the term for that place considered two degrees past black magic? Since you live there, I have to assume you know the name.

Re: Simdjson – Parsing Gigabytes of JSON per Second

#29

Post by scottlamb »

aristidb wrote: post #15
westurner wrote: post #12

> Requirements: […] A processor with AVX2 (i.e., Intel processors starting with the Haswell microarchitecture released 2013, and processors from AMD starting with the Rizen)

Also noteworthy that on Intel at least, using AVX/AVX2 reduces the frequency of the CPU for a while. It can even go below base clock.

iirc, it's complicated. Some instructions don't reduce the frequency; some reduce it a little; some reduce it a lot.

I'm not sure AVX2 is as ubiquitous as the README says: "We assume AVX2 support which is available in all recent mainstream x86 processors produced by AMD and Intel."

I guess "mainstream" is somewhat subjective, but some recent Chromebooks have Celeron processors with no AVX2:

https://us-store.acer.com/chromebook-14-cb3-431-c5fm

https://ark.intel.com/products/91831/Intel-Celeron-Processor...

Post reply on HN