| Message ID | 20250217-pks-update-ref-optimization-v1-6-a2b6d87a24af@pks.im (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | refs: batch refname availability checks | expand |
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? > Signed-off-by: Patrick Steinhardt <ps@pks.im> > --- > refs.c | 12 ++++++++++++ > 1 file changed, 12 insertions(+) > > diff --git a/refs.c b/refs.c > index 5a9b0f2fa1e..eaf41421f50 100644 > --- a/refs.c > +++ b/refs.c > @@ -2476,6 +2476,7 @@ int refs_verify_refnames_available(struct ref_store *refs, > { > struct strbuf dirname = STRBUF_INIT; > struct strbuf referent = STRBUF_INIT; > + struct strset dirnames; > int ret = -1; > > /* > @@ -2485,6 +2486,8 @@ int refs_verify_refnames_available(struct ref_store *refs, > > assert(err); > > + strset_init(&dirnames); > + > for (size_t i = 0; i < refnames->nr; i++) { > const char *refname = refnames->items[i].string; > const char *extra_refname; > @@ -2514,6 +2517,14 @@ int refs_verify_refnames_available(struct ref_store *refs, > if (skip && string_list_has_string(skip, dirname.buf)) > continue; > > + /* > + * If we've already seen the directory we don't need to > + * process it again. Skip it to avoid checking checking > + * common prefixes like "refs/heads/" repeatedly. > + */ > + if (!strset_add(&dirnames, dirname.buf)) > + continue; > + This was simple and neat. Nice. > if (!initial_transaction && > !refs_read_raw_ref(refs, dirname.buf, &oid, &referent, > &type, &ignore_errno)) { > @@ -2574,6 +2585,7 @@ int refs_verify_refnames_available(struct ref_store *refs, > cleanup: > strbuf_release(&referent); > strbuf_release(&dirname); > + strset_clear(&dirnames); > return ret; > } > > > -- > 2.48.1.666.gff9fcf71b7.dirty
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
diff --git a/refs.c b/refs.c index 5a9b0f2fa1e..eaf41421f50 100644 --- a/refs.c +++ b/refs.c @@ -2476,6 +2476,7 @@ int refs_verify_refnames_available(struct ref_store *refs, { struct strbuf dirname = STRBUF_INIT; struct strbuf referent = STRBUF_INIT; + struct strset dirnames; int ret = -1; /* @@ -2485,6 +2486,8 @@ int refs_verify_refnames_available(struct ref_store *refs, assert(err); + strset_init(&dirnames); + for (size_t i = 0; i < refnames->nr; i++) { const char *refname = refnames->items[i].string; const char *extra_refname; @@ -2514,6 +2517,14 @@ int refs_verify_refnames_available(struct ref_store *refs, if (skip && string_list_has_string(skip, dirname.buf)) continue; + /* + * If we've already seen the directory we don't need to + * process it again. Skip it to avoid checking checking + * common prefixes like "refs/heads/" repeatedly. + */ + if (!strset_add(&dirnames, dirname.buf)) + continue; + if (!initial_transaction && !refs_read_raw_ref(refs, dirname.buf, &oid, &referent, &type, &ignore_errno)) { @@ -2574,6 +2585,7 @@ int refs_verify_refnames_available(struct ref_store *refs, cleanup: strbuf_release(&referent); strbuf_release(&dirname); + strset_clear(&dirnames); return ret; }
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. Signed-off-by: Patrick Steinhardt <ps@pks.im> --- refs.c | 12 ++++++++++++ 1 file changed, 12 insertions(+)