{"thread":{"id":"409","subject":"Re: The criss-cross merge case","startedAt":"2005-04-30T12:32:11Z","lastAt":"2005-04-30T12:32:11Z","messageCount":1,"participants":["Adam J. Richter"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"2256","messageId":"200504301232.j3UCWBO05174@adam.yggdrasil.com","threadId":"409","inReplyTo":null,"subject":"Re: The criss-cross merge case","fromName":"Adam J. Richter","fromEmail":"adam@yggdrasil.com","sentAt":"2005-04-30T12:32:11Z","receivedAt":"2005-04-30T12:32:11Z","isPatch":false,"sender":{"key":"adam@yggdrasil.com","avatar":null},"body":"On Fri, 29 Apr 2005 07:19:18 -0500, Wayne Scott wrote:\n>On 4/28/05, Adam J. Richter <adam@yggdrasil.com> wrote:\n>> On 2005-04-28, Benedikt Schmidt wrote:\n>> >AFAIK the paper mentioned in the GNU diff sources [1] is an improvement\n>> >to an earlier paper by the same author titled\n>> >\"A File Comparison Program\" - Miller, Myers - 1985.\n>> [...]\n>> >[1] http://citeseer.ist.psu.edu/myers86ond.html\n>> \n>>         Monotone apparently uses a futher acceleration of that algorithm\n>> from the 1989 paper, also co-authored by the Myers, \"An O(NP) Sequence\n>> Comparison Algorithm\" by Sun Wu, Udi Manber, and Gene Myers.\n>> http://www.eecs.berkeley.edu/~gene/Papers/np_diff.pdf .  The Monotone\n>> implementation was apparently a port of an implementation originally\n>> written in Scheme by Aubrey Jaffer.\n>> \n>>         I don't fully understand the 1989 paper, but I get the\n>> general impression that is a small change to the previous algorithm\n>> (the one in GNU diff) that might be a 30 line patch if someone\n>> got around to submitting it, and seems to make the code run more\n>> than twice as fast in practice.  One of these days, I will probably get\n>> around to coding up a patch to GNU diff if nobody beats me to it.\n>> \n>>         Making diff run faster may have at least one potentially useful\n>> benefit for merging.  A faster diff makes it more practical run diff\n>> on smaller units of comparison.  I posted a note here before about\n>> converting the input files to diff3 to have just one character per\n>> line, and then undoing that transformation of the result to produce\n>> a character based merge that seemed to work pretty well in the\n>> couple of tests that I tried.\n\n>I just read that paper and unless I am mistaken, it already describes\n>the basis for how GNU diff works.  I don't think anything in that\n>paper would make it faster.\n>\n>I also don't find anything to suggest the Monotone guys have rewritten\n>diff.  Just some notes from graydon that notes python's difflib uses a\n>non-optimal diff that is faster in some cases.\n\n\tIn terminology that can only be understood by reading\nthe 1985 paper, the 1989 paper describes a possible reduction\nin the number of diagonals in the edit graph that iterations of the\n1989 algorithm have to consider.  I say \"possible reduction\" because\nthe reduction can be zero in the worse case, although I get the\nimpression that it should be a reduction of 50% or better\ntypically, and it makes the case where the changes is just\na bunch of inserts run in linear time.\n\n\tI believe that the longest common subsequence finder\nat the core of GNU diff does not currently perform this optimization,\nbut the one in monotone-0.18/lcs.{cc,hh} does.\n\n                    __     ______________\nAdam J. Richter        \\ /\nadam@yggdrasil.com      | g g d r a s i l\n"}]}