Post by Eldwood in Would smaller content-addressed updates be useful for itch.io developers?

Viewing post in Would smaller content-addressed updates be useful for itch.io developers?

In your benchmarks, you acknowledge that pairwise diffs can produce smaller downloads, then dismiss them because you need N² of diffs. That’s technically true if you want to go from one arbitrary version to any other arbitrary version in one step, but nobody actually uses pairwise diffs that way.

The most common use of pairwise diffs only creates diffs between adjacent pairs, because by far the most common use case is going from one version to the next version. This provides optimal download sizes so long as no versions are skipped. Only N diffs are needed.

If skipping versions is common, one neat trick is to only provide power-of-two diffs between versions that are themselves powers of 2, i.e. pairwise diffs between adjacent diffs in the sequences 0-1-2-3-4-…, 0-2-4-6-8-10…, 0-4-8-16-32…, 0-8-16-32-64… and so on. This only requires 2N diffs and allows you to move between arbitrary versions with only O(2 log M) steps, where M is the distance between the versions.

Finally, if new versions are very frequent and very similar to each other, there’s always the trick of setting one version (the first one, or the one after the last major change) as the “base” version and only storing diffs to and from the base version. This only requires N diffs (recalculated each time the base version changes) and 2 diffs to change from one arbitrary version to another arbitrary version, at the cost of potentially very large diffs.

Like Reply

Orelvis4 days ago

That’s a really good point, and I think you’re right.

My N² argument only applies to the “all pairs, arbitrary version jump in one step” case, which is not how pairwise patch systems are usually deployed in practice. Adjacent diffs, power-of-two/sparse ladders, and base-version strategies are much more realistic baselines.

I’m going to update the wording and benchmarks to reflect that. Instead of framing pairwise diffs as “bad because N²”, I’ll compare CAVS against several practical patch policies:

adjacent-only diffs;
power-of-two ladder diffs;
base-version diffs;
all-pairs as the theoretical one-step baseline;
CAVS content-addressed / hybrid reconstruction.

I still think CAVS has an interesting tradeoff because it can reuse cache, previous installed artifacts, and content-addressed chunks without requiring a separate patch graph for every route. But you’re right that the comparison should be against realistic patch policies, not just the worst-case all-pairs model.

Thanks for pointing this out. This is exactly the kind of feedback I was hoping to get.

Like Reply

Orelvis4 days ago

You were right — my previous wording was too focused on the all-pairs N² case, which is not the way pairwise patch systems are usually deployed.

I updated the benchmark to compare CAVS against more practical patch policies, including adjacent-only updates, skip-heavy scenarios, warm-cache cases, and replayable patch graphs. The new results are now documented in docs/results/v1.1.0/patch-policy/ and summarized in BENCHMARKS.md.

The goal is no longer to frame pairwise diffs as “bad because N²”, but to compare CAVS against realistic policies and show the tradeoffs in storage, update size, skipped-version behavior, apply path length, and cache reuse.

Thanks again for pointing this out — it made the benchmark much better.

Like Reply