From: Derrick Stolee <stolee@gmail.com>
Date: Thu, 18 Jun 2020 01:37:31 GMT
Subject: Re: [PATCH 0/2] Accelerate "git merge-base --is-ancestor"
Message-ID: <9bdbd5f7-7c12-e71a-4e1c-747d247abdc9@gmail.com>
In-Reply-To: <xmqqzh91s9mn.fsf@gitster.c.googlers.com>

On 6/17/2020 4:46 PM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> It was recently [1] reported (and not-so-recently [2] reported) that "git
>> merge-base --is-ancestor" can be pretty slow. In fact, it is regularly
>> slower than "git branch --contains" or "git tag --contains", which are
>> answering a "harder" query.
>>
>> [1] https://lore.kernel.org/git/20200607195347.GA8232@szeder.dev/
>>
>> [2] https://lore.kernel.org/git/87608bawoa.fsf@evledraar.gmail.com/
>>
>> The root cause is that the in_merge_base() implementation is skipping the
>> fast can_all_from_reach() implementation and using paint_down_to_common()
>> instead. Note that these are equivalent: a commit A is in the set of
>> merge-bases between A and B if and only if B can reach A.
> 
> OK, so in short, this codepath was not taking advantage of the
> generation numbers and that was the difference?

Correct. We now use generation numbers more often, when
available. All callers of in_merge_bases() will become
faster, which includes callers in these builtins:

	- branch
	- fetch
	- log
	- merge-base
	- receive-pack

and these libgit files:

	- fast-import.c
	- http-push.c
	- merge-recursive.c (several!)
	- pack-bitmap-write.c

Thanks,
-Stolee