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

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

From
Patrick Steinhardt <ps@pks.im>
Date
Jul 7, 2026, 15:24 UTC
Message-ID
<ak0aRtvSxSyIWieg@pks.im>
In-Reply-To
<1459371d3ab2f237152e20040987b4cb6a5eca77.1783344957.git.gitgitgadget@gmail.com>
On Mon, Jul 06, 2026 at 01:35:56PM +0000, Kristofer Karlsson via GitGitGadget wrote:
Show 24 quoted lines
> From: Kristofer Karlsson <krka@spotify.com>
> 
> When many refs are deleted and then re-created, update-ref exhibits
> quadratic behavior.  With 8000 refs deleted and re-created, the
> runtime is ~15s, quadrupling for each doubling of input size.
> 
> The root cause is the merged iterator's suppress_deletions flag.
> When set, merged_iter_next_void() silently consumes tombstone records
> in a tight internal loop before returning to the caller.  This
> prevents higher-level code from checking iteration bounds (such as
> prefix or refname comparisons) until after all tombstones have been
> scanned.
> 
> This affects two code paths during ref creation:
> 
>  - refs_verify_refnames_available() seeks to "refs/tags/foo-1/" to
>    check for D/F conflicts and must scan through all subsequent
>    tombstones before the caller can see that they are past the prefix
>    of interest.
> 
>  - reftable_backend_read_ref() seeks to a specific refname and must
>    scan through all subsequent tombstones before returning "not
>    found", because the merged iterator skips the matching tombstone
>    and searches for the next live record.

It probably not only impacts reference creation, but also every reader that wants to search for a specific reference that doesn't exist.

Show 6 quoted lines
> Fix this by removing suppress_deletions from the merged iterator and
> instead handling deletion records at each call site in the reftable
> backend, where prefix and refname bounds are available.  Tombstones
> are now returned to callers, which skip them after their existing
> bounds checks.  This allows iteration to terminate as soon as a
> tombstone past the relevant bound is encountered.

This option is still used by downstream users of the reftable library, like libgit2. So we shouldn't just delete it outright.

Show 14 quoted lines
> diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c
> index 4ae22922de..8c4f119ff1 100644
> --- a/refs/reftable-backend.c
> +++ b/refs/reftable-backend.c
> @@ -633,6 +633,9 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator)
>  			break;
>  		}
>  
> +		if (iter->ref.value_type == REFTABLE_REF_DELETION)
> +			continue;
> +
>  		if (iter->exclude_patterns && should_exclude_current_ref(iter))
>  			continue;
>  

Okay. I was first wondering whether we should move this call earlier. But we actually don't want to, as this is the code that precedes the above:

	if (iter->prefix_len &&
	    strncmp(iter->prefix, iter->ref.refname, iter->prefix_len)) {
		iter->err = 1;
		break;
	}

So this allows us to not only skip the current iteration, but completely abort iteration by observing tombstones that sort after our prefix.

In any case, as far as I can see all sites where we iterate through either ref or log records have been adapted to handle deletions.

Thanks!
Patrick
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson
Message 8 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.