Another question (open to debate): should the cost of parsing include validation? Is it reasonable to quietly return “reasonable’ results of a query on something that isn’t valid JSON?
This is a query that affects Mison more (as far as I can tell). Mison’s ability to skip fields might allow it to pass over JSON syntax errors without noticing (they didn’t publish code, so I can tell for sure).
Also, it has outstanding features like fast skipping of not needed fields (key/value pairs) or crazily fast parsing and serialization of java.time.* classes.
Just see benchmark results below. BTW, they include results for parsing and serialization of messages from the Twitter API:
WARNING: Results of GraalVM CE/EE are only for a rough evaluation of possible potential of this new tech.
Final results can be changed significantly after JMH tool and GraalVM developers will provide mutual compatibility.
In most cases jsoniter-scala works on par with best binary serializers for Java and Scala:
For some limited kind of work like parsing with projection or parsing of arrays of UUIDs jsoniter-scala can archive 2 bytes per cycle (or ~2Gb per second on contemporary desktops) that is quite competitive with the state of art filter/parsers like Mison or Sparser.
Using a loop with the same input may give an unfair advantage to Java as the JIT may kick in and optimize the code for the input. The effect could exist in C++ at a smaller scale with the branch prediction getting better. As an example of such flawed benchmark: https://github.com/nodejs/node/pull/1457#issuecomment-94188258.
I didn’t read the Microsoft paper, so this is pure speculation on my side.
steguasays:
I am a happy user of RapidJSON, selected after looking at this nice benchmarks: nativejson-benchmark.
Unfortunately, that benchmark does not include Java libraries.
Jansays:
It does make a lot of sense!
Does it look like they claim 16 cycles per byte and you think it is 4? You may be right. Benchmarking is hard. But take a look at the abstract – 10x improvement for “analytical”, “FSM” (and probably some SIMD)?
Analytical? Dom style parser will always loose reading 3 out of 20 (per record). I would expect streaming parser to do 2x+ better. No allocations, copying or parsing digits into numbers nobody will use.
How are streaming parsers implemented? Which one is not a loop reading character by character (byte by byte)? Can any compiler vectorize that? (and remove branching?)
Modern regexp libraries (like hyperscan) show great results with vectorized FSM. I believe such techniques would speed up analytical query over json (scanning for 50 bytes out of 1000 bytes record).
Does it matter? Json is de facto standard format for data exchange between companies these days. Many open datasets and just about every startup use json extensively. So yeah, if someone (Microsoft?) spend the time doing it, please open source it! I would greatly appreciate having it in spark!
BTW: No, you will not get 10x in practice. Nobody does json, everybody does json.gz. But gzip is very slow. Thanks to Amdahl’s law you will get only 2x improvement with vectorized FSM json parser. Gunzip will take 90% cpu then.
Great pointer: it’s fast and header-only. Thanks a lot!
Regarding Java vs C++. They are pretty close. In the land of the search engines, we see more carefully implemented Java engines beat C++ implementations. We all know Lucene is very fast and hard to beat. There is another example: Galago is a Java re implementation of Indri. So, it uses a similar query evaluation paradigm, but it is nevertheless about 2x faster.
For some limited kind of work like parsing with projection or parsing of arrays of UUIDs jsoniter-scala can archive 2 bytes per cycle (or ~2Gb per second on contemporary desktops) that is quite competitive with the state of art filter/parsers like Mison or Sparser.
Another question (open to debate): should the cost of parsing include validation? Is it reasonable to quietly return “reasonable’ results of a query on something that isn’t valid JSON?
This is a query that affects Mison more (as far as I can tell). Mison’s ability to skip fields might allow it to pass over JSON syntax errors without noticing (they didn’t publish code, so I can tell for sure).
How fast? It depends…
If you consider Jackson from the JVM world then, please, try jsoniter-scala:
https://github.com/plokhotnyuk/jsoniter-scala
It parses from input streams or byte arrays immediately to Scala data structures without any intermediate representation like strings, hash maps, etc.
So jsoniter-scala is much safer and efficient than any other JSON-parser for Scala.
It has methods for scanning through multi-Gb value streams or JSON arrays and parse values without need to hold them all in memory:
https://github.com/plokhotnyuk/jsoniter-scala/blob/master/core/src/main/scala/com/github/plokhotnyuk/jsoniter_scala/core/package.scala#L79
Also, it has outstanding features like fast skipping of not needed fields (key/value pairs) or crazily fast parsing and serialization of java.time.* classes.
Just see benchmark results below. BTW, they include results for parsing and serialization of messages from the Twitter API:
http://jmh.morethan.io/?source=https://plokhotnyuk.github.io/jsoniter-scala/jdk8.json
All results for JDK 8/10 and GraalVM CE/EE on the one page:
https://plokhotnyuk.github.io/jsoniter-scala/
WARNING: Results of GraalVM CE/EE are only for a rough evaluation of possible potential of this new tech.
Final results can be changed significantly after JMH tool and GraalVM developers will provide mutual compatibility.
In most cases jsoniter-scala works on par with best binary serializers for Java and Scala:
https://github.com/dkomanov/scala-serialization/pull/8
For some limited kind of work like parsing with projection or parsing of arrays of UUIDs jsoniter-scala can archive 2 bytes per cycle (or ~2Gb per second on contemporary desktops) that is quite competitive with the state of art filter/parsers like Mison or Sparser.
Results and code of projection benchmark:
https://github.com/guillaumebort/mison/pull/1
Results (need to scroll down to ArrayOfUUIDsBenchmark section) and code of benchmark for parsing of UUID arrays:
http://jmh.morethan.io/?source=https://plokhotnyuk.github.io/jsoniter-scala/oraclejdk11.json
https://github.com/plokhotnyuk/jsoniter-scala/blob/master/jsoniter-scala-benchmark/src/main/scala/com/github/plokhotnyuk/jsoniter_scala/macros/ArrayOfUUIDsBenchmark.scala
Using a loop with the same input may give an unfair advantage to Java as the JIT may kick in and optimize the code for the input. The effect could exist in C++ at a smaller scale with the branch prediction getting better. As an example of such flawed benchmark: https://github.com/nodejs/node/pull/1457#issuecomment-94188258.
I didn’t read the Microsoft paper, so this is pure speculation on my side.
I am a happy user of RapidJSON, selected after looking at this nice benchmarks: nativejson-benchmark.
Unfortunately, that benchmark does not include Java libraries.
It does make a lot of sense!
Does it look like they claim 16 cycles per byte and you think it is 4? You may be right. Benchmarking is hard. But take a look at the abstract – 10x improvement for “analytical”, “FSM” (and probably some SIMD)?
Analytical? Dom style parser will always loose reading 3 out of 20 (per record). I would expect streaming parser to do 2x+ better. No allocations, copying or parsing digits into numbers nobody will use.
How are streaming parsers implemented? Which one is not a loop reading character by character (byte by byte)? Can any compiler vectorize that? (and remove branching?)
Modern regexp libraries (like hyperscan) show great results with vectorized FSM. I believe such techniques would speed up analytical query over json (scanning for 50 bytes out of 1000 bytes record).
Does it matter? Json is de facto standard format for data exchange between companies these days. Many open datasets and just about every startup use json extensively. So yeah, if someone (Microsoft?) spend the time doing it, please open source it! I would greatly appreciate having it in spark!
BTW: No, you will not get 10x in practice. Nobody does json, everybody does json.gz. But gzip is very slow. Thanks to Amdahl’s law you will get only 2x improvement with vectorized FSM json parser. Gunzip will take 90% cpu then.
Great pointer: it’s fast and header-only. Thanks a lot!
Regarding Java vs C++. They are pretty close. In the land of the search engines, we see more carefully implemented Java engines beat C++ implementations. We all know Lucene is very fast and hard to beat. There is another example: Galago is a Java re implementation of Indri. So, it uses a similar query evaluation paradigm, but it is nevertheless about 2x faster.
Yes. I am not assuming that Java is slower than C++ in actual systems, but RapidJSON is C++ written with performance in mind.
When parsing bytes, there are tricks that are easy in C++ but hard in Java.
Surely being stringly makes JSON inefficient from a processor standpoint anyway?
Also are those 8 cycles / byte a simplification because of amortised costs? (unless it’s unique to Skylake lines).
Surely being stringly makes JSON inefficient from a processor standpoint anyway?
Not necessarily.
Also are those 8 cycles / byte a simplification because of amortised costs? (unless it’s unique to Skylake lines).
It is specific to the machine I tested on.
For some limited kind of work like parsing with projection or parsing of arrays of UUIDs jsoniter-scala can archive 2 bytes per cycle (or ~2Gb per second on contemporary desktops) that is quite competitive with the state of art filter/parsers like Mison or Sparser.
Results and code of projection benchmark:
https://github.com/guillaumebort/mison/pull/1
Results (need to scroll down to ArrayOfUUIDsBenchmark section) and code of benchmark for parsing of UUID arrays:
http://jmh.morethan.io/?source=https://plokhotnyuk.github.io/jsoniter-scala/oraclejdk11.json
https://github.com/plokhotnyuk/jsoniter-scala/blob/master/jsoniter-scala-benchmark/src/main/scala/com/github/plokhotnyuk/jsoniter_scala/macros/ArrayOfUUIDsBenchmark.scala