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

Re: [PATCH v3 2/2] reftable: fix quadratic behavior in the presence of tombstones

From
Kristofer Karlsson <krka@spotify.com>
Date
Jul 10, 2026, 15:03 UTC
Message-ID
<CAL71e4POhVpQ9FvLmjUc4ex_=T-DuCd7cas1D4uzqzg3RyDw+Q@mail.gmail.com>
In-Reply-To
<alECc90WZ9RPqMaA@pks.im>
On Fri, 10 Jul 2026 at 16:32, Patrick Steinhardt <ps@pks.im> wrote:
Show 5 quoted lines
>
> > This also requires adding deletion checks to the log iteration paths,
> > since suppress_deletions applied to both ref and log iterators.
>
> Nit: s/applied/applies/

Language and using correct tense is always the tricky part -- will fix if a reroll is needed for other reasons.

> > +     int suppress_deletions;
>
> A comment would've been nice, but I don't think this warrants a reroll.

Agreed, the field name felt self-documenting to me, but I will add a short comment if there is a reroll. Something like this? "boolean: filters out tombstoned/deleted refs early if true"

> > -     new_merged->suppress_deletions = 1;
> > +     new_merged->suppress_deletions = st->opts.suppress_deletions;
>
> Yup, this looks good to me.
Thanks for the quick review.

Another thing I have been thinking about: should we consider suppress_deletions a temporary stopgap, with the goal of eventually removing it?

I took a look at libgit2's refdb_reftable.c to see what it would look like. It doesn't seem _too_ complicated (but I have been wrong about complexity before):

reftable_stack_read_ref() and reftable_stack_read_log() already check is_deletion() after the seek+next, so the call sites that use those would work correctly without suppress_deletions too. (I think?)

The other call sites that iterate would need the same type of filter as we have in this patch series.

So the total cost for libgit2 to stop relying on suppress_deletions would be fairly small and it would maybe also got a nice performance boost for the edge cases, though I have not attempted to verify that.

That said, it does not affect this patch - regardless of the future we will need this flag now.

Thanks, Kristofer

Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 21 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.