6 ms·

vu128: Efficient variable-length integers

93 points by jmillikin 2y ago

chubot 2y ago
FWIW the lobste.rs thread surfaced this 2016 comment thread about PrefixVarint vs. LEB128 varint in protobufs, which has lots of good info, and makes the UTF-8 analogy: https://news.ycombinator.com/item?id=11263378 https://news.ycombinator.com/item?id=11263378 Also sqlite varint: https://sqlite.org/src4/doc/trunk/www/varint.wiki https://sqlite.org/src4/doc/trunk/www/varint.wiki
- akira2501 2y ago
  > Also sqlite varint: That's not actually in use. The SQLite3 format is far more basic: "A variable-length integer or "varint" is a static Huffman encoding of 64-bit twos-complement integers that uses less space for small positive values. A varint is between 1 and 9 bytes in length. The varint consists of either zero or more bytes which have the high-order bit set followed by a single byte with the high-order bit clear, or nine bytes, whichever is shorter. The lower seven bits of each of the first eight bytes and all 8 bits of the ninth byte are used to reconstruct the 64-bit twos-complement integer. Varints are big-endian: bits taken from the earlier byte of the varint are more significant than bits taken from the later bytes." From: https://www.sqlite.org/fileformat2.html https://www.sqlite.org/fileformat2.html Section 1.6
vitiral 2y ago
zig-zag encoding is brilliant. Basically you can determine positive or negative based on odd/even and divide by 2 to get the value. I tried to come up with a similar encoding and never thought of this
- repelsteeltje 2y ago
  Yeah basically it's ones complement (or twos complement) but with the sign bit on the right, rather than the left.
- edflsafoiewq 2y ago
  It's the same as enumerating 2D points in a spiral, but restricted to 1D.
deleted 2y ago
[deleted]
Const-me 2y ago
When I need them I usually implement the codec used in MKV format: https://www.rfc-editor.org/rfc/rfc8794.html https://www.rfc-editor.org/rfc/rfc8794.html Similar performance characteristics, i.e. just the first byte tells the encoded length, no need to test every byte. Luckily, most programming languages have intrinsic functions for BSWAP instruction.
- repelsteeltje 2y ago
  Mkv (and av1, vp8, vp9) use the leb128 format which the article mentions is inefficient parse for off the shelf CPUs. Leb128 is relatively efficient in bitstream and sidesteps potential mpeg-la patent issues. (H264, maybe 14496 part 14)
  - Const-me 2y ago
    I don't think they do. These formats are based on EBML, see the RFC link in my previous comment. That VINT encoding is not LEB128, it's better. BTW I once implemented my own parser in C#, see that source file: https://github.com/Const-me/Vrmac/blob/master/VrmacVideo/Containers/MKV/Primitives.cs https://github.com/Const-me/Vrmac/blob/master/VrmacVideo/Con...
deleted 2y ago
[deleted]
kunley 2y ago
There is also SQLite varint, https://sqlite.org/src4/doc/trunk/www/varint.wiki https://sqlite.org/src4/doc/trunk/www/varint.wiki IIRC different from both Leb128 and VLQ, and quite neat. It's for 64bit (u)ints, though
terrelln 2y ago
Variable-length integer schemes are great when you are encoding one integer. But when you are encoding a list of integers, you should really consider a different scheme. Variable-length integer schemes generally interleave the control bits & data bits. This means you don't know where the next integer starts until you at least partially decode the current integer. When encoding a list of integers, you would rather put all the control information together, and all the data together. This generally allows for significantly more efficient decoding using SIMD.
- tatersolid 2y ago
  Don’t forget column-stores. Lists of floats and ints are generally “full size” but then XORed with the preceding value then the result is compressed in chunks with a high-speed compressor like LZ4. We see 20x or higher compression ratios on many of our column-stores which contain data such as invoice amounts as metrics. Decompression overhead is below zero (much faster than operating on the raw uncompressed data which is bound by memory bandwidth or IO)
- lifthrasiir 2y ago
  Yeah, see Stream VByte [1] for more information. [1] https://arxiv.org/abs/1709.08990 https://arxiv.org/abs/1709.08990
zigzag312 2y ago
How does it compare to vint64[0] performance-wise? For values that fit the 64-bit space. [0] https://crates.io/crates/vint64 https://crates.io/crates/vint64
- lifthrasiir 2y ago
  This is another variation of putting control bits to the first byte, where the number of following bytes is indicated by the number of trailing 1 bits instead of leading 1 bits. I'm not sure which one is more efficient though.
