| Comment: | perf: bound the delta encoder's hash-collision chain walk (#176) (#178)
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]> |
|---|---|
| Timelines: | family | ancestors | descendants | both | trunk | v0.7.0 |
| Files: | files | file ages | folders |
| SHA3-256: |
b1b6c09b41156f1e84f3148ca0509b4a |
| User & Date: | [email protected] on 2026-07-27 14:22:51.000 |
| Other Links: | manifest | tags |
|
2026-07-27
| ||
| 16:19 |
docs: reconcile CHANGELOG with 15-tag release history (#181)
- Convert [Unreleased] to [0.7.0] and complete with remaining 67 commits - Add sections for v0.2.0 through v0.6.3 with commit-derived summaries - Add empty [Unreleased] section for future work - Highlight module path breaking change (libfossil → go-libfossil) - Maintain Keep a Changelog + SemVer format and existing prose style check-in: 35b79c90c6 user: [email protected] tags: trunk | |
| 14:22 |
perf: bound the delta encoder's hash-collision chain walk (#176) (#178)
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 | |
| 13:59 |
ci: warm fossil's global config database once before the test steps (#177)
Fossil keeps a per-user global config database outside any repository and creates it lazily on first use. The fossil-gated tests invoke the binary with inherited env -- nothing sets HOME -- and go test runs packages concurrently, several of which shell out to fossil. On a fresh runner that database does not exist yet, so two test processes can race to create it: one wins and the others fail with "table global_config already exists". Create it once, single-threaded, after the install and version check and before any build or test step, so no test process is ever the one to create it. fossil version does not open that database, so the existing version check does not incidentally cover this; fossil all list does, and is silent. The warm-up command's exit status is ignored on purpose -- it exists to touch a file, not to assert anything. The file check that follows is the part that matters: a warm-up that silently stopped creating the database would leave the race live while looking like protection, so its absence fails the job loudly. Refs #174 Co-authored-by: Dan Mestas <[email protected]> check-in: bba767af03 user: [email protected] tags: trunk | |