Where: src/shared/delta.c:266-295 (match loop for j in 0..block_count per window).
Problem: For each byte position the rolling Adler-32 is compared against EVERY signature block (8192 blocks @64MiB, 32768 @256MiB); changed regions step 1 byte at a time paying a full scan. Mostly-matching 64MiB file with ~1% altered bytes ~ billions of iterations.
Fix: Build a hash table/buckets over sig->blocks keyed by adler (chain on collision, verify with xxh32) once per delta_compute -> O(1) bucket probe per window (textbook rsync algorithm).
Keep numeric correctness; add a stress/unit test with a mostly-matching large buffer.
Found by perf review of `dev` (9f8b588).
**Where:** src/shared/delta.c:266-295 (match loop `for j in 0..block_count` per window).
**Problem:** For each byte position the rolling Adler-32 is compared against EVERY signature block (8192 blocks @64MiB, 32768 @256MiB); changed regions step 1 byte at a time paying a full scan. Mostly-matching 64MiB file with ~1% altered bytes ~ billions of iterations.
**Fix:** Build a hash table/buckets over sig->blocks keyed by adler (chain on collision, verify with xxh32) once per delta_compute -> O(1) bucket probe per window (textbook rsync algorithm).
Keep numeric correctness; add a stress/unit test with a mostly-matching large buffer.
Fixed on dev via fix/perf-delta (5fed088): delta_compute now builds an Adler-keyed hash index (chains preserve ascending block order, lowest-index wins) -> ~O(bytes); ~216x faster on 32MiB/128-change benchmark. Differential + round-trip unit tests added.
CI run #461: all jobs green (lint, build-and-test, sanitizers address+undefined, fuzz-build, coverage, valgrind). Unit 25/25, integration 83 passed / 10 skipped / 1 xpassed. Closing.
**Resolved on `dev`** (HEAD f7c6c91).
Fixed on dev via fix/perf-delta (5fed088): delta_compute now builds an Adler-keyed hash index (chains preserve ascending block order, lowest-index wins) -> ~O(bytes); ~216x faster on 32MiB/128-change benchmark. Differential + round-trip unit tests added.
CI run #461: all jobs green (lint, build-and-test, sanitizers address+undefined, fuzz-build, coverage, valgrind). Unit 25/25, integration 83 passed / 10 skipped / 1 xpassed. Closing.
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
Found by perf review of
dev(9f8b588).Where: src/shared/delta.c:266-295 (match loop
for j in 0..block_countper window).Problem: For each byte position the rolling Adler-32 is compared against EVERY signature block (8192 blocks @64MiB, 32768 @256MiB); changed regions step 1 byte at a time paying a full scan. Mostly-matching 64MiB file with ~1% altered bytes ~ billions of iterations.
Fix: Build a hash table/buckets over sig->blocks keyed by adler (chain on collision, verify with xxh32) once per delta_compute -> O(1) bucket probe per window (textbook rsync algorithm).
Keep numeric correctness; add a stress/unit test with a mostly-matching large buffer.
Resolved on
dev(HEADf7c6c91).Fixed on dev via fix/perf-delta (
5fed088): delta_compute now builds an Adler-keyed hash index (chains preserve ascending block order, lowest-index wins) -> ~O(bytes); ~216x faster on 32MiB/128-change benchmark. Differential + round-trip unit tests added.CI run #461: all jobs green (lint, build-and-test, sanitizers address+undefined, fuzz-build, coverage, valgrind). Unit 25/25, integration 83 passed / 10 skipped / 1 xpassed. Closing.