Timeline

emitMatches walked a hash bucket's entire collision chain at every target position with no limit. rollingHash is a weak multiply-accumulate over a 16-byte window, so low-entropy content — repeated tokens, runs of whitespace, ordinary SQL and C boilerplate — funnels an enormous number of source windows into one bucket, making Create quadratic in target length. Measured on the issue's repro (repeated 8-byte token, one 10-byte edit): 32 KiB 0.133s, 64 KiB 0.496s, 128 KiB 1.950s, 256 KiB 7.765s — ~3.9x per doubling — against 0.013s for a 128 KiB high-entropy control.

Bound the walk at maxChainCandidates, matching the `int limit = 250` that fossil's delta_create (src/delta.c) puts on the identical loop. The same walk also computed each candidate's match length twice, once to test it against the nHash threshold and again to read the value; compute it once.

Extract the walk into bestMatch so the bound is testable on a candidate count rather than on wall-clock time, which cannot flake on loaded CI.

Delta output changes, as fossil's own limit makes it change: a capped search can settle for a shorter match, so the encoder emits more copy commands. This lands our output on canonical fossil's — 128 KiB: 266 bytes vs fossil's 260; 1 MiB: 2142 vs 2120 — where before the unbounded walk produced 44 and 50 bytes and paid quadratic time for them.

After: 128 KiB 1.950s -> 0.018s, and 1 MiB 125.036s -> 0.062s.

Verified the deltas still apply byte-for-byte, by our Apply and by canonical fossil 2.28's test-delta-apply.

Co-authored-by: Dan Mestas <[email protected]> check-in: b1b6c09b41 user: [email protected] tags: trunk, v0.7.0