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:

quoted

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]: [ref]