]> git.ipfire.org Git - thirdparty/git.git/commit
show-branch: use prio_queue
authorRené Scharfe <l.s.r@web.de>
Fri, 26 Dec 2025 07:44:28 +0000 (08:44 +0100)
committerJunio C Hamano <gitster@pobox.com>
Sun, 28 Dec 2025 05:01:23 +0000 (14:01 +0900)
commitabf05d856f50fbd8f0390b31e7187d78930dbaf5
treedf5167498d385c2b5419febf55334537deb36ae4
parent9a2fb147f2c61d0cab52c883e7e26f5b7948e3ed
show-branch: use prio_queue

Building a list using commit_list_insert_by_date() has quadratic worst
case complexity.  Avoid it by using prio_queue.

Use prio_queue_peek()+prio_queue_replace() instead of prio_queue_get()+
prio_queue_put() if possible, as the former only rebalance the
prio_queue heap once instead of twice.

In sane repositories this won't make much of a difference because the
number of items in the list or queue won't be very high:

Benchmark 1: ./git_v2.52.0 show-branch origin/main origin/next origin/seen origin/todo
  Time (mean ± σ):     538.2 ms ±   0.8 ms    [User: 527.6 ms, System: 9.6 ms]
  Range (min … max):   537.0 ms … 539.2 ms    10 runs

Benchmark 2: ./git show-branch origin/main origin/next origin/seen origin/todo
  Time (mean ± σ):     530.6 ms ±   0.4 ms    [User: 519.8 ms, System: 9.8 ms]
  Range (min … max):   530.1 ms … 531.3 ms    10 runs

Summary
  ./git show-branch origin/main origin/next origin/seen origin/todo ran
    1.01 ± 0.00 times faster than ./git_v2.52.0 show-branch origin/main origin/next origin/seen origin/todo

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%

Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
builtin/show-branch.c
t/perf/p6010-merge-base.sh