commit: use generation numbers for in_merge_bases()
commitf9b8908b85247ef60001a683c281af0080e9ee77
authorDerrick Stolee <dstolee@microsoft.com>
Tue, 1 May 2018 12:47:17 +0000 (1 12:47 +0000)
committerJunio C Hamano <gitster@pobox.com>
Tue, 22 May 2018 03:36:34 +0000 (22 12:36 +0900)
tree2c686d90564dfc810cff7c47e0b895a6e562d1ef
parent819807b33f820dc17d96f043747daf18c5e38516
commit: use generation numbers for in_merge_bases()

The containment algorithm for 'git branch --contains' is different
from that for 'git tag --contains' in that it uses is_descendant_of()
instead of contains_tag_algo(). The expensive portion of the branch
algorithm is computing merge bases.

When a commit-graph file exists with generation numbers computed,
we can avoid this merge-base calculation when the target commit has
a larger generation number than the initial commits.

Performance tests were run on a copy of the Linux repository where
HEAD is contained in v4.13 but no earlier tag. Also, all tags were
copied to branches and 'git branch --contains' was tested:

Before: 60.0s
After:   0.4s
Rel %: -99.3%

Reported-by: Jeff King <peff@peff.net>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit.c