Re: [PATCH v2 17/18] commit-reach: make can_all_from_reach... linear

2018-09-12 Thread Derrick Stolee
On 9/12/2018 12:29 AM, Jeff King wrote: On Wed, Sep 12, 2018 at 12:14:25AM -0400, Jeff King wrote: + ALLOC_ARRAY(list, from->nr); for (i = 0; i < from->nr; i++) { - struct object *from_one = from->objects[i].item; + list[i] = (struct commit

Re: [PATCH v2 17/18] commit-reach: make can_all_from_reach... linear

2018-09-11 Thread Jeff King
On Wed, Sep 12, 2018 at 12:14:25AM -0400, Jeff King wrote: > > + ALLOC_ARRAY(list, from->nr); > > for (i = 0; i < from->nr; i++) { > > - struct object *from_one = from->objects[i].item; > > + list[i] = (struct commit *)from->objects[i].item; > > Some of the objects in

Re: [PATCH v2 17/18] commit-reach: make can_all_from_reach... linear

2018-09-11 Thread Jeff King
On Fri, Jul 20, 2018 at 04:33:28PM +, Derrick Stolee wrote: > The can_all_from_reach_with_flags() algorithm is currently quadratic in > the worst case, because it calls the reachable() method for every 'from' > without tracking which commits have already been walked or which can > already

Re: [PATCH v2 17/18] commit-reach: make can_all_from_reach... linear

2018-08-01 Thread Derrick Stolee
On 7/23/2018 4:41 PM, Jonathan Tan wrote: + if (parse_commit(list[i]) || + list[i]->generation < min_generation) Here... + if (parse_commit(parent->item) || + parent->item->date

Re: [PATCH v2 17/18] commit-reach: make can_all_from_reach... linear

2018-07-23 Thread Jonathan Tan
> + if (parse_commit(list[i]) || > + list[i]->generation < min_generation) Here... > + if (parse_commit(parent->item) || > + parent->item->date < > min_commit_date || > +

[PATCH v2 17/18] commit-reach: make can_all_from_reach... linear

2018-07-20 Thread Derrick Stolee
The can_all_from_reach_with_flags() algorithm is currently quadratic in the worst case, because it calls the reachable() method for every 'from' without tracking which commits have already been walked or which can already reach a commit in 'to'. Rewrite the algorithm to walk each commit a