From: Patrick Steinhardt Date: Tue, 07 Jul 2026 15:24:54 GMT Subject: Re: [PATCH 2/2] reftable: fix quadratic behavior when re-creating deleted refs Message-ID: In-Reply-To: <1459371d3ab2f237152e20040987b4cb6a5eca77.1783344957.git.gitgitgadget@gmail.com> On Mon, Jul 06, 2026 at 01:35:56PM +0000, Kristofer Karlsson via GitGitGadget wrote: > From: Kristofer Karlsson > > 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. > 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. > 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