{"thread":{"id":"374","subject":"Re: The criss-cross merge case","startedAt":"2005-04-28T14:25:01Z","lastAt":"2005-04-29T12:19:18Z","messageCount":2,"participants":["Adam J. Richter","Wayne Scott"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"2038","messageId":"200504281425.j3SEP1H00534@freya.yggdrasil.com","threadId":"374","inReplyTo":null,"subject":"Re: The criss-cross merge case","fromName":"Adam J. Richter","fromEmail":"adam@yggdrasil.com","sentAt":"2005-04-28T14:25:01Z","receivedAt":"2005-04-28T14:25:01Z","isPatch":false,"sender":{"key":"adam@yggdrasil.com","avatar":null},"body":"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\tMonotone apparently uses a futher acceleration of that algorithm\nfrom the 1989 paper, also co-authored by the Myers, \"An O(NP) Sequence\nComparison Algorithm\" by Sun Wu, Udi Manber, and Gene Myers.\nhttp://www.eecs.berkeley.edu/~gene/Papers/np_diff.pdf .  The Monotone\nimplementation was apparently a port of an implementation originally\nwritten in Scheme by Aubrey Jaffer.\n\n\tI don't fully understand the 1989 paper, but I get the\ngeneral 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\ngot around to submitting it, and seems to make the code run more\nthan twice as fast in practice.  One of these days, I will probably get\naround to coding up a patch to GNU diff if nobody beats me to it.\n\n\tMaking diff run faster may have at least one potentially useful\nbenefit for merging.  A faster diff makes it more practical run diff\non smaller units of comparison.  I posted a note here before about\nconverting the input files to diff3 to have just one character per\nline, and then undoing that transformation of the result to produce\na character based merge that seemed to work pretty well in the\ncouple of tests that I tried.\n\n                    __     ______________ \nAdam J. Richter        \\ /\nadam@yggdrasil.com      | g g d r a s i l\n"},{"id":"2126","messageId":"59a6e58305042905191f4eca98@mail.gmail.com","threadId":"374","inReplyTo":"200504281425.j3SEP1H00534@freya.yggdrasil.com","subject":"Re: The criss-cross merge case","fromName":"Wayne Scott","fromEmail":"wsc9tt@gmail.com","sentAt":"2005-04-29T12:19:18Z","receivedAt":"2005-04-29T12:19:18Z","isPatch":false,"sender":{"key":"wsc9tt@gmail.com","avatar":"https://gravatar.com/avatar/2418bf5fa7f1625a2b9dd049db4ab56110f561610421d6f2559f7c018ce53eb3?d=mp&s=160"},"body":"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\nI just read that paper and unless I am mistaken, it already describes\nthe basis for how GNU diff works.  I don't think anything in that\npaper would make it faster.\n\nI also don't find anything to suggest the Monotone guys have rewritten\ndiff.  Just some notes from graydon that notes python's difflib uses a\nnon-optimal diff that is faster in some cases.\n\n-Wayne\n"}]}