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

2018-04-04 Thread Jeff King
On Wed, Apr 04, 2018 at 02:53:45PM -0400, Derrick Stolee wrote: > > 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

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

2018-04-04 Thread Derrick Stolee
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,

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

2018-04-04 Thread Jeff King
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 * > >

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

2018-04-04 Thread Brandon Williams
On 04/04, Derrick Stolee wrote: > On 4/4/2018 11:45 AM, Derrick Stolee wrote: > > The containment algorithm for 'git branch --contains' is different > > from that for 'git tag --contains' in that it uses is_descendant_of() > > instead of contains_tag_algo(). The expensive portion of the branch > >

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

2018-04-04 Thread Derrick Stolee
On 4/4/2018 11:45 AM, Derrick Stolee wrote: The containment algorithm for 'git branch --contains' is different from that for 'git tag --contains' in that it uses is_descendant_of() instead of contains_tag_algo(). The expensive portion of the branch algorithm is computing merge bases. When a

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

2018-04-04 Thread Derrick Stolee
The containment algorithm for 'git branch --contains' is different from that for 'git tag --contains' in that it uses is_descendant_of() instead of contains_tag_algo(). The expensive portion of the branch algorithm is computing merge bases. When a commit-graph file exists with generation numbers