6 ms·
Indeed, I feel like much of this is self-inflicted and could be avoided completely if only more developers would learn to use far more compact and efficient bin
by userbinator 6y ago
Indeed, I feel like much of this is self-inflicted and could be avoided completely if only more developers would learn to use far more compact and efficient binary formats instead, where parsing (if it could even be called that) is just a natural consequence of reading the data itself.
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."
- mumblemumble 6y ago> In a binary format, you read n bytes and interpret it as an integer or a floating-point value directly. IF it's a raw binary format. Other formats, such as protocol buffers, use packed representations in order to save space.
- CoolGuySteve 6y agoThis always struck me as being dumber than streaming the whole file through lz4 or something similar. At least by separating the compression from the encoding you have a choice of when decompression vs decoding will happen.
- lalaithion 6y agoDoes lz4 really have low enough overhead that it can compress a single integer better than having a predetermined compression scheme for small numbers? Sure, most protos are not a single integer, but i'd doubt it if the average proto message was more than 1 kb.
- cbsmith 6y agolz4 is kind of amazing, but yes, it does not really help when compressing a single integer.
- mumblemumble 6y agoFor certain inputs, compression doesn't necessarily work out so well, because of the overhead introduced by the compression format itself. For example, "compressing" a small datagram may actually make it larger. 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.
- cbsmith 6y agoCompression algos come with their own disadvantages. Varint encoding exploits the normal distribution/Benford's law type reality that the vast majority of fixed point numbers tend to be closer to zero than their upper bounds. As fast as lz4 is, encoding & decoding varint is way, way faster. There are other advantages too... lz4 works at the block level, rather than the field level, so you have effects from surrounding fields and the need to decode all the fields/records at once. You also need a certain size block for it to really be useful... There are cases where what you are saying makes a lot of sense, and for that you have things like FlatBuffers & CapnProto.
- kentonv 6y agoVarint is not compression. Proper compression looks for redundancy in data and eliminates it. 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.
- tjchear 6y agoAnd if the source architecture and destination architecture use identical endian-ness.
- beached_whale 6y agoFun fact, JSON's number type isn't floating point. It may map to it, but the limits on the numbers that are representible are defined by the encoder and decoder.
- deleted 6y ago[deleted]
- cbsmith 6y agoWhich creates this lovely reality where you effectively have numbers that can be accurately represented in IEEE float but can't be represented accurately in decimal notation, and numbers that can be represented accurately in decimal notation but not in IEEE float. All of those cases are dicey with JSON.
- beached_whale 6y agoCurious, what number is representable in IEEE float but not as a decimal?
- nayuki 6y ago+Infinity, -Infinity, NaN (quiet, signaling, miscellaneous).
- beached_whale 6y agoWell, those are all error conditions and not a number. NaN's explicitly say they aren't, and +-Inf may or may not be infinity, all we know is that it is outside the representable range of IEEE floating point.
- derefr 6y agoIMHO, code should check for floating-point overflow just like it checks for integer overflow. If your inputs are finite and your output is infinite, that's similar to your inputs being positive and your output being negative: you should check for it and emit an error instead. Then infinity (like negative numbers) can have an actual semantic meaning, rather than just being the detritus of an error condition.
- zwieback 6y agoHaving grown up with 8bit home computers everything about the web seems insanely inefficient. But text formats do have undeniable upside. Best would be more portable efficient formats like protobuf.
- smolder 6y agoThis is why I love using serde bincode serialization. I can even deal with serde bincode binary blobs inside rust based wasm on the front end. It can save a ton of bytes on the wire, used appropriately.
- alfalfasprout 6y agoUnfortunately, binary formats still have plenty of issues too like usually requiring schemas (msgpack doesn't but it's MUCH slower than something with a schema like flatbuffers). They also are fairly clunky for handling nested structured data (eg; arrays of maps).
- nonbirithm 6y agoIt might be worth noting that, by the words of Douglas Crockford, JSON wasn't even at first specified, it was "discovered."[0] As in, a small group of people at a startup were wanting an object interchange format they could use in the browser in the early 2000s, found that JavaScript object literals worked good enough, and went with that. It only became a standard after the fact. 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. [0] http://www.json.org/fatfree.html http://www.json.org/fatfree.html