Re: [PATCH] xdiff: improve trimming preprocessing

From: Jun Wu <quark@fb.com>
Date: Mar 6, 2018, 23:59 UTC
Message-ID: <1520378039-sup-4143@x1c>
In-Reply-To: <xmqq7eqp3suv.fsf@gitster-ct.c.googlers.com>

Excerpts from Junio C Hamano's message of 2018-03-06 11:29:44 -0800:

Show 12 quoted lines

> Eric Sunshine <sunshine@sunshineco.com> writes:
> 
> > On Tue, Mar 6, 2018 at 6:53 AM, Jun Wu <quark@fb.com> wrote:
> >> xdiff-interface trims common suffix if ctxlen is 0. Teach it to also
> >> trim common prefix, and trim less lines if ctxlen > 0. So it can benefit
> >> the default diff command, as seen by profiling: [...]
> 
> I vaguely recall that we have tried this in the distant past, found
> that it produced incorrect result, and that is why we limit the
> optimization for no-context case.
> 
> Does anybody have an archive reference?

I think it's d2f8295 ("Re(-re)*fix trim_common_tail()", 2007-12-20).

Yeah, this is more complex than I thought. In Mercurial's use-case, ctxlen is 0 and context are added in a higher layer so it's fine.

It's clearly hunk shifting causing problems. I'll send a V2 to forbid hunk shifting if it can possibly lose context lines. That implies counting suffix lines, which adds some overhead but the overall perf win still seems worthwhile.