René Scharfe <l.s.r@xxxxxx> writes:
> pop_most_recent_commit() calls commit_list_insert_by_date(), which and
> is itself called in a loop, which can lead to quadratic complexity.
> Replace the commit_list with a prio_queue to ensure logarithmic worst
> case complexity and convert all three users.
>
> Add a performance test that exercises one of them using a pathological
> history that consists of 50% merges and 50% root commits to demonstrate
> the speedup:
>
> Test v2.50.1 HEAD
> ----------------------------------------------------------------------
> 1501.2: rev-parse ':/65535' 2.48(2.47+0.00) 0.20(0.19+0.00) -91.9%
>
> Alas, sane histories don't benefit from the conversion much, and
> traversing Git's own history takes a 1% performance hit on my machine:
;-)
> $ hyperfine -w3 -L git ./git_2.50.1,./git '{git} rev-parse :/^Initial.revision'
> Benchmark 1: ./git_2.50.1 rev-parse :/^Initial.revision
> Time (mean ± σ): 1.071 s ± 0.004 s [User: 1.052 s, System: 0.017 s]
> Range (min … max): 1.067 s … 1.078 s 10 runs
>
> Benchmark 2: ./git rev-parse :/^Initial.revision
> Time (mean ± σ): 1.079 s ± 0.003 s [User: 1.060 s, System: 0.017 s]
> Range (min … max): 1.074 s … 1.083 s 10 runs
>
> Summary
> ./git_2.50.1 rev-parse :/^Initial.revision ran
> 1.01 ± 0.00 times faster than ./git rev-parse :/^Initial.revision
