vu128: Efficient variable-length integers
john-millikin.com
john-millikin.com
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].
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.
Indeed CBOR does this, and that's another reason you should put continuation bits to the first byte: it allows for much greater control.
If you're (worst case) is 8 bytes for 61 bits, that's no 0 overhead, but 3 bits overhead.
Another detail is that vu128 is double 64 bits, ie: 17 bytes worst case or 8 bits overhead. Would presumably be 4 bits in your example to represent 124 bit payload.
Or (depending on the context of this counter) you may never want to overflow at all - in which case you're best of with a variable length representation that is open ended (like r or python arbitrary precision)
So it’s just not a practical concern - I just panic if it hits the limit. I think you may be failing to comprehend just how large numbers like this get and how long it takes to count because it’s such a very real concern with 32 bit counters. Addition of course can always overflow but this is a straight up strictly monotonic counter that counts from 0 to 2^61.
And panicing is exactly the kind of mitigation I had in mind initially; just don't silently do the unexpected.
> I think you may be failing to comprehend just how large numbers like this get
On the other hand, us programmers are also notorious for failing to comprehend just how long our software will live on...
Yeah, and it's worth noting that this encoding is very close to just length then value. It only saves space for numbers up to about ±100. In a lot of situations it wouldn't actually do better than tag-length-value.
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.
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.
Leb128 is relatively efficient in bitstream and sidesteps potential mpeg-la patent issues. (H264, maybe 14496 part 14)
BTW I once implemented my own parser in C#, see that source file: https://github.com/Const-me/Vrmac/blob/master/VrmacVideo/Con...
IIRC different from both Leb128 and VLQ, and quite neat. It's for 64bit (u)ints, though
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
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 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.
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.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>.
[2] https://lobste.rs/s/qvoe7a/vu128_efficient_variable_length#c...
I never fully groked the Zipf distribution but am I correct to conclude the worst case for vu128 would be alternating integers on either side of the branch condition?
Thanks for the link to the slides, also clever!
> Am I interpreting the behavior correctly to think that: your code has
> one branch per int and that branch will be predicted well when your
> integers are all of similar magnitude?
> I never fully groked the Zipf distribution but am I correct to conclude
> the worst case for vu128 would be alternating integers on either side of
> the branch condition?
In terms of bytes/sec, the worst case is a set of integers exclusively in the range [0xF0, 0xFF] -- big enough to skip the fast path, small enough that each byte has to go through the full bit-masking.
In terms of values/sec, the worst is really big integers because writing 8 bytes (or 16, for `encode_u128`) to a buffer takes longer than writing one byte.
However, regardless of measurement, the worst case for vu128 is faster than VLQ/LEB128 -- except for distributions containing only [0x00, 0x7F] in which case they're all equivalent.
---
Also, after some comments on Lobsters about cases where space efficiency in the u16 range really matters, I'm experimenting with a version that tries to match or exceed VLQ/LEB128 for size efficiency at all bit lengths.
It has three more branches, but in practice this hasn't turned out to matter much -- it seems that indefinite loops are slower than a fixed set of branches, so still significantly faster than VLQ/LEB128 on most sets of integers.
// like LEB128 but continuation bits are packed into the
// leading byte -- sometimes called "prefixed varint"
0xxxxxxx // 7 bits of payload
10xxxxxx xxxxxxxx // 14 bits of payload
110xxxxx xxxxxxxx xxxxxxxx // 21 bits payload
1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx // 28 bits payload
// For payloads > 28 bits, use (0xF0 | length) type prefix,
// same as original post.
1111____ xxxxxxxx xxxxxxxx [...]
https://news.ycombinator.com/item?id=11263378
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 Section 1.6