From: brian m. carlson Date: Wed, 08 Jul 2026 11:15:41 GMT Subject: Re: [PATCH 0/2] reftable: fix quadratic behavior when re-creating deleted refs Message-ID: In-Reply-To: On 2026-07-06 at 13:35:54, Kristofer Karlsson via GitGitGadget wrote: > This series fixes quadratic behavior in update-ref when many refs are > deleted (tombstoned) and then new refs are created with the reftable > backend. […] > The first patch adds tests for tombstone scenarios: a perf test (p1401) > exercising two patterns with 8000 refs, and a correctness test (t0610) > verifying that deleted-then-recreated refs are visible. > > The second patch is the pure optimization. Both p1401 tests go from ~14s to > ~0.2s with the fix. > > Note that auto-compaction typically merges tombstones before they accumulate > to this degree, so the quadratic behavior may not show up in every workflow. > But the fix ensures correct time complexity regardless of compaction state, > and the change is fairly contained. I had hit this before when doing some benchmarks for using reftable at $DAYJOB. We had discussed it on the list and decided that it was synthetic at the time, but I'm glad to see that this is being fixed now. I don't have comments on the patches themselves because I haven't spent enough time in the reftable code to be familiar with it, but I do definitely appreciate the performance improvement. -- brian m. carlson (they/them) Toronto, Ontario, CA