# DDIA Ch. 5: varint & zigzag — −1 costs 10 bytes, or 1 ## Concept Protocol Buffers stores integers as *varints* — variable-length, so a small positive number is a single byte. But a plain `int64` (or `int32`) encodes a *negative* value by two's-complement sign extension to the full 64-bit width, so the number `−1` — all ones in binary — fills all **ten** varint payload bytes. The `sint64`/`sint32` types apply **zigzag** encoding, which folds small- magnitude negatives back down to small varints, so `−1` is one payload byte again. You will predict the per-value sizes, watch `−1` cost **10 payload bytes as `int64` versus 1 as `sint64`**, then encode 1000 small negatives each way and see the plain `int64` batch come out **~7× larger** for a single wrong field type. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 5 — *Encoding and Evolution*, §"Protocol Buffers" (varint encoding; negative numbers and zigzag): > It uses variable-length integers: the number 1337 is encoded in two bytes The book notes that with the plain varint a negative number always occupies the full width, and that the `sint` types exist precisely to fix that. Here you encode both and measure the gap — down to the byte. ## Prerequisites The surprise is about *how* a varint spends its bytes on a negative number. These help; each line notes where it shows up. 1. **Varint encoding** — Protobuf packs an integer into 1–10 bytes, 7 value bits per byte with a continuation bit; small positives need few bytes. This is why `1` is one payload byte and `1337` is two (see the per-value table). 2. **Two's complement & sign extension** — a negative `int64` has its high bits all set, so `−1` is 64 one-bits; the varint must emit every one of them, which is the 10-byte payload you will measure. 3. **Zigzag encoding** — `sint`'s trick: map `0,−1,1,−2,2,…` to `0,1,2,3,4,…` so small *magnitudes* (positive or negative) stay small varints. This is why `sint64` brings `−1` back to one payload byte. 4. **Field tags & the wire format** — each field is a `(tag, value)` pair; the tag is one byte here, so an isolated single-field message measures `1 tag + payload`. That is why the `−1` totals read 11 and 2, not 10 and 1. ### Where to learn them - **Varints, tags, wire types (#1, #4):** the Protocol Buffers "Encoding" spec page — it walks the byte layout of a varint and a tag. - **Zigzag (#3):** the same spec's "Signed integers" section, which gives the `(n << 1) ^ (n >> 63)` mapping. - **Two's complement (#2):** any systems-programming reference; the one fact you need is that `−1` is all ones. If only one is new, make it #3 — zigzag is the whole reason `sint` exists. ## Environment Deterministic, so the byte counts reproduce exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.12.13 via `uv`, with Protocol Buffers (`grpcio-tools` compiling the `.proto` at runtime + the `protobuf` runtime) — no Docker - Four single-purpose messages: `Plain { int64 a }`, `Zig { sint64 a }`, and their `repeated` counterparts, so each measurement isolates one field type ## Mental model Four one-field messages, so `len(SerializeToString())` is `tag + payload` and the payload is what varies: - **`int64 a = 1`** — plain varint. Positives are compact; a *negative* is sign- extended to 64 bits, so its payload is always 10 bytes. - **`sint64 a = 1`** — zigzag varint. Both signs stay compact by magnitude, so `−1` is 1 payload byte. - **`repeated int64` / `repeated sint64`** — the same choice at scale: 1000 small negatives, packed. The plain field pays the 10-byte tax on every element. Every field's tag is one byte (field 1, wire type 0 → `0x08`), so subtract 1 from each total to read the varint payload. The whole exercise is one script, `code/varint_zigzag.py`. ## Setup ``` cd study/ddia/ch05/code uv run --python 3.12 --with grpcio-tools --with protobuf \ python3 varint_zigzag.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — predict the per-value sizes **Predict.** For each value, guess the encoded size as `int64` and as `sint64`, in bytes (total = 1 tag byte + varint payload): `1`, `1337`, `−1`, `−1000`, `2147483647`, `−2147483648`. (Most people expect the two columns to match — they do for the positives. The negatives are the surprise.) ### Step 2 — measure per value **Do.** Run the script. **Observe.** ``` per-value encoded size (single-field message, so total = tag + payload): value int64 sint64 ratio 1 2b 2b 1.0x 1337 3b 3b 1.0x -1 11b 2b 5.5x -1000 11b 3b 3.7x 2147483647 6b 6b 1.0x -2147483648 11b 6b 1.8x the headline (-1): int64 = 1 tag + 10 varint payload = 11 bytes; sint64 = 1 tag + 1 varint payload = 2 bytes. the varint payload alone: 10 bytes vs 1 byte -- a 10x blowup for one sign bit. ``` **Positives tie; negatives don't.** For `1`, `1337`, and even the `int32`-max `2147483647`, the two encodings are identical — zigzag buys nothing for positives. But every negative in the `int64` column is **11 bytes** (10 payload + 1 tag), regardless of magnitude: `−1` and `−2147483648` cost exactly the same, because both are sign-extended to the full 64 bits. `sint64` tracks *magnitude* instead, so `−1` is 2 bytes and `−1000` is 3. ### Step 3 — the batch that pays for it **Predict.** Now encode 1000 small negative integers (each in `−1..−100`) as a packed `repeated int64` and again as `repeated sint64`. Guess each total, and the ratio between them. **Observe.** ``` batch of 1000 small negative ints (packed repeated field): repeated int64 10003 bytes repeated sint64 1363 bytes -> the plain int64 batch is 7.3x larger, wasting 8640 bytes on sign extension. ``` **One wrong field type, ~7× the bytes.** The `int64` batch spends ~10 bytes per element (each small negative sign-extended to 10 payload bytes); the `sint64` batch spends 1–2. Same numbers, same schema shape, same wire — the only difference is `int64` vs `sint64`, and it costs **8640 wasted bytes** on a thousand-element array. ## What you should see - Positives are identical in both encodings: `1` → 2b, `1337` → 3b, `2147483647` → 6b, either way. - `−1` is **10 varint payload bytes as `int64`** (11 total) versus **1** as `sint64` (2 total) — a 10× payload blowup for the sign bit. - Every negative `int64` is 11 bytes regardless of magnitude; `−1` and `−2147483648` cost the same. - The 1000-element batch: **`repeated int64` 10003 → `repeated sint64` 1363** bytes, ~7.3× and 8640 bytes wasted. ## Why A varint stores an integer 7 bits at a time, low bits first, using the 8th bit of each byte as a "more bytes follow" flag. A small positive number has only a few significant bits, so it fits in one or two bytes — that is the whole appeal of varints. The catch is *negative* numbers. Protobuf's plain `int32`/`int64` represents them in two's complement, where a negative value has all its high bits set: `−1` is 64 one-bits. The varint has no way to know those leading ones are "just the sign" — it must emit all 64 significant bits, which takes ⌈64 / 7⌉ = 10 payload bytes. That is why *any* negative `int64`, from `−1` to the most negative `int32`, encodes to the same 10-byte payload: they all have the top bits set. Zigzag fixes this by choosing a different mapping to the non-negative varint space. Instead of two's complement, `sint64` encodes `n` as `(n << 1) ^ (n >> 63)` — interleaving the signs: `0 → 0`, `−1 → 1`, `1 → 2`, `−2 → 3`, and so on. Now the varint length tracks *magnitude*, not sign, so a small negative is as cheap as a small positive. Positives gain nothing (the map is a shift-and-XOR that keeps them small either way), which is exactly what the tied columns show. The batch just multiplies the per-element gap by a thousand: pick `int64` for a column of small negatives and you ship ~7× the bytes for no benefit. **The boundary — the tax is on the *sign*, not the size, and only for the plain types.** `sint` is not a free upgrade: it *loses* to plain `int` when your values are overwhelmingly non-negative and occasionally large positives, because zigzag doubles a positive's value before encoding (which can push it into one more varint byte). The rule of thumb is: use `sint32`/`sint64` when a field is frequently negative, plain `int32`/`int64` when it is almost always non-negative, and `fixed32`/`fixed64` when values are large and uniformly distributed. None of this touches `float`/`double` (always fixed-width) or the field *tag* (one byte here). The surprise is narrow but sharp: a single field declared `int64` instead of `sint64` can 10× a negative-heavy column, and Protobuf gives you no warning — it is a schema-design choice, made once, paid on every record. ### Go deeper 1. **Find zigzag's break-even.** Encode large *positive* values (say `2^60`) as `int64` and `sint64`. Predict which wins now that zigzag's shift can cost an extra byte — and confirm the rule "`sint` for negative-heavy fields only." 2. **Try `fixed64`.** Add a `fixed64` field and encode `−1`, `1337`, and `2^60`. Predict its size (constant 8 bytes) and find the crossover where fixed-width beats both varint types. 3. **Decode the 10 bytes by hand.** Serialize `Plain(a=-1)` and print the raw bytes in hex. Predict them first: `0x08` (tag) then ten bytes — nine `0xFF` and a final `0x01` — and see two's-complement sign extension in the wire.