]> git.ipfire.org Git - thirdparty/git.git/commit
commit-reach: avoid commit_list_insert_by_date()
authorRené Scharfe <l.s.r@web.de>
Fri, 24 Oct 2025 16:47:10 +0000 (18:47 +0200)
committerJunio C Hamano <gitster@pobox.com>
Fri, 24 Oct 2025 17:13:17 +0000 (10:13 -0700)
commit134ec330d2945002d0ceb7de2ac6cd7ab0af762d
treedf8145a78d96e4eff0460dd674afaaed69b67834
parent81f86aacc4eb74cdb9c2c8082d36d2070c666045
commit-reach: avoid commit_list_insert_by_date()

Building a list using commit_list_insert_by_date() has quadratic worst
case complexity.  Avoid it by just appending in the loop and sorting at
the end.

The number of merge bases is usually small, so don't expect speedups in
normal repositories.  It has no limit, though.  The added perf test
shows a nice improvement when dealing with 16384 merge bases:

Test                     v2.51.1           HEAD
-----------------------------------------------------------------
6010.2: git merge-base   0.55(0.54+0.00)   0.03(0.02+0.00) -94.5%

Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit-reach.c
t/perf/p6010-merge-base.sh [new file with mode: 0755]