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.
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.
https://news.ycombinator.com/item?id=11263378
Also sqlite varint:
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
[2] https://www.rfc-editor.org/rfc/rfc8949.html#section-3