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