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

[PATCH 1/2] t: add tests for ref tombstone scenarios

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

Add a performance test and a correctness test for update-ref when many tombstones are present in a reftable.

The performance test (p1401) exercises two scenarios:
 - 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.

Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 t/perf/p1401-ref-store-tombstones.sh | 44 ++++++++++++++++++++++++++++
 t/t0610-reftable-basics.sh           | 22 ++++++++++++++
 2 files changed, 66 insertions(+)
 create mode 100755 t/perf/p1401-ref-store-tombstones.sh
diff --git a/t/perf/p1401-ref-store-tombstones.sh b/t/perf/p1401-ref-store-tombstones.sh
new file mode 100755
index 0000000000..e40a6dcbf4
--- /dev/null
+++ b/t/perf/p1401-ref-store-tombstones.sh
@@ -0,0 +1,44 @@
+#!/bin/sh
+
+test_description="Tests performance of ref operations with many tombstones"
+
+. ./perf-lib.sh
+
+test_expect_success "setup" '
+	git init --ref-format=reftable repo &&
+	blob=$(echo foo | git -C repo hash-object -w --stdin) &&
+	for i in $(test_seq 8000)
+	do
+		printf "create refs/tags/tag-%d %s\n" "$i" "$blob" ||
+		return 1
+	done >repo/input &&
+	git -C repo update-ref --stdin <repo/input &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_perf "recreate refs after mass delete" '
+	git -C repo update-ref --stdin <repo/input &&
+	git -C repo for-each-ref --format="delete %(refname)" |
+	git -C repo update-ref --stdin
+'
+
+test_expect_success "setup asymmetric" '
+	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
+'
+
+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
+'
+
+test_done
diff --git a/t/t0610-reftable-basics.sh b/t/t0610-reftable-basics.sh
index e19e036898..4b7cfe38e4 100755
--- a/t/t0610-reftable-basics.sh
+++ b/t/t0610-reftable-basics.sh
@@ -1163,4 +1163,26 @@ 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
-- 
gitgitgadget
Previous: Kristofer Karlsson via GitGitGadgetNext: Patrick Steinhardt
Message 2 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.