4 ms·

Compression algos come with their own disadvantages. Varint encoding exploits the normal distribution/Benford's law type reality that the vast majority of fixed

Compression 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 ago
Varint 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.
- kentonv 6y ago
  Hmm, I guess, ironically, lz4 does not do a Huffman pass, unlike most other compression algorithms. It only does dictionary-matching, which I imagine has a tougher time squeezing the zeros out of fixed-width-encoded integers. 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) https://en.wikipedia.org/wiki/LZ4_(compression_algorithm)
  - cbsmith 6y ago
    My experience is indeed that lz4 tends to work reasonably well on protobuf encoded data, which generally does not compress terribly well. I hadn't much thought about why, but your reasoning makes sense.
- mumblemumble 6y ago
  I'd love to hear more on that last part, if you care to share more details. I've always been a little curious if varints are worth the effort, at least as a default format. Seems like there's a decent chance that what you gain by shaving bytes, you lose in branch instructions.
- neild 6y ago
  Protobuf varints are particularly annoying because they require searching for a terminating byte. A naive implementation needs to make 20 comparisons to decode an 8-byte int (checking the value of each byte, and for overflow in the input data). UTF-8-style varints, where the encoded length can be determined entirely from the first byte, are much nicer.
  - cbsmith 6y ago
    Again, for small integers, this isn't really much of a disadvantage. You can find the terminating byte very efficiently. The bigger issue with varint tends to be more that when you pack data into bytes you have a lot more unaligned memory access. You can work around this, but it increases the complexity of your decoder. 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.

kentonv 6y ago

Varint 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.

kentonv 6y ago
Hmm, I guess, ironically, lz4 does not do a Huffman pass, unlike most other compression algorithms. It only does dictionary-matching, which I imagine has a tougher time squeezing the zeros out of fixed-width-encoded integers. 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) https://en.wikipedia.org/wiki/LZ4_(compression_algorithm)
- cbsmith 6y ago
  My experience is indeed that lz4 tends to work reasonably well on protobuf encoded data, which generally does not compress terribly well. I hadn't much thought about why, but your reasoning makes sense.
mumblemumble 6y ago
I'd love to hear more on that last part, if you care to share more details. I've always been a little curious if varints are worth the effort, at least as a default format. Seems like there's a decent chance that what you gain by shaving bytes, you lose in branch instructions.
neild 6y ago
Protobuf varints are particularly annoying because they require searching for a terminating byte. A naive implementation needs to make 20 comparisons to decode an 8-byte int (checking the value of each byte, and for overflow in the input data). UTF-8-style varints, where the encoded length can be determined entirely from the first byte, are much nicer.
- cbsmith 6y ago
  Again, for small integers, this isn't really much of a disadvantage. You can find the terminating byte very efficiently. The bigger issue with varint tends to be more that when you pack data into bytes you have a lot more unaligned memory access. You can work around this, but it increases the complexity of your decoder. 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.