Re: [PATCH 06/14] refs: stop re-verifying common prefixes for availability

[Patrick Steinhardt <ps@pks.im>]

On Tue, Feb 18, 2025 at 08:12:05AM -0800, Karthik Nayak wrote:
> Patrick Steinhardt <ps@pks.im> writes:
> 
> > One of the checks done by `refs_verify_refnames_available()` is whether
> > any of the prefixes of a reference already exists. For example, given a
> > reference "refs/heads/main", we'd check whether "refs/heads" or "refs"
> > already exist, and if so we'd abort the transaction.
> >
> > When updating multiple references at once, this check is performed for
> > each of the references individually. Consequently, because references
> > tend to have common prefixes like "refs/heads/" or refs/tags/", we
> > evaluate the availability of these prefixes repeatedly. Naturally this
> > is a waste of compute, as the availability of those prefixes should in
> > general not change in the middle of a transaction. And if it would,
> > backends would notice at a later point in time.
> >
> > Optimize this pattern by storing prefixes in a `strset` so that we can
> > trivially track those prefixes that we have already checked. This leads
> > to a significant speedup when creating many references that all share a
> > common prefix:
> >
> >     Benchmark 1: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD~)
> >       Time (mean ± σ):      63.1 ms ±   1.8 ms    [User: 41.0 ms, System: 21.6 ms]
> >       Range (min … max):    60.6 ms …  69.5 ms    38 runs
> >
> >     Benchmark 2: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD)
> >       Time (mean ± σ):      40.0 ms ±   1.3 ms    [User: 29.3 ms, System: 10.3 ms]
> >       Range (min … max):    38.1 ms …  47.3 ms    61 runs
> >
> >     Summary
> >       update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) ran
> >         1.58 ± 0.07 times faster than update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD~)
> >
> > Note that the same speedup cannot be observed for the "files" backend
> > because it still performs availability check per reference.
> >
> 
> In the previous commit, you started using the new function in the
> reftable backend, can we not make a similar change to the files backend?

It's quite a bit more intricate in the "files" backend because the
creation of the lockfiles and calls to `refs_verify_refname_available()`
are intertwined with one another:

  - `lock_raw_ref()` verifies availability when it hits either EEXISTS
    or EISDIR to generate error messages. This is probably nothing we
    have to care about too much, as these are irrelevant in the good
    path.

  - `lock_raw_ref()` also verifies availability though in the case where
    it _could_ create the lockfile to check whether it is conflicting
    with any packed refs. This one could potentially be batched. It's a
    curious thing in the first place as we do not have the packed refs
    locked at this point in time, so this check might even be racy.

  - `lock_ref_oid_basic()` also checks availability with packed refs, so
    this is another case where we might batch the checks. But the
    function is only used when copying/renaming references or when
    expiring reflogs, so it won't be called for many refs.

  - We call it in `refs_refname_ref_available()`, which is executed when
    copying/renaming references. Uninteresting due to the same reason as
    the previous entry.

  - We call it in `files_transaction_finish_initial()`. This one should
    be rather trivial to batch. Again though, no locking with packed
    refs, so the checks are racy.

So... it's a bit more complicated here compared to the reftable backend,
and I didn't feel like opening a can of worms with the potentially-racy
checks with the packed backend.

Anyway, I think we still can and probably should use the new mechanism
in two cases:

  - During normal transactions to batch the availability checks with the
    packed backend. I will have to ignore the issue of a potential race,
    but other than that the change is straight forward and the result is
    a slight speedup:

      Benchmark 1: update-ref: create many refs (preexisting = 100000, new = 10000, revision = HEAD~)
         Time (mean ± σ):     393.4 ms ±   4.0 ms    [User: 64.1 ms, System: 327.5 ms]
         Range (min … max):   387.8 ms … 398.7 ms    10 runs

       Benchmark 2: update-ref: create many refs (preexisting = 100000, new = 10000, revision = HEAD)
         Time (mean ± σ):     373.3 ms ±   3.4 ms    [User: 48.8 ms, System: 322.7 ms]
         Range (min … max):   368.7 ms … 378.6 ms    10 runs

       Summary
         update-ref: create many refs (preexisting = 100000, new = 10000, revision = HEAD) ran
           1.05 ± 0.01 times faster than update-ref: create many refs (preexisting = 100000, new = 10000, revision = HEAD~)

  - During the initial transaction. Here the change is even more trivial
    and we can also fix the race as we eventually lock the packed-refs
    file anyway. This leads to a noticeable speedup when migrating from
    the reftable backend to the files backend:

      Benchmark 1: migrate reftable:files (refcount = 1000000, revision = HEAD~)
        Time (mean ± σ):     980.6 ms ±  10.9 ms    [User: 801.8 ms, System: 172.4 ms]
        Range (min … max):   964.7 ms … 995.3 ms    10 runs

      Benchmark 2: migrate reftable:files (refcount = 1000000, revision = HEAD)
        Time (mean ± σ):     739.7 ms ±   6.6 ms    [User: 551.9 ms, System: 181.9 ms]
        Range (min … max):   727.9 ms … 747.2 ms    10 runs

      Summary
        migrate reftable:files (refcount = 1000000, revision = HEAD) ran
          1.33 ± 0.02 times faster than migrate reftable:files (refcount = 1000000, revision = HEAD~)

I'll include these changes in the next version, thanks for questioning
why I skipped over the "files" backend.

Patrick