5 ms·
The encoding actually used is that the first bit of every byte is a flag for if there's a next byte, for a maximum of 10 bytes. Fun facts: those are commonly k
by seiji 11y ago
The encoding actually used is that the first bit of every byte is a flag for if there's a next byte, for a maximum of 10 bytes.
Fun facts: those are commonly known as "vbytes." They are the slowest kind of variable width integer encoding. The simplest (naive, and generally considered "wrong") implementations of variable-width-by-continuation-bits uses 10 bytes maximum. A proper implementation uses 9 bytes maximum.
There's actually no reason to ever use 10 bytes in this encoding. If you use 10 bytes, that means your last byte only holds one bit of actual user data. That's not very cool. But, your next-to-last byte holds seven bits of user data and one bit of metadata. We can easily say "if we're at the next to last byte, don't use metadata, just use all the bits we need." All you have to do is say "if we are currently at 9 bytes, don't use a 10th byte, just use this 9th byte directly." bam. Your 9th byte now has 8 bits of user data and you don't roll over a useless 10th byte with one bit of data.
The "slide all continuation bits into the first byte" sounds like a trick, but it's really using a TLV encoding where the first byte just holds a number between 1 and 8, so the entire integer+metadata is now [1 type byte][1 to 8 user data] = 2 to 9 bytes total. Using this scheme also kills any "1 byte, standalone, variable width integer" capability (unless you're storing partial values in the first T/L byte, but then that limits you to a much lower max value for one byte).
- haberman 11y ago> Using this scheme also kills any "1 byte, standalone, variable width integer" capability (unless you're storing partial values in the first T/L byte, but then that limits you to a much lower max value for one byte). You can get the best of both worlds. The way to do it is: separate continuation bits (1's) from data bits with a 0. This gives identical encoding-length characteristics as what you are calling "vbytes" (1 byte can encode 0-127, 2 bytes can encode 128-16383, etc) while still front-loading the continuation bits.
- seiji 11y agoThat's clever too, but it seems we're back to masking/shifting things all over the place too (which seemed to be an anti-design goal listed above. These can also have the "avoid 10 bytes" optimization by just reading the next 8 bytes exactly if the first byte is just all ones (no need for a zero separator; it would be in the way and push out the final bit to its own isolated byte again).
- haberman 11y agoUnlike "vbytes", this scheme only requires a single shift/mask, rather than one per byte.
- KMag 11y agoNo, it's not a type-length-value encoding, just a length-value encoding. I should have been more explicit in my UTF-8 reference. I'm really talking about a UTF-8 like encoding, except that it doesn't specially mark any of the continuation bytes and generalizes to lengths of 9 bytes, so the encoding (plus using zigzag encoding to put the sign bit in the least significant bit) is: 0xxxxxxS : 1 byte, 7 bits of data, -64 to 63 10xxxxxx xxxxxxxS : 2 bytes, 14 bits of data, -8192 to 8191 110xxxxx xxxxxxxx xxxxxxxS : 3 bytes, 21 bits of data, -(2^20) to 2^20 -1 1110xxxx xxxxxxxx xxxxxxxx xxxxxxxS : 4 bytes, 28 bits of data, -2^27 to 2^27-1 ... and so on. int64_t zigzag_decode(uint64_t in) { /* Signed right-shift is implementation-defined behavior in C */ COMPILE_TIME_ASSERT( (1LL << 63) >> 63 == -1, compiler_uses_signed_arith_shift ); return (int64_t) ((((int64_t) in << 63 ) >> 63 ) ^ (in >> 1)); } You can actually get slightly more dense packing using an encoding that doesn't have any non-canonical encodings by adding a length-dependent constant before the zigzag decoding step, but that's a bit more complicated to explain, and allows some 9 byte encoding values that won't fit in an int64_t.
- seiji 11y agowell, the "type" is presumed by a schema or somewhere by the time you hit your decoder, so it's technically there even if physically absent (and "LV encoding" doesn't seem to be a thing with any meaningful search results). Or we can just store everything as int64_t natively anyway. It's only 8 bytes after all (and storage is big these days).
- KMag 11y agoStorage is big, but disk bandwidth and network bandwidth are still limiting factors for many applications.
- uxcn 11y agoThe FAST (FIX Adapted for STreaming) protocol also uses a stop bit encoding. My guess was the data dependencies added to the pipeline would wash out the message size saved on average.