From: Patrick Steinhardt Date: Fri, 10 Jul 2026 14:32:19 GMT Subject: Re: [PATCH v3 2/2] reftable: fix quadratic behavior in the presence of tombstones Message-ID: In-Reply-To: <4fdcec84406431d56b7a7e593fd8e843c3b1ad52.1783679767.git.gitgitgadget@gmail.com> On Fri, Jul 10, 2026 at 10:36:07AM +0000, Kristofer Karlsson via GitGitGadget wrote: > From: Kristofer Karlsson > > 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/ > 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. > 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