]> git.ipfire.org Git - thirdparty/git.git/commit
commit-reach: early exit paint_down_to_common for single merge-base
authorKristofer Karlsson <krka@spotify.com>
Mon, 11 May 2026 12:59:12 +0000 (12:59 +0000)
committerJunio C Hamano <gitster@pobox.com>
Tue, 12 May 2026 00:33:43 +0000 (09:33 +0900)
commit93e5b1680e30650ceca889a56429a055f17033bd
treec060586821450b8c82e3215d02cea1483626bb21
parent53f9561055e8377a18a2430262857a3650c73dab
commit-reach: early exit paint_down_to_common for single merge-base

Commits not in the commit-graph get GENERATION_NUMBER_INFINITY and
sort to the top of the priority queue.  After those, commits with
finite generation numbers are popped in non-increasing order.
When MERGE_BASE_FIND_ALL is not set the first doubly-painted commit
with a finite generation is therefore a best merge-base: no commit
still in the queue can be a descendant of it.  Skip the expensive
STALE drain in this case.

Add MERGE_BASE_FIND_ALL to the merge_base_flags enum.  Callers that
need every merge-base (repo_get_merge_bases_many, repo_get_merge_bases,
repo_in_merge_bases_many, remove_redundant_no_gen) pass the flag to
preserve existing behavior.  git merge-base (without --all) passes 0,
triggering the early exit.

On a 2.2M-commit merge-heavy monorepo with commit-graph:

  HEAD vs ~500:   5,229ms -> 24ms
  HEAD vs ~1000:  4,214ms -> 39ms
  HEAD vs ~5000:  3,799ms -> 46ms
  HEAD vs ~10000: 3,827ms -> 61ms

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
builtin/merge-base.c
commit-reach.c
commit-reach.h
t/t6600-test-reach.sh