[PATCH 0/2] reftable: fix quadratic behavior when re-creating deleted refs

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

This series fixes quadratic behavior in update-ref when many refs are
deleted (tombstoned) and then new refs are created with the reftable
backend.

The root cause is the merged iterator's suppress_deletions flag, which
silently consumes tombstone records in a tight internal loop. This prevents
higher-level code from checking iteration bounds until after all tombstones
have been scanned, making both refs_verify_refnames_available() and
reftable_backend_read_ref() O(n) per call in the presence of tombstones.

The fix removes suppress_deletions from the merged iterator and instead
handles deletion records at each call site in the reftable backend, where
prefix and refname bounds are available. This lets existing bounds checks
terminate iteration early when encountering tombstones past the relevant
bound.

The first patch adds tests for tombstone scenarios: a perf test (p1401)
exercising two patterns with 8000 refs, and a correctness test (t0610)
verifying that deleted-then-recreated refs are visible.

The second patch is the pure optimization. Both p1401 tests go from ~14s to
~0.2s with the fix.

Note that auto-compaction typically merges tombstones before they accumulate
to this degree, so the quadratic behavior may not show up in every workflow.
But the fix ensures correct time complexity regardless of compaction state,
and the change is fairly contained.

Previous discussion:
https://lore.kernel.org/git/20260701080014.GA3748390@coredump.intra.peff.net/

Kristofer Karlsson (2):
  t: add tests for ref tombstone scenarios
  reftable: fix quadratic behavior when re-creating deleted refs

 refs/reftable-backend.c              | 54 ++++++++++++++++++++++------
 reftable/merged.c                    | 12 +------
 reftable/merged.h                    |  4 ---
 reftable/stack.c                     |  1 -
 t/perf/p1401-ref-store-tombstones.sh | 44 +++++++++++++++++++++++
 t/t0610-reftable-basics.sh           | 22 ++++++++++++
 6 files changed, 110 insertions(+), 27 deletions(-)
 create mode 100755 t/perf/p1401-ref-store-tombstones.sh


base-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2166%2Fspkrka%2Freftable-tombstone-perf-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2166/spkrka/reftable-tombstone-perf-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2166
-- 
gitgitgadget