]> git.ipfire.org Git - thirdparty/git.git/commit
describe: use prio_queue
authorRené Scharfe <l.s.r@web.de>
Sun, 3 Aug 2025 11:38:29 +0000 (13:38 +0200)
committerJunio C Hamano <gitster@pobox.com>
Sun, 3 Aug 2025 16:13:27 +0000 (09:13 -0700)
commit66e2adb8f6fe97bb480d96205fb3473b8c1fe4df
treef72dd0edd8a8ea4e0e7d7717cd80984df1f99c9d
parent866e6a391f466baeeb98bc585845ea638322c04b
describe: use prio_queue

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>
builtin/describe.c