Replace the use a list-based priority queue whose order is maintained by
commit_list_insert_by_date() with a prio_queue. This avoids quadratic
worst-case complexity. And in the somewhat contrived example of
describing the 4751 commits from v2.41.0 to v2.47.0 in one go (to get a
sizable chunk of describe work with minimal ref loading overhead) it's
significantly faster:
Benchmark 1: ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 1.558 s ± 0.002 s [User: 1.492 s, System: 0.051 s]
Range (min … max): 1.557 s … 1.562 s 10 runs
Benchmark 2: ./git describe $(git rev-list v2.41.0..v2.47.0)
Time (mean ± σ): 1.209 s ± 0.006 s [User: 1.143 s, System: 0.051 s]
Range (min … max): 1.201 s … 1.219 s 10 runs
Summary
./git describe $(git rev-list v2.41.0..v2.47.0) ran
1.29 ± 0.01 times faster than ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)
Signed-off-by: René Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>