weird quadratic reftable behavior, was: Re: [PATCH 3/3] t5551: pack refs after creating many tags
- From
Jeff King <peff@peff.net>
- Date
- Jun 30, 2026, 23:58 UTC
- Message-ID
- <20260630235850.GB3759976@coredump.intra.peff.net>
- In-Reply-To
- <20260630234702.GA3759976@coredump.intra.peff.net>
On Tue, Jun 30, 2026 at 07:47:02PM -0400, Jeff King wrote:
Show 9 quoted lines
> 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. :)
-Peff