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, 06:17 UTC
Message-ID
<akSxCUfm2P7ocLJX@pks.im>
In-Reply-To
<20260630235850.GB3759976@coredump.intra.peff.net>
On Tue, Jun 30, 2026 at 07:58:50PM -0400, Jeff King wrote:
Show 41 quoted lines
> On Tue, Jun 30, 2026 at 07:47:02PM -0400, Jeff King wrote:
> 
> > There was one other oddity I didn't quite resolve. You may notice the
> > gross reftable.orig stuff in hyperfine. I originally wrote this as:
> > 
> >     git for-each-ref --format="delete %(refname)" | git update-ref --stdin
> > 
> > but for some reason that causes the subsequent update-ref to loop
> > infinitely on merged_iter_next_entry(). It does so reliably, but I can't
> > reproduce it outside of hyperfine. Super weird, and I'm sure I'm missing
> > something obvious.
> 
> Ah, maybe not infinite, but probably quadratic. The key is that you have
> to delete a lot of refs and then try to insert them again. So with this
> script:
> 
>   nr=$1; shift
>   rm -rf .git
>   
>   git init --ref-format=reftable
>   blob=$(echo foo | git hash-object -w --stdin)
>   seq -f "create refs/tags/foo-%g $blob" $nr >input
>   git update-ref --stdin <input
>   git for-each-ref --format="delete %(refname)" | git update-ref --stdin
>   time git update-ref --stdin <input
> 
> I get results like this:
> 
>   nr   | runtime
>   ------------
>   1000 | 0.125s
>   2000 | 0.454s
>   4000 | 1.811s
>   8000 | 7.091s
> 
> So for every doubling of the input size, the runtime quadruples. I guess
> it is iterating through some deleted tombstone entries, but I'm not sure
> why.
> 
> That's probably a more interesting and productive performance problem to
> work on than micro-optimizing out the last few microseconds of writing. :)
This is a known issue, I think [1].

The problem here is the tombstoning: when you delete all references, chances are that they are not truly gone but that every reference is just tombstoned. The problem with this is that reading refs may now take signifciantly more time as we cannot just say "this stack is empty". Instead, we need to figure out that it is empty by processing all the tombstones, and that takes a lot of time.

I remember that I did some digging back then and improved the status quo quite significantly by optimizing `refs_verify_refname_available()`. I'm sure there are more opportunities for optimization here though -- I have a feeling that we for example exhaust the merged iterator until its end when searching for a specific refname, where we could easily abort once the observed tombstone name sorts lexicographically after the needle.

But eventually I decided to not care too much about this edge case, as it seems very specific to this artificial benchmark scenario. Which of course doesn't mean that it's not worth doing, I just had bigger fish to fry and didn't get around to it yet.

Patrick
[1]: <Z602dzQggtDdcgCX@tapette.crustytoothpaste.net>
Previous: Jeff KingNext: Jeff King
Message 27 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.