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

[Patrick Steinhardt <ps@pks.im>]

On Tue, Jun 30, 2026 at 07:58:50PM -0400, Jeff King wrote:
> 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>