Re: [PATCH 8/6] commit: use generation numbers for in_merge_bases()

[Derrick Stolee <stolee@gmail.com>]

On 4/4/2018 2:24 PM, Jeff King wrote:
> On Wed, Apr 04, 2018 at 11:48:42AM -0400, Derrick Stolee wrote:
>
>>> 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].

I guess I want to specify: the only reason to NOT switch to the tags 
algorithm is because it _may_ hurt existing cases in certain data shapes...

> I'd have to do some timings, but I suspect we may want to switch to the
> "tag --contains" algorithm anyway. This still does N independent
> merge-base operations, one per ref. So with enough refs, you're still
> better off throwing it all into one big traversal.

...and I suppose your timings are to find out if there are data shapes 
where the branch algorithm is faster. Perhaps that is impossible now 
that we have the generation number cutoff for the tag algorithm.

Since the branch algorithm checks generation numbers before triggering 
pain_down_to_common(), we will do N independent merge-base calculations, 
where N is the number of branches with large enough generation numbers 
(which is why my test does so well: most are below the target generation 
number). This doesn't help at all if none of the refs are in the graph.

The other thing to do is add a minimum generation for the walk in 
paint_down_to_common() so even if commit->generation <= min_generation 
we still only walk down to commit->generation instead of all merge 
bases. This is something we could change in a later patch.

Patches 7 and 8 seem to me like simple changes with no downside UNLESS 
we are deciding instead to delete the code I'm changing.

Thanks,
-Stolee