danking00 2y ago
If I’m following, this presents an alternative format and implementation to LEB128 which encodes and decodes substantially faster. Notably, the implementation is quite simple. Cool! And agreed that modern CPUs really suffer from branches. Should I interpret the plot to mean the average elapsed wall clock time per integer decoded/encoded? And can I conclude the throughput is the reciprocal? So about 100,000 integers per second or around a 1 MB/s of decompressed data. I know this is a bit unfair because the implementation is much more complex, but my first thought is why I would use vu128 instead of Lemire’s Stream VByte: https://arxiv.org/abs/1709.08990 https://arxiv.org/abs/1709.08990 A slight tangent but I stumbled on this library which stores floats XOR’ed with the previous float in the stream: https://github.com/velvia/compressed-vec https://github.com/velvia/compressed-vec it seems really clever to me! They reference “Gorilla: A Fast, Scalable, In-Memory Time Series Database” which in turn references two 2006 papers: “Fast Lossless Compression of Scientific Floating-Point Data” and “Fast and Efficient Compression of Floating-Point Data”. Frustratingly, the FB paper doesn’t benchmark their XOR-based floating point encoding but the earlier two papers do.
- jmillikin 2y ago
  The plot is the time to encode/decode a list of 10,000 random integers in a uniform distribution. The throughput is 2-10 GiB/s[0] on my desktop, with portable scalar operations (no SIMD). Distributions skewed toward small values are slightly faster[1]. I believe a decoder than used SIMD would perform even faster since the format is friendly to the BMI instructions found on newer CPUs. You could also store the data as concat(prefix_bytes) + concat(payloads), which would really get things going. For scientific data with lots of multi-byte f64 values, the single branch for < 0xF0 might be unnecessary and undesirable. There are other formats that can be decoded by completely branchless SIMD, at the cost of larger sizes for very small values. For example, Google has a format that uses the first byte as a bitmask: https://static.googleusercontent.com/media/research.google.com/en//people/jeff/WSDM09-keynote.pdf https://static.googleusercontent.com/media/research.google.c... [0] vu128 is less affected by value size than VLQ/LEB128, so on fast hardware it decodes 10,000 8-bit values in about the same time as 10,000 64-bit values. [1] In the discussion on lobste.rs[2] a user wondered what the results would look like with a distribution containing lots of small values. A zipf distribution's results looks like <https://i.imgur.com/WGFtz6f.png https://i.imgur.com/WGFtz6f.png>. [2] https://lobste.rs/s/qvoe7a/vu128_efficient_variable_length#c_zo4swo https://lobste.rs/s/qvoe7a/vu128_efficient_variable_length#c...
ixau 2y ago
In terms of serializing JSON to a binary representation, which includes variable length integers, check CBOR https://datatracker.ietf.org/doc/html/rfc8949 https://datatracker.ietf.org/doc/html/rfc8949
lifthrasiir 2y ago
As with many other variable-length integer encodings, its efficiency really depends on the expected input distribution. One glaring issue in this regard is that its 2-byte encoding is rather wasted: only 6.25% out of all possible encodings are useful. This can be possibly fixed by making the 2-byte encoding represent 240..495 instead of 0..255. You can even make use of some bits from the first byte, so that for example the sequence goes like: 0=00 1=01 2=02 .. BF=BF C0=C0C0 C1=C0C1 .. 30FF=F0FF 3100=F13100 .. (all in hex). A radically different design, used by for example 7z, is also possible if you put all continuation bits into the first byte. For example, instead of having `1xxxxxxx 1yyyyyyy 0zzzzzzz` for 3-byte encoding, use `110xxxxx yyyyyyyy zzzzzzzz`. This is essentially as compact as more common VLQ and LEB128 encodings, but you can determine the length of the whole sequence from the first byte alone! Unfortunately this is less suitable for integers larger than 64 bits, because then you run out of bits in the first byte. But it ends up with a rather elegant encoding for 64-bit integers, where `11111110` indicates 7 bytes and `11111111` indicates 8 bytes with no additional 0 bit needed. > An afternoon of web searching has failed to uncover a prior name for this particular encoding, so I'm going to name it vu128 and describe it below. If any reader knows of prior art, please send it my way. I don't know if it has other names, but a similar encoding can be seen from X.690 [1] and the "additional information" bit field of CBOR [2]. [1] https://en.wikipedia.org/wiki/X.690#Length_octets https://en.wikipedia.org/wiki/X.690#Length_octets [2] https://www.rfc-editor.org/rfc/rfc8949.html#section-3 https://www.rfc-editor.org/rfc/rfc8949.html#section-3
- klabb3 2y ago
  > Unfortunately this is less suitable for integers larger than 64 bits, because then you run out of bits in the first byte. Just spitballing here but is it necessary to support every increment of octets? Do we really need a 7 octet/56bit width for instance? Instead couldn’t we just allow widths of log2(n_octets)? An int64 would need 2 bits of length info (8, 16, 32, 64). Or maybe I’m thinking wrong cause not all bits are can be used. > its efficiency really depends on the expected input distribution Right. But everything else in computers is rounded to the nearest power of 2, so maybe it works here too haha.
  - lifthrasiir 2y ago

