describe: use prio_queue_replace()

Optimize the sequence get+put to peek+replace to avoid one unnecessary
heap rebalance.

Do that by tracking partial get operations in a prio_queue wrapper,
struct lazy_queue, and using wrapper functions that turn get into peek
and put into replace as needed.  This is simpler than tracking the
state explicitly in the calling code.

We get a nice speedup on top of the previous patch's conversion to
prio_queue:

Benchmark 1: ./git_2.50.1 describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):      1.559 s ±  0.002 s    [User: 1.493 s, System: 0.051 s]
  Range (min … max):    1.556 s …  1.563 s    10 runs

Benchmark 2: ./git_describe_pq describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):      1.204 s ±  0.001 s    [User: 1.138 s, System: 0.051 s]
  Range (min … max):    1.202 s …  1.205 s    10 runs

Benchmark 3: ./git describe $(git rev-list v2.41.0..v2.47.0)
  Time (mean ± σ):     850.9 ms ±   1.6 ms    [User: 786.6 ms, System: 49.8 ms]
  Range (min … max):   849.1 ms … 854.1 ms    10 runs

Summary
  ./git describe $(git rev-list v2.41.0..v2.47.0) ran
    1.41 ± 0.00 times faster than ./git_describe_pq describe $(git rev-list v2.41.0..v2.47.0)
    1.83 ± 0.00 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>

0 files changed, 0 insertions, 0 deletions