THE FOLD / LOOT / THE STASH / THE VARINT
THE VARINT
the wasted bytes were buying the ability to not look
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Most integers are small. A fixed 32-bit field spends four bytes on the number seven. A varint spends seven bits per byte on the value and one on the question “is there more?”
LIT verified live. 200,000 values encoded and decoded with 0 round-trip failures. The boundaries are exact: 1 byte up to 127, 2 up to 16,383, 3 up to 2,097,151. Across the range the mean is 2.917 bytes against a fixed 4 — 27.06% smaller, and that is the worst case for varints because the values are uniformly spread.
LIT verified live. 200,000 values encoded and decoded with 0 round-trip failures. The boundaries are exact: 1 byte up to 127, 2 up to 16,383, 3 up to 2,097,151. Across the range the mean is 2.917 bytes against a fixed 4 — 27.06% smaller, and that is the worst case for varints because the values are uniformly spread.
2 HOW IT WAS WEAVED · AI + HUMAN
Varints are the backbone of Protocol Buffers and appear in nearly every binary format that expects small numbers.
AVAN (AI) chose a uniform sweep deliberately, which is the least flattering input possible. Real data is skewed toward small values and does far better; quoting that figure would be quoting the marketing. 27.06% on uniform values is the floor, and a floor is worth more than a best case.
AVAN (AI) chose a uniform sweep deliberately, which is the least flattering input possible. Real data is skewed toward small values and does far better; quoting that figure would be quoting the marketing. 27.06% on uniform values is the floor, and a floor is worth more than a best case.
3 ONE DIMENSION
Bytes per value, and where each boundary sits.
4 TWO DIMENSIONS · INTERACTIVE
Encode a value and watch the continuation bits.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a length that is part of the value.
AVAN’s addition (the inverse-companion): the forward reading is that varints make small numbers cheap. The inverse is that they make every number unskippable. A fixed field can be jumped over without being read; a varint must be decoded byte by byte to find out where it ends, so random access into an array of them is gone. Read backwards, the four wasted bytes were buying you the ability to not look, and a format that always knows where things are is paying for that with space.
LIT 200,000 values encode and decode with 0 round-trip failures at exact boundaries - 1 byte up to 127, 2 up to 16,383, 3 up to 2,097,151 - for a mean of 2.917 bytes against a fixed 4, which is 27.06% smaller and is the worst case for varints because the values are uniformly spread
FIG Varints are the backbone of Protocol Buffers and appear in nearly every binary format that expects small numbers. AVAN chose a uniform sweep deliberately, which is the least flattering input possible: real data is skewed toward small values and does far better, and quoting that figure would be quoting the marketing. 27.06% on uniform values is the floor, and a floor is worth more than a best case.
FIG Varints are the backbone of Protocol Buffers and appear in nearly every binary format that expects small numbers. AVAN chose a uniform sweep deliberately, which is the least flattering input possible: real data is skewed toward small values and does far better, and quoting that figure would be quoting the marketing. 27.06% on uniform values is the floor, and a floor is worth more than a best case.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN