Comment by lifthrasiir | Hacker News Reader

Comment by lifthrasiir | Hacker News Reader

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

[2] https://www.rfc-editor.org/rfc/rfc8949.html#section-3

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

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

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.

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.

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.

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)

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.

:-) fair enough.

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

Honestly if any code I’ve written survives 100 years to cause problems I’ll be impressed. 1000 years I’ll be ecstatic.

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.

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.

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.

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

Reply on news.ycombinator.com