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

Re: weird quadratic reftable behavior, was: Re: [PATCH 3/3] t5551: pack refs after creating many tags

From
Patrick Steinhardt <ps@pks.im>
Date
Jul 1, 2026, 10:07 UTC
Message-ID
<akTm7BDohsy85sN8@pks.im>
In-Reply-To
<CAL71e4PfXA-ixKR6r7fu_7_QmdzK+rTRs29mOsUYKaq+_a5q5w@mail.gmail.com>
On Wed, Jul 01, 2026 at 11:04:45AM +0200, Kristofer Karlsson wrote:
Show 21 quoted lines
> On Wed, 1 Jul 2026 at 10:00, Jeff King <peff@peff.net> wrote:
> 
> > Yeah, it is (mostly) the same problem. About half the time is spent in
> > refs_verify_refnames_available().
> >
> > The other half is in reftable_be_transaction_prepare(). Looks like it
> > makes individual calls to prepare_single_update(), which reads each ref.
> > And those reads are expensive because of all of the tombstones. It might
> > be possible to do an iterator merge or similar between the sorted list
> > of transaction refs and the reftable contents.
> 
> Hi, sorry for jumping in -- I found this interesting and started
> poking at the code. I think both halves may share the same root
> cause.
> 
> The merged iterator's suppress_deletions flag filters out tombstones
> internally, which means higher-level code with prefix or refname
> bounds never gets a chance to stop iteration early. By letting
> tombstones pass through and filtering them one layer up in the
> reftable backend, the existing bounds checks can kick in before
> we scan through all the tombstones.

Ah, interesting. This kind of hits int o the direction that I proposed of stopping iteration once we hit the first reference that has a lexicographically-larget refname. But I thought about having to solve it generically in the iterator somehow, and I wasn't really looking forward to that.

Your solutions works around that issue indeed. It of course doesn't solve reference iteration, which would still be expensive. But it does solve the issue where we just want to look up a single reference, which is what Peff noticed to be slow.

Show 12 quoted lines
> So instead of doing full scans inside merged_iter_next_void()
> we can just delegate to merged_iter_next_entry() and instead
> add a loop to reftable_be_reflog_exists() that skips
> tombstones (but is amortized O(1)).
> 
> Now multiple call sites would need to add something like this
> to compensate for returning tombstones:
> 
>     if (reftable_log_record_is_deletion(&iter->log))
>         continue;
> 
> but it may be worth it if it reduces cost when there are many refs.
I think it certainly might be.
Show 5 quoted lines
> The key spot is reftable_ref_iterator_advance(), where the deletion
> skip goes right after the existing prefix check -- so a tombstone
> past the prefix stops iteration immediately instead of being
> silently consumed. The same idea applies to reftable_backend_read_ref()
> and the log iteration paths.
Yup.
Show 19 quoted lines
> I have a local branch with this attempted fix. Rerunning the
> benchmark:
> 
>   Before:
>     nr=1000  0.306s
>     nr=2000  0.945s
>     nr=4000  3.816s
>     nr=8000  14.93s
> 
>   After:
>     nr=1000   0.020s
>     nr=2000   0.044s
>     nr=4000   0.071s
>     nr=8000   0.145s
>     nr=16000  0.258s
>     nr=32000  0.591s
> 
> I can send a proper patch if needed/wanted, but I might have missed
> something silly here.

Nice gains. I certainly think it would make sense to polish this a bit and then cast it into a patch.

Patrick
Previous: Kristofer KarlssonNext: Kristofer Karlsson
Message 30 of 42 in “Re: [RFH] Why do osx CI jobs so unreliable?”
  1. Michael MontalboJun 20, 2026
  2. Jeff KingJun 21, 2026
  3. Patrick SteinhardtJun 22, 2026
  4. Patrick SteinhardtJun 22, 2026
  5. Patrick SteinhardtJun 22, 2026
  6. Patrick SteinhardtJun 22, 2026
  7. Michael MontalboJun 26, 2026
  8. Jeff KingJun 26, 2026
  9. Patrick SteinhardtJun 26, 2026
  10. Junio C HamanoJun 26, 2026
  11. Michael MontalboJun 26, 2026
  12. 0/3 fixing expensive http test timeoutsJeff King, Jun 28, 2026
  13. 1/3 t/lib-httpd: bump apache timeoutJeff King, Jun 28, 2026
  14. Michael MontalboJul 2, 2026
  15. 2/3 t5551: put many-tags case into its own repoJeff King, Jun 28, 2026
  16. Junio C HamanoJun 28, 2026
  17. Jeff KingJun 29, 2026
  18. Junio C HamanoJun 29, 2026
  19. Jeff KingJun 29, 2026
  20. 3/3 t5551: pack refs after creating many tagsJeff King, Jun 28, 2026
  21. Junio C HamanoJun 28, 2026
  22. Patrick SteinhardtJun 29, 2026
  23. Jeff KingJun 29, 2026
  24. Patrick SteinhardtJun 30, 2026
  25. Jeff KingJun 30, 2026
  26. weird quadratic reftable behavior, was: Re: [PATCH 3/3] t5551: pack refs after creating many tagsJeff King, Jun 30, 2026
  27. Patrick SteinhardtJul 1, 2026
  28. Jeff KingJul 1, 2026
  29. Kristofer KarlssonJul 1, 2026
  30. Patrick SteinhardtJul 1, 2026
  31. Kristofer KarlssonJul 3, 2026
  32. Patrick SteinhardtJul 6, 2026
  33. Kristofer KarlssonJul 6, 2026
  34. Patrick SteinhardtJun 29, 2026
  35. Junio C HamanoJun 29, 2026
  36. Patrick SteinhardtJun 29, 2026
  37. Junio C HamanoJun 29, 2026
  38. Patrick SteinhardtJun 30, 2026
  39. Junio C HamanoJun 30, 2026
  40. Patrick SteinhardtJul 1, 2026
  41. Jeff KingJun 26, 2026
  42. Junio C HamanoJun 22, 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.