From: Derrick Stolee <dstolee@microsoft.com>
Date: Tue, 1 May 2018 12:47:19 +0000 (+0000)
Subject: commit: add short-circuit to paint_down_to_common()
X-Git-Tag: v2.19.0-rc0~192^2~4
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/d7c1ec3efd0092ee665085cba4e8a2bcef95143b?ds=inline;hp=d7c1ec3efd0092ee665085cba4e8a2bcef95143b

commit: add short-circuit to paint_down_to_common()

When running 'git branch --contains', the in_merge_bases_many()
method calls paint_down_to_common() to discover if a specific
commit is reachable from a set of branches. Commits with lower
generation number are not needed to correctly answer the
containment query of in_merge_bases_many().

Add a new parameter, min_generation, to paint_down_to_common() that
prevents walking commits with generation number strictly less than
min_generation. If 0 is given, then there is no functional change.

For in_merge_bases_many(), we can pass commit->generation as the
cutoff, and this saves time during 'git branch --contains' queries
that would otherwise walk "around" the commit we are inspecting.

For a copy of the Linux repository, where HEAD is checked out at
v4.13~100, we get the following performance improvement for
'git branch --contains' over the previous commit:

Before: 0.21s
After:  0.13s
Rel %: -38%

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---