git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
Date
Jul 6, 2026, 13:35 UTC
Message-ID
<pull.2166.git.1783344957.gitgitgadget@gmail.com>

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

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

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

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

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

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

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

Kristofer Karlsson (2):
  t: add tests for ref tombstone scenarios
  reftable: fix quadratic behavior when re-creating deleted refs
 refs/reftable-backend.c              | 54 ++++++++++++++++++++++------
 reftable/merged.c                    | 12 +------
 reftable/merged.h                    |  4 ---
 reftable/stack.c                     |  1 -
 t/perf/p1401-ref-store-tombstones.sh | 44 +++++++++++++++++++++++
 t/t0610-reftable-basics.sh           | 22 ++++++++++++
 6 files changed, 110 insertions(+), 27 deletions(-)
 create mode 100755 t/perf/p1401-ref-store-tombstones.sh
base-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2166%2Fspkrka%2Freftable-tombstone-perf-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2166/spkrka/reftable-tombstone-perf-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2166
-- 
gitgitgadget
Next: Kristofer Karlsson via GitGitGadget
Message 1 of 22 in “reftable: fix quadratic behavior when re-creating deleted refs”
  1. 0/2 reftable: fix quadratic behavior when re-creating deleted refsKristofer Karlsson via GitGitGadget, Jul 6, 2026
  2. 1/2 t: add tests for ref tombstone scenariosKristofer Karlsson via GitGitGadget, Jul 6, 2026
  3. Patrick SteinhardtJul 7, 2026
  4. Kristofer KarlssonJul 7, 2026
  5. Patrick SteinhardtJul 8, 2026
  6. Kristofer KarlssonJul 8, 2026
  7. 2/2 reftable: fix quadratic behavior when re-creating deleted refsKristofer Karlsson via GitGitGadget, Jul 6, 2026
  8. Patrick SteinhardtJul 7, 2026
  9. Kristofer KarlssonJul 7, 2026
  10. brian m. carlsonJul 8, 2026
  11. 0/2 reftable: fix quadratic behavior when re-creating deleted refsKristofer Karlsson via GitGitGadget, Jul 9, 2026
  12. 1/2 t/perf: add perf test for ref tombstone scenariosKristofer Karlsson via GitGitGadget, Jul 9, 2026
  13. 2/2 reftable: fix quadratic behavior in the presence of tombstonesKristofer Karlsson via GitGitGadget, Jul 9, 2026
  14. Patrick SteinhardtJul 9, 2026
  15. Kristofer KarlssonJul 9, 2026
  16. Patrick SteinhardtJul 9, 2026
  17. 0/2 reftable: fix quadratic behavior when re-creating deleted refsKristofer Karlsson via GitGitGadget, Jul 10, 2026
  18. 1/2 t/perf: add perf test for ref tombstone scenariosKristofer Karlsson via GitGitGadget, Jul 10, 2026
  19. 2/2 reftable: fix quadratic behavior in the presence of tombstonesKristofer Karlsson via GitGitGadget, Jul 10, 2026
  20. Patrick SteinhardtJul 10, 2026
  21. Kristofer KarlssonJul 10, 2026
  22. Patrick SteinhardtJul 13, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.