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 stops setting suppress_deletions on the stack's merged table 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 suppress_deletions flag and its logic are retained in the merged iterator for downstream users of the reftable library (e.g. libgit2).
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 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/stack.c | 1 -
t/perf/p1401-ref-store-tombstones.sh | 46 ++++++++++++++++++++++++
3 files changed, 89 insertions(+), 12 deletions(-)
create mode 100755 t/perf/p1401-ref-store-tombstones.sh
base-commit: f85a7e662054a7b0d9070e432508831afa214b47
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2166%2Fspkrka%2Freftable-tombstone-perf-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2166/spkrka/reftable-tombstone-perf-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/2166
Range-diff vs v1:
1: d8ffdcb4f8 ! 1: 889d0d38bc t: add tests for ref tombstone scenarios
@@ Metadata
Author: Kristofer Karlsson <krka@spotify.com>
## Commit message ##
- t: add tests for ref tombstone scenarios
+ t/perf: add perf test for ref tombstone scenarios
- Add a performance test and a correctness test for update-ref when
- many tombstones are present in a reftable.
+ Add performance tests for update-ref when many tombstones are present
+ in a reftable.
- The performance test (p1401) exercises two scenarios:
+ The first test exercises the scenario where all refs are deleted
+ (creating tombstones) and then re-created with the same names, which
+ currently exhibits quadratic behavior.
- - All refs are deleted (creating tombstones) and then re-created
- with the same names, which currently exhibits quadratic behavior.
-
- - An asymmetric variant where refs are deleted and then new,
- differently-named refs are created. When the tombstones sort
- after the new refs, every create scans all tombstones, making
- this case even worse than re-creating the same refs.
-
- The correctness test (t0610) verifies that refs deleted and then
- re-created with the same names are visible afterwards.
+ The second test uses a separate repository with an asymmetric variant
+ where refs are deleted and then new, differently-named refs are
+ created. When the tombstones sort after the new refs, every create
+ scans all tombstones, making this case even worse than re-creating
+ the same refs.
Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
@@ t/perf/p1401-ref-store-tombstones.sh (new)
+'
+
+test_expect_success "setup asymmetric" '
++ git init --ref-format=reftable repo2 &&
++ blob=$(echo foo | git -C repo2 hash-object -w --stdin) &&
+ for i in $(test_seq 8000)
+ do
+ printf "create refs/tags/old-%d %s\n" "$i" "$blob" ||
+ return 1
-+ done >repo/input-old &&
-+ sed "s/old-/new-/" <repo/input-old >repo/input-new &&
-+ git -C repo update-ref --stdin <repo/input-old &&
-+ git -C repo for-each-ref --format="delete %(refname)" |
-+ git -C repo update-ref --stdin
++ done >repo2/input-old &&
++ sed "s/old-/new-/" <repo2/input-old >repo2/input-new &&
++ git -C repo2 update-ref --stdin <repo2/input-old &&
++ git -C repo2 for-each-ref --format="delete %(refname)" |
++ git -C repo2 update-ref --stdin
+'
+
+test_perf "create new refs after deleting differently-named refs" '
-+ git -C repo update-ref --stdin <repo/input-new &&
-+ git -C repo for-each-ref --format="delete %(refname)" |
-+ git -C repo update-ref --stdin
++ git -C repo2 update-ref --stdin <repo2/input-new &&
++ git -C repo2 for-each-ref --format="delete %(refname)" refs/tags/ |
++ git -C repo2 update-ref --stdin
+'
+
+test_done
-
- ## t/t0610-reftable-basics.sh ##
-@@ t/t0610-reftable-basics.sh: test_expect_success 'writes do not persist peeled value for invalid tags' '
- )
- '
-
-+test_expect_success 'delete and re-create refs with tombstones' '
-+ test_when_finished "rm -rf repo" &&
-+ git init repo &&
-+ test_commit -C repo A &&
-+ A=$(git -C repo rev-parse HEAD) &&
-+ cat >input <<-EOF &&
-+ create refs/tags/a $A
-+ create refs/tags/b $A
-+ create refs/tags/c $A
-+ EOF
-+ git -C repo update-ref --stdin <input &&
-+
-+ # delete all tags, leaving tombstones
-+ git -C repo for-each-ref --format="delete %(refname)" refs/tags/ |
-+ git -C repo update-ref --stdin &&
-+
-+ # re-create the same refs and verify they are visible
-+ git -C repo update-ref --stdin <input &&
-+ git -C repo tag -l >actual &&
-+ test_line_count = 3 actual
-+'
-+
- test_done
2: 1459371d3a ! 2: c13f15ddc2 reftable: fix quadratic behavior when re-creating deleted refs
@@ Metadata
Author: Kristofer Karlsson <krka@spotify.com>
## Commit message ##
- reftable: fix quadratic behavior when re-creating deleted refs
+ reftable: fix quadratic behavior in the presence of tombstones
- When many refs are deleted and then re-created, update-ref exhibits
- quadratic behavior. With 8000 refs deleted and re-created, the
- runtime is ~15s, quadrupling for each doubling of input size.
+ When many tombstones are present in a reftable, operations that need
+ to look up or iterate over refs exhibit quadratic behavior. With
+ 8000 refs deleted and re-created, update-ref takes ~15s, quadrupling
+ for each doubling of input size.
The root cause is the merged iterator's suppress_deletions flag.
When set, merged_iter_next_void() silently consumes tombstone records
@@ Commit message
prefix or refname comparisons) until after all tombstones have been
scanned.
- This affects two code paths during ref creation:
+ This affects any code path that seeks into a range containing
+ tombstones, including:
- refs_verify_refnames_available() seeks to "refs/tags/foo-1/" to
check for D/F conflicts and must scan through all subsequent
@@ Commit message
found", because the merged iterator skips the matching tombstone
and searches for the next live record.
- Fix this by removing suppress_deletions from the merged iterator and
- instead handling deletion records at each call site in the reftable
- backend, where prefix and refname bounds are available. Tombstones
- are now returned to callers, which skip them after their existing
- bounds checks. This allows iteration to terminate as soon as a
- tombstone past the relevant bound is encountered.
+ Fix this by no longer setting suppress_deletions on the stack's
+ merged table and instead handling deletion records at each call site
+ in the reftable backend, where prefix and refname bounds are
+ available. Tombstones are now returned to callers, which skip them
+ after their existing bounds checks. This allows iteration to
+ terminate as soon as a tombstone past the relevant bound is
+ encountered.
+
+ The suppress_deletions flag and its logic in the merged iterator are
+ retained for downstream users of the reftable library (e.g. libgit2).
This also requires adding deletion checks to the log iteration paths,
since suppress_deletions applied to both ref and log iterators.
@@ refs/reftable-backend.c: static int reftable_be_fsck(struct ref_store *ref_store
case REFTABLE_REF_VAL2: {
struct object_id oid;
- ## reftable/merged.c ##
-@@ reftable/merged.c: struct merged_iter {
- struct merged_subiter *subiters;
- struct merged_iter_pqueue pq;
- size_t subiters_len;
-- int suppress_deletions;
- ssize_t advance_index;
- };
-
-@@ reftable/merged.c: static int merged_iter_seek_void(void *it, struct reftable_record *want)
-
- static int merged_iter_next_void(void *p, struct reftable_record *rec)
- {
-- struct merged_iter *mi = p;
-- while (1) {
-- int err = merged_iter_next_entry(mi, rec);
-- if (err)
-- return err;
-- if (mi->suppress_deletions && reftable_record_is_deletion(rec))
-- continue;
-- return 0;
-- }
-+ return merged_iter_next_entry(p, rec);
- }
-
- static struct reftable_iterator_vtable merged_iter_vtable = {
-@@ reftable/merged.c: int merged_table_init_iter(struct reftable_merged_table *mt,
- goto out;
- }
- mi->advance_index = -1;
-- mi->suppress_deletions = mt->suppress_deletions;
- mi->subiters = subiters;
- mi->subiters_len = mt->tables_len;
-
-
- ## reftable/merged.h ##
-@@ reftable/merged.h: struct reftable_merged_table {
- size_t tables_len;
- enum reftable_hash hash_id;
-
-- /* If unset, produce deletions. This is useful for compaction. For the
-- * full stack, deletions should be produced. */
-- int suppress_deletions;
--
- uint64_t min;
- uint64_t max;
- };
-
## reftable/stack.c ##
@@ reftable/stack.c: static int reftable_stack_reload_once(struct reftable_stack *st,
/* Update the stack to point to the new tables. */