Simdjson: Parsing gigabytes of JSON per second
github.com
github.com
Looks like the last active discussion of Roaring Bitmaps was 6 years ago: https://news.ycombinator.com/item?id=8796997 possibly when it was first introduced. Interesting comments!
> How do these compare space and performance wise with Judy arrays, which are 256-ary trees whose nodes also distinguish between sparse and dense subsets? https://en.wikipedia.org/wiki/Judy_array
Good question, since the patent on them won't expire until Nov 29, 2020.
Judy arrays seem to be much less known. Looks like today will be Datastructure Thursday; lots of neat stuff to dig into.
It doesn't help that the documentation is very weird.
As an example of a headache, one node type in Judy has a count, followed by that many index bytes, followed by the same number of pointers. In Rust, that would naturally be a struct with two variable-sized fields, which isn't possible, so it's done by defining a struct generic over a pair of array types:
https://github.com/adevore/rudy/blob/300f2cc7842f6329a76fff0...
It looks to me like this is only ever instantiated for 2, 7, or 31 elements, whereas i think for original Judy, it can be any size up to 31 elements (maybe?). Handling a genuinely variable length in Rust would be rather gnarly, because there have to be different types for each length.
I always wondered if relatively recent changes in x86 CPU µarchs broke some of the assumptions that made libjudy perform this great even on Pentium-class hardware, and if the de facto only complete implementation (that I happen to be aware of) could be improved as a consequence, if those changes (i.e., hugely increased cache sizes, etc.) were considered.
What about his floating point conversion software that is basically David Gay's?
His software has very few tests (especially for floating point), there's no paper for the method but nevertheless it apparently gets used at Google almost instantly.
So it looks as if there are connections that regular OSS authors don't have.
I let him know about this and he added the last footnote in [1], but no update of his blog or related github page saying "hah, turns out this was a known method at least in IBM'. It left a slight bad impression in my mind.
So, yeah ..
[1]: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...
See "2 Outline of Approach" section, last 2 paragraphs:
[2]: https://dominoweb.draco.res.ibm.com/reports/rc24100.pdf
Yes, it does not claim anywhere it is his invention - it starts the description of the algorithm with "The common solution", but if you read it, it really looks like the development of the technique as a whole is his; at the end one note says: "The technique described in this blog post is in used within Microsoft Arriba."
If no one had pointed out that it is not his, I would have thought that it was his, the blog post title is "A fast alternative to the fast modulo reduction", and not "How X's algorithm for fast modulo reduction works. My implementation".
However this library maintains roughly constant throughput for both small (eg 300 byte) and large documents, if it’s benchmarks are accurate.
The graph over mb/s for different json-string sizes seem completely bogus. Small sizes should give more overhead and be slower but the line is totally flat.
https://github.com/simdjson/simdjson/blob/master/doc/growing...
I think it perhaps doesn’t fully build json values into fast-to-access data structures but I don’t think this is unique amongst fast json parsers, or indeed necessary.
It seems reasonably believable that it could maintain high throughput if it has minimal setup and keeps everything linear.
The lib doesn't do double keys properly though, and returns the first result instead of the last. If you don't scan to the end each time at look-up and do no expensive hash map-backed tree I understand why it is faster at parsing ...
> When the names within an object are not unique, the behavior of software that receives such an object is unpredictable.
The lib is really nice to use from 5 minutes of testing.
Performance matters
I suppose on the human level the more important reason is I often get requests from non-techies in the company to see snippets from this data. They can read JSON just fine (Well, most of them... a few still insist on using Excel, so I have to flatten the JSON to csv with jq)
I agree with you (depending on the use-case, of course).
I was talking about dumping the data into one of those databases (SQLite, Postgres, or MongoDB) and using their JSON querying functionality.
If, however, you're really talking about a single JSON document, then you're going to be generating that 190GB intermediate JSON file either way. Plugging it into a database to query it just seems like an extra step for little benefit. (It's basically a variant on the question of whether you'll get better whole-pipeline latency from a data warehouse, or a data lake — which has no general answer.)
I don't think there's any reason it's necessary to have an 190gb json file, nor anything stopping one from incrementally dumping it into Sqlite. Though it would depend on the format of the proprietary file.
But I will add that there's an obvious benefit to dumping the data into the database: it has indexes and querying capacity that doesn't involve full 190GB file scans. The I/O of a 190gb scan alone takes time.
[0]: http://ndjson.org/
[0]: https://github.com/ndjson/ndjson.github.io/issues/1
[1]: https://github.com/ndjson/ndjson.github.io/issues/1#issuecom...
The problem with splunk is that it’s way less expressive than perl, grep, etc, so there are certain useful analyses that simply can’t be run.
To work around that, I see applications duplicate information over and over in their log output.
The end result vs text files is a 2x blow up because of JSON, then a 5-10x blow up because of splunk.
It’s not hard to implement a distributed log processor on top of ssh, and I think open source solutions exist. I don’t know why more companies don’t do that.
As a side benefit, your log files stay human readable. In addition to being more flexible, in practice, the result is something like an order of magnitude cheaper and faster than splunk.
It is real-world in terms of exposing I/O bottlenecks, if they exist in the architecture (compared to GPU, for example). I suspect it is the default/natural metric these researchers use rather than an exercise in cherry picking results.
The underlying question is a good one: when does it make sense to adopt a SIMD library for JSON parsing?
One of my favourite examples of this is numerical values, which is notably called out in the performance results for this library as being one of the slowest paths.
In a textual format you need to read digits and accumulate them, and JSON allows floating-point which is even more complex to correctly parse.
In a binary format, you read n bytes and interpret it as an integer or a floating-point value directly. One machine instruction instead of dozens if not hundreds or more.
I see such inefficiencies so often that I wonder if most developers even know how to read/write binary formats anymore...
"The fastest way to do something is to not do it at all."
IF it's a raw binary format. Other formats, such as protocol buffers, use packed representations in order to save space.
At least by separating the compression from the encoding you have a choice of when decompression vs decoding will happen.
I also believe (but am not prepared to prove) that packed representations can, under the right circumstances, evade some information theoretic limits that constrain lossless compression, by engaging in a little honest cheating. Since you're using a purpose-specific format instead of creating a general-purpose compression scheme, you don't have to record every single bit of information in the blob itself. You can use a side channel - in the form of the format specification itself - to record some information.
Which is why you see a packed representation (perhaps with optional compression) in things like protocol buffers, whereas a format like Parquet that's meant to store large volumes of self-describing data will just go straight for compression.
There are cases where what you are saying makes a lot of sense, and for that you have things like FlatBuffers & CapnProto.
All a compression algorithm has to do to get similar advantages to varint is notice that 0-valued bytes are common and compress them. A simple Huffman coding will do that nicely.
Is varint actually "way, way faster" than Huffman? I don't think it's entirely clear -- it probably depends on the implementation. Protobuf generated code inlines copies of varint encoding all over the place, which is better than not inlining, but still not very nice to the instruction cache. Huffman coding would process the entire buffer in one go and can be a much tighter loop. A lot of work has gone into optimizing Huffman coding, including with things like SIMD. You can't really leverage SIMD for Varints in Protobuf because the input is not a homogenous array. Varint is known to be a very branchy format which is not so great for performance. Branchless Huffman is a thing.
You can probably do even better with an algorithm tailor-made to look for zeros. I took a crack at this with "packed" format in Cap'n Proto, which I implemented in a branchless way, but not with SIMD (I'm no good at assembly). It's been like 7 years since I did the benchmarks but IIRC capnp+packing turned out to be pretty similar to protobuf in both size and speed... but there are a lot of confounding factors there. Could be interesting to replace Varint with fixed-width encoding in Protobuf itself and then run packing on the output and see how that performs...
But it really doesn't seem obvious to me at all that Varint would be "much faster" than a matching compression algorithm. Do you have some data behind that or is it just a hunch?
Disclaimer: I'm not a compression expert. I am the author of Protobuf v2 though. My recollection is that the original designers of Protobuf were never very happy with varint encoding. It was a casual decision made early on that became impossible to change later.
I wonder if this implies lz4 pairs well with Protobuf (since it does Varint) but that Cap'n Proto users should look at different algorithms (or maybe apply packing followed by lz4).
Source: https://en.wikipedia.org/wiki/LZ4_(compression_algorithm)
UTF-8-style varints, where the encoded length can be determined entirely from the first byte, are much nicer.
Flatbuffers, Cap'nproto, and similar formats can pad everything else for alignment, at the cost of easily compressible nulls. For a lot of use cases, that's a good trade off.
> Varint is not compression. Proper compression looks for redundancy in data and eliminates it.
I'm not sure why you are choosing to make a semantic argument about an assertion I didn't make, but very well. Compression is any mechanism that allows you to encode information using fewer bits than the original representation. There are compression mechanisms that don't require there to be any redundancy within the data they are compressing (for example, with a fixed dictionary).
> Huffman coding would process the entire buffer in one go and can be a much tighter loop.
That's a very good point, except part of how lz4 pulls off the wonders that it pulls off is by not having an entropy encoding stage... so no Huffman coding going on there. You can optimize Huffman coding all you want, but it still going to be slower than lz4's "not doing it" (hence why lz4 is so fast), which is in turn slower than varint.
You're right, you can't really leverage x86's various SIMD extensions for varints, because varints are usually only less than four bytes long. On the other hand, you can use normal processor instructions for executing an instruction in parallel on a sequence of bytes packed in to a 32-bit or 64-bit register. I agree that protobuf has some surprisingly untuned logic for this (in fairness, the three bits reserved for field identifiers does hamper taking advantage of it, but then those also screw up the use of SIMD instructions in general).
I agree that I found capnp+packing to be very competitive with protobuf for certain applications, as you had promised. However, as you said, there are confounding factors there.
The notion that varint is much faster is intuitive rather than benchmarks. I've looked at the assembly for a varint decoder and compared it to lz4. While the lz4 might be able to win out if you are trying to decode a long sequence of bytes, it's all over but the crying within a a few instructions for simply decoding a small integer.
> My recollection is that the original designers of Protobuf were never very happy with varint encoding. It was a casual decision made early on that became impossible to change later.
That is my recollection as well (although a lot of the pain was around the ugly work around for signed integers). Varint isn't the best thing, but it is a thing, and if used properly, it does yield advantages.
If the data you have requires more thought as to how to store it than "JavaScript's object notation is good enough," then perhaps a specialized binary format would work better.
Then again, nearly all APIs only accept and receive JSON. JSON is the one object notation that gets all the attention, so most maintainers will focus their time making optimizations for reading or writing JSON. And if you don't like XML or YAML for some reason, then JSON is tempting to use as a config file format, although it critically lacks comments or heredocs.
My understanding is that they run a code that does 2000 branches based on a pseudo-random sequence. Over around 10 runs of that code, the CPU supposedly learns to correctly predict those 2000 branches and the performance steadily increases.
Do the modern branch predictors really have the capability to remember an exact sequence of past 2000 decisions on the same branch instruction? Also, why would the performance increase incrementally like that? I would imagine that it would remember the loop history on the first run and achieve maximum performance on the second run.
I doubt that there's really a neural net in the silicon doing this as the author speculates.
There is a wealth of patents and articles if you search for "neural net branch prediction patent".
[1] https://cdn.arstechnica.net/wp-content/uploads/sites/3/2016/...
This slide is about speculative execution not necessarily about branch prediction.
I did some more searching and found an article at https://acad.ro/sectii2002/proceedings/doc2019-2/12-Vintan.p... which describes Samsung Galaxy S7 phones having these type of branch predictors as far back as 2016 and AMD CPUs having perceptron based branch predictors as far back as 2011. It was not officially known if Intel also uses neural networks in their chips, but the author of that paper "strongly believes" it does and I concur that it's unlikely they don't given that Samsung, Oracle, IBM, ARM and AMD all seem to use them.
To learn more about state of start BP look for Andre Seznec (INRIA/IRISA) and Daniel Jimenez (Texas A&M University) work. They are usually the winners of Championship Branch Prediction [2,3].
[1] https://fuse.wikichip.org/news/2458/a-look-at-the-amd-zen-2-...
Performance-sensitive json-parsing Node users must do this instead:
require("simdjson").lazyParse(jsonString).valueForKeyPath("foo.bar[1]")
The idea being that characters that are more common in the underlying language would be represented as lower integers and then use varint encoding so that the data itself is smaller.
I did some experiments here and was able to compress our data by 25-45% in many situations.
There are multiple issues here though. If you're compressing the data anyway you might not have as big of a win in terms of storage but you still might if you still need to decode the data into its original text.
Still, though, you could have a fixed-size encoding that could still be more compact than UTF-8, if you limited what it could encode (and then held either it, or UTF-8 text, in a tagged union, as an ADT wrapped with an API of string operations that will implicitly "promote" your limited encoding to UTF-8 if the other arg is UTF-8, the same way integers get "promoted" to floats when you math them together.)
Then your limited-encoding text could hold and manipulate e.g. ASCII, or Japanese hiragana and katakana, or APL, or whatever else your system mostly holds, as a random-access array of single-octet codepoints; until something outside of that stream comes up, at which point you get UTF-8 text instead and your random-access operations become shimmed by seq-scans.
(Or you get a rope with both UTF-8 strings and limited-encoding strings as leaf nodes!)
Of course, if you didn't catch it, I'm talking about going back to having code pages. :) Just, from a perspective where everything is "canonically" UTF-8 and code pages are an internal optimization within your string ADT; rather than everything "canonically" being char[] of the system code page.
Most common Lempel-Ziv compressors (gzip/brotli/zstd) use some form of entropy encoding (Huffman/Arithmetic/ANS) but that is in addition to lz algorithm (usually lz77) itself.
You can have a Lempel-Ziv compressor that doesn't use entropy encoding, look at something like lz4.
lz77 essentially works by copying parts of the recent window of decompressed data. e.g if a phrase of length 10 was used 100 characters ago we could encode 100,10 instead of the phrase itself. Most compressors use entropy encoding on those offset and length streams.
It looks like pysimdjson's biggest performance gain compared to e.g. orjson is when you can cherry-pick single values out of the JSON and avoid deserializing the whole document.
You see a real benefit when you don't need or want the entire document, and can use the JSON pointer or proxy object interface.
I needed to parse a very very large JSON document and pull out a subset of data, which didn't work, because it exceeded available RAM.
But it's a good project, otherwise.
Consequently it swapped so hard I was never going to finish processing. So I used a streaming parser, and it finished in minutes.
I don't think it's the bottleneck at the moment, but it's good to know there are faster parsers out there. Had a small search but couldn't find any plans to incorporate simdjson, besides a thread from last year on Emacs China forums.
This comment is incorrect: https://github.com/simdjson/simdjson/blob/v0.4.7/src/haswell...
The behavior of that instruction is well specified for all inputs. If the high bit is set, the corresponding output byte will be 0. If the high bit is zero, only the lower 4 bits will be used for the index. Ability to selectively zero out some bytes while shuffling is useful sometimes.
I’m not sure about this part: https://github.com/simdjson/simdjson/blob/v0.4.7/src/simdpru... popcnt instruction is very fast, the latency is 3 cycles on Skylake, and only 1 cycle on Zen2. It produces same result without RAM loads and therefore without taking precious L1D space. The code uses popcnt sometimes, but apparently the lookup table is still used in other places.
I think you are misinterpreting the way that "undefined" is being used here. It's not a claim that one will get unpredictable results for this particular implementation, rather it's about the specification of the function. It's telling the user that the behavior of this function for out of range values is not guaranteed to remain the same across time as the code is changed, or across different architectures.
> I’m not sure about this part: ... popcnt instruction is very fast
I haven't worked on this particular code, but I've coauthored a paper with Daniel on beating popcnt using AVX2 instructions: https://lemire.me/en/publication/arxiv1611.07612/. While you are right that at times saving L1 space is a greater priority, I'd bet that the approach used here was tested and found to be faster on Haswell. I'm not sure if you noticed that the page you linked is Haswell specific?
That “function” compiles into a single CPU instruction. The OP is perfectly aware of that, that’s why really_inline is there.
> on beating popcnt using AVX2 instructions
It’s easy to do with pshufb when you have many values on input. I have wrote about it years before that article, see there: https://github.com/Const-me/LookupTables#test-results
> I'd bet that the approach used here was tested and found to be faster on Haswell
I'd bet it’s an error.
> if you noticed that the page you linked is Haswell specific
I did. Was disappointed though, I expected to find something newer than Haswell from 2013, like Zen 2 or Skylake. When doing micro-optimizations like that, the exact micro-architecture matters.
I'm sure optimizations for more recent architectures would be appreciated, and Daniel is wonderfully accepting of patches. Be careful though, or you might inadvertently end up as the maintainer of the whole project!
https://github.com/simdjson/simdjson/blob/master/singleheade...
enum instruction_set {
DEFAULT = 0x0,
NEON = 0x1,
AVX2 = 0x4,
SSE42 = 0x8,
PCLMULQDQ = 0x10,
BMI1 = 0x20,
BMI2 = 0x40
};
#if defined(__arm__) || defined(__aarch64__) // incl. armel, armhf, arm64
#if defined(__ARM_NEON)Anyone knows what library does V8 use or how does it compare?
ie.
{
// 100GB of data
}[1] It might be the case that modern benchmark-obsessed JS engines defer JSON parsing in this case though, in which case you definitely should not switch to simdjson.
I broke those out into a Rust library that was >100x faster (IIRC) in synthetic benchmarks with the same complexity. Plugging it in with FFI into the Nodejs app and it actually performed slightly worse due to FFI overhead and translation.
So for large documents; could be worth it. For lots of small objects; probably not. You'd have to try on real-world data for your use-case to know.
This is interesting. Have you tried to optimize for reducing the overhead? I can imagine that this can be hard/complex and require a refactoring of the consumer in some scenarios.