From: Derrick Stolee <stolee@gmail.com>
Date: Wed, 04 Apr 2018 15:48:42 GMT
Subject: Re: [PATCH 8/6] commit: use generation numbers for in_merge_bases()
Message-ID: <14e4e1d3-5c77-dc7c-10d5-e9406b992f0e@gmail.com>
In-Reply-To: <20180404154554.140716-2-dstolee@microsoft.com>

On 4/4/2018 11:45 AM, Derrick Stolee wrote:
> 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 target 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>
> ---
>   commit.c | 9 ++++++++-
>   1 file changed, 8 insertions(+), 1 deletion(-)
>
> diff --git a/commit.c b/commit.c
> index 858f4fdbc9..2566cba79f 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -1059,12 +1059,19 @@ int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit *
>   {
>   	struct commit_list *bases;
>   	int ret = 0, i;
> +	uint32_t min_generation = GENERATION_NUMBER_UNDEF;
>   
>   	if (parse_commit(commit))
>   		return ret;
> -	for (i = 0; i < nr_reference; i++)
> +	for (i = 0; i < nr_reference; i++) {
>   		if (parse_commit(reference[i]))
>   			return ret;
> +		if (min_generation > reference[i]->generation)
> +			min_generation = reference[i]->generation;
> +	}
> +
> +	if (commit->generation > min_generation)
> +		return 0;
>   
>   	bases = paint_down_to_common(commit, nr_reference, reference);
>   	if (commit->object.flags & PARENT2)

This patch may suffice to speed up 'git branch --contains' instead of 
needing to always use the 'git tag --contains' algorithm as considered 
in [1].

Thanks,
-Stolee

[1] 
https://public-inbox.org/git/20180303051516.GE27689@sigill.intra.peff.net/
     Re: [PATCH 0/4] Speed up git tag --contains