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