From: Derrick Stolee Date: Fri, 19 Oct 2018 12:32:19 GMT Subject: Re: [PATCH 1/1] commit-reach: fix first-parent heuristic Message-ID: In-Reply-To: On 10/19/2018 1:24 AM, Junio C Hamano wrote: > "Derrick Stolee via GitGitGadget" 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'. Thanks, -Stolee