93 points by jmillikin 2y ago

FWIW the lobste.rs thread surfaced this 2016 comment thread about PrefixVarint vs. LEB128 varint in protobufs, which has lots of good info, and makes the UTF-8 analogy: https://news.ycombinator.com/item?id=11263378 https://news.ycombinator.com/item?id=11263378 Also sqlite varint: https://sqlite.org/src4/doc/trunk/www/varint.wiki https://sqlite.org/src4/doc/trunk/www/varint.wiki

akira2501 2y ago
> Also sqlite varint: That's not actually in use. The SQLite3 format is far more basic: "A variable-length integer or "varint" is a static Huffman encoding of 64-bit twos-complement integers that uses less space for small positive values. A varint is between 1 and 9 bytes in length. The varint consists of either zero or more bytes which have the high-order bit set followed by a single byte with the high-order bit clear, or nine bytes, whichever is shorter. The lower seven bits of each of the first eight bytes and all 8 bits of the ninth byte are used to reconstruct the 64-bit twos-complement integer. Varints are big-endian: bits taken from the earlier byte of the varint are more significant than bits taken from the later bytes." From: https://www.sqlite.org/fileformat2.html https://www.sqlite.org/fileformat2.html Section 1.6

vitiral 2y ago

zig-zag encoding is brilliant. Basically you can determine positive or negative based on odd/even and divide by 2 to get the value. I tried to come up with a similar encoding and never thought of this

repelsteeltje 2y ago
Yeah basically it's ones complement (or twos complement) but with the sign bit on the right, rather than the left.
edflsafoiewq 2y ago
It's the same as enumerating 2D points in a spiral, but restricted to 1D.

deleted 2y ago

[deleted]

Const-me 2y ago

When I need them I usually implement the codec used in MKV format: https://www.rfc-editor.org/rfc/rfc8794.html https://www.rfc-editor.org/rfc/rfc8794.html Similar performance characteristics, i.e. just the first byte tells the encoded length, no need to test every byte. Luckily, most programming languages have intrinsic functions for BSWAP instruction.

repelsteeltje 2y ago
Mkv (and av1, vp8, vp9) use the leb128 format which the article mentions is inefficient parse for off the shelf CPUs. Leb128 is relatively efficient in bitstream and sidesteps potential mpeg-la patent issues. (H264, maybe 14496 part 14)
- Const-me 2y ago
  I don't think they do. These formats are based on EBML, see the RFC link in my previous comment. That VINT encoding is not LEB128, it's better. BTW I once implemented my own parser in C#, see that source file: https://github.com/Const-me/Vrmac/blob/master/VrmacVideo/Containers/MKV/Primitives.cs https://github.com/Const-me/Vrmac/blob/master/VrmacVideo/Con...

deleted 2y ago

[deleted]

kunley 2y ago

There is also SQLite varint, https://sqlite.org/src4/doc/trunk/www/varint.wiki https://sqlite.org/src4/doc/trunk/www/varint.wiki IIRC different from both Leb128 and VLQ, and quite neat. It's for 64bit (u)ints, though

terrelln 2y ago

Variable-length integer schemes are great when you are encoding one integer. But when you are encoding a list of integers, you should really consider a different scheme. Variable-length integer schemes generally interleave the control bits & data bits. This means you don't know where the next integer starts until you at least partially decode the current integer. When encoding a list of integers, you would rather put all the control information together, and all the data together. This generally allows for significantly more efficient decoding using SIMD.

tatersolid 2y ago
Don’t forget column-stores. Lists of floats and ints are generally “full size” but then XORed with the preceding value then the result is compressed in chunks with a high-speed compressor like LZ4. We see 20x or higher compression ratios on many of our column-stores which contain data such as invoice amounts as metrics. Decompression overhead is below zero (much faster than operating on the raw uncompressed data which is bound by memory bandwidth or IO)
lifthrasiir 2y ago
Yeah, see Stream VByte [1] for more information. [1] https://arxiv.org/abs/1709.08990 https://arxiv.org/abs/1709.08990

zigzag312 2y ago

How does it compare to vint64[0] performance-wise? For values that fit the 64-bit space. [0] https://crates.io/crates/vint64 https://crates.io/crates/vint64

lifthrasiir 2y ago
This is another variation of putting control bits to the first byte, where the number of following bytes is indicated by the number of trailing 1 bits instead of leading 1 bits. I'm not sure which one is more efficient though.

danking00 2y ago

