This series fixes quadratic behavior in the reftable backend when many
tombstones are present. Any operation that seeks into a range containing
tombstones is affected, including ref lookups and D/F conflict checks.

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 makes suppress_deletions configurable via reftable_stack_options
(defaulting to off) and 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.

Downstream users of the reftable library (e.g. libgit2) can enable
suppress_deletions through the stack options to retain the previous
behavior.

The first patch adds a perf test (p1401) exercising two tombstone scenarios
with 8000 refs. The second patch is the optimization. Both p1401 tests go
from ~13s 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.

Changes since v2:

 * Add suppress_deletions to reftable_stack_options so downstream callers
   can control it at stack creation time (suggested by Patrick)

Changes since v1:

 * Keep suppress_deletions in the reftable library for downstream users;
   only stop setting it in stack.c
 * Broaden scope description to cover all readers, not just ref creation
 * Use separate repositories in perf test to avoid cross-scenario state
 * Drop correctness test (implicitly covered by t1400)

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

Kristofer Karlsson (2):
  t/perf: add perf test for ref tombstone scenarios
  reftable: fix quadratic behavior in the presence of tombstones

 refs/reftable-backend.c              | 54 ++++++++++++++++++++++------
 reftable/reftable-stack.h            |  2 ++
 reftable/stack.c                     |  2 +-
 t/perf/p1401-ref-store-tombstones.sh | 46 ++++++++++++++++++++++++
 4 files changed, 92 insertions(+), 12 deletions(-)
 create mode 100755 t/perf/p1401-ref-store-tombstones.sh

base-commit: f85a7e662054a7b0d9070e432508831afa214b47

Submitted-As: https://lore.kernel.org/git/pull.2166.v3.git.1783679767.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2166.git.1783344957.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2166.v2.git.1783598912.gitgitgadget@gmail.com