The 21× Multiplier: What It Costs to Compute a Delta

Everyone measures the patch. On the two binaries in this post, a delta replaces a 13.6 MB download with a 250 KB one — and that ratio is the whole pitch. On NB-IoT at 20 kbps it is the difference between an hour and a half and under two minutes.

Nobody measures what it costs to make the patch.

For a 13.6 MB Go binary, bsdiff peaks at 296 MiB of resident memory. Not a leak, not a bug: that is the algorithm’s working set, allocated and released for every patch you generate. Twenty-one times the input.

I found this while bounding the server side of ota-updater. The patch-size question I had already answered; this is the other half of the ledger.

The measurement

#

Two consecutive real builds of the same Go service — not synthetic data, just the binary before and after a normal week of commits.

Two points is enough to see the shape: it scales linearly. Double the artifact, double the memory. There is no plateau waiting for you at a larger size.

That matters more than the absolute number, because artifacts only ever grow. A service that is 13 MB today is 30 MB after you add a vendored dependency and an embedded frontend, and the memory bill grows exactly in step.

Where 21× actually goes

#

I expected the answer to be “diffing is just expensive”. It is more specific and more fixable than that. From gabstv/go-bsdiff:

iii := make([]int, len(oldbin)+1)   // suffix array
vvv := make([]int, len(iii))        // inverse permutation

On 64-bit Go, int is eight bytes. Those two lines are 16 bytes per input byte — 16 of the 21×. The remaining 5× is the old binary, the new binary, the patch buffer and GC headroom.

So the dominant cost is not the diffing. It is two index tables sized by the input, holding values that for any realistic binary fit comfortably in 32 bits.

There is a second property that matters more than the size:

The suffix array is computed, not file-backed. The kernel cannot reclaim it under memory pressure the way it reclaims the page cache. It is anonymous memory, and on a host without swap it is the OOM killer’s problem.

This is worth separating clearly, because “use less memory” has two very different meanings. Caches you can serve from a file and let the kernel manage — the page cache is shared between processes, reclaimed on demand, and costs your heap nothing. A suffix array is not that. No amount of mmap helps, because the bytes do not exist on disk to be mapped.

Halving it with a data type

#

If 16 of the 21× is two []int arrays, and the values fit in 32 bits, the obvious question is what happens if you say so.

I forked the library and changed five function signatures. 66 lines of diff in a 510-line file.

Generation also got 28% faster on the larger pair. Smaller arrays, better cache locality — the memory saving pays for itself twice.

The patch format does not change, which is the part that makes this checkable: I verified it by having the stock, unmodified patcher apply the fork’s output and compare byte for byte against the target. It reproduces exactly.

One honest caveat, and it is why this has not shipped: the fork produces a patch 3% larger than the original. Valid, verified, applies correctly — but not bit-identical, which means my conversion changed a tie-break somewhere in the sort ordering. I do not yet know where. Shipping a diffing algorithm with a behavioural difference I cannot explain is exactly the kind of thing that is cheap to do and expensive to debug, so it sits in a branch with the open question written down next to it.

The other option, and the rule that killed it

#

zstd --patch-from does the same job with a completely different algorithm: compress the new file using the old one as a dictionary. It is dramatically cheaper.

Two things I did not expect. First, it works in pure Go: klauspost/compress exposes WithEncoderDictRaw and a 512 MiB maximum window, which is everything --patch-from needs. No CGO, no shelling out to a binary — which for a project whose whole premise is CGO_ENABLED=0 static binaries is the difference between an option and a non-starter. Second, the numbers:

Less than half the memory, twelve times faster. And a patch 3.6× larger.

That looked like a real dilemma for about ten minutes, until I wrote down what each side actually multiplies by:

Generation is O(versions). Transfer is O(devices).

A patch is generated once per (from, to) pair and cached forever. It is transferred once per device. So the memory cost is amortised across your release cadence, and the size cost is multiplied by your fleet.

For a thousand devices, that trade is 73 device-hours of extra radio to save 163 MiB of peak on one server, once per release. Stated that way it stops being a dilemma.

The asymmetry is the reusable part. It applies to any distribution system where one side produces and many consume, and it points the same direction every time: optimise the term the fleet multiplies, not the term the release amortises.

What actually shipped

#

Neither. Both alternatives change the multiplier; what I needed first was to stop the multiplier from mattering.

The cap is one config value: above a configured artifact size, the server does not diff at all. It serves the whole compressed target instead. The device still updates — it spends downlink rather than the server spending RAM — and the growth scenario stops being an outage and becomes a line in a config file.

The interesting part was not the cap. It was where to enforce it.

My first instinct was to put the check in the storage layer, next to the allocation it protects. That is where the memory is spent, so that is where the guard belongs.

It would have been a bug. The component that decides what to tell the device would have dispatched a generation, received nothing back, and answered “not ready, retry later” — on every heartbeat, forever. The device would poll politely until the end of time while every dashboard stayed green.

That is the same failure mode I had already built a whole fallback path to eliminate, reintroduced through the back door by putting a limit in the layer that felt most natural.

So the decision lives with the component that answers the device, and the storage layer enforces it as well — because that package is importable, and a direct consumer should not be able to allocate the process to death either. Two checks, one for correctness of the answer, one for safety of the library.

Three smaller properties that took a test each to pin down:

• A patch already on disk is served regardless of the cap. The memory was spent when it was generated. Lowering the limit must not invalidate work already done.
• A missing binary is not a budget failure. Reporting it as one sends the caller down the wrong recovery path.
• It is never silent. Over-budget pairs log a warning naming the artifact and its size, and the metric that counts full transfers rises. A limit that quietly changes every device’s download from 250 KB to 13 MB without saying so would be worse than no limit.

What I would take from this

#

The measurement was worth more than any of the fixes.

I could have spent that time implementing the int32 fork, and I would have had a 30% improvement to a number I had never actually looked at, on a system whose real risk was that the number grows linearly with a quantity I do not control. Measuring first turned “make it faster” into “make it bounded”, which was a different and better problem.

The specific numbers here are one algorithm on two Go binaries on my machine. The two habits generalise:

Measure the production cost, not just the transfer cost. Every compression and diffing scheme advertises its output size. Almost none advertise the working set required to produce it, and that is the number that decides whether your server survives your artifacts growing.

Write down which term multiplies. Most optimisation trade-offs stop being close calls the moment you name what each side scales with. Generation amortises, transfer multiplies — and that one sentence resolved a decision I had been circling for an afternoon.

What I don’t know yet

#

The 3% patch-size difference in the int32 fork is unexplained, and until it is, that fork is not going anywhere near production.

The zstd --patch-from path is measured but unbuilt. It is the obvious answer for artifacts too large for bsdiff — a per-artifact opt-in rather than a replacement — and I have not written the code that would let both modes coexist, which means a second transfer path to sign, version and test.

And none of this has met a real fleet. Two binaries, one machine, one server on localhost. The measurements are reproducible; that is not the same as proven.

The measurements, the harnesses and the saved fork patch are in docs/delta-memory.md, so the next person — probably me — does not have to redo them.