Re: [PATCH] show-branch: use prio_queue

From: René Scharfe <l.s.r@web.de>
Date: Dec 29, 2025, 20:01 UTC
Message-ID: <c30ebbab-e303-4301-971b-7ff619389597@web.de>
In-Reply-To: <01d09293-4b60-4a47-9350-73b1ff796c9a@gmail.com>

On 12/29/25 7:09 PM, Derrick Stolee wrote:

Show 27 quoted lines

> On 12/26/2025 2:44 AM, René Scharfe wrote:
> 
>> That number is not limited, though, and in pathological cases like the
>> one in p6010 we see a sizable improvement:
>>
>> Test                      v2.52.0           HEAD
>> ------------------------------------------------------------------
>> 6010.4: git show-branch   2.19(2.19+0.00)   0.03(0.02+0.00) -98.6%
> 
> I love to see improvements like this, even if the construction is
> unlikely to exist in reality. I do think it's likely to be valuable
> for some large repos with many parallel branches.
> 
> Indeed, I tested this patch against a monorepo with lots of merges
> with hyperfine, getting this output:
> 
> Benchmark 1: old
>   Time (mean ± σ):      3.303 s ±  0.146 s    [User: 0.058 s, System: 0.069 s]
>   Range (min … max):    3.162 s …  3.631 s    10 runs
> 
> Benchmark 2: new
>   Time (mean ± σ):     141.7 ms ±   3.2 ms    [User: 30.5 ms, System: 93.1 ms]
>   Range (min … max):   137.5 ms … 149.4 ms    19 runs
> 
> Summary
>   new ran
>    23.31 ± 1.15 times faster than old

Woah, the perf test gets a speedup by factor 46 in a repository purpose-built to highlight this very difference, and here you get half of that in the wild! Interesting to see that there are real commit histories out there with such a taxing topology.

And thanks for your review!

René