Re: [PATCH 1/1] commit-reach: fix first-parent heuristic

[Junio C Hamano <gitster@pobox.com>]

Derrick Stolee <stolee@gmail.com> writes:

> On 10/19/2018 1:24 AM, Junio C Hamano wrote:
>> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
>>
>>> We can also re-run the performance tests from commit 4fbcca4e
>>> "commit-reach: make can_all_from_reach... linear".
>>>
>>> Performance was measured on the Linux repository using
>>> 'test-tool reach can_all_from_reach'. The input included rows seeded by
>>> tag values. The "small" case included X-rows as v4.[0-9]* and Y-rows as
>>> v3.[0-9]*. This mimics a (very large) fetch that says "I have all major
>>> v3 releases and want all major v4 releases." The "large" case included
>>> X-rows as "v4.*" and Y-rows as "v3.*". This adds all release-candidate
>>> tags to the set, which does not greatly increase the number of objects
>>> that are considered, but does increase the number of 'from' commits,
>>> demonstrating the quadratic nature of the previous code.
>> These micro-benchmarks are interesting, but we should also remember
>> to describe the impact of the bug being fixed in the larger picture.
>> What end-user visible operations are affected?  Computing merge-base?
>> Finding if a push fast-forwards?  Something else?
>
> Sorry about that. Here is a description that could be inserted into
> the commit message:
>
> The can_all_from_reach() method synthesizes the logic for one
> iteration of can_all_from_reach_with_flags() which is used by the
> server during fetch negotiation to determine if more haves/wants are
> needed. The logic is also used by is_descendant_of() which is used to
> check if a force-push is required and in 'git branch --contains'.

I am afraid that it is still not end-user serving enough.  The level
of "larger picture" I had in mind was those that would appear as an
entry in the release notes, e.g. (this is for illustration purposes
only; I do not claim its actual contents is correct).

	We started using commit generation numbers in various
	reachability computations, but due to a bug, negitiation
	between the "git fetch" and the server started to require
	30% more roundtrips than necessary, and it has become less
	efficient to see if a commit is a descendant of another
	commit in certain cases, which has been corrected in this
	release.

Thanks.