On Wed, Feb 19, 2025 at 02:23:27PM +0100, Patrick Steinhardt wrote: > Hi, > > this patch series has been inspired by brian's report that the reftable > backend is significantly slower when writing many references compared to > the files backend. As explained in that thread, the underlying issue is > the design of tombstone references: when we first delete all references > in a repository and then recreate them, we still have all the tombstones > and thus we need to churn through all of them to figure out that they > have been deleted in the first place. The files backend does not have > this issue. > > I consider the benchmark itself to be kind of broken, as it stems from > us deleting all refs and then recreating them. And if you pack refs in > between then the "reftable" backend outperforms the "files" backend. > > But there are a couple of opportunities here anyway. While we cannot > make the underlying issue of tombstones being less efficient go away, > this has prompted me to have a deeper look at where we spend all the > time. There are three ideas in this series: > > - git-update-ref(1) performs ambiguity checks for any full-size object > ID, which triggers a lot of reads. This is somewhat pointless though > given that the manpage explicitly points out that the command is > about object IDs, even though it does know to parse refs. But being > part of plumbing, emitting the warning here does not make a ton of > sense, and favoring object IDs over references in these cases is the > obvious thing to do anyway. > > - For each ref "refs/heads/bar", we need to verify that neither > "refs/heads" nor "refs" exists. This was repeated for every refname, > but because most refnames use common prefixes this made us re-check > a lot of prefixes. This is addressed by using a `strset` of already > checked prefixes. > > - For each ref "refs/heads/bar", we need to verify that no ref > "refs/heads/bar/*" exists. We always created a new ref iterator for > this check, which requires us to discard all internal state and then > recreate it. The reftable library has already been refactored though > to have reseekable iterators, so we backfill this functionality to > all the other iterators and then reuse the iterator. > > With the (somewhat broken) benchmark we see a small speedup with the > "files" backend: > > Benchmark 1: update-ref (refformat = files, revision = master) > Time (mean ± σ): 234.4 ms ± 1.9 ms [User: 75.6 ms, System: 157.2 ms] > Range (min … max): 232.2 ms … 236.9 ms 10 runs > > Benchmark 2: update-ref (refformat = files, revision = HEAD) > Time (mean ± σ): 184.2 ms ± 2.0 ms [User: 62.8 ms, System: 119.9 ms] > Range (min … max): 181.1 ms … 187.0 ms 10 runs > > Summary > update-ref (refformat = files, revision = HEAD) ran > 1.27 ± 0.02 times faster than update-ref (refformat = files, revision = master) > > And a huge speedup with the "reftable" backend: > > Benchmark 1: update-ref (refformat = reftable, revision = master) > Time (mean ± σ): 16.852 s ± 0.061 s [User: 16.754 s, System: 0.059 s] > Range (min … max): 16.785 s … 16.982 s 10 runs > > Benchmark 2: update-ref (refformat = reftable, revision = HEAD) > Time (mean ± σ): 2.230 s ± 0.009 s [User: 2.192 s, System: 0.029 s] > Range (min … max): 2.215 s … 2.244 s 10 runs > > Summary > update-ref (refformat = reftable, revision = HEAD) ran > 7.56 ± 0.04 times faster than update-ref (refformat = reftable, revision = master) > > We're still not up to speed with the "files" backend, but considerably > better. Given that this is an extreme edge case and not reflective of > the general case I'm okay with this result for now. > > But more importantly, this refactoring also has a positive effect when > updating references in a repository with preexisting refs, which I > consider to be the more realistic scenario. The following benchmark > creates 10k refs with 100k preexisting refs. > > With the "files" backend we see a modest improvement: > > Benchmark 1: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = master) > Time (mean ± σ): 478.4 ms ± 11.9 ms [User: 96.7 ms, System: 379.6 ms] > Range (min … max): 465.4 ms … 496.6 ms 10 runs > > Benchmark 2: update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD) > Time (mean ± σ): 388.5 ms ± 10.3 ms [User: 52.0 ms, System: 333.8 ms] > Range (min … max): 376.5 ms … 403.1 ms 10 runs > > Summary > update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = HEAD) ran > 1.23 ± 0.04 times faster than update-ref: create many refs (refformat = files, preexisting = 100000, new = 10000, revision = master) > > But with the "reftable" backend we see an almost 5x improvement, where > it's now ~15x faster than the "files" backend: > > Benchmark 1: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = master) > Time (mean ± σ): 153.9 ms ± 2.0 ms [User: 96.5 ms, System: 56.6 ms] > Range (min … max): 150.5 ms … 158.4 ms 18 runs > > Benchmark 2: update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) > Time (mean ± σ): 32.2 ms ± 1.2 ms [User: 27.6 ms, System: 4.3 ms] > Range (min … max): 29.8 ms … 38.6 ms 71 runs > > Summary > update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = HEAD) ran > 4.78 ± 0.19 times faster than update-ref: create many refs (refformat = reftable, preexisting = 100000, new = 10000, revision = master) > This is an amazing improvement. > The series is structured as follows: > > - Patches 1 to 4 implement the logic to skip ambiguity checks in > git-update-ref(1). > > - Patch 5 to 8 introduce batched checks. > > - Patch 9 deduplicates the ref prefix checks. > > - Patch 10 to 16 implement the infrastructure to reseek iterators. > > - Patch 17 starts to reuse iterators for nested ref checks. > > Changes in v2: > - Point out why we also have to touch up the `dir_iterator`. > - Fix up the comment explaining `ITER_DONE`. > - Fix up comments that show usage patterns of the ref and dir iterator > interfaces. > - Start batching availability checks in the "files" backend, as well. > - Improve the commit message that drops the ambiguity check so that we > also point to 25fba78d36b (cat-file: disable object/refname > ambiguity check for batch mode, 2013-07-12). > - Link to v1: https://lore.kernel.org/r/20250217-pks-update-ref-optimization-v1-0-a2b6d87a24af@xxxxxx > > Thanks! > > Patrick > > [1]: <Z602dzQggtDdcgCX@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> I have reviewed [PATCH v2 09/16] - [PATCH v2 16/16], leave some comments. For other patches, I don't have energy to review. So maybe others could help. Thanks, Jialuo
