{"thread":{"id":"65929","subject":"[PATCH 0/2] reftable: fix quadratic behavior when re-creating deleted refs","startedAt":"2026-07-06T13:35:59Z","lastAt":"2026-07-13T05:15:07Z","messageCount":22,"participants":["Kristofer Karlsson via GitGitGadget","Patrick Steinhardt","Kristofer Karlsson","brian m. carlson"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"547226","messageId":"pull.2166.git.1783344957.gitgitgadget@gmail.com","threadId":"65929","inReplyTo":null,"subject":"[PATCH 0/2] reftable: fix quadratic behavior when re-creating deleted refs","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-06T13:35:54Z","receivedAt":"2026-07-06T13:35:59Z","isPatch":true,"body":"This series fixes quadratic behavior in update-ref when many refs are\ndeleted (tombstoned) and then new refs are created with the reftable\nbackend.\n\nThe root cause is the merged iterator's suppress_deletions flag, which\nsilently consumes tombstone records in a tight internal loop. This prevents\nhigher-level code from checking iteration bounds until after all tombstones\nhave been scanned, making both refs_verify_refnames_available() and\nreftable_backend_read_ref() O(n) per call in the presence of tombstones.\n\nThe fix removes suppress_deletions from the merged iterator and instead\nhandles deletion records at each call site in the reftable backend, where\nprefix and refname bounds are available. This lets existing bounds checks\nterminate iteration early when encountering tombstones past the relevant\nbound.\n\nThe first patch adds tests for tombstone scenarios: a perf test (p1401)\nexercising two patterns with 8000 refs, and a correctness test (t0610)\nverifying that deleted-then-recreated refs are visible.\n\nThe second patch is the pure optimization. Both p1401 tests go from ~14s to\n~0.2s with the fix.\n\nNote that auto-compaction typically merges tombstones before they accumulate\nto this degree, so the quadratic behavior may not show up in every workflow.\nBut the fix ensures correct time complexity regardless of compaction state,\nand the change is fairly contained.\n\nPrevious discussion:\nhttps://lore.kernel.org/git/20260701080014.GA3748390@coredump.intra.peff.net/\n\nKristofer Karlsson (2):\n t: add tests for ref tombstone scenarios\n reftable: fix quadratic behavior when re-creating deleted refs\n\n refs/reftable-backend.c | 54 ++++++++++++++++++++++------\n reftable/merged.c | 12 +------\n reftable/merged.h | 4 ---\n reftable/stack.c | 1 -\n t/perf/p1401-ref-store-tombstones.sh | 44 +++++++++++++++++++++++\n t/t0610-reftable-basics.sh | 22 ++++++++++++\n 6 files changed, 110 insertions(+), 27 deletions(-)\n create mode 100755 t/perf/p1401-ref-store-tombstones.sh\n\n\nbase-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2166%2Fspkrka%2Freftable-tombstone-perf-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2166/spkrka/reftable-tombstone-perf-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2166\n-- \ngitgitgadget\n"},{"id":"547227","messageId":"d8ffdcb4f8c1988c109761ddb9daff8c07caa2b1.1783344957.git.gitgitgadget@gmail.com","threadId":"65929","inReplyTo":"pull.2166.git.1783344957.gitgitgadget@gmail.com","subject":"[PATCH 1/2] t: add tests for ref tombstone scenarios","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-06T13:35:55Z","receivedAt":"2026-07-06T13:36:01Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nAdd a performance test and a correctness test for update-ref when\nmany tombstones are present in a reftable.\n\nThe performance test (p1401) exercises two scenarios:\n\n - All refs are deleted (creating tombstones) and then re-created\n with the same names, which currently exhibits quadratic behavior.\n\n - An asymmetric variant where refs are deleted and then new,\n differently-named refs are created. When the tombstones sort\n after the new refs, every create scans all tombstones, making\n this case even worse than re-creating the same refs.\n\nThe correctness test (t0610) verifies that refs deleted and then\nre-created with the same names are visible afterwards.\n\nHelped-by: Jeff King \nSigned-off-by: Kristofer Karlsson \n---\n t/perf/p1401-ref-store-tombstones.sh | 44 ++++++++++++++++++++++++++++\n t/t0610-reftable-basics.sh | 22 ++++++++++++++\n 2 files changed, 66 insertions(+)\n create mode 100755 t/perf/p1401-ref-store-tombstones.sh\n\ndiff --git a/t/perf/p1401-ref-store-tombstones.sh b/t/perf/p1401-ref-store-tombstones.sh\nnew file mode 100755\nindex 0000000000..e40a6dcbf4\n--- /dev/null\n+++ b/t/perf/p1401-ref-store-tombstones.sh\n@@ -0,0 +1,44 @@\n+#!/bin/sh\n+\n+test_description=\"Tests performance of ref operations with many tombstones\"\n+\n+. ./perf-lib.sh\n+\n+test_expect_success \"setup\" '\n+\tgit init --ref-format=reftable repo &&\n+\tblob=$(echo foo | git -C repo hash-object -w --stdin) &&\n+\tfor i in $(test_seq 8000)\n+\tdo\n+\t\tprintf \"create refs/tags/tag-%d %s\\n\" \"$i\" \"$blob\" ||\n+\t\treturn 1\n+\tdone >repo/input &&\n+\tgit -C repo update-ref --stdin repo/input-old &&\n+\tsed \"s/old-/new-/\" repo/input-new &&\n+\tgit -C repo update-ref --stdin input <<-EOF &&\n+\tcreate refs/tags/a $A\n+\tcreate refs/tags/b $A\n+\tcreate refs/tags/c $A\n+\tEOF\n+\tgit -C repo update-ref --stdin actual &&\n+\ttest_line_count = 3 actual\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"547228","messageId":"1459371d3ab2f237152e20040987b4cb6a5eca77.1783344957.git.gitgitgadget@gmail.com","threadId":"65929","inReplyTo":"pull.2166.git.1783344957.gitgitgadget@gmail.com","subject":"[PATCH 2/2] reftable: fix quadratic behavior when re-creating deleted refs","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-06T13:35:56Z","receivedAt":"2026-07-06T13:36:03Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nWhen many refs are deleted and then re-created, update-ref exhibits\nquadratic behavior. With 8000 refs deleted and re-created, the\nruntime is ~15s, quadrupling for each doubling of input size.\n\nThe root cause is the merged iterator's suppress_deletions flag.\nWhen set, merged_iter_next_void() silently consumes tombstone records\nin a tight internal loop before returning to the caller. This\nprevents higher-level code from checking iteration bounds (such as\nprefix or refname comparisons) until after all tombstones have been\nscanned.\n\nThis affects two code paths during ref creation:\n\n - refs_verify_refnames_available() seeks to \"refs/tags/foo-1/\" to\n check for D/F conflicts and must scan through all subsequent\n tombstones before the caller can see that they are past the prefix\n of interest.\n\n - reftable_backend_read_ref() seeks to a specific refname and must\n scan through all subsequent tombstones before returning \"not\n found\", because the merged iterator skips the matching tombstone\n and searches for the next live record.\n\nFix this by removing suppress_deletions from the merged iterator and\ninstead handling deletion records at each call site in the reftable\nbackend, where prefix and refname bounds are available. Tombstones\nare now returned to callers, which skip them after their existing\nbounds checks. This allows iteration to terminate as soon as a\ntombstone past the relevant bound is encountered.\n\nThis also requires adding deletion checks to the log iteration paths,\nsince suppress_deletions applied to both ref and log iterators.\n\nBoth tests in p1401 go from ~14s to ~0.2s with this change.\n\nReported-by: Jeff King \nSigned-off-by: Kristofer Karlsson \n---\n refs/reftable-backend.c | 54 ++++++++++++++++++++++++++++++++---------\n reftable/merged.c | 12 +--------\n reftable/merged.h | 4 ---\n reftable/stack.c | 1 -\n 4 files changed, 44 insertions(+), 27 deletions(-)\n\ndiff --git a/refs/reftable-backend.c b/refs/reftable-backend.c\nindex 4ae22922de..8c4f119ff1 100644\n--- a/refs/reftable-backend.c\n+++ b/refs/reftable-backend.c\n@@ -86,7 +86,8 @@ static int reftable_backend_read_ref(struct reftable_backend *be,\n \tif (ret)\n \t\tgoto done;\n \n-\tif (strcmp(ref.refname, refname)) {\n+\tif (strcmp(ref.refname, refname) ||\n+\t reftable_ref_record_is_deletion(&ref)) {\n \t\tret = 1;\n \t\tgoto done;\n \t}\n@@ -112,7 +113,6 @@ static int reftable_backend_read_ref(struct reftable_backend *be,\n \t\toidread(oid, reftable_ref_record_val1(&ref),\n \t\t\t&hash_algos[hash_id]);\n \t} else {\n-\t\t/* We got a tombstone, which should not happen. */\n \t\tBUG(\"unhandled reference value type %d\", ref.value_type);\n \t}\n \n@@ -633,6 +633,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \t\t\tbreak;\n \t\t}\n \n+\t\tif (iter->ref.value_type == REFTABLE_REF_DELETION)\n+\t\t\tcontinue;\n+\n \t\tif (iter->exclude_patterns && should_exclude_current_ref(iter))\n \t\t\tcontinue;\n \n@@ -1492,6 +1495,8 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data\n \t\t\t\t\tret = 0;\n \t\t\t\t\tbreak;\n \t\t\t\t}\n+\t\t\t\tif (reftable_log_record_is_deletion(&log))\n+\t\t\t\t\tcontinue;\n \n \t\t\t\tALLOC_GROW(logs, logs_nr + 1, logs_alloc);\n \t\t\t\ttombstone = &logs[logs_nr++];\n@@ -1889,6 +1894,8 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&old_log))\n+\t\t\tcontinue;\n \n \t\tfree(old_log.refname);\n \n@@ -2019,6 +2026,9 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator)\n \t\tif (iter->err)\n \t\t\tbreak;\n \n+\t\tif (reftable_log_record_is_deletion(&iter->log))\n+\t\t\tcontinue;\n+\n \t\t/*\n \t\t * We want the refnames that we have reflogs for, so we skip if\n \t\t * we've already produced this name. This could be faster by\n@@ -2178,6 +2188,8 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log))\n+\t\t\tcontinue;\n \n \t\tret = yield_log_record(refs, &log, fn, cb_data);\n \t\tif (ret)\n@@ -2230,6 +2242,10 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log)) {\n+\t\t\treftable_log_record_release(&log);\n+\t\t\tcontinue;\n+\t\t}\n \n \t\tALLOC_GROW(logs, logs_nr + 1, logs_alloc);\n \t\tlogs[logs_nr++] = log;\n@@ -2276,18 +2292,26 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,\n \t\tgoto done;\n \n \t/*\n-\t * Check whether we get at least one log record for the given ref name.\n-\t * If so, the reflog exists, otherwise it doesn't.\n+\t * Check whether we get at least one non-deleted log record for the\n+\t * given ref name. If so, the reflog exists, otherwise it doesn't.\n \t */\n-\tret = reftable_iterator_next_log(&it, &log);\n-\tif (ret < 0)\n-\t\tgoto done;\n-\tif (ret > 0) {\n-\t\tret = 0;\n-\t\tgoto done;\n+\twhile (1) {\n+\t\tret = reftable_iterator_next_log(&it, &log);\n+\t\tif (ret < 0)\n+\t\t\tgoto done;\n+\t\tif (ret > 0) {\n+\t\t\tret = 0;\n+\t\t\tgoto done;\n+\t\t}\n+\t\tif (strcmp(log.refname, refname)) {\n+\t\t\tret = 0;\n+\t\t\tgoto done;\n+\t\t}\n+\t\tif (!reftable_log_record_is_deletion(&log))\n+\t\t\tbreak;\n \t}\n \n-\tret = strcmp(log.refname, refname) == 0;\n+\tret = 1;\n \n done:\n \treftable_iterator_destroy(&it);\n@@ -2399,6 +2423,8 @@ static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_da\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log))\n+\t\t\tcontinue;\n \n \t\ttombstone.refname = (char *)arg->refname;\n \t\ttombstone.value_type = REFTABLE_LOG_DELETION;\n@@ -2580,6 +2606,10 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,\n \t\t\treftable_log_record_release(&log);\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log)) {\n+\t\t\treftable_log_record_release(&log);\n+\t\t\tcontinue;\n+\t\t}\n \n \t\toidread(&old_oid, log.value.update.old_hash,\n \t\t\tref_store->repo->hash_algo);\n@@ -2746,6 +2776,8 @@ static int reftable_be_fsck(struct ref_store *ref_store, struct fsck_options *o,\n \t\treport.path = refname.buf;\n \n \t\tswitch (ref.value_type) {\n+\t\tcase REFTABLE_REF_DELETION:\n+\t\t\tcontinue;\n \t\tcase REFTABLE_REF_VAL1:\n \t\tcase REFTABLE_REF_VAL2: {\n \t\t\tstruct object_id oid;\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 733de07454..2f9a361234 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -26,7 +26,6 @@ struct merged_iter {\n \tstruct merged_subiter *subiters;\n \tstruct merged_iter_pqueue pq;\n \tsize_t subiters_len;\n-\tint suppress_deletions;\n \tssize_t advance_index;\n };\n \n@@ -166,15 +165,7 @@ static int merged_iter_seek_void(void *it, struct reftable_record *want)\n \n static int merged_iter_next_void(void *p, struct reftable_record *rec)\n {\n-\tstruct merged_iter *mi = p;\n-\twhile (1) {\n-\t\tint err = merged_iter_next_entry(mi, rec);\n-\t\tif (err)\n-\t\t\treturn err;\n-\t\tif (mi->suppress_deletions && reftable_record_is_deletion(rec))\n-\t\t\tcontinue;\n-\t\treturn 0;\n-\t}\n+\treturn merged_iter_next_entry(p, rec);\n }\n \n static struct reftable_iterator_vtable merged_iter_vtable = {\n@@ -278,7 +269,6 @@ int merged_table_init_iter(struct reftable_merged_table *mt,\n \t\tgoto out;\n \t}\n \tmi->advance_index = -1;\n-\tmi->suppress_deletions = mt->suppress_deletions;\n \tmi->subiters = subiters;\n \tmi->subiters_len = mt->tables_len;\n \ndiff --git a/reftable/merged.h b/reftable/merged.h\nindex 4317e5f5f6..6fafd1d080 100644\n--- a/reftable/merged.h\n+++ b/reftable/merged.h\n@@ -17,10 +17,6 @@ struct reftable_merged_table {\n \tsize_t tables_len;\n \tenum reftable_hash hash_id;\n \n-\t/* If unset, produce deletions. This is useful for compaction. For the\n-\t * full stack, deletions should be produced. */\n-\tint suppress_deletions;\n-\n \tuint64_t min;\n \tuint64_t max;\n };\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex 1fba96ddb3..77aeac4715 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -337,7 +337,6 @@ static int reftable_stack_reload_once(struct reftable_stack *st,\n \t/* Update the stack to point to the new tables. */\n \tif (st->merged)\n \t\treftable_merged_table_free(st->merged);\n-\tnew_merged->suppress_deletions = 1;\n \tst->merged = new_merged;\n \n \tif (st->tables)\n-- \ngitgitgadget\n"},{"id":"547338","messageId":"ak0aNrBpuo7ZwZ2k@pks.im","threadId":"65929","inReplyTo":"d8ffdcb4f8c1988c109761ddb9daff8c07caa2b1.1783344957.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/2] t: add tests for ref tombstone scenarios","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-07-07T15:24:38Z","receivedAt":"2026-07-07T15:24:48Z","isPatch":true,"body":"On Mon, Jul 06, 2026 at 01:35:55PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> diff --git a/t/perf/p1401-ref-store-tombstones.sh b/t/perf/p1401-ref-store-tombstones.sh\n> new file mode 100755\n> index 0000000000..e40a6dcbf4\n> --- /dev/null\n> +++ b/t/perf/p1401-ref-store-tombstones.sh\n> @@ -0,0 +1,44 @@\n> +#!/bin/sh\n> +\n> +test_description=\"Tests performance of ref operations with many tombstones\"\n> +\n> +. ./perf-lib.sh\n> +\n> +test_expect_success \"setup\" '\n> +\tgit init --ref-format=reftable repo &&\n> +\tblob=$(echo foo | git -C repo hash-object -w --stdin) &&\n> +\tfor i in $(test_seq 8000)\n> +\tdo\n> +\t\tprintf \"create refs/tags/tag-%d %s\\n\" \"$i\" \"$blob\" ||\n> +\t\treturn 1\n> +\tdone >repo/input &&\n> +\tgit -C repo update-ref --stdin +\tgit -C repo for-each-ref --format=\"delete %(refname)\" |\n> +\tgit -C repo update-ref --stdin\n> +'\n> +\n> +test_perf \"recreate refs after mass delete\" '\n> +\tgit -C repo update-ref --stdin +\tgit -C repo for-each-ref --format=\"delete %(refname)\" |\n> +\tgit -C repo update-ref --stdin\n> +'\n\nYou're not only benchmarking the reference recreation, but also their\ndeletion. If I'm not misreading things, then you can queue cleanups via\n`test_when_finished`, and these calls will not be measured.\n\n> +test_expect_success \"setup asymmetric\" '\n> +\tfor i in $(test_seq 8000)\n> +\tdo\n> +\t\tprintf \"create refs/tags/old-%d %s\\n\" \"$i\" \"$blob\" ||\n> +\t\treturn 1\n> +\tdone >repo/input-old &&\n> +\tsed \"s/old-/new-/\" repo/input-new &&\n> +\tgit -C repo update-ref --stdin +\tgit -C repo for-each-ref --format=\"delete %(refname)\" |\n> +\tgit -C repo update-ref --stdin\n> +'\n\nWould it make sense to use separate repositories? Otherwise, state from\nthe preceding benchmark(s) will impact subsequent ones.\n\n> diff --git a/t/t0610-reftable-basics.sh b/t/t0610-reftable-basics.sh\n> index e19e036898..4b7cfe38e4 100755\n> --- a/t/t0610-reftable-basics.sh\n> +++ b/t/t0610-reftable-basics.sh\n> @@ -1163,4 +1163,26 @@ test_expect_success 'writes do not persist peeled value for invalid tags' '\n> \t)\n> '\n> \n> +test_expect_success 'delete and re-create refs with tombstones' '\n> +\ttest_when_finished \"rm -rf repo\" &&\n> +\tgit init repo &&\n> +\ttest_commit -C repo A &&\n> +\tA=$(git -C repo rev-parse HEAD) &&\n> +\tcat >input <<-EOF &&\n> +\tcreate refs/tags/a $A\n> +\tcreate refs/tags/b $A\n> +\tcreate refs/tags/c $A\n> +\tEOF\n> +\tgit -C repo update-ref --stdin +\n> +\t# delete all tags, leaving tombstones\n> +\tgit -C repo for-each-ref --format=\"delete %(refname)\" refs/tags/ |\n> +\tgit -C repo update-ref --stdin &&\n> +\n> +\t# re-create the same refs and verify they are visible\n> +\tgit -C repo update-ref --stdin +\tgit -C repo tag -l >actual &&\n> +\ttest_line_count = 3 actual\n> +'\n\nI wonder whether this test really adds any value. We probably have lots\nof tests already that test creation/deletion of references.\n\nPatrick\n"},{"id":"547339","messageId":"ak0aRtvSxSyIWieg@pks.im","threadId":"65929","inReplyTo":"1459371d3ab2f237152e20040987b4cb6a5eca77.1783344957.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/2] reftable: fix quadratic behavior when re-creating deleted refs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-07-07T15:24:54Z","receivedAt":"2026-07-07T15:24:58Z","isPatch":true,"body":"On Mon, Jul 06, 2026 at 01:35:56PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> From: Kristofer Karlsson \n> \n> When many refs are deleted and then re-created, update-ref exhibits\n> quadratic behavior. With 8000 refs deleted and re-created, the\n> runtime is ~15s, quadrupling for each doubling of input size.\n> \n> The root cause is the merged iterator's suppress_deletions flag.\n> When set, merged_iter_next_void() silently consumes tombstone records\n> in a tight internal loop before returning to the caller. This\n> prevents higher-level code from checking iteration bounds (such as\n> prefix or refname comparisons) until after all tombstones have been\n> scanned.\n> \n> This affects two code paths during ref creation:\n> \n> - refs_verify_refnames_available() seeks to \"refs/tags/foo-1/\" to\n> check for D/F conflicts and must scan through all subsequent\n> tombstones before the caller can see that they are past the prefix\n> of interest.\n> \n> - reftable_backend_read_ref() seeks to a specific refname and must\n> scan through all subsequent tombstones before returning \"not\n> found\", because the merged iterator skips the matching tombstone\n> and searches for the next live record.\n\nIt probably not only impacts reference creation, but also every reader\nthat wants to search for a specific reference that doesn't exist.\n\n> Fix this by removing suppress_deletions from the merged iterator and\n> instead handling deletion records at each call site in the reftable\n> backend, where prefix and refname bounds are available. Tombstones\n> are now returned to callers, which skip them after their existing\n> bounds checks. This allows iteration to terminate as soon as a\n> tombstone past the relevant bound is encountered.\n\nThis option is still used by downstream users of the reftable library,\nlike libgit2. So we shouldn't just delete it outright.\n\n> diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c\n> index 4ae22922de..8c4f119ff1 100644\n> --- a/refs/reftable-backend.c\n> +++ b/refs/reftable-backend.c\n> @@ -633,6 +633,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)\n> \t\t\tbreak;\n> \t\t}\n> \n> +\t\tif (iter->ref.value_type == REFTABLE_REF_DELETION)\n> +\t\t\tcontinue;\n> +\n> \t\tif (iter->exclude_patterns && should_exclude_current_ref(iter))\n> \t\t\tcontinue;\n> \n\nOkay. I was first wondering whether we should move this call earlier.\nBut we actually don't want to, as this is the code that precedes the\nabove:\n\n\tif (iter->prefix_len &&\n\t strncmp(iter->prefix, iter->ref.refname, iter->prefix_len)) {\n\t\titer->err = 1;\n\t\tbreak;\n\t}\n\nSo this allows us to not only skip the current iteration, but completely\nabort iteration by observing tombstones that sort after our prefix.\n\nIn any case, as far as I can see all sites where we iterate through\neither ref or log records have been adapted to handle deletions.\n\nThanks!\n\nPatrick\n"},{"id":"547356","messageId":"CAL71e4NQLyM1T3YCL1Q09wfnkq7B3ah6i38yBeK8ZJCx1JejgQ@mail.gmail.com","threadId":"65929","inReplyTo":"ak0aRtvSxSyIWieg@pks.im","subject":"Re: [PATCH 2/2] reftable: fix quadratic behavior when re-creating deleted refs","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-07T16:04:15Z","receivedAt":"2026-07-07T16:04:26Z","isPatch":true,"body":"On Tue, 7 Jul 2026 at 17:24, Patrick Steinhardt wrote:\n>\n> > This affects two code paths during ref creation:\n> >\n> > - refs_verify_refnames_available() seeks to \"refs/tags/foo-1/\" to\n> > check for D/F conflicts and must scan through all subsequent\n> > tombstones before the caller can see that they are past the prefix\n> > of interest.\n> >\n> > - reftable_backend_read_ref() seeks to a specific refname and must\n> > scan through all subsequent tombstones before returning \"not\n> > found\", because the merged iterator skips the matching tombstone\n> > and searches for the next live record.\n>\n> It probably not only impacts reference creation, but also every reader\n> that wants to search for a specific reference that doesn't exist.\n\nHm good point, I will try to rephrase this better.\n\n> > Fix this by removing suppress_deletions from the merged iterator and\n> > instead handling deletion records at each call site in the reftable\n> > backend, where prefix and refname bounds are available. Tombstones\n> > are now returned to callers, which skip them after their existing\n> > bounds checks. This allows iteration to terminate as soon as a\n> > tombstone past the relevant bound is encountered.\n>\n> This option is still used by downstream users of the reftable library,\n> like libgit2. So we shouldn't just delete it outright.\n\nGood catch! I can keep suppress_deletions as-is and just\nstop setting it from stack.c. That way libgit2 is unchanged, while\nwe still optimize it at the other call sites. The reftable library\ndiff then shrinks to a single removed line.\n\n> > diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c\n> > index 4ae22922de..8c4f119ff1 100644\n> > --- a/refs/reftable-backend.c\n> > +++ b/refs/reftable-backend.c\n> > @@ -633,6 +633,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)\n> > break;\n> > }\n> >\n> > + if (iter->ref.value_type == REFTABLE_REF_DELETION)\n> > + continue;\n> > +\n> > if (iter->exclude_patterns && should_exclude_current_ref(iter))\n> > continue;\n> >\n>\n> Okay. I was first wondering whether we should move this call earlier.\n> But we actually don't want to, as this is the code that precedes the\n> above:\n>\n> if (iter->prefix_len &&\n> strncmp(iter->prefix, iter->ref.refname, iter->prefix_len)) {\n> iter->err = 1;\n> break;\n> }\n>\n> So this allows us to not only skip the current iteration, but completely\n> abort iteration by observing tombstones that sort after our prefix.\n\nIndeed, this is the primary win.\n\n> In any case, as far as I can see all sites where we iterate through\n> either ref or log records have been adapted to handle deletions.\n\nThanks! Appreciate the review (and spotting the libgit breakage!)\nKristofer\n"},{"id":"547358","messageId":"CAL71e4ORdJXsz58SH71VjDNAWZ39T3+TrWN+gScAFx=Gt0CTkQ@mail.gmail.com","threadId":"65929","inReplyTo":"ak0aNrBpuo7ZwZ2k@pks.im","subject":"Re: [PATCH 1/2] t: add tests for ref tombstone scenarios","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-07T16:12:31Z","receivedAt":"2026-07-07T16:12:43Z","isPatch":true,"body":"On Tue, 7 Jul 2026 at 17:24, Patrick Steinhardt wrote:\n>\n> On Mon, Jul 06, 2026 at 01:35:55PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> > diff --git a/t/perf/p1401-ref-store-tombstones.sh b/t/perf/p1401-ref-store-tombstones.sh\n> > new file mode 100755\n> > index 0000000000..e40a6dcbf4\n> > --- /dev/null\n> > +++ b/t/perf/p1401-ref-store-tombstones.sh\n> > @@ -0,0 +1,44 @@\n> > +#!/bin/sh\n> > +\n> > +test_description=\"Tests performance of ref operations with many tombstones\"\n> > +\n> > +. ./perf-lib.sh\n> > +\n> > +test_expect_success \"setup\" '\n> > + git init --ref-format=reftable repo &&\n> > + blob=$(echo foo | git -C repo hash-object -w --stdin) &&\n> > + for i in $(test_seq 8000)\n> > + do\n> > + printf \"create refs/tags/tag-%d %s\\n\" \"$i\" \"$blob\" ||\n> > + return 1\n> > + done >repo/input &&\n> > + git -C repo update-ref --stdin > + git -C repo for-each-ref --format=\"delete %(refname)\" |\n> > + git -C repo update-ref --stdin\n> > +'\n> > +\n> > +test_perf \"recreate refs after mass delete\" '\n> > + git -C repo update-ref --stdin > + git -C repo for-each-ref --format=\"delete %(refname)\" |\n> > + git -C repo update-ref --stdin\n> > +'\n>\n> You're not only benchmarking the reference recreation, but also their\n> deletion. If I'm not misreading things, then you can queue cleanups via\n> `test_when_finished`, and these calls will not be measured.\n\nI don't think measuring the full create+delete cycle is wrong per se,\nbut you are right that if we can benchmark something more isolated\nis even more useful. I will try to split this up better.\n\n> > +test_expect_success \"setup asymmetric\" '\n> > + for i in $(test_seq 8000)\n> > + do\n> > + printf \"create refs/tags/old-%d %s\\n\" \"$i\" \"$blob\" ||\n> > + return 1\n> > + done >repo/input-old &&\n> > + sed \"s/old-/new-/\" repo/input-new &&\n> > + git -C repo update-ref --stdin > + git -C repo for-each-ref --format=\"delete %(refname)\" |\n> > + git -C repo update-ref --stdin\n> > +'\n>\n> Would it make sense to use separate repositories? Otherwise, state from\n> the preceding benchmark(s) will impact subsequent ones.\n\nAgreed, I can use a fresh repo for each scenario.\n\n>\n> > diff --git a/t/t0610-reftable-basics.sh b/t/t0610-reftable-basics.sh\n> > +test_expect_success 'delete and re-create refs with tombstones' '\n>\n> I wonder whether this test really adds any value. We probably have lots\n> of tests already that test creation/deletion of references.\n\nI could not find an existing test that covers the delete-then-recreate\nflow (where tombstones are present when the new refs are created).\nThe existing tests cover creation and deletion separately but not the\ninteraction with tombstones.\n(But perhaps such a test exists and I just can't find it.)\n\nThanks,\nKristofer\n"},{"id":"547461","messageId":"ak3nWvyX4E9qB4T1@pks.im","threadId":"65929","inReplyTo":"CAL71e4ORdJXsz58SH71VjDNAWZ39T3+TrWN+gScAFx=Gt0CTkQ@mail.gmail.com","subject":"Re: [PATCH 1/2] t: add tests for ref tombstone scenarios","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-07-08T05:59:54Z","receivedAt":"2026-07-08T06:00:00Z","isPatch":true,"body":"On Tue, Jul 07, 2026 at 06:12:31PM +0200, Kristofer Karlsson wrote:\n> On Tue, 7 Jul 2026 at 17:24, Patrick Steinhardt wrote:\n> > On Mon, Jul 06, 2026 at 01:35:55PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> > > diff --git a/t/t0610-reftable-basics.sh b/t/t0610-reftable-basics.sh\n> > > +test_expect_success 'delete and re-create refs with tombstones' '\n> >\n> > I wonder whether this test really adds any value. We probably have lots\n> > of tests already that test creation/deletion of references.\n> \n> I could not find an existing test that covers the delete-then-recreate\n> flow (where tombstones are present when the new refs are created).\n> The existing tests cover creation and deletion separately but not the\n> interaction with tombstones.\n> (But perhaps such a test exists and I just can't find it.)\n\nIn t1400 we definitely have some tests where we exercise this\nimplicitly. In any case, if we want to retain this test I'd rather add\nit to t1400 itself, as the functionality that we're testing is itself\nnot specific to the backend.\n\nPatrick\n"},{"id":"547474","messageId":"CAL71e4NuiRwXMHsTrrqPK=NJJTvBe6E4eqnk90zjj3Z2hgkbmQ@mail.gmail.com","threadId":"65929","inReplyTo":"ak3nWvyX4E9qB4T1@pks.im","subject":"Re: [PATCH 1/2] t: add tests for ref tombstone scenarios","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-08T07:28:16Z","receivedAt":"2026-07-08T07:28:31Z","isPatch":true,"body":"On Wed, 8 Jul 2026 at 08:00, Patrick Steinhardt wrote:\n>\n> >\n> > I could not find an existing test that covers the delete-then-recreate\n> > flow (where tombstones are present when the new refs are created).\n> > The existing tests cover creation and deletion separately but not the\n> > interaction with tombstones.\n> > (But perhaps such a test exists and I just can't find it.)\n>\n> In t1400 we definitely have some tests where we exercise this\n> implicitly. In any case, if we want to retain this test I'd rather add\n> it to t1400 itself, as the functionality that we're testing is itself\n> not specific to the backend.\n\nThanks, you are right about the placement -- the contract is valid\nregardless of backend.\nYou are also right about it already being tested this is implicitly\ntested between multiple test runs since they have shared state\n(the repo). Multiple tests delete the ref as clean up and\nmultiple tests also create a ref and verifies it.\n\nSo it is technically covered but it depends on multiple tests\nbeing executed. I think this is simply exposing my personal\npreference to have more self-contained and explicit tests,\nbut I am happy to drop the added tests -- it is perhaps more\nimportant to avoid bloating the test code.\n\nI will drop the added correctness test for the next iteration.\n\nThanks,\nKristofer\n"},{"id":"547483","messageId":"ak4xXTHJwhNzfDLF@fruit.crustytoothpaste.net","threadId":"65929","inReplyTo":"pull.2166.git.1783344957.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/2] reftable: fix quadratic behavior when re-creating deleted refs","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2026-07-08T11:15:41Z","receivedAt":"2026-07-08T11:15:44Z","isPatch":true,"body":"On 2026-07-06 at 13:35:54, Kristofer Karlsson via GitGitGadget wrote:\n> This series fixes quadratic behavior in update-ref when many refs are\n> deleted (tombstoned) and then new refs are created with the reftable\n> backend.\n\n[…]\n\n> The first patch adds tests for tombstone scenarios: a perf test (p1401)\n> exercising two patterns with 8000 refs, and a correctness test (t0610)\n> verifying that deleted-then-recreated refs are visible.\n> \n> The second patch is the pure optimization. Both p1401 tests go from ~14s to\n> ~0.2s with the fix.\n> \n> Note that auto-compaction typically merges tombstones before they accumulate\n> to this degree, so the quadratic behavior may not show up in every workflow.\n> But the fix ensures correct time complexity regardless of compaction state,\n> and the change is fairly contained.\n\nI had hit this before when doing some benchmarks for using reftable at\n$DAYJOB. We had discussed it on the list and decided that it was\nsynthetic at the time, but I'm glad to see that this is being fixed now.\n\nI don't have comments on the patches themselves because I haven't spent\nenough time in the reftable code to be familiar with it, but I do\ndefinitely appreciate the performance improvement.\n-- \nbrian m. carlson (they/them)\nToronto, Ontario, CA\n"},{"id":"547602","messageId":"pull.2166.v2.git.1783598912.gitgitgadget@gmail.com","threadId":"65929","inReplyTo":"pull.2166.git.1783344957.gitgitgadget@gmail.com","subject":"[PATCH v2 0/2] reftable: fix quadratic behavior when re-creating deleted refs","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-09T12:08:29Z","receivedAt":"2026-07-09T12:08:34Z","isPatch":true,"body":"This series fixes quadratic behavior in the reftable backend when many\ntombstones are present. Any operation that seeks into a range containing\ntombstones is affected, including ref lookups and D/F conflict checks.\n\nThe root cause is the merged iterator's suppress_deletions flag, which\nsilently consumes tombstone records in a tight internal loop. This prevents\nhigher-level code from checking iteration bounds until after all tombstones\nhave been scanned, making both refs_verify_refnames_available() and\nreftable_backend_read_ref() O(n) per call in the presence of tombstones.\n\nThe fix stops setting suppress_deletions on the stack's merged table and\ninstead handles deletion records at each call site in the reftable backend,\nwhere prefix and refname bounds are available. This lets existing bounds\nchecks terminate iteration early when encountering tombstones past the\nrelevant bound.\n\nThe suppress_deletions flag and its logic are retained in the merged\niterator for downstream users of the reftable library (e.g. libgit2).\n\nThe first patch adds a perf test (p1401) exercising two tombstone scenarios\nwith 8000 refs. The second patch is the optimization. Both p1401 tests go\nfrom ~13s to ~0.2s with the fix.\n\nNote that auto-compaction typically merges tombstones before they accumulate\nto this degree, so the quadratic behavior may not show up in every workflow.\nBut the fix ensures correct time complexity regardless of compaction state,\nand the change is fairly contained.\n\nChanges since v1:\n\n * Keep suppress_deletions in the reftable library for downstream users;\n only stop setting it in stack.c\n * Broaden scope description to cover all readers, not just ref creation\n * Use separate repositories in perf test to avoid cross-scenario state\n * Drop correctness test (implicitly covered by t1400)\n\nPrevious discussion:\nhttps://lore.kernel.org/git/20260701080014.GA3748390@coredump.intra.peff.net/\n\nKristofer Karlsson (2):\n t/perf: add perf test for ref tombstone scenarios\n reftable: fix quadratic behavior in the presence of tombstones\n\n refs/reftable-backend.c | 54 ++++++++++++++++++++++------\n reftable/stack.c | 1 -\n t/perf/p1401-ref-store-tombstones.sh | 46 ++++++++++++++++++++++++\n 3 files changed, 89 insertions(+), 12 deletions(-)\n create mode 100755 t/perf/p1401-ref-store-tombstones.sh\n\n\nbase-commit: f85a7e662054a7b0d9070e432508831afa214b47\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2166%2Fspkrka%2Freftable-tombstone-perf-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2166/spkrka/reftable-tombstone-perf-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/2166\n\nRange-diff vs v1:\n\n 1: d8ffdcb4f8 ! 1: 889d0d38bc t: add tests for ref tombstone scenarios\n @@ Metadata\n Author: Kristofer Karlsson \n \n ## Commit message ##\n - t: add tests for ref tombstone scenarios\n + t/perf: add perf test for ref tombstone scenarios\n \n - Add a performance test and a correctness test for update-ref when\n - many tombstones are present in a reftable.\n + Add performance tests for update-ref when many tombstones are present\n + in a reftable.\n \n - The performance test (p1401) exercises two scenarios:\n + The first test exercises the scenario where all refs are deleted\n + (creating tombstones) and then re-created with the same names, which\n + currently exhibits quadratic behavior.\n \n - - All refs are deleted (creating tombstones) and then re-created\n - with the same names, which currently exhibits quadratic behavior.\n -\n - - An asymmetric variant where refs are deleted and then new,\n - differently-named refs are created. When the tombstones sort\n - after the new refs, every create scans all tombstones, making\n - this case even worse than re-creating the same refs.\n -\n - The correctness test (t0610) verifies that refs deleted and then\n - re-created with the same names are visible afterwards.\n + The second test uses a separate repository with an asymmetric variant\n + where refs are deleted and then new, differently-named refs are\n + created. When the tombstones sort after the new refs, every create\n + scans all tombstones, making this case even worse than re-creating\n + the same refs.\n \n Helped-by: Jeff King \n Signed-off-by: Kristofer Karlsson \n @@ t/perf/p1401-ref-store-tombstones.sh (new)\n +'\n +\n +test_expect_success \"setup asymmetric\" '\n ++\tgit init --ref-format=reftable repo2 &&\n ++\tblob=$(echo foo | git -C repo2 hash-object -w --stdin) &&\n +\tfor i in $(test_seq 8000)\n +\tdo\n +\t\tprintf \"create refs/tags/old-%d %s\\n\" \"$i\" \"$blob\" ||\n +\t\treturn 1\n -+\tdone >repo/input-old &&\n -+\tsed \"s/old-/new-/\" repo/input-new &&\n -+\tgit -C repo update-ref --stdin repo2/input-old &&\n ++\tsed \"s/old-/new-/\" repo2/input-new &&\n ++\tgit -C repo2 update-ref --stdin input <<-EOF &&\n -+\tcreate refs/tags/a $A\n -+\tcreate refs/tags/b $A\n -+\tcreate refs/tags/c $A\n -+\tEOF\n -+\tgit -C repo update-ref --stdin actual &&\n -+\ttest_line_count = 3 actual\n -+'\n -+\n - test_done\n 2: 1459371d3a ! 2: c13f15ddc2 reftable: fix quadratic behavior when re-creating deleted refs\n @@ Metadata\n Author: Kristofer Karlsson \n \n ## Commit message ##\n - reftable: fix quadratic behavior when re-creating deleted refs\n + reftable: fix quadratic behavior in the presence of tombstones\n \n - When many refs are deleted and then re-created, update-ref exhibits\n - quadratic behavior. With 8000 refs deleted and re-created, the\n - runtime is ~15s, quadrupling for each doubling of input size.\n + When many tombstones are present in a reftable, operations that need\n + to look up or iterate over refs exhibit quadratic behavior. With\n + 8000 refs deleted and re-created, update-ref takes ~15s, quadrupling\n + for each doubling of input size.\n \n The root cause is the merged iterator's suppress_deletions flag.\n When set, merged_iter_next_void() silently consumes tombstone records\n @@ Commit message\n prefix or refname comparisons) until after all tombstones have been\n scanned.\n \n - This affects two code paths during ref creation:\n + This affects any code path that seeks into a range containing\n + tombstones, including:\n \n - refs_verify_refnames_available() seeks to \"refs/tags/foo-1/\" to\n check for D/F conflicts and must scan through all subsequent\n @@ Commit message\n found\", because the merged iterator skips the matching tombstone\n and searches for the next live record.\n \n - Fix this by removing suppress_deletions from the merged iterator and\n - instead handling deletion records at each call site in the reftable\n - backend, where prefix and refname bounds are available. Tombstones\n - are now returned to callers, which skip them after their existing\n - bounds checks. This allows iteration to terminate as soon as a\n - tombstone past the relevant bound is encountered.\n + Fix this by no longer setting suppress_deletions on the stack's\n + merged table and instead handling deletion records at each call site\n + in the reftable backend, where prefix and refname bounds are\n + available. Tombstones are now returned to callers, which skip them\n + after their existing bounds checks. This allows iteration to\n + terminate as soon as a tombstone past the relevant bound is\n + encountered.\n +\n + The suppress_deletions flag and its logic in the merged iterator are\n + retained for downstream users of the reftable library (e.g. libgit2).\n \n This also requires adding deletion checks to the log iteration paths,\n since suppress_deletions applied to both ref and log iterators.\n @@ refs/reftable-backend.c: static int reftable_be_fsck(struct ref_store *ref_store\n \t\tcase REFTABLE_REF_VAL2: {\n \t\t\tstruct object_id oid;\n \n - ## reftable/merged.c ##\n -@@ reftable/merged.c: struct merged_iter {\n - \tstruct merged_subiter *subiters;\n - \tstruct merged_iter_pqueue pq;\n - \tsize_t subiters_len;\n --\tint suppress_deletions;\n - \tssize_t advance_index;\n - };\n - \n -@@ reftable/merged.c: static int merged_iter_seek_void(void *it, struct reftable_record *want)\n - \n - static int merged_iter_next_void(void *p, struct reftable_record *rec)\n - {\n --\tstruct merged_iter *mi = p;\n --\twhile (1) {\n --\t\tint err = merged_iter_next_entry(mi, rec);\n --\t\tif (err)\n --\t\t\treturn err;\n --\t\tif (mi->suppress_deletions && reftable_record_is_deletion(rec))\n --\t\t\tcontinue;\n --\t\treturn 0;\n --\t}\n -+\treturn merged_iter_next_entry(p, rec);\n - }\n - \n - static struct reftable_iterator_vtable merged_iter_vtable = {\n -@@ reftable/merged.c: int merged_table_init_iter(struct reftable_merged_table *mt,\n - \t\tgoto out;\n - \t}\n - \tmi->advance_index = -1;\n --\tmi->suppress_deletions = mt->suppress_deletions;\n - \tmi->subiters = subiters;\n - \tmi->subiters_len = mt->tables_len;\n - \n -\n - ## reftable/merged.h ##\n -@@ reftable/merged.h: struct reftable_merged_table {\n - \tsize_t tables_len;\n - \tenum reftable_hash hash_id;\n - \n --\t/* If unset, produce deletions. This is useful for compaction. For the\n --\t * full stack, deletions should be produced. */\n --\tint suppress_deletions;\n --\n - \tuint64_t min;\n - \tuint64_t max;\n - };\n -\n ## reftable/stack.c ##\n @@ reftable/stack.c: static int reftable_stack_reload_once(struct reftable_stack *st,\n \t/* Update the stack to point to the new tables. */\n\n-- \ngitgitgadget\n"},{"id":"547603","messageId":"889d0d38bc9952a9f5f74063c685c72c299b1490.1783598912.git.gitgitgadget@gmail.com","threadId":"65929","inReplyTo":"pull.2166.v2.git.1783598912.gitgitgadget@gmail.com","subject":"[PATCH v2 1/2] t/perf: add perf test for ref tombstone scenarios","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-09T12:08:30Z","receivedAt":"2026-07-09T12:08:35Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nAdd performance tests for update-ref when many tombstones are present\nin a reftable.\n\nThe first test exercises the scenario where all refs are deleted\n(creating tombstones) and then re-created with the same names, which\ncurrently exhibits quadratic behavior.\n\nThe second test uses a separate repository with an asymmetric variant\nwhere refs are deleted and then new, differently-named refs are\ncreated. When the tombstones sort after the new refs, every create\nscans all tombstones, making this case even worse than re-creating\nthe same refs.\n\nHelped-by: Jeff King \nSigned-off-by: Kristofer Karlsson \n---\n t/perf/p1401-ref-store-tombstones.sh | 46 ++++++++++++++++++++++++++++\n 1 file changed, 46 insertions(+)\n create mode 100755 t/perf/p1401-ref-store-tombstones.sh\n\ndiff --git a/t/perf/p1401-ref-store-tombstones.sh b/t/perf/p1401-ref-store-tombstones.sh\nnew file mode 100755\nindex 0000000000..9e3d8031aa\n--- /dev/null\n+++ b/t/perf/p1401-ref-store-tombstones.sh\n@@ -0,0 +1,46 @@\n+#!/bin/sh\n+\n+test_description=\"Tests performance of ref operations with many tombstones\"\n+\n+. ./perf-lib.sh\n+\n+test_expect_success \"setup\" '\n+\tgit init --ref-format=reftable repo &&\n+\tblob=$(echo foo | git -C repo hash-object -w --stdin) &&\n+\tfor i in $(test_seq 8000)\n+\tdo\n+\t\tprintf \"create refs/tags/tag-%d %s\\n\" \"$i\" \"$blob\" ||\n+\t\treturn 1\n+\tdone >repo/input &&\n+\tgit -C repo update-ref --stdin repo2/input-old &&\n+\tsed \"s/old-/new-/\" repo2/input-new &&\n+\tgit -C repo2 update-ref --stdin \n\nWhen many tombstones are present in a reftable, operations that need\nto look up or iterate over refs exhibit quadratic behavior. With\n8000 refs deleted and re-created, update-ref takes ~15s, quadrupling\nfor each doubling of input size.\n\nThe root cause is the merged iterator's suppress_deletions flag.\nWhen set, merged_iter_next_void() silently consumes tombstone records\nin a tight internal loop before returning to the caller. This\nprevents higher-level code from checking iteration bounds (such as\nprefix or refname comparisons) until after all tombstones have been\nscanned.\n\nThis affects any code path that seeks into a range containing\ntombstones, including:\n\n - refs_verify_refnames_available() seeks to \"refs/tags/foo-1/\" to\n check for D/F conflicts and must scan through all subsequent\n tombstones before the caller can see that they are past the prefix\n of interest.\n\n - reftable_backend_read_ref() seeks to a specific refname and must\n scan through all subsequent tombstones before returning \"not\n found\", because the merged iterator skips the matching tombstone\n and searches for the next live record.\n\nFix this by no longer setting suppress_deletions on the stack's\nmerged table and instead handling deletion records at each call site\nin the reftable backend, where prefix and refname bounds are\navailable. Tombstones are now returned to callers, which skip them\nafter their existing bounds checks. This allows iteration to\nterminate as soon as a tombstone past the relevant bound is\nencountered.\n\nThe suppress_deletions flag and its logic in the merged iterator are\nretained for downstream users of the reftable library (e.g. libgit2).\n\nThis also requires adding deletion checks to the log iteration paths,\nsince suppress_deletions applied to both ref and log iterators.\n\nBoth tests in p1401 go from ~14s to ~0.2s with this change.\n\nReported-by: Jeff King \nSigned-off-by: Kristofer Karlsson \n---\n refs/reftable-backend.c | 54 ++++++++++++++++++++++++++++++++---------\n reftable/stack.c | 1 -\n 2 files changed, 43 insertions(+), 12 deletions(-)\n\ndiff --git a/refs/reftable-backend.c b/refs/reftable-backend.c\nindex 212408c769..028f0211af 100644\n--- a/refs/reftable-backend.c\n+++ b/refs/reftable-backend.c\n@@ -84,7 +84,8 @@ static int reftable_backend_read_ref(struct reftable_backend *be,\n \tif (ret)\n \t\tgoto done;\n \n-\tif (strcmp(ref.refname, refname)) {\n+\tif (strcmp(ref.refname, refname) ||\n+\t reftable_ref_record_is_deletion(&ref)) {\n \t\tret = 1;\n \t\tgoto done;\n \t}\n@@ -110,7 +111,6 @@ static int reftable_backend_read_ref(struct reftable_backend *be,\n \t\toidread(oid, reftable_ref_record_val1(&ref),\n \t\t\t&hash_algos[hash_id]);\n \t} else {\n-\t\t/* We got a tombstone, which should not happen. */\n \t\tBUG(\"unhandled reference value type %d\", ref.value_type);\n \t}\n \n@@ -652,6 +652,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \t\t\tbreak;\n \t\t}\n \n+\t\tif (iter->ref.value_type == REFTABLE_REF_DELETION)\n+\t\t\tcontinue;\n+\n \t\tif (iter->exclude_patterns && should_exclude_current_ref(iter))\n \t\t\tcontinue;\n \n@@ -1532,6 +1535,8 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data\n \t\t\t\t\tret = 0;\n \t\t\t\t\tbreak;\n \t\t\t\t}\n+\t\t\t\tif (reftable_log_record_is_deletion(&log))\n+\t\t\t\t\tcontinue;\n \n \t\t\t\tALLOC_GROW(logs, logs_nr + 1, logs_alloc);\n \t\t\t\ttombstone = &logs[logs_nr++];\n@@ -1929,6 +1934,8 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&old_log))\n+\t\t\tcontinue;\n \n \t\tfree(old_log.refname);\n \n@@ -2061,6 +2068,9 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator)\n \t\tif (iter->err)\n \t\t\tbreak;\n \n+\t\tif (reftable_log_record_is_deletion(&iter->log))\n+\t\t\tcontinue;\n+\n \t\t/*\n \t\t * We want the refnames that we have reflogs for, so we skip if\n \t\t * we've already produced this name. This could be faster by\n@@ -2220,6 +2230,8 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log))\n+\t\t\tcontinue;\n \n \t\tret = yield_log_record(refs, &log, fn, cb_data);\n \t\tif (ret)\n@@ -2272,6 +2284,10 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log)) {\n+\t\t\treftable_log_record_release(&log);\n+\t\t\tcontinue;\n+\t\t}\n \n \t\tALLOC_GROW(logs, logs_nr + 1, logs_alloc);\n \t\tlogs[logs_nr++] = log;\n@@ -2318,18 +2334,26 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,\n \t\tgoto done;\n \n \t/*\n-\t * Check whether we get at least one log record for the given ref name.\n-\t * If so, the reflog exists, otherwise it doesn't.\n+\t * Check whether we get at least one non-deleted log record for the\n+\t * given ref name. If so, the reflog exists, otherwise it doesn't.\n \t */\n-\tret = reftable_iterator_next_log(&it, &log);\n-\tif (ret < 0)\n-\t\tgoto done;\n-\tif (ret > 0) {\n-\t\tret = 0;\n-\t\tgoto done;\n+\twhile (1) {\n+\t\tret = reftable_iterator_next_log(&it, &log);\n+\t\tif (ret < 0)\n+\t\t\tgoto done;\n+\t\tif (ret > 0) {\n+\t\t\tret = 0;\n+\t\t\tgoto done;\n+\t\t}\n+\t\tif (strcmp(log.refname, refname)) {\n+\t\t\tret = 0;\n+\t\t\tgoto done;\n+\t\t}\n+\t\tif (!reftable_log_record_is_deletion(&log))\n+\t\t\tbreak;\n \t}\n \n-\tret = strcmp(log.refname, refname) == 0;\n+\tret = 1;\n \n done:\n \treftable_iterator_destroy(&it);\n@@ -2442,6 +2466,8 @@ static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_da\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log))\n+\t\t\tcontinue;\n \n \t\ttombstone.refname = (char *)arg->refname;\n \t\ttombstone.value_type = REFTABLE_LOG_DELETION;\n@@ -2625,6 +2651,10 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,\n \t\t\treftable_log_record_release(&log);\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log)) {\n+\t\t\treftable_log_record_release(&log);\n+\t\t\tcontinue;\n+\t\t}\n \n \t\toidread(&old_oid, log.value.update.old_hash,\n \t\t\tref_store->repo->hash_algo);\n@@ -2791,6 +2821,8 @@ static int reftable_be_fsck(struct ref_store *ref_store, struct fsck_options *o,\n \t\treport.path = refname.buf;\n \n \t\tswitch (ref.value_type) {\n+\t\tcase REFTABLE_REF_DELETION:\n+\t\t\tcontinue;\n \t\tcase REFTABLE_REF_VAL1:\n \t\tcase REFTABLE_REF_VAL2: {\n \t\t\tstruct object_id oid;\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex ab12926708..fd7d8f3f1e 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -337,7 +337,6 @@ static int reftable_stack_reload_once(struct reftable_stack *st,\n \t/* Update the stack to point to the new tables. */\n \tif (st->merged)\n \t\treftable_merged_table_free(st->merged);\n-\tnew_merged->suppress_deletions = 1;\n \tst->merged = new_merged;\n \n \tif (st->tables)\n-- \ngitgitgadget\n"},{"id":"547607","messageId":"ak-n6K4heV2kHviZ@pks.im","threadId":"65929","inReplyTo":"c13f15ddc20f721443fa1d462ea1b7c2356fbffc.1783598912.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/2] reftable: fix quadratic behavior in the presence of tombstones","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-07-09T13:53:44Z","receivedAt":"2026-07-09T13:53:53Z","isPatch":true,"body":"On Thu, Jul 09, 2026 at 12:08:31PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> diff --git a/reftable/stack.c b/reftable/stack.c\n> index ab12926708..fd7d8f3f1e 100644\n> --- a/reftable/stack.c\n> +++ b/reftable/stack.c\n> @@ -337,7 +337,6 @@ static int reftable_stack_reload_once(struct reftable_stack *st,\n> \t/* Update the stack to point to the new tables. */\n> \tif (st->merged)\n> \t\treftable_merged_table_free(st->merged);\n> -\tnew_merged->suppress_deletions = 1;\n> \tst->merged = new_merged;\n> \n> \tif (st->tables)\n\nOkay, we still retain the field after this patch. But the question is:\nhow would libgit2 now set it? I think we should rather extend the\n`struct reftable_stack_options` so that the caller can control whether\nor not to suppress deletions at stack creation time.\n\nThanks!\n\nPatrick\n"},{"id":"547609","messageId":"CAL71e4PrtZwB8TMg3eBj=LzC7ik+C8yxLYEEEP7SDgMPiWSs0Q@mail.gmail.com","threadId":"65929","inReplyTo":"ak-n6K4heV2kHviZ@pks.im","subject":"Re: [PATCH v2 2/2] reftable: fix quadratic behavior in the presence of tombstones","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-09T14:48:43Z","receivedAt":"2026-07-09T14:48:56Z","isPatch":true,"body":"On Thu, 9 Jul 2026 at 15:53, Patrick Steinhardt wrote:\n>\n> On Thu, Jul 09, 2026 at 12:08:31PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> > diff --git a/reftable/stack.c b/reftable/stack.c\n> > index ab12926708..fd7d8f3f1e 100644\n> > --- a/reftable/stack.c\n> > +++ b/reftable/stack.c\n> > @@ -337,7 +337,6 @@ static int reftable_stack_reload_once(struct reftable_stack *st,\n> > /* Update the stack to point to the new tables. */\n> > if (st->merged)\n> > reftable_merged_table_free(st->merged);\n> > - new_merged->suppress_deletions = 1;\n> > st->merged = new_merged;\n> >\n> > if (st->tables)\n>\n> Okay, we still retain the field after this patch. But the question is:\n> how would libgit2 now set it? I think we should rather extend the\n> `struct reftable_stack_options` so that the caller can control whether\n> or not to suppress deletions at stack creation time.\n\nYou are right, I (still) missed the compatibility problem here.\n\nI started thinking about a way to make it fully backwards compatible,\nbut then I looked at the libgit2 repo and realized it will need\nupdating anyway since it predates the reftable_stack_options split.\n\nI will add suppress_deletions to reftable_stack_options as you\nsuggested.\n\nThanks,\nKristofer\n"},{"id":"547610","messageId":"ak-2EHY6YlFkW9p6@pks.im","threadId":"65929","inReplyTo":"CAL71e4PrtZwB8TMg3eBj=LzC7ik+C8yxLYEEEP7SDgMPiWSs0Q@mail.gmail.com","subject":"Re: [PATCH v2 2/2] reftable: fix quadratic behavior in the presence of tombstones","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-07-09T14:54:08Z","receivedAt":"2026-07-09T14:54:19Z","isPatch":true,"body":"On Thu, Jul 09, 2026 at 04:48:43PM +0200, Kristofer Karlsson wrote:\n> On Thu, 9 Jul 2026 at 15:53, Patrick Steinhardt wrote:\n> >\n> > On Thu, Jul 09, 2026 at 12:08:31PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> > > diff --git a/reftable/stack.c b/reftable/stack.c\n> > > index ab12926708..fd7d8f3f1e 100644\n> > > --- a/reftable/stack.c\n> > > +++ b/reftable/stack.c\n> > > @@ -337,7 +337,6 @@ static int reftable_stack_reload_once(struct reftable_stack *st,\n> > > /* Update the stack to point to the new tables. */\n> > > if (st->merged)\n> > > reftable_merged_table_free(st->merged);\n> > > - new_merged->suppress_deletions = 1;\n> > > st->merged = new_merged;\n> > >\n> > > if (st->tables)\n> >\n> > Okay, we still retain the field after this patch. But the question is:\n> > how would libgit2 now set it? I think we should rather extend the\n> > `struct reftable_stack_options` so that the caller can control whether\n> > or not to suppress deletions at stack creation time.\n> \n> You are right, I (still) missed the compatibility problem here.\n> \n> I started thinking about a way to make it fully backwards compatible,\n> but then I looked at the libgit2 repo and realized it will need\n> updating anyway since it predates the reftable_stack_options split.\n\nYeah, that's something I'll handle soon(ish).\n\n> I will add suppress_deletions to reftable_stack_options as you\n> suggested.\n\nThanks!\n\nPatrick\n"},{"id":"547709","messageId":"pull.2166.v3.git.1783679767.gitgitgadget@gmail.com","threadId":"65929","inReplyTo":"pull.2166.v2.git.1783598912.gitgitgadget@gmail.com","subject":"[PATCH v3 0/2] reftable: fix quadratic behavior when re-creating deleted refs","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-10T10:36:05Z","receivedAt":"2026-07-10T10:36:10Z","isPatch":true,"body":"This series fixes quadratic behavior in the reftable backend when many\ntombstones are present. Any operation that seeks into a range containing\ntombstones is affected, including ref lookups and D/F conflict checks.\n\nThe root cause is the merged iterator's suppress_deletions flag, which\nsilently consumes tombstone records in a tight internal loop. This prevents\nhigher-level code from checking iteration bounds until after all tombstones\nhave been scanned, making both refs_verify_refnames_available() and\nreftable_backend_read_ref() O(n) per call in the presence of tombstones.\n\nThe fix makes suppress_deletions configurable via reftable_stack_options\n(defaulting to off) and handles deletion records at each call site in the\nreftable backend, where prefix and refname bounds are available. This lets\nexisting bounds checks terminate iteration early when encountering\ntombstones past the relevant bound.\n\nDownstream users of the reftable library (e.g. libgit2) can enable\nsuppress_deletions through the stack options to retain the previous\nbehavior.\n\nThe first patch adds a perf test (p1401) exercising two tombstone scenarios\nwith 8000 refs. The second patch is the optimization. Both p1401 tests go\nfrom ~13s to ~0.2s with the fix.\n\nNote that auto-compaction typically merges tombstones before they accumulate\nto this degree, so the quadratic behavior may not show up in every workflow.\nBut the fix ensures correct time complexity regardless of compaction state,\nand the change is fairly contained.\n\nChanges since v2:\n\n * Add suppress_deletions to reftable_stack_options so downstream callers\n can control it at stack creation time (suggested by Patrick)\n\nChanges since v1:\n\n * Keep suppress_deletions in the reftable library for downstream users;\n only stop setting it in stack.c\n * Broaden scope description to cover all readers, not just ref creation\n * Use separate repositories in perf test to avoid cross-scenario state\n * Drop correctness test (implicitly covered by t1400)\n\nPrevious discussion:\nhttps://lore.kernel.org/git/20260701080014.GA3748390@coredump.intra.peff.net/\n\nKristofer Karlsson (2):\n t/perf: add perf test for ref tombstone scenarios\n reftable: fix quadratic behavior in the presence of tombstones\n\n refs/reftable-backend.c | 54 ++++++++++++++++++++++------\n reftable/reftable-stack.h | 2 ++\n reftable/stack.c | 2 +-\n t/perf/p1401-ref-store-tombstones.sh | 46 ++++++++++++++++++++++++\n 4 files changed, 92 insertions(+), 12 deletions(-)\n create mode 100755 t/perf/p1401-ref-store-tombstones.sh\n\n\nbase-commit: f85a7e662054a7b0d9070e432508831afa214b47\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2166%2Fspkrka%2Freftable-tombstone-perf-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2166/spkrka/reftable-tombstone-perf-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/2166\n\nRange-diff vs v2:\n\n 1: 889d0d38bc = 1: 889d0d38bc t/perf: add perf test for ref tombstone scenarios\n 2: c13f15ddc2 ! 2: 4fdcec8440 reftable: fix quadratic behavior in the presence of tombstones\n @@ Commit message\n found\", because the merged iterator skips the matching tombstone\n and searches for the next live record.\n \n - Fix this by no longer setting suppress_deletions on the stack's\n - merged table and instead handling deletion records at each call site\n - in the reftable backend, where prefix and refname bounds are\n - available. Tombstones are now returned to callers, which skip them\n - after their existing bounds checks. This allows iteration to\n - terminate as soon as a tombstone past the relevant bound is\n - encountered.\n + Fix this by making suppress_deletions configurable via\n + reftable_stack_options instead of unconditionally enabling it. Git\n + no longer sets the flag, so tombstones are now returned to callers in\n + the reftable backend, which skip them after their existing bounds\n + checks. This allows iteration to terminate as soon as a tombstone\n + past the relevant bound is encountered.\n \n - The suppress_deletions flag and its logic in the merged iterator are\n - retained for downstream users of the reftable library (e.g. libgit2).\n + Downstream users of the reftable library (e.g. libgit2) can still\n + enable suppress_deletions through the stack options to retain the\n + previous behavior.\n \n This also requires adding deletion checks to the log iteration paths,\n since suppress_deletions applied to both ref and log iterators.\n \n - Both tests in p1401 go from ~14s to ~0.2s with this change.\n + Both tests in p1401 go from ~13s to ~0.2s with this change.\n \n Reported-by: Jeff King \n Signed-off-by: Kristofer Karlsson \n @@ refs/reftable-backend.c: static int reftable_be_fsck(struct ref_store *ref_store\n \t\tcase REFTABLE_REF_VAL2: {\n \t\t\tstruct object_id oid;\n \n + ## reftable/reftable-stack.h ##\n +@@ reftable/reftable-stack.h: struct reftable_stack_options {\n + \t */\n + \tvoid (*on_reload)(void *payload);\n + \tvoid *on_reload_payload;\n ++\n ++\tint suppress_deletions;\n + };\n + \n + /* open a new reftable stack. The tables along with the table list will be\n +\n ## reftable/stack.c ##\n @@ reftable/stack.c: static int reftable_stack_reload_once(struct reftable_stack *st,\n \t/* Update the stack to point to the new tables. */\n \tif (st->merged)\n \t\treftable_merged_table_free(st->merged);\n -\tnew_merged->suppress_deletions = 1;\n ++\tnew_merged->suppress_deletions = st->opts.suppress_deletions;\n \tst->merged = new_merged;\n \n \tif (st->tables)\n\n-- \ngitgitgadget\n"},{"id":"547710","messageId":"889d0d38bc9952a9f5f74063c685c72c299b1490.1783679767.git.gitgitgadget@gmail.com","threadId":"65929","inReplyTo":"pull.2166.v3.git.1783679767.gitgitgadget@gmail.com","subject":"[PATCH v3 1/2] t/perf: add perf test for ref tombstone scenarios","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-10T10:36:06Z","receivedAt":"2026-07-10T10:36:11Z","isPatch":true,"body":"From: Kristofer Karlsson \n\nAdd performance tests for update-ref when many tombstones are present\nin a reftable.\n\nThe first test exercises the scenario where all refs are deleted\n(creating tombstones) and then re-created with the same names, which\ncurrently exhibits quadratic behavior.\n\nThe second test uses a separate repository with an asymmetric variant\nwhere refs are deleted and then new, differently-named refs are\ncreated. When the tombstones sort after the new refs, every create\nscans all tombstones, making this case even worse than re-creating\nthe same refs.\n\nHelped-by: Jeff King \nSigned-off-by: Kristofer Karlsson \n---\n t/perf/p1401-ref-store-tombstones.sh | 46 ++++++++++++++++++++++++++++\n 1 file changed, 46 insertions(+)\n create mode 100755 t/perf/p1401-ref-store-tombstones.sh\n\ndiff --git a/t/perf/p1401-ref-store-tombstones.sh b/t/perf/p1401-ref-store-tombstones.sh\nnew file mode 100755\nindex 0000000000..9e3d8031aa\n--- /dev/null\n+++ b/t/perf/p1401-ref-store-tombstones.sh\n@@ -0,0 +1,46 @@\n+#!/bin/sh\n+\n+test_description=\"Tests performance of ref operations with many tombstones\"\n+\n+. ./perf-lib.sh\n+\n+test_expect_success \"setup\" '\n+\tgit init --ref-format=reftable repo &&\n+\tblob=$(echo foo | git -C repo hash-object -w --stdin) &&\n+\tfor i in $(test_seq 8000)\n+\tdo\n+\t\tprintf \"create refs/tags/tag-%d %s\\n\" \"$i\" \"$blob\" ||\n+\t\treturn 1\n+\tdone >repo/input &&\n+\tgit -C repo update-ref --stdin repo2/input-old &&\n+\tsed \"s/old-/new-/\" repo2/input-new &&\n+\tgit -C repo2 update-ref --stdin \n\nWhen many tombstones are present in a reftable, operations that need\nto look up or iterate over refs exhibit quadratic behavior. With\n8000 refs deleted and re-created, update-ref takes ~15s, quadrupling\nfor each doubling of input size.\n\nThe root cause is the merged iterator's suppress_deletions flag.\nWhen set, merged_iter_next_void() silently consumes tombstone records\nin a tight internal loop before returning to the caller. This\nprevents higher-level code from checking iteration bounds (such as\nprefix or refname comparisons) until after all tombstones have been\nscanned.\n\nThis affects any code path that seeks into a range containing\ntombstones, including:\n\n - refs_verify_refnames_available() seeks to \"refs/tags/foo-1/\" to\n check for D/F conflicts and must scan through all subsequent\n tombstones before the caller can see that they are past the prefix\n of interest.\n\n - reftable_backend_read_ref() seeks to a specific refname and must\n scan through all subsequent tombstones before returning \"not\n found\", because the merged iterator skips the matching tombstone\n and searches for the next live record.\n\nFix this by making suppress_deletions configurable via\nreftable_stack_options instead of unconditionally enabling it. Git\nno longer sets the flag, so tombstones are now returned to callers in\nthe reftable backend, which skip them after their existing bounds\nchecks. This allows iteration to terminate as soon as a tombstone\npast the relevant bound is encountered.\n\nDownstream users of the reftable library (e.g. libgit2) can still\nenable suppress_deletions through the stack options to retain the\nprevious behavior.\n\nThis also requires adding deletion checks to the log iteration paths,\nsince suppress_deletions applied to both ref and log iterators.\n\nBoth tests in p1401 go from ~13s to ~0.2s with this change.\n\nReported-by: Jeff King \nSigned-off-by: Kristofer Karlsson \n---\n refs/reftable-backend.c | 54 +++++++++++++++++++++++++++++++--------\n reftable/reftable-stack.h | 2 ++\n reftable/stack.c | 2 +-\n 3 files changed, 46 insertions(+), 12 deletions(-)\n\ndiff --git a/refs/reftable-backend.c b/refs/reftable-backend.c\nindex 212408c769..028f0211af 100644\n--- a/refs/reftable-backend.c\n+++ b/refs/reftable-backend.c\n@@ -84,7 +84,8 @@ static int reftable_backend_read_ref(struct reftable_backend *be,\n \tif (ret)\n \t\tgoto done;\n \n-\tif (strcmp(ref.refname, refname)) {\n+\tif (strcmp(ref.refname, refname) ||\n+\t reftable_ref_record_is_deletion(&ref)) {\n \t\tret = 1;\n \t\tgoto done;\n \t}\n@@ -110,7 +111,6 @@ static int reftable_backend_read_ref(struct reftable_backend *be,\n \t\toidread(oid, reftable_ref_record_val1(&ref),\n \t\t\t&hash_algos[hash_id]);\n \t} else {\n-\t\t/* We got a tombstone, which should not happen. */\n \t\tBUG(\"unhandled reference value type %d\", ref.value_type);\n \t}\n \n@@ -652,6 +652,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \t\t\tbreak;\n \t\t}\n \n+\t\tif (iter->ref.value_type == REFTABLE_REF_DELETION)\n+\t\t\tcontinue;\n+\n \t\tif (iter->exclude_patterns && should_exclude_current_ref(iter))\n \t\t\tcontinue;\n \n@@ -1532,6 +1535,8 @@ static int write_transaction_table(struct reftable_writer *writer, void *cb_data\n \t\t\t\t\tret = 0;\n \t\t\t\t\tbreak;\n \t\t\t\t}\n+\t\t\t\tif (reftable_log_record_is_deletion(&log))\n+\t\t\t\t\tcontinue;\n \n \t\t\t\tALLOC_GROW(logs, logs_nr + 1, logs_alloc);\n \t\t\t\ttombstone = &logs[logs_nr++];\n@@ -1929,6 +1934,8 @@ static int write_copy_table(struct reftable_writer *writer, void *cb_data)\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&old_log))\n+\t\t\tcontinue;\n \n \t\tfree(old_log.refname);\n \n@@ -2061,6 +2068,9 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator)\n \t\tif (iter->err)\n \t\t\tbreak;\n \n+\t\tif (reftable_log_record_is_deletion(&iter->log))\n+\t\t\tcontinue;\n+\n \t\t/*\n \t\t * We want the refnames that we have reflogs for, so we skip if\n \t\t * we've already produced this name. This could be faster by\n@@ -2220,6 +2230,8 @@ static int reftable_be_for_each_reflog_ent_reverse(struct ref_store *ref_store,\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log))\n+\t\t\tcontinue;\n \n \t\tret = yield_log_record(refs, &log, fn, cb_data);\n \t\tif (ret)\n@@ -2272,6 +2284,10 @@ static int reftable_be_for_each_reflog_ent(struct ref_store *ref_store,\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log)) {\n+\t\t\treftable_log_record_release(&log);\n+\t\t\tcontinue;\n+\t\t}\n \n \t\tALLOC_GROW(logs, logs_nr + 1, logs_alloc);\n \t\tlogs[logs_nr++] = log;\n@@ -2318,18 +2334,26 @@ static int reftable_be_reflog_exists(struct ref_store *ref_store,\n \t\tgoto done;\n \n \t/*\n-\t * Check whether we get at least one log record for the given ref name.\n-\t * If so, the reflog exists, otherwise it doesn't.\n+\t * Check whether we get at least one non-deleted log record for the\n+\t * given ref name. If so, the reflog exists, otherwise it doesn't.\n \t */\n-\tret = reftable_iterator_next_log(&it, &log);\n-\tif (ret < 0)\n-\t\tgoto done;\n-\tif (ret > 0) {\n-\t\tret = 0;\n-\t\tgoto done;\n+\twhile (1) {\n+\t\tret = reftable_iterator_next_log(&it, &log);\n+\t\tif (ret < 0)\n+\t\t\tgoto done;\n+\t\tif (ret > 0) {\n+\t\t\tret = 0;\n+\t\t\tgoto done;\n+\t\t}\n+\t\tif (strcmp(log.refname, refname)) {\n+\t\t\tret = 0;\n+\t\t\tgoto done;\n+\t\t}\n+\t\tif (!reftable_log_record_is_deletion(&log))\n+\t\t\tbreak;\n \t}\n \n-\tret = strcmp(log.refname, refname) == 0;\n+\tret = 1;\n \n done:\n \treftable_iterator_destroy(&it);\n@@ -2442,6 +2466,8 @@ static int write_reflog_delete_table(struct reftable_writer *writer, void *cb_da\n \t\t\tret = 0;\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log))\n+\t\t\tcontinue;\n \n \t\ttombstone.refname = (char *)arg->refname;\n \t\ttombstone.value_type = REFTABLE_LOG_DELETION;\n@@ -2625,6 +2651,10 @@ static int reftable_be_reflog_expire(struct ref_store *ref_store,\n \t\t\treftable_log_record_release(&log);\n \t\t\tbreak;\n \t\t}\n+\t\tif (reftable_log_record_is_deletion(&log)) {\n+\t\t\treftable_log_record_release(&log);\n+\t\t\tcontinue;\n+\t\t}\n \n \t\toidread(&old_oid, log.value.update.old_hash,\n \t\t\tref_store->repo->hash_algo);\n@@ -2791,6 +2821,8 @@ static int reftable_be_fsck(struct ref_store *ref_store, struct fsck_options *o,\n \t\treport.path = refname.buf;\n \n \t\tswitch (ref.value_type) {\n+\t\tcase REFTABLE_REF_DELETION:\n+\t\t\tcontinue;\n \t\tcase REFTABLE_REF_VAL1:\n \t\tcase REFTABLE_REF_VAL2: {\n \t\t\tstruct object_id oid;\ndiff --git a/reftable/reftable-stack.h b/reftable/reftable-stack.h\nindex 11f9963f4f..5d22d84e80 100644\n--- a/reftable/reftable-stack.h\n+++ b/reftable/reftable-stack.h\n@@ -42,6 +42,8 @@ struct reftable_stack_options {\n \t */\n \tvoid (*on_reload)(void *payload);\n \tvoid *on_reload_payload;\n+\n+\tint suppress_deletions;\n };\n \n /* open a new reftable stack. The tables along with the table list will be\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex ab12926708..caaedf24d6 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -337,7 +337,7 @@ static int reftable_stack_reload_once(struct reftable_stack *st,\n \t/* Update the stack to point to the new tables. */\n \tif (st->merged)\n \t\treftable_merged_table_free(st->merged);\n-\tnew_merged->suppress_deletions = 1;\n+\tnew_merged->suppress_deletions = st->opts.suppress_deletions;\n \tst->merged = new_merged;\n \n \tif (st->tables)\n-- \ngitgitgadget\n"},{"id":"547735","messageId":"alECc90WZ9RPqMaA@pks.im","threadId":"65929","inReplyTo":"4fdcec84406431d56b7a7e593fd8e843c3b1ad52.1783679767.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 2/2] reftable: fix quadratic behavior in the presence of tombstones","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-07-10T14:32:19Z","receivedAt":"2026-07-10T14:32:26Z","isPatch":true,"body":"On Fri, Jul 10, 2026 at 10:36:07AM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> From: Kristofer Karlsson \n> \n> When many tombstones are present in a reftable, operations that need\n> to look up or iterate over refs exhibit quadratic behavior. With\n> 8000 refs deleted and re-created, update-ref takes ~15s, quadrupling\n> for each doubling of input size.\n> \n> The root cause is the merged iterator's suppress_deletions flag.\n> When set, merged_iter_next_void() silently consumes tombstone records\n> in a tight internal loop before returning to the caller. This\n> prevents higher-level code from checking iteration bounds (such as\n> prefix or refname comparisons) until after all tombstones have been\n> scanned.\n> \n> This affects any code path that seeks into a range containing\n> tombstones, including:\n> \n> - refs_verify_refnames_available() seeks to \"refs/tags/foo-1/\" to\n> check for D/F conflicts and must scan through all subsequent\n> tombstones before the caller can see that they are past the prefix\n> of interest.\n> \n> - reftable_backend_read_ref() seeks to a specific refname and must\n> scan through all subsequent tombstones before returning \"not\n> found\", because the merged iterator skips the matching tombstone\n> and searches for the next live record.\n> \n> Fix this by making suppress_deletions configurable via\n> reftable_stack_options instead of unconditionally enabling it. Git\n> no longer sets the flag, so tombstones are now returned to callers in\n> the reftable backend, which skip them after their existing bounds\n> checks. This allows iteration to terminate as soon as a tombstone\n> past the relevant bound is encountered.\n> \n> Downstream users of the reftable library (e.g. libgit2) can still\n> enable suppress_deletions through the stack options to retain the\n> previous behavior.\n> \n> This also requires adding deletion checks to the log iteration paths,\n> since suppress_deletions applied to both ref and log iterators.\n\nNit: s/applied/applies/\n\n> diff --git a/reftable/reftable-stack.h b/reftable/reftable-stack.h\n> index 11f9963f4f..5d22d84e80 100644\n> --- a/reftable/reftable-stack.h\n> +++ b/reftable/reftable-stack.h\n> @@ -42,6 +42,8 @@ struct reftable_stack_options {\n> \t */\n> \tvoid (*on_reload)(void *payload);\n> \tvoid *on_reload_payload;\n> +\n> +\tint suppress_deletions;\n> };\n\nA comment would've been nice, but I don't think this warrants a reroll.\n\n> diff --git a/reftable/stack.c b/reftable/stack.c\n> index ab12926708..caaedf24d6 100644\n> --- a/reftable/stack.c\n> +++ b/reftable/stack.c\n> @@ -337,7 +337,7 @@ static int reftable_stack_reload_once(struct reftable_stack *st,\n> \t/* Update the stack to point to the new tables. */\n> \tif (st->merged)\n> \t\treftable_merged_table_free(st->merged);\n> -\tnew_merged->suppress_deletions = 1;\n> +\tnew_merged->suppress_deletions = st->opts.suppress_deletions;\n> \tst->merged = new_merged;\n\nYup, this looks good to me.\n\nThanks!\n\nPatrick\n"},{"id":"547740","messageId":"CAL71e4POhVpQ9FvLmjUc4ex_=T-DuCd7cas1D4uzqzg3RyDw+Q@mail.gmail.com","threadId":"65929","inReplyTo":"alECc90WZ9RPqMaA@pks.im","subject":"Re: [PATCH v3 2/2] reftable: fix quadratic behavior in the presence of tombstones","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-07-10T15:03:28Z","receivedAt":"2026-07-10T15:03:43Z","isPatch":true,"body":"On Fri, 10 Jul 2026 at 16:32, Patrick Steinhardt wrote:\n>\n> > This also requires adding deletion checks to the log iteration paths,\n> > since suppress_deletions applied to both ref and log iterators.\n>\n> Nit: s/applied/applies/\n\nLanguage and using correct tense is always the tricky part --\nwill fix if a reroll is needed for other reasons.\n\n> > + int suppress_deletions;\n>\n> A comment would've been nice, but I don't think this warrants a reroll.\n\nAgreed, the field name felt self-documenting to me, but I will\nadd a short comment if there is a reroll.\nSomething like this?\n\"boolean: filters out tombstoned/deleted refs early if true\"\n\n> > - new_merged->suppress_deletions = 1;\n> > + new_merged->suppress_deletions = st->opts.suppress_deletions;\n>\n> Yup, this looks good to me.\n\nThanks for the quick review.\n\nAnother thing I have been thinking about: should we consider\nsuppress_deletions a temporary stopgap, with the goal of\neventually removing it?\n\nI took a look at libgit2's refdb_reftable.c to see what\nit would look like. It doesn't seem _too_ complicated\n(but I have been wrong about complexity before):\n\nreftable_stack_read_ref() and reftable_stack_read_log()\nalready check is_deletion() after the seek+next,\nso the call sites that use those would work correctly\nwithout suppress_deletions too. (I think?)\n\nThe other call sites that iterate would need the same\ntype of filter as we have in this patch series.\n\nSo the total cost for libgit2 to stop relying on\nsuppress_deletions would be fairly small and it would maybe\nalso got a nice performance boost for the edge cases,\nthough I have not attempted to verify that.\n\nThat said, it does not affect this patch - regardless\nof the future we will need this flag now.\n\nThanks,\nKristofer\n"},{"id":"547938","messageId":"alR0U_OVOiYuFnXh@pks.im","threadId":"65929","inReplyTo":"CAL71e4POhVpQ9FvLmjUc4ex_=T-DuCd7cas1D4uzqzg3RyDw+Q@mail.gmail.com","subject":"Re: [PATCH v3 2/2] reftable: fix quadratic behavior in the presence of tombstones","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-07-13T05:14:59Z","receivedAt":"2026-07-13T05:15:07Z","isPatch":true,"body":"On Fri, Jul 10, 2026 at 05:03:28PM +0200, Kristofer Karlsson wrote:\n> On Fri, 10 Jul 2026 at 16:32, Patrick Steinhardt wrote:\n> >\n> > > This also requires adding deletion checks to the log iteration paths,\n> > > since suppress_deletions applied to both ref and log iterators.\n> >\n> > Nit: s/applied/applies/\n> \n> Language and using correct tense is always the tricky part --\n> will fix if a reroll is needed for other reasons.\n> \n> > > + int suppress_deletions;\n> >\n> > A comment would've been nice, but I don't think this warrants a reroll.\n> \n> Agreed, the field name felt self-documenting to me, but I will\n> add a short comment if there is a reroll.\n> Something like this?\n> \"boolean: filters out tombstoned/deleted refs early if true\"\n\nI'd drop the \"boolean: \" prefix, but other than that this looks sensible\nto me.\n\n> > > - new_merged->suppress_deletions = 1;\n> > > + new_merged->suppress_deletions = st->opts.suppress_deletions;\n> >\n> > Yup, this looks good to me.\n> \n> Thanks for the quick review.\n> \n> Another thing I have been thinking about: should we consider\n> suppress_deletions a temporary stopgap, with the goal of\n> eventually removing it?\n\nMaybe? I'll update libgit2 as soon as both ps/reftable-hardening and\nkk/reftable-tombstone-quadratic-fix have been merged to \"master\". Once\ndone, feel free to create a pull request against libgit2 to deactivate\n`suppress_deletions` there, and once that's happened we can also drop\nthe code in Git itself.\n\nThanks!\n\nPatrick\n"}]}