From: Kristofer Karlsson Date: Tue, 07 Jul 2026 16:04:15 GMT Subject: Re: [PATCH 2/2] reftable: fix quadratic behavior when re-creating deleted refs Message-ID: In-Reply-To: On Tue, 7 Jul 2026 at 17:24, Patrick Steinhardt wrote: > > > 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. > > 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. > > 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