From abf05d856f50fbd8f0390b31e7187d78930dbaf5 Mon Sep 17 00:00:00 2001 From: René Scharfe Date: Fri, 26 Dec 2025 08:44:28 +0100 Subject: show-branch: use prio_queue MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 Signed-off-by: Junio C Hamano --- t/perf/p6010-merge-base.sh | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 't') diff --git a/t/perf/p6010-merge-base.sh b/t/perf/p6010-merge-base.sh index 54f52fa23e..08212dd037 100755 --- a/t/perf/p6010-merge-base.sh +++ b/t/perf/p6010-merge-base.sh @@ -83,9 +83,9 @@ build_history2 () { test_expect_success 'setup' ' max_level=15 && build_history $max_level | git fast-import --export-marks=marks && - git tag one && + git branch one && build_history2 $max_level | git fast-import --import-marks=marks --force && - git tag two && + git branch two && git gc && git log --format=%H --no-merges >expect ' @@ -98,4 +98,8 @@ test_expect_success 'verify result' ' test_cmp expect actual ' +test_perf 'git show-branch' ' + git show-branch one two +' + test_done -- cgit v1.3