4 ms·

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

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
  > Just spitballing here but is it necessary to support every increment of octets? Indeed CBOR does this, and that's another reason you should put continuation bits to the first byte: it allows for much greater control.
vlovich123 2y ago
If you don’t need the full 64-bit space and can go 61-bit, you can actually encode variableness in 3-bits and at most have an 8 byte value vs the 9byte value here (ie 0 overhead). Three bits to indicate whether the length is 1 to 8 bytes and the remainder for the values. This is still 5 bits more efficient if you used the full 64-bits but unless you can make use of those extra 5 bits somehow (eg tightly packing another value that’s also partially sliced), it’s not buying you anything.
- repelsteeltje 2y ago
  Clever. But.. 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.
  - vlovich123 2y ago
    0 overhead in that it takes 8 bytes in memory and up to 8 bytes serialized. You can’t slice a byte partially unless you’re doing packing so I think it’s fair to characterize it as 0 overhead, but sure it’s 3 bits of overhead vs 8. It came up because I had a counter and just arbitrarily cut off the range cause I couldn’t possibly ever have it count that high. But yeah, the same idea could be extended to 128 bits.
    - repelsteeltje 2y ago
      Fair enough. In case this was a counter, best make sure you get the overflow logic right. The normal 64 bit wrapping won't kick in if you're just able to (de) seriaize only 61 bits. 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)
      - vlovich123 2y ago
        It would take your absolute top of the line CPU doing nothing but incrementing the counter for more than 12 years to worry about overflowing a 61 bit number. And what this is counting is much more expensive than incrementing a counter so you can’t run this at 6Ghz. Maybe ~500mhz which gets you to > 100 years if that’s all you’re doing but this counter is a side operation that won’t see much traffic even at scale so you’re talking about millennia in practice I suspect. 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.
plesner 2y ago
I implemented a slight variation of this a while back which worked as described up to 11110xxx but then a prefix byte of 11111xxx meant a payload of 64*2^xxx bits. So 11111000 is followed by a 64-bit value, 11111001 by a 128-bit, up to 11111111 which is 8192 bits.
Dylan16807 2y ago
> its efficiency really depends on the expected input distribution. One glaring issue in this regard is that its 2-byte encoding is rather wasted 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.
lostmsu 2y ago
Also, real-world numbers tend to swarm around powers of 10 and, in computers, powers of 2. It might make sense to encode those in a special way. E.g. <pow2-prefix><var-len-power><0/1 - to subtract one> and <pow10-prefix><var-len-power><0/1 - to subtract one>. E.g. assuming 10 prefix reserved for pow2 and 11 for pow10, 255 would be encoded as 10_1000_1, 65535 would be 10_10000_1, 65536 would be 10_10000_0, and 10000 would be 11_11_0.
- lifthrasiir 2y ago
  That should be probably resolved outside of the serialization. For example you can easily map -4n-1 to 2^(8+n), -4n-2 to 2^(8+n)-1, -4n-3 to 10^(3+n) and -4n-4 to 10^(3+n)-1 for all n >= 0.
deleted 2y ago
[deleted]

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
> Just spitballing here but is it necessary to support every increment of octets? Indeed CBOR does this, and that's another reason you should put continuation bits to the first byte: it allows for much greater control.

vlovich123 2y ago

If you don’t need the full 64-bit space and can go 61-bit, you can actually encode variableness in 3-bits and at most have an 8 byte value vs the 9byte value here (ie 0 overhead). Three bits to indicate whether the length is 1 to 8 bytes and the remainder for the values. This is still 5 bits more efficient if you used the full 64-bits but unless you can make use of those extra 5 bits somehow (eg tightly packing another value that’s also partially sliced), it’s not buying you anything.

repelsteeltje 2y ago
Clever. But.. 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.
- vlovich123 2y ago
  0 overhead in that it takes 8 bytes in memory and up to 8 bytes serialized. You can’t slice a byte partially unless you’re doing packing so I think it’s fair to characterize it as 0 overhead, but sure it’s 3 bits of overhead vs 8. It came up because I had a counter and just arbitrarily cut off the range cause I couldn’t possibly ever have it count that high. But yeah, the same idea could be extended to 128 bits.
  - repelsteeltje 2y ago
    Fair enough. In case this was a counter, best make sure you get the overflow logic right. The normal 64 bit wrapping won't kick in if you're just able to (de) seriaize only 61 bits. 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)
    - vlovich123 2y ago
      It would take your absolute top of the line CPU doing nothing but incrementing the counter for more than 12 years to worry about overflowing a 61 bit number. And what this is counting is much more expensive than incrementing a counter so you can’t run this at 6Ghz. Maybe ~500mhz which gets you to > 100 years if that’s all you’re doing but this counter is a side operation that won’t see much traffic even at scale so you’re talking about millennia in practice I suspect. 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.

plesner 2y ago

I implemented a slight variation of this a while back which worked as described up to 11110xxx but then a prefix byte of 11111xxx meant a payload of 64*2^xxx bits. So 11111000 is followed by a 64-bit value, 11111001 by a 128-bit, up to 11111111 which is 8192 bits.

Dylan16807 2y ago

> its efficiency really depends on the expected input distribution. One glaring issue in this regard is that its 2-byte encoding is rather wasted 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.

lostmsu 2y ago

Also, real-world numbers tend to swarm around powers of 10 and, in computers, powers of 2. It might make sense to encode those in a special way. E.g. <pow2-prefix><var-len-power><0/1 - to subtract one> and <pow10-prefix><var-len-power><0/1 - to subtract one>. E.g. assuming 10 prefix reserved for pow2 and 11 for pow10, 255 would be encoded as 10_1000_1, 65535 would be 10_10000_1, 65536 would be 10_10000_0, and 10000 would be 11_11_0.

lifthrasiir 2y ago
That should be probably resolved outside of the serialization. For example you can easily map -4n-1 to 2^(8+n), -4n-2 to 2^(8+n)-1, -4n-3 to 10^(3+n) and -4n-4 to 10^(3+n)-1 for all n >= 0.

deleted 2y ago

[deleted]