Toon Claes <toon@xxxxxxxxx> writes: > Karthik Nayak <karthik.188@xxxxxxxxx> writes: > >> The 'git bundle create' command has non-linear performance with the >> number of refs in the repository. Benchmarking the command shows that >> a large portion of the time (~75%) is spent in the >> `object_array_remove_duplicates()` function. >> >> The `object_array_remove_duplicates()` function was added in >> b2a6d1c686 (bundle: allow the same ref to be given more than once, >> 2009-01-17) to skip duplicate refs provided by the user from being >> written to the bundle. Since this is an O(N^2) algorithm, in repos with >> large number of references, this can take up a large amount of time. >> >> Let's instead use a 'strset' to skip duplicates inside >> `write_bundle_refs()`. This improves the performance by around 6 times >> when tested against in repository with 100000 refs: >> >> Benchmark 1: bundle (refcount = 100000, revision = master) >> Time (mean ± σ): 14.653 s ± 0.203 s [User: 13.940 s, System: 0.762 s] >> Range (min … max): 14.237 s … 14.920 s 10 runs >> >> Benchmark 2: bundle (refcount = 100000, revision = HEAD) >> Time (mean ± σ): 2.394 s ± 0.023 s [User: 1.684 s, System: 0.798 s] >> Range (min … max): 2.364 s … 2.425 s 10 runs >> >> Summary >> bundle (refcount = 100000, revision = HEAD) ran >> 6.12 ± 0.10 times faster than bundle (refcount = 100000, revision = master) > > I've done some benchmarking with some "real life" repositories, which > only have a couple of thousand refs and there the difference > (expectedly) barely noticable. Which is good to know there also isn't > any regression. > > This version looks good to me, I approve. > > -- > Toon Thanks Toon. That is good news. That is also what the earlier benchmarks showed. For smaller repositories the difference becomes inconsequential, but for large repos, this can take significant amount of time.
Attachment:
signature.asc
Description: PGP signature
