{"thread":{"id":"17593","subject":"Bram Cohen speaks up about patience diff","startedAt":"2009-02-05T20:19:54Z","lastAt":"2009-02-05T20:19:54Z","messageCount":1,"participants":["Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"103376","messageId":"alpine.DEB.1.00.0902052113590.7491@intel-tinevez-2-302","threadId":"17593","inReplyTo":null,"subject":"Bram Cohen speaks up about patience diff","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-02-05T20:19:54Z","receivedAt":"2009-02-05T20:19:54Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nBram sent me two mails explaining a bit more of the details behind \npatience diff, and invited me to forward the content.  So here you are:\n\n-- snipsnap --\nFrom: Bram Cohen <spam-protected-as-per-brams-request@spam.la>\nTo: Johannes Schindelin <Johannes.Schindelin@gmx.de>\nSent: Wednesday, February 4, 2009 3:52:54 PM\nSubject: patience diff advantages/disadvantages\n\nHey Johannes, I just did some web searching for patience search and came \nacross the recent discussion of it. I'm not on whatever mailing list that \ndiscussion was on, but I have some thoughts on it which you might wish to \nshare.\n\nThe reverse engineered intuition that non-unique lines are 'less \nimportant' than unique lines is a correct one, and specifically the case \nof lots of curly bracket lines in C and END lines in Pascal and similar \ncases are the main motivating factor.\n\nFor most common cases, any reasonable diff algorithm will give the same \nresult. The cases where the results are quite dramatic are ones where the \namount of change between the two versions is very large. The test cases \nbeing tried in recent discussion are from developers familiar with version \ncontrol, who are being very judicious in their development process and \nintentionally trying to keep things from diverging too badly. In those \ncases, outputs will generally speaking always be the same and where they \naren't the differences are frequently a judgement call.\n\nThe really bad cases are ones where two versions have diverged \ndramatically and the developer isn't being careful to keep patch sizes \nunder control. Under those circumstances a diff algorithm can occasionally \nbecome 'misaligned' in that it matches long sections of curly brackets \ntogether, but it winds up correlating the curly brackets of functions in \none version with the curly brackets of the next later function in the \nother version. This situation is *very ugly*, and can result in a totally \nunusable conflict file in the situation where you need such things to be \npresented coherently the most. I have in fact seen it happen (in fact, \nit's happened to me). I don't have a sample of it, but as you can imagine \nsuch a sample case must by its nature be rather large and uninsightful - \nit basically just looks ugly.\n\nSo 'unique lines' is a simple cross-language proxy for 'unimportant \nlines'. 'short lines' of course also can work, but might give false \npositives and it depends what you mean by 'short'. There's also an \nimplementation and code maintainability advantage to unique lines. The \npatience algorithm is far simpler to understand and implement than the \nfancy-shmancy recent LCS algorithms. While patience sorting is far from \nobvious, LCS algorithms with good asymptotics are extremely opaque. I \nsuspect that a properly implemented patience diff could be just as fast if \nnot faster than LCS, but that would require quite a bit more algorithmic \nmagic than I for one am prepared to design, test and debug. In very real \nterms the amount of time effort, and trickery the different \nimplementations have had put into them is very different, so current speed \ndifferences aren't exactly a fair comparison (although far from \nirrelevant, because nobody with the necessary expertise is volunteering to \nspend that much time on patience diff as of yet).\n\nSome other things I forgot to mention - it isn't clear from the discussion \nwhether you're doing the heuristic of matching beginning/ending lines when \neverything else doesn't match (this heuristic could also be applied first, \nwhich would be faster and almost always yield the same results). That's \nimportant so that long sections of white space get matched to each other. \nAlso, I disagree that LCS is necessarily a good idea when matching, say \n12121 to 212. What was meant by that case is highly ambiguous, and the \nmost conservative thing is to simply give a conflict for the whole \nsection. (If matching, say, 12121 to 1212 then the first lines match \nheuristic will make them mostly match with an extra 1 at the end of the \nfirst one).\n\nThe most difficult real-world diff cases have to do with lots of blank \nlines, if we represent a blank line by 'S', then the diff from 'SSSSS' to \n'SSSXSSS' is highly ambiguous - an extra S was added, but there are four \nreasonable places for assuming it was put in, each of which a reasonable \ncase can be made for, and I suspect that there's an analogue to Arrow's \ntheorem that trying to do the right thing in particular edge cases must \nnecessarily result in intermediary cases where the criteria are in direct \nconflict. (My patience implementation, by the way, will match the first \nthree lines of the five Ss to the the first three of the second set of Ss, \nand the last two to the last two, with the string XS inserted into the \nmiddle, which is arguably the best behavior, but could under some \ncircumstances result in very confused three-way merges dependending on \nwhat happened on the other side).\n"}]}