From: Tay Ray Chuan Date: Wed, 13 Jul 2011 16:36:18 GMT Subject: Re: [RFC/PATCH 1/3] teach --histogram to diff Message-ID: In-Reply-To: <7vy6036zon.fsf@alter.siamese.dyndns.org> On Wed, Jul 13, 2011 at 3:56 AM, Junio C Hamano wrote: > This is just half-a-review (bottom half of the file). > [snip] >> +                     result = histogram_diff(xpp, env, >> +                             line1, lcs.begin1 - line1, >> +                             line2, lcs.begin2 - line2); >> +                     result = histogram_diff(xpp, env, >> +                             lcs.end1 + 1, LINE_END(1) - lcs.end1, >> +                             lcs.end2 + 1, LINE_END(2) - lcs.end2); > > The result from the first half before lcs is discarded? > >> +                     result *= -1; > > Again, what does this function (called recursively) return, and what does > flipping the sign of it do? Oops, my bad. >[snip] >> +     reduce_common_start_end(xpp, env, &line1, &count1, &line2, &count2); > > What this does is logically not specific to histogram algorithm but can be > applied to other backends, no? And I vaguely recall that Linus did try > something like this once, found some issues with it when context is set to > non zero, and stopped doing it (sorry, I do not have any more details). > > I am not suggesting you to remove this call or hoist the call to one level > up to xdl_do_diff(), but I do have to wonder how much of the performance > improvement you reported is due to this common head/tail reduction. I believe xdiff already performs this for the Meyers algorithm (in xprepare.c:xdl_trim_ends()), but the Meyers code doesn't look like it uses this information at all. If this is the case, then I do think that a large part of the performance improvement is due to this common reduction - for git log -p, one would expect a pretty large number of common head/tail lines in files within a commit. -- Cheers, Ray Chuan