When does encoding an integer field as a varint make a payload larger rather than smaller?
answer
- seven payload bits per byte
- the eighth bit means more follows
- small numbers cheap, wide numbers dear
- past 2^28 it loses to fixed four
- sign extension makes a negative ten bytes
basics
~20 sWhen the values are large or negative. A varint spends seven bits per byte, so a 32-bit value at or above 2^28 costs five bytes against four fixed, and a full-width 64-bit value costs ten against eight.
solid answer
~50 sA **varint** stores seven payload bits per byte and uses the eighth bit to say whether another byte follows. So cost tracks magnitude: values under 128 take one byte, under 16,384 take two, and so on. That is a large win on counters, small measurements and enumerated codes, and a loss at the top of the range — any 32-bit value at or above 2^28 needs five bytes where a fixed 32-bit field needs four, and that is fifteen-sixteenths of the 32-bit space if the values are uniformly random. Negatives are worse: in two's complement a negative number has its high bits set, so it sign-extends to the full width and encodes in ten bytes. **ZigZag** encoding fixes that by interleaving signs onto the unsigned line, so cost follows magnitude again. Random identifiers and hashes belong in fixed-width fields.
code
pseudocode · 8 linesfunction write_varint(n, out): # n is non-negative
while n >= 128:
out.append((n mod 128) + 128) # 7 payload bits, continuation set
n = n div 128
out.append(n) # last byte, continuation clear
# write_varint(37, out) -> [37]
# write_varint(200, out) -> [200, 1]go deeper
Know that some encodings spend fewer bytes on small numbers and more on large ones, rather than a flat four or eight bytes for every value of the field.
Explain the seven-payload-bits-plus-continuation-bit layout, and be able to say roughly where a varint stops paying off against a fixed-width field of the same declared type.
Choose per field from the measured distribution: identifiers, hashes and randomly spread keys into fixed-width fields, counters and small measurements into varints, signed values into a ZigZag mapping.
The higher-value move is upstream of the encoding — reshaping a field so its values are small, or replacing a repeated string with an enumerated code, beats arguing about the integer representation.
## How a varint spends its bytes A **variable-length integer** — varint — encodes a non-negative number in as many bytes as its magnitude needs. Each byte carries **seven payload bits**; the remaining high bit is a **continuation flag** that says "another byte follows". The payload groups are emitted low-order first, so a decoder accumulates seven bits at a time until it meets a byte with the flag clear. That single design choice produces the whole cost curve: | bytes | unsigned values it covers | |---|---| | 1 | 0 – 127 | | 2 | 128 – 16,383 | | 3 | 16,384 – 2,097,151 | | 4 | 2,097,152 – 268,435,455 | | 5 | 268,435,456 – 34,359,738,367 | | … | … | | 10 | up to 2^64 − 1 | Each row is 2^(7k) − 1 at its top. Ten bytes is the ceiling for a 64-bit value, because seven bits per byte needs ten bytes to carry sixty-four. ## Where it wins - **Counters and small measurements.** A latency in milliseconds, a retry count, a status code, a queue depth: one or two bytes instead of a flat four or eight. - **Enumerated codes.** A severity level with a handful of members is always one byte. - **Sparse records.** In a tag-plus-value scheme, an absent field costs nothing at all, so the varint saving compounds with not sending the field. - **Field tags themselves.** The tag is a varint too. In a scheme that packs the field number with a three-bit type code, field numbers 1–15 fit in one tag byte and 16 upward need two — a real lever when a field appears on every record of a high-volume stream. ## Where it loses The break-even against a fixed-width field is where the varint's seven-bits-per-byte budget falls behind: - Against a **fixed 32-bit** field, a varint loses for any value **at or above 2^28** (268,435,456), which is **fifteen-sixteenths of the 32-bit unsigned range**. A hash truncated to 32 bits, or a randomly generated key, lands there almost every time. - Against a **fixed 64-bit** field, a varint needs nine or ten bytes for **255 of every 256** uniformly random values, because anything at or above 2^56 crosses into the nine-byte band. - **Negative values** are the sharpest trap. In two's complement a negative number has all its high bits set, so a plain varint over the sign-extended width emits the maximum: **ten bytes for −1**. A field that is nominally small but occasionally negative can cost more than a fixed-width one on exactly the records you did not expect. ## ZigZag, and why it exists **ZigZag** encoding maps signed values onto the unsigned line so that small magnitudes stay small on either side of zero: 0 → 0, −1 → 1, 1 → 2, −2 → 3, 2 → 4. Concretely it shifts the value left by one and flips every bit when the value was negative. The varint then encodes that unsigned image, so **cost follows magnitude rather than sign**. A field of small differences either side of zero — a drift, a delta, a correction — is unusable as a plain varint and perfectly cheap as a ZigZag one. ## Choosing per field The decision is per field and it is made from the value distribution, not from the declared type: 1. **Look at the actual distribution.** Not the range the type allows — the range the data occupies. A field declared 64-bit whose values never exceed a few thousand is a varint field. 2. **Identifiers, hashes and random keys go fixed-width.** They are uniformly spread across the range by construction, which is the varint's worst case, and a fixed width also lets a reader skip the field without decoding it. 3. **Signed fields that can go negative take ZigZag**, or are redefined so they cannot. 4. **Compare expected bytes, not the worst case.** Cost is per value, so a field that is usually small and occasionally huge still wins: you pay the wide encoding only on the rare values. One boundary is worth marking. The strongest move is often not the encoding at all but **reshaping the values so they are small** — storing a value relative to a per-batch base rather than in absolute terms, or replacing a repeated string with an enumerated code. Pushed further, that becomes the family of per-column encodings that a columnar analytics layout owns, and that is a different subject from the record-level choice described here.
- What problem does ZigZag encoding solve, and how?A negative value in two's complement has its high bits set, so a plain varint sign-extends it to the full width — ten bytes for −1. ZigZag interleaves the two signs onto the unsigned line (0→0, −1→1, 1→2, −2→3), so the encoded image of a small negative is a small unsigned number. Cost then follows magnitude rather than sign.
- If a field's values are usually small but occasionally enormous, which encoding wins?Usually the varint still wins, because cost is paid per value: the wide encoding is charged only on the rare large ones, so compare expected bytes rather than the worst case. The exception is a field a reader wants to skip or seek past without decoding, where a fixed width buys predictable offsets instead of bytes.
- Why does the choice of field numbers affect payload size?Because the tag is itself a varint. Where the tag packs the field number together with a small type code, numbers 1–15 fit in one byte and 16 upward need two. On a stream where a field appears on every record, promoting it into the low numbers saves a byte per record — small per record, real per day.
saying these in an interview costs you the question
- Believes a varint is always smaller than a fixed-width field
- Thinks a varint compresses the number rather than re-spelling it
- Forgets that a negative value sign-extends to the full width
- Assumes random identifiers and hashes benefit from variable length
- Confuses the continuation bit with a sign bit
- Picks the encoding from the declared type, not the value distribution