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

[Jeff King <peff@peff.net>]

On Wed, Jul 01, 2026 at 08:17:45AM +0200, Patrick Steinhardt wrote:

> 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.

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.

> 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.

Yeah, that's fair. I dug a bit further in case there was anything useful
to write up, but I don't have much to add beyond what's here and in the
thread you linked. We can let it live on in the archive for now.

-Peff