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

[PATCH v3 1/2] t/perf: add perf test for ref tombstone scenarios

From
Kristofer Karlsson via GitGitGadget <gitgitgadget@gmail.com>
Date
Jul 10, 2026, 10:36 UTC
Message-ID
<889d0d38bc9952a9f5f74063c685c72c299b1490.1783679767.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.2166.v3.git.1783679767.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>

Add performance tests for update-ref when many tombstones are present in a reftable.

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.

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 | 46 ++++++++++++++++++++++++++++
 1 file changed, 46 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..9e3d8031aa
--- /dev/null
+++ b/t/perf/p1401-ref-store-tombstones.sh
@@ -0,0 +1,46 @@
+#!/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" '
+	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 >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 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
-- 
gitgitgadget
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson via GitGitGadget
Message 18 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.