Re: [PATCH 0/2] reftable: fix quadratic behavior when re-creating deleted refs

["brian m. carlson" <sandals@crustytoothpaste.net>]

[-- Attachment #1: Type: text/plain, Size: 1301 bytes --]

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 325 bytes --]