Re: [PATCH 2/2] reftable: fix quadratic behavior when re-creating deleted refs
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jul 7, 2026, 16:04 UTC
- Message-ID
- <CAL71e4NQLyM1T3YCL1Q09wfnkq7B3ah6i38yBeK8ZJCx1JejgQ@mail.gmail.com>
- In-Reply-To
- <ak0aRtvSxSyIWieg@pks.im>
On Tue, 7 Jul 2026 at 17:24, Patrick Steinhardt <ps@pks.im> wrote:
Show 15 quoted lines
> > > 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.
Hm good point, I will try to rephrase this better.
Show 9 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.
Good catch! I can keep suppress_deletions as-is and just stop setting it from stack.c. That way libgit2 is unchanged, while we still optimize it at the other call sites. The reftable library diff then shrinks to a single removed line.
Show 27 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.Indeed, this is the primary win.
> 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! Appreciate the review (and spotting the libgit breakage!) Kristofer