From: Toon Claes <toon@iotcl.com>
Date: Thu, 10 Apr 2025 08:57:29 GMT
Subject: Re: [PATCH v2 2/2] bundle: fix non-linear performance scaling with refs
Message-ID: <871pu0fl6u.fsf@iotcl.com>
In-Reply-To: <20250408-488-generating-bundles-with-many-references-has-non-linear-performance-v2-2-0802fc36a23d@gmail.com>

Karthik Nayak <karthik.188@gmail.com> 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