Re: The criss-cross merge case

Adam J. Richter· Apr 28, 2005, 14:25 UTC · lore

On 2005-04-28, Benedikt Schmidt wrote:

>AFAIK the paper mentioned in the GNU diff sources [1] is an improvement
>to an earlier paper by the same author titled
>"A File Comparison Program" - Miller, Myers - 1985.

[...]

>[1] http://citeseer.ist.psu.edu/myers86ond.html

	Monotone apparently uses a futher acceleration of that algorithm
from the 1989 paper, also co-authored by the Myers, "An O(NP) Sequence
Comparison Algorithm" by Sun Wu, Udi Manber, and Gene Myers.
http://www.eecs.berkeley.edu/~gene/Papers/np_diff.pdf .  The Monotone
implementation was apparently a port of an implementation originally
written in Scheme by Aubrey Jaffer.

	I don't fully understand the 1989 paper, but I get the
general impression that is a small change to the previous algorithm
(the one in GNU diff) that might be a 30 line patch if someone
got around to submitting it, and seems to make the code run more
than twice as fast in practice.  One of these days, I will probably get
around to coding up a patch to GNU diff if nobody beats me to it.

	Making diff run faster may have at least one potentially useful
benefit for merging.  A faster diff makes it more practical run diff
on smaller units of comparison.  I posted a note here before about
converting the input files to diff3 to have just one character per
line, and then undoing that transformation of the result to produce
a character based merge that seemed to work pretty well in the
couple of tests that I tried.

                    __     ______________ 
Adam J. Richter        \ /
adam@yggdrasil.com      | g g d r a s i l

Wayne Scott· Apr 29, 2005, 12:19 UTC · re: Adam J. Richter · lore

On 4/28/05, Adam J. Richter <adam@yggdrasil.com> wrote:

Show 28 quoted lines

> On 2005-04-28, Benedikt Schmidt wrote:
> >AFAIK the paper mentioned in the GNU diff sources [1] is an improvement
> >to an earlier paper by the same author titled
> >"A File Comparison Program" - Miller, Myers - 1985.
> [...]
> >[1] http://citeseer.ist.psu.edu/myers86ond.html
> 
>         Monotone apparently uses a futher acceleration of that algorithm
> from the 1989 paper, also co-authored by the Myers, "An O(NP) Sequence
> Comparison Algorithm" by Sun Wu, Udi Manber, and Gene Myers.
> http://www.eecs.berkeley.edu/~gene/Papers/np_diff.pdf .  The Monotone
> implementation was apparently a port of an implementation originally
> written in Scheme by Aubrey Jaffer.
> 
>         I don't fully understand the 1989 paper, but I get the
> general impression that is a small change to the previous algorithm
> (the one in GNU diff) that might be a 30 line patch if someone
> got around to submitting it, and seems to make the code run more
> than twice as fast in practice.  One of these days, I will probably get
> around to coding up a patch to GNU diff if nobody beats me to it.
> 
>         Making diff run faster may have at least one potentially useful
> benefit for merging.  A faster diff makes it more practical run diff
> on smaller units of comparison.  I posted a note here before about
> converting the input files to diff3 to have just one character per
> line, and then undoing that transformation of the result to produce
> a character based merge that seemed to work pretty well in the
> couple of tests that I tried.

I just read that paper and unless I am mistaken, it already describes the basis for how GNU diff works. I don't think anything in that paper would make it faster.

I also don't find anything to suggest the Monotone guys have rewritten diff. Just some notes from graydon that notes python's difflib uses a non-optimal diff that is faster in some cases.

-Wayne