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
