Re: weird quadratic reftable behavior, was: Re: [PATCH 3/3] t5551: pack refs after creating many tags
- From
Kristofer Karlsson <krka@spotify.com>
- Date
- Jul 1, 2026, 09:04 UTC
- Message-ID
- <CAL71e4PfXA-ixKR6r7fu_7_QmdzK+rTRs29mOsUYKaq+_a5q5w@mail.gmail.com>
- In-Reply-To
- <20260701080014.GA3748390@coredump.intra.peff.net>
On Wed, 1 Jul 2026 at 10:00, Jeff King <peff@peff.net> wrote:
Show 8 quoted lines
> 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.
Hi, sorry for jumping in -- I found this interesting and started poking at the code. I think both halves may share the same root cause.
The merged iterator's suppress_deletions flag filters out tombstones internally, which means higher-level code with prefix or refname bounds never gets a chance to stop iteration early. By letting tombstones pass through and filtering them one layer up in the reftable backend, the existing bounds checks can kick in before we scan through all the tombstones.
So instead of doing full scans inside merged_iter_next_void() we can just delegate to merged_iter_next_entry() and instead add a loop to reftable_be_reflog_exists() that skips tombstones (but is amortized O(1)).
Now multiple call sites would need to add something like this to compensate for returning tombstones:
if (reftable_log_record_is_deletion(&iter->log))
continue;but it may be worth it if it reduces cost when there are many refs.
The key spot is reftable_ref_iterator_advance(), where the deletion skip goes right after the existing prefix check -- so a tombstone past the prefix stops iteration immediately instead of being silently consumed. The same idea applies to reftable_backend_read_ref() and the log iteration paths.
I have a local branch with this attempted fix. Rerunning the benchmark:
Before:
nr=1000 0.306s
nr=2000 0.945s
nr=4000 3.816s
nr=8000 14.93s After:
nr=1000 0.020s
nr=2000 0.044s
nr=4000 0.071s
nr=8000 0.145s
nr=16000 0.258s
nr=32000 0.591sI can send a proper patch if needed/wanted, but I might have missed something silly here.
Thanks, Kristofer