Re: [PATCH 0/2] reftable: fix quadratic behavior when re-creating deleted refs
- From
brian m. carlson <sandals@crustytoothpaste.net>
- Date
- Jul 8, 2026, 11:15 UTC
- Message-ID
- <ak4xXTHJwhNzfDLF@fruit.crustytoothpaste.net>
- In-Reply-To
- <pull.2166.git.1783344957.gitgitgadget@gmail.com>
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.
[…]
Show 11 quoted lines
> 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