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

Re: [PATCH v3 2/2] reftable: fix quadratic behavior in the presence of tombstones

From
Patrick Steinhardt <ps@pks.im>
Date
Jul 10, 2026, 14:32 UTC
Message-ID
<alECc90WZ9RPqMaA@pks.im>
In-Reply-To
<4fdcec84406431d56b7a7e593fd8e843c3b1ad52.1783679767.git.gitgitgadget@gmail.com>
On Fri, Jul 10, 2026 at 10:36:07AM +0000, Kristofer Karlsson via GitGitGadget wrote:
Show 40 quoted lines
> From: Kristofer Karlsson <krka@spotify.com>
> 
> When many tombstones are present in a reftable, operations that need
> to look up or iterate over refs exhibit quadratic behavior.  With
> 8000 refs deleted and re-created, update-ref takes ~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 any code path that seeks into a range containing
> tombstones, including:
> 
>  - 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.
> 
> Fix this by making suppress_deletions configurable via
> reftable_stack_options instead of unconditionally enabling it.  Git
> no longer sets the flag, so tombstones are now returned to callers in
> the reftable backend, which skip them after their existing bounds
> checks.  This allows iteration to terminate as soon as a tombstone
> past the relevant bound is encountered.
> 
> Downstream users of the reftable library (e.g. libgit2) can still
> enable suppress_deletions through the stack options to retain the
> previous behavior.
> 
> This also requires adding deletion checks to the log iteration paths,
> since suppress_deletions applied to both ref and log iterators.
Nit: s/applied/applies/
Show 11 quoted lines
> diff --git a/reftable/reftable-stack.h b/reftable/reftable-stack.h
> index 11f9963f4f..5d22d84e80 100644
> --- a/reftable/reftable-stack.h
> +++ b/reftable/reftable-stack.h
> @@ -42,6 +42,8 @@ struct reftable_stack_options {
>  	 */
>  	void (*on_reload)(void *payload);
>  	void *on_reload_payload;
> +
> +	int suppress_deletions;
>  };
A comment would've been nice, but I don't think this warrants a reroll.
Show 11 quoted lines
> diff --git a/reftable/stack.c b/reftable/stack.c
> index ab12926708..caaedf24d6 100644
> --- a/reftable/stack.c
> +++ b/reftable/stack.c
> @@ -337,7 +337,7 @@ static int reftable_stack_reload_once(struct reftable_stack *st,
>  	/* Update the stack to point to the new tables. */
>  	if (st->merged)
>  		reftable_merged_table_free(st->merged);
> -	new_merged->suppress_deletions = 1;
> +	new_merged->suppress_deletions = st->opts.suppress_deletions;
>  	st->merged = new_merged;
Yup, this looks good to me.
Thanks!
Patrick
Previous: Kristofer Karlsson via GitGitGadgetNext: Kristofer Karlsson
Message 20 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.