However this library maintains roughly constant throughput for both small (eg 300 byte) and large documents, if it’s benchmarks are accurate.
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?
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.
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.
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.