If I’m following, this presents an alternative format and implementation to LEB128 which encodes and decodes substantially faster. Notably, the implementation is quite simple. Cool! And agreed that modern CPUs really suffer from branches. Should I interpret the plot to mean the average elapsed wall clock time per integer decoded/encoded? And can I conclude the throughput is the reciprocal? So about 100,000 integers per second or around a 1 MB/s of decompressed data. I know this is a bit unfair because the implementation is much more complex, but my first thought is why I would use vu128 instead of Lemire’s Stream VByte: https://arxiv.org/abs/1709.08990 https://arxiv.org/abs/1709.08990 A slight tangent but I stumbled on this library which stores floats XOR’ed with the previous float in the stream: https://github.com/velvia/compressed-vec https://github.com/velvia/compressed-vec it seems really clever to me! They reference “Gorilla: A Fast, Scalable, In-Memory Time Series Database” which in turn references two 2006 papers: “Fast Lossless Compression of Scientific Floating-Point Data” and “Fast and Efficient Compression of Floating-Point Data”. Frustratingly, the FB paper doesn’t benchmark their XOR-based floating point encoding but the earlier two papers do.

jmillikin 2y ago
The plot is the time to encode/decode a list of 10,000 random integers in a uniform distribution. The throughput is 2-10 GiB/s[0] on my desktop, with portable scalar operations (no SIMD). Distributions skewed toward small values are slightly faster[1]. I believe a decoder than used SIMD would perform even faster since the format is friendly to the BMI instructions found on newer CPUs. You could also store the data as concat(prefix_bytes) + concat(payloads), which would really get things going. For scientific data with lots of multi-byte f64 values, the single branch for < 0xF0 might be unnecessary and undesirable. There are other formats that can be decoded by completely branchless SIMD, at the cost of larger sizes for very small values. For example, Google has a format that uses the first byte as a bitmask: https://static.googleusercontent.com/media/research.google.com/en//people/jeff/WSDM09-keynote.pdf https://static.googleusercontent.com/media/research.google.c... [0] vu128 is less affected by value size than VLQ/LEB128, so on fast hardware it decodes 10,000 8-bit values in about the same time as 10,000 64-bit values. [1] In the discussion on lobste.rs[2] a user wondered what the results would look like with a distribution containing lots of small values. A zipf distribution's results looks like <https://i.imgur.com/WGFtz6f.png https://i.imgur.com/WGFtz6f.png>. [2] https://lobste.rs/s/qvoe7a/vu128_efficient_variable_length#c_zo4swo https://lobste.rs/s/qvoe7a/vu128_efficient_variable_length#c...

ixau 2y ago

In terms of serializing JSON to a binary representation, which includes variable length integers, check CBOR https://datatracker.ietf.org/doc/html/rfc8949 https://datatracker.ietf.org/doc/html/rfc8949

lifthrasiir 2y ago

As with many other variable-length integer encodings, its efficiency really depends on the expected input distribution. One glaring issue in this regard is that its 2-byte encoding is rather wasted: only 6.25% out of all possible encodings are useful. This can be possibly fixed by making the 2-byte encoding represent 240..495 instead of 0..255. You can even make use of some bits from the first byte, so that for example the sequence goes like: 0=00 1=01 2=02 .. BF=BF C0=C0C0 C1=C0C1 .. 30FF=F0FF 3100=F13100 .. (all in hex). A radically different design, used by for example 7z, is also possible if you put all continuation bits into the first byte. For example, instead of having `1xxxxxxx 1yyyyyyy 0zzzzzzz` for 3-byte encoding, use `110xxxxx yyyyyyyy zzzzzzzz`. This is essentially as compact as more common VLQ and LEB128 encodings, but you can determine the length of the whole sequence from the first byte alone! Unfortunately this is less suitable for integers larger than 64 bits, because then you run out of bits in the first byte. But it ends up with a rather elegant encoding for 64-bit integers, where `11111110` indicates 7 bytes and `11111111` indicates 8 bytes with no additional 0 bit needed. > An afternoon of web searching has failed to uncover a prior name for this particular encoding, so I'm going to name it vu128 and describe it below. If any reader knows of prior art, please send it my way. I don't know if it has other names, but a similar encoding can be seen from X.690 [1] and the "additional information" bit field of CBOR [2]. [1] https://en.wikipedia.org/wiki/X.690#Length_octets https://en.wikipedia.org/wiki/X.690#Length_octets [2] https://www.rfc-editor.org/rfc/rfc8949.html#section-3 https://www.rfc-editor.org/rfc/rfc8949.html#section-3

klabb3 2y ago
> Unfortunately this is less suitable for integers larger than 64 bits, because then you run out of bits in the first byte. Just spitballing here but is it necessary to support every increment of octets? Do we really need a 7 octet/56bit width for instance? Instead couldn’t we just allow widths of log2(n_octets)? An int64 would need 2 bits of length info (8, 16, 32, 64). Or maybe I’m thinking wrong cause not all bits are can be used. > its efficiency really depends on the expected input distribution Right. But everything else in computers is rounded to the nearest power of 2, so maybe it works here too haha.
- lifthrasiir 2y ago