git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

Previous: Patrick SteinhardtNext: brian m. carlson
Message 9 of 22 in “reftable: fix quadratic behavior when re-creating deleted refs”
  1. 0/2 reftable: fix quadratic behavior when re-creating deleted refsKristofer Karlsson via GitGitGadget, Jul 6, 2026
  2. 1/2 t: add tests for ref tombstone scenariosKristofer Karlsson via GitGitGadget, Jul 6, 2026
  3. Patrick SteinhardtJul 7, 2026
  4. Kristofer KarlssonJul 7, 2026
  5. Patrick SteinhardtJul 8, 2026
  6. Kristofer KarlssonJul 8, 2026
  7. 2/2 reftable: fix quadratic behavior when re-creating deleted refsKristofer Karlsson via GitGitGadget, Jul 6, 2026
  8. Patrick SteinhardtJul 7, 2026
  9. Kristofer KarlssonJul 7, 2026
  10. brian m. carlsonJul 8, 2026
  11. 0/2 reftable: fix quadratic behavior when re-creating deleted refsKristofer Karlsson via GitGitGadget, Jul 9, 2026
  12. 1/2 t/perf: add perf test for ref tombstone scenariosKristofer Karlsson via GitGitGadget, Jul 9, 2026
  13. 2/2 reftable: fix quadratic behavior in the presence of tombstonesKristofer Karlsson via GitGitGadget, Jul 9, 2026
  14. Patrick SteinhardtJul 9, 2026
  15. Kristofer KarlssonJul 9, 2026
  16. Patrick SteinhardtJul 9, 2026
  17. 0/2 reftable: fix quadratic behavior when re-creating deleted refsKristofer Karlsson via GitGitGadget, Jul 10, 2026
  18. 1/2 t/perf: add perf test for ref tombstone scenariosKristofer Karlsson via GitGitGadget, Jul 10, 2026
  19. 2/2 reftable: fix quadratic behavior in the presence of tombstonesKristofer Karlsson via GitGitGadget, Jul 10, 2026
  20. Patrick SteinhardtJul 10, 2026
  21. Kristofer KarlssonJul 10, 2026
  22. Patrick SteinhardtJul 13, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.