Re: [PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection

On Tue, Jan 28, 2014 at 01:55:09PM -0800, Junio C Hamano wrote: > Kirill Smelkov writes: > > > diff --git a/combine-diff.c b/combine-diff.c > > index 3b92c448..98c2562 100644 > > --- a/combine-diff.c > > +++ b/combine-diff.c > > @@ -15,8 +15,8 @@ > > ... > > + while (1) { > > ... > > +

Re: [PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection

Kirill Smelkov writes: > diff --git a/combine-diff.c b/combine-diff.c > index 3b92c448..98c2562 100644 > --- a/combine-diff.c > +++ b/combine-diff.c > @@ -15,8 +15,8 @@ > ... > + while (1) { > ... > + if (cmp < 0) { > + if (pprev) > +

Re: [PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection

On Mon, Jan 20, 2014 at 08:20:40PM +0400, Kirill Smelkov wrote: [...] > @@ -1343,6 +1374,26 @@ void diff_tree_combined(const unsigned char *sha1, > if (p->len) > num_paths++; > } > + > + /* order paths according to diffcore_order */ > + if (opt->or

[PATCH 3/4] combine-diff: Optimize combine_diff_path sets intersection

Currently, when generating combined diff, for a commit, we intersect diff paths from diff(parent_0,commit) to diff(parent_i,commit) comparing all paths pairs, i.e. doing it the quadratic way. That is correct, but could be optimized: Paths come from trees in sorted (= tree) order, and so does diff_