{"thread":{"id":"48944","subject":"[PATCH] Documentation/diff-options: explain different diff algorithms","startedAt":"2018-07-24T00:36:25Z","lastAt":"2018-08-10T22:19:04Z","messageCount":13,"participants":["Stefan Beller","Jonathan Nieder","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"353436","messageId":"20180724003619.185290-1-sbeller@google.com","threadId":"48944","inReplyTo":null,"subject":"[PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-24T00:36:19Z","receivedAt":"2018-07-24T00:36:25Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"As a user I wondered what the diff algorithms are about. Offer at least\na basic explanation on the differences of the diff algorithms.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n Documentation/diff-options.txt | 32 +++++++++++++++++++++++++-------\n 1 file changed, 25 insertions(+), 7 deletions(-)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex f466600972f..0d765482027 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -94,16 +94,34 @@ diff\" algorithm internally.\n \tChoose a diff algorithm. The variants are as follows:\n +\n --\n-`default`, `myers`;;\n-\tThe basic greedy diff algorithm. Currently, this is the default.\n `minimal`;;\n-\tSpend extra time to make sure the smallest possible diff is\n-\tproduced.\n+\tA diff as produced by the basic greedy algorithm described in\n+\tlink:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations]\n+`default`, `myers`;;\n+\tThe same algorithm as `minimal`, extended with a heuristic to\n+\treduce extensive searches. Currently, this is the default.\n `patience`;;\n-\tUse \"patience diff\" algorithm when generating patches.\n+\tUse \"patience diff\" algorithm when generating patches. This\n+\tmatches the longest common subsequence of unique lines on\n+\tboth sides, recursively. It obtained its name by the way the\n+\tlongest subsequence is found, as that is a byproduct of the\n+\tpatience sorting algorithm. If there are no unique lines left\n+\tit falls back to `myers`. Empirically this algorithm produces\n+\ta more readable output for code, but it does not garantuee\n+\tthe shortest output.\n `histogram`;;\n-\tThis algorithm extends the patience algorithm to \"support\n-\tlow-occurrence common elements\".\n+\tThis algorithm re-implements the `patience` algorithm with\n+\t\"support of low-occurrence common elements\" and only picks\n+\tone element of the LCS for the recursion. It is often the\n+\tfastest, but in cornercases (when there are many longest\n+\tcommon subsequences of the same length) it produces bad\n+\tresults as seen in:\n+\n+\t\tseq 1 100 >one\n+\t\techo 99 > two\n+\t\tseq 1 2 98 >>two\n+\t\tgit diff --no-index --histogram one two\n+\n --\n +\n For instance, if you configured diff.algorithm variable to a\n-- \n2.18.0.345.g5c9ce644c3-goog\n\n"},{"id":"353441","messageId":"20180724044051.GA208393@aiede.svl.corp.google.com","threadId":"48944","inReplyTo":"20180724003619.185290-1-sbeller@google.com","subject":"Re: [PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2018-07-24T04:40:52Z","receivedAt":"2018-07-24T04:41:00Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nStefan Beller wrote:\n\n> As a user I wondered what the diff algorithms are about. Offer at least\n> a basic explanation on the differences of the diff algorithms.\n\nInteresting.  Let's see.\n\n[...]\n> --- a/Documentation/diff-options.txt\n> +++ b/Documentation/diff-options.txt\n> @@ -94,16 +94,34 @@ diff\" algorithm internally.\n>  \tChoose a diff algorithm. The variants are as follows:\n>  +\n>  --\n> -`default`, `myers`;;\n> -\tThe basic greedy diff algorithm. Currently, this is the default.\n>  `minimal`;;\n> +\tA diff as produced by the basic greedy algorithm described in\n\nWhy this reordering?\n\n> +\tlink:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations]\n\nThis URL doesn't seem likely to stay stable.  Are appearances\ndeceiving?  (Maybe so, since that's the same host as libxdiff's\nhomepage <http://www.xmailserver.org/xdiff-lib.html>.)  It might be\nworth mentioning the author and date just in case.\n\n> -\tSpend extra time to make sure the smallest possible diff is\n> -\tproduced.\n> +`default`, `myers`;;\n> +\tThe same algorithm as `minimal`, extended with a heuristic to\n> +\treduce extensive searches. Currently, this is the default.\n\nAmusing --- this means that the Myers diff is spelled as \"minimal\"\ninstead of \"myers\".\n\n>  `patience`;;\n> -\tUse \"patience diff\" algorithm when generating patches.\n> +\tUse \"patience diff\" algorithm when generating patches. This\n> +\tmatches the longest common subsequence of unique lines on\n> +\tboth sides, recursively. It obtained its name by the way the\n> +\tlongest subsequence is found, as that is a byproduct of the\n> +\tpatience sorting algorithm. If there are no unique lines left\n> +\tit falls back to `myers`. Empirically this algorithm produces\n> +\ta more readable output for code, but it does not garantuee\n> +\tthe shortest output.\n\nProbably also worth mentioning that this was invented by Bram Cohen\nfor the bazaar vcs.\n\n>  `histogram`;;\n> -\tThis algorithm extends the patience algorithm to \"support\n> -\tlow-occurrence common elements\".\n> +\tThis algorithm re-implements the `patience` algorithm with\n\nWhat does reimplements mean here?  Do you mean that it is a variation\non patience?\n\n> +\t\"support of low-occurrence common elements\" and only picks\n> +\tone element of the LCS for the recursion. It is often the\n\nDoes LCS mean longest common subsequence or longest common substring\nhere?  Probably best to spell it out to avoid confusion.\n\n> +\tfastest, but in cornercases (when there are many longest\n\ns/cornercases/corner cases/\n\n> +\tcommon subsequences of the same length) it produces bad\n> +\tresults as seen in:\n> +\n> +\t\tseq 1 100 >one\n> +\t\techo 99 > two\n> +\t\tseq 1 2 98 >>two\n> +\t\tgit diff --no-index --histogram one two\n\nI wonder if these details (about all the algorithms) should go in a\nseparate Diff Algorithms section and this section could focus on\nwhat use cases warrant using each, referring to that section for\ndetails.  What do you think?\n\nThanks and hope that helps,\nJonathan\n"},{"id":"353499","messageId":"CAGZ79kap9TovN2ia4pEgz33dh=9y89cVYZWnB_1e6iHpR=kDOQ@mail.gmail.com","threadId":"48944","inReplyTo":"20180724044051.GA208393@aiede.svl.corp.google.com","subject":"Re: [PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-24T17:38:03Z","receivedAt":"2018-07-24T17:38:17Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Jul 23, 2018 at 9:41 PM Jonathan Nieder <jrnieder@gmail.com> wrote:\n>\n> Hi,\n>\n> Stefan Beller wrote:\n>\n> > As a user I wondered what the diff algorithms are about. Offer at least\n> > a basic explanation on the differences of the diff algorithms.\n>\n> Interesting.  Let's see.\n>\n> [...]\n> > --- a/Documentation/diff-options.txt\n> > +++ b/Documentation/diff-options.txt\n> > @@ -94,16 +94,34 @@ diff\" algorithm internally.\n> >       Choose a diff algorithm. The variants are as follows:\n> >  +\n> >  --\n> > -`default`, `myers`;;\n> > -     The basic greedy diff algorithm. Currently, this is the default.\n> >  `minimal`;;\n> > +     A diff as produced by the basic greedy algorithm described in\n>\n> Why this reordering?\n\nbecause Myers (below) is constructed from minimal + heuristic.\nBefore this patch we say Myers is myers and minimal \"spends\nextra cycles\", which is true if you read the code, as it just is\n\n    for (...) {\n        test_path\n        if (need_min)\n            continue;\n        if (heuristic_good_enough())\n            break;\n    }\n\nhttps://github.com/git/git/blob/master/xdiff/xdiffi.c#L152\n\nSo the \"minimal\" algorithm is the basic myers algorithm,\nand the \"myers\" algorithm is the extended version (extended\nwith a heuristic to be fast in corner cases, still producing good\nenough diffs).\n\n>\n> > +     link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations]\n>\n> This URL doesn't seem likely to stay stable.  Are appearances\n> deceiving?  (Maybe so, since that's the same host as libxdiff's\n> homepage <http://www.xmailserver.org/xdiff-lib.html>.)  It might be\n> worth mentioning the author and date just in case.\n\nI though about it and did not mention it, as the name\n\"An O(ND) Difference Algorithm and its Variations\" is already\nenough to find that paper quickly.\n\n> > -     Spend extra time to make sure the smallest possible diff is\n> > -     produced.\n> > +`default`, `myers`;;\n> > +     The same algorithm as `minimal`, extended with a heuristic to\n> > +     reduce extensive searches. Currently, this is the default.\n>\n> Amusing --- this means that the Myers diff is spelled as \"minimal\"\n> instead of \"myers\".\n>\n> >  `patience`;;\n> > -     Use \"patience diff\" algorithm when generating patches.\n> > +     Use \"patience diff\" algorithm when generating patches. This\n> > +     matches the longest common subsequence of unique lines on\n> > +     both sides, recursively. It obtained its name by the way the\n> > +     longest subsequence is found, as that is a byproduct of the\n> > +     patience sorting algorithm. If there are no unique lines left\n> > +     it falls back to `myers`. Empirically this algorithm produces\n> > +     a more readable output for code, but it does not garantuee\n> > +     the shortest output.\n>\n> Probably also worth mentioning that this was invented by Bram Cohen\n> for the bazaar vcs.\n\nI tried to balance the part that reads like a history lesson and the\nimmediately useful part (why is this better, when should I use it?)\n\nMentioning bazaar probably makes sense. Not sure about the author,\nbut I'll include him in a reroll of this patch.\n\n> >  `histogram`;;\n> > -     This algorithm extends the patience algorithm to \"support\n> > -     low-occurrence common elements\".\n> > +     This algorithm re-implements the `patience` algorithm with\n>\n> What does reimplements mean here?  Do you mean that it is a variation\n> on patience?\n\nIt is supposed to be a variation of patience, but as it comes with its\nown implementation which I would not fully trust (as it was ported\nfrom JGit, and reading the comments over there, a misunderstanding\nof LCS made it possible to have only one midpoint before recursing)\n\nSo it is not just taking the patience algorithm and adding support for\n\"low-occurrence common elements\"  (what does that even mean?\npatience already distinguishes uniques and non-uniques), but\nits own implementation, hence it is not bug-for-bug compatible.\n\n> > +     \"support of low-occurrence common elements\" and only picks\n> > +     one element of the LCS for the recursion. It is often the\n>\n> Does LCS mean longest common subsequence or longest common substring\n> here?  Probably best to spell it out to avoid confusion.\n\nWhen writing the patch I meant to refer to longest common subsequence\nfrom above, but by picking just one element, this algorithm understands it\nas longest common string.\n\n\n>\n> > +     fastest, but in cornercases (when there are many longest\n>\n> s/cornercases/corner cases/\n>\n> > +     common subsequences of the same length) it produces bad\n> > +     results as seen in:\n> > +\n> > +             seq 1 100 >one\n> > +             echo 99 > two\n> > +             seq 1 2 98 >>two\n> > +             git diff --no-index --histogram one two\n>\n> I wonder if these details (about all the algorithms) should go in a\n> separate Diff Algorithms section and this section could focus on\n> what use cases warrant using each, referring to that section for\n> details.  What do you think?\n\nYeah I thought about putting together a\nDocumentation/technical/diffs.txt that talk about all kinds of diffing\n(basic diff algorithms, options, how to diff trees), but considered\nrolling this as a band aid until that document fully materializes.\n\nThanks,\nStefan\n"},{"id":"353523","messageId":"xmqq4lgoxusr.fsf@gitster-ct.c.googlers.com","threadId":"48944","inReplyTo":"CAGZ79kap9TovN2ia4pEgz33dh=9y89cVYZWnB_1e6iHpR=kDOQ@mail.gmail.com","subject":"Re: [PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-07-24T20:06:44Z","receivedAt":"2018-07-24T20:06:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> On Mon, Jul 23, 2018 at 9:41 PM Jonathan Nieder <jrnieder@gmail.com> wrote:\n>>\n>> Hi,\n>>\n>> Stefan Beller wrote:\n>>\n>> > As a user I wondered what the diff algorithms are about. Offer at least\n>> > a basic explanation on the differences of the diff algorithms.\n>>\n>> Interesting.  Let's see.\n>>\n>> [...]\n>> > --- a/Documentation/diff-options.txt\n>> > +++ b/Documentation/diff-options.txt\n>> > @@ -94,16 +94,34 @@ diff\" algorithm internally.\n>> >       Choose a diff algorithm. The variants are as follows:\n>> >  +\n>> >  --\n>> > -`default`, `myers`;;\n>> > -     The basic greedy diff algorithm. Currently, this is the default.\n>> >  `minimal`;;\n>> > +     A diff as produced by the basic greedy algorithm described in\n>>\n>> Why this reordering?\n>\n> because Myers (below) is constructed from minimal + heuristic.\n> ...\n> So the \"minimal\" algorithm is the basic myers algorithm,\n> and the \"myers\" algorithm is the extended version (extended\n> with a heuristic to be fast in corner cases, still producing good\n> enough diffs).\n\nI am not sure that is a good reason for the target readers of this\ndocument to move the default from the beginning to somewhere in the\nmiddle.  For a textbook that explains different algorithms and gives\noverview of how they work, that order may be appropriate, though.\n\n>> > -     Spend extra time to make sure the smallest possible diff is\n>> > -     produced.\n>> > +`default`, `myers`;;\n>> > +     The same algorithm as `minimal`, extended with a heuristic to\n>> > +     reduce extensive searches. Currently, this is the default.\n>>\n>> Amusing --- this means that the Myers diff is spelled as \"minimal\"\n>> instead of \"myers\".\n\nYeah, I had the same thought---for an end-user documentation update,\nthis change and the reordering does not feel like an improvement.\n\n>> I wonder if these details (about all the algorithms) should go in a\n>> separate Diff Algorithms section and this section could focus on\n>> what use cases warrant using each, referring to that section for\n>> details.  What do you think?\n\nGood suggestion.\n"},{"id":"354687","messageId":"20180806222551.132628-1-sbeller@google.com","threadId":"48944","inReplyTo":"20180724044051.GA208393@aiede.svl.corp.google.com","subject":"[PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-06T22:25:51Z","receivedAt":"2018-08-06T22:26:03Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"As a user I wondered what the diff algorithms are about. Offer at least\na basic explanation on the differences of the diff algorithms.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n Documentation/diff-options.txt | 10 +++++++---\n Documentation/git-diff.txt     | 34 ++++++++++++++++++++++++++++++++++\n 2 files changed, 41 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex f394608b42c..eae033a21ea 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -91,14 +91,18 @@ appearing as a deletion or addition in the output. It uses the \"patience\n diff\" algorithm internally.\n \n --diff-algorithm={patience|minimal|histogram|myers}::\n-\tChoose a diff algorithm. The variants are as follows:\n+\tChoose a diff algorithm. See the discussion of DIFF ALGORITHMS\n+ifndef::git-diff[]\n+\tin linkgit:git-diff[1]\n+endif::git-diff[]\n+\t. The variants are as follows:\n +\n --\n `default`, `myers`;;\n \tThe basic greedy diff algorithm. Currently, this is the default.\n `minimal`;;\n-\tSpend extra time to make sure the smallest possible diff is\n-\tproduced.\n+\tThe same algorithm as `myers`, but spend extra time to make\n+\tsure the smallest possible diff is produced.\n `patience`;;\n \tUse \"patience diff\" algorithm when generating patches.\n `histogram`;;\ndiff --git a/Documentation/git-diff.txt b/Documentation/git-diff.txt\nindex b180f1fa5bf..b182389aaae 100644\n--- a/Documentation/git-diff.txt\n+++ b/Documentation/git-diff.txt\n@@ -119,6 +119,40 @@ include::diff-options.txt[]\n \n include::diff-format.txt[]\n \n+DIFF ALGORITHMS\n+---------------\n+`Myers`\n+\n+A diff as produced by the basic greedy algorithm described in\n+link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations].\n+with a run time of O(M + N + D^2). It employs a heuristic to allow for\n+a faster diff at the small cost of diff size.\n+The `minimal` algorithm has that heuristic turned off.\n+\n+`Patience`\n+\n+This algorithm by Bram Cohen matches the longest common subsequence\n+of unique lines on both sides, recursively. It obtained its name by\n+the way the longest subsequence is found, as that is a byproduct of\n+the patience sorting algorithm. If there are no unique lines left\n+it falls back to `myers`. Empirically this algorithm produces\n+a more readable output for code, but it does not garantuee\n+the shortest output.\n+\n+`Histogram`\n+\n+This algorithm finds the longest common substring and recursively\n+diffs the content before and after the longest common substring.\n+If there are no common substrings left, fallback to `myers`.\n+This is often the fastest, but in corner cases (when there are\n+many common substrings of the same length) it produces bad\n+results as seen in:\n+\n+\tseq 1 100 >one\n+\techo 99 > two\n+\tseq 1 2 98 >>two\n+\tgit diff --no-index --histogram one two\n+\n EXAMPLES\n --------\n \n-- \n2.18.0.597.ga71716f1ad-goog\n\n"},{"id":"354696","messageId":"20180806231843.GA4117@aiede.svl.corp.google.com","threadId":"48944","inReplyTo":"20180806222551.132628-1-sbeller@google.com","subject":"Re: [PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2018-08-06T23:18:43Z","receivedAt":"2018-08-06T23:18:48Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nStefan Beller wrote:\n> --- a/Documentation/diff-options.txt\n> +++ b/Documentation/diff-options.txt\n> @@ -91,14 +91,18 @@ appearing as a deletion or addition in the output. It uses the \"patience\n>  diff\" algorithm internally.\n>  \n>  --diff-algorithm={patience|minimal|histogram|myers}::\n> -\tChoose a diff algorithm. The variants are as follows:\n> +\tChoose a diff algorithm. See the discussion of DIFF ALGORITHMS\n> +ifndef::git-diff[]\n> +\tin linkgit:git-diff[1]\n> +endif::git-diff[]\n> +\t. The variants are as follows:\n\nThis means outside of git-diff(1), I'd see\n\n\tSee the discussion of DIFF ALGORITHMS in git-diff(1) .\n\nAnd in git-diff(1), I'd see\n\n\tSee the discussion of DIFF ALGORITHMS .\n\nBoth don't seem quite right, since they have an extra space before the\nperiod.  The git-diff(1) seems especially not quite right --- does it\nintend to say something like \"See the DIFF ALGORITHMS section for more\ndiscussion\"?\n\n[...]\n> --- a/Documentation/git-diff.txt\n> +++ b/Documentation/git-diff.txt\n> @@ -119,6 +119,40 @@ include::diff-options.txt[]\n>  \n>  include::diff-format.txt[]\n>  \n> +DIFF ALGORITHMS\n> +---------------\n\nPlease add some introductory words about what the headings refer to.\n\n> +`Myers`\n> +\n> +A diff as produced by the basic greedy algorithm described in\n> +link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations].\n> +with a run time of O(M + N + D^2). It employs a heuristic to allow for\n> +a faster diff at the small cost of diff size.\n> +The `minimal` algorithm has that heuristic turned off.\n> +\n> +`Patience`\n> +\n> +This algorithm by Bram Cohen matches the longest common subsequence\n> +of unique lines on both sides, recursively. It obtained its name by\n> +the way the longest subsequence is found, as that is a byproduct of\n> +the patience sorting algorithm. If there are no unique lines left\n> +it falls back to `myers`. Empirically this algorithm produces\n> +a more readable output for code, but it does not garantuee\n\nnit: s/garantuee/guarantee/\n\n> +the shortest output.\n\nTrivia: the `minimal` variant of Myers doesn't guarantee shortest\noutput, either: what it minimizes is the number of lines marked as\nadded or removed.  If you want to minimize context lines too, then\nthat would be a new variant. ;-)\n\n[...]\n> +`Histogram`\n> +\n> +This algorithm finds the longest common substring and recursively\n> +diffs the content before and after the longest common substring.\n\noptional: may be worth a short aside in the text about the distinction\nbetween LCS and LCS. ;-)\n\nIt would be especially useful here, since the alphabet used in these\nstrings is *lines* instead of characters, so the first-time reader\ncould probably use some help in building their intuition.\n\n> +If there are no common substrings left, fallback to `myers`.\n\nnit: fallback is the noun, fall back is the verb.\n\n> +This is often the fastest, but in corner cases (when there are\n> +many common substrings of the same length) it produces bad\n\nCan you clarify what \"bad\" means?  E.g. would \"unexpected\", or \"poorly\naligned\", match what you mean?\n\n> +results as seen in:\n> +\n> +\tseq 1 100 >one\n> +\techo 99 > two\n> +\tseq 1 2 98 >>two\n> +\tgit diff --no-index --histogram one two\n> +\n>  EXAMPLES\n>  --------\n\nThanks,\nJonathan\n"},{"id":"354746","messageId":"xmqq600mmaqn.fsf@gitster-ct.c.googlers.com","threadId":"48944","inReplyTo":"20180806231843.GA4117@aiede.svl.corp.google.com","subject":"Re: [PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-08-07T15:56:16Z","receivedAt":"2018-08-07T15:56:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Nieder <jrnieder@gmail.com> writes:\n\n> Both don't seem quite right, since they have an extra space before the\n> period.  The git-diff(1) seems especially not quite right --- does it\n> intend to say something like \"See the DIFF ALGORITHMS section for more\n> discussion\"?\n\nGood suggestion and doing so would nicely allow side-stepping the\nspace before the dot issue, i.e. \"See the DIFF ALGO section (in\ngit-diff(1)) for more discussion\".   I like it.\n\n> [...]\n>> --- a/Documentation/git-diff.txt\n>> +++ b/Documentation/git-diff.txt\n>> @@ -119,6 +119,40 @@ include::diff-options.txt[]\n>>  \n>>  include::diff-format.txt[]\n>>  \n>> +DIFF ALGORITHMS\n>> +---------------\n>\n> Please add some introductory words about what the headings refer to.\n>\n>> +`Myers`\n>> +\n>> +A diff as produced by the basic greedy algorithm described in\n>> +link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations].\n>> +...\n>> +\n>> +`Patience`\n>> +\n>> +This algorithm by Bram Cohen matches the longest common subsequence\n>> +...\n> [...]\n>> +`Histogram`\n>> +\n>> +This algorithm finds the longest common substring and recursively\n>> +diffs the content before and after the longest common substring.\n\nAs a first-time reader, I felt that it is a bit uneven that there is\nno attribution for only this item, unlike the description for Myers\nand Patience.\n"},{"id":"355026","messageId":"CAGZ79kZR_gj00JORH3WB_T+_mgtQm5PGt6+DSMFUbJM+C4FxVw@mail.gmail.com","threadId":"48944","inReplyTo":"xmqq600mmaqn.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-09T19:26:41Z","receivedAt":"2018-08-09T19:26:55Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Aug 7, 2018 at 8:56 AM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Jonathan Nieder <jrnieder@gmail.com> writes:\n>\n> > Both don't seem quite right, since they have an extra space before the\n> > period.  The git-diff(1) seems especially not quite right --- does it\n> > intend to say something like \"See the DIFF ALGORITHMS section for more\n> > discussion\"?\n>\n> Good suggestion and doing so would nicely allow side-stepping the\n> space before the dot issue, i.e. \"See the DIFF ALGO section (in\n> git-diff(1)) for more discussion\".   I like it.\n\nMe, too.\n\n> >> +`Histogram`\n> >> +\n> >> +This algorithm finds the longest common substring and recursively\n> >> +diffs the content before and after the longest common substring.\n>\n> As a first-time reader, I felt that it is a bit uneven that there is\n> no attribution for only this item, unlike the description for Myers\n> and Patience.\n\nYeah. That is because I spent too much time thinking how this algo is\nflawed (in its design as the comments in the initial commit in JGit\nindicate that design error when reading closely) when I was trying to\nunderstand it deeply.\n\nMaybe I should emphasize the trade off for performance gain\nmore as Shawn really cared about performance. After all it offers\nthe best performance in *many* common cases, but has a\n\"long tail\" of really unfortunate results, too.\n"},{"id":"355031","messageId":"CAGZ79kby35z6pQb9DN+SvF6jA1aPMKmxyrtHM7kiwGjwD3abPA@mail.gmail.com","threadId":"48944","inReplyTo":"20180806231843.GA4117@aiede.svl.corp.google.com","subject":"Re: [PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-09T19:51:53Z","receivedAt":"2018-08-09T19:52:06Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Aug 6, 2018 at 4:18 PM Jonathan Nieder <jrnieder@gmail.com> wrote:\n\n> > +DIFF ALGORITHMS\n> > +---------------\n>\n> Please add some introductory words about what the headings refer to.\n\nok.\n\n>\n> > +the shortest output.\n>\n> Trivia: the `minimal` variant of Myers doesn't guarantee shortest\n> output, either: what it minimizes is the number of lines marked as\n> added or removed.  If you want to minimize context lines too, then\n> that would be a new variant. ;-)\n\n... and take line length into account. ;-)\n\nIt minimizes the edit distance in terms of lines, i.e. in a context-less diff\nwe get the lowest number of lines possible.\n\n> > +This algorithm finds the longest common substring and recursively\n> > +diffs the content before and after the longest common substring.\n>\n> optional: may be worth a short aside in the text about the distinction\n> between LCS and LCS. ;-)\n>\n> It would be especially useful here, since the alphabet used in these\n> strings is *lines* instead of characters, so the first-time reader\n> could probably use some help in building their intuition.\n\nThat makes sense.\n\n>\n> > +This is often the fastest, but in corner cases (when there are\n> > +many common substrings of the same length) it produces bad\n>\n> Can you clarify what \"bad\" means?  E.g. would \"unexpected\", or \"poorly\n> aligned\", match what you mean?\n\nI'll just go with unexpected.\n\n> > +results as seen in:\n> > +\n> > +     seq 1 100 >one\n> > +     echo 99 > two\n> > +     seq 1 2 98 >>two\n> > +     git diff --no-index --histogram one two\n"},{"id":"355068","messageId":"20180810001010.58870-1-sbeller@google.com","threadId":"48944","inReplyTo":"20180724003619.185290-1-sbeller@google.com","subject":"[PATCH 0/2] Getting data on different diff algorithms WAS: Documentation/diff-options: explain different diff algorithms","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-10T00:10:08Z","receivedAt":"2018-08-10T00:10:22Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"I instrumented range-diff to use different diff algorithms for the patches,\n(I chose default-myers and patience) and then run on the same range,\nvia ./git-range-diff v2.10.0..HEAD v2.10.0..HEAD\nand I found 5245 same, 304 slightly different and 4 completely different\npatches in that range.\n\nLooking at the interdiff is not very pleasing even when reading it with\ncoloring and move detection.\n\nManually looking at them, I found the patience diff easier to review.\n\nComparing the 'default' diff algorithm to 'minimal', I'll see \n 5491 same, 58 slightly different and 0 completely different patches.\n \nComparing 'default' to 'histogram', I'll see\n 5255 same, 294 slightly different and 8 completely different patches.\n \nComparing 'histogram' to 'patience', I'll see \n 5337 same, 212 slightly different and 10 completely different patches.\n\nThis is all to just put data out there, on how much difference to expect from\nthe diff algorithms. I have not yet dug into the quality of the diffs.\n\nStefan\n\n\nStefan Beller (2):\n  WIP: range-diff: take extra arguments for different diffs.\n  WIP range-diff: print some statistics about the range\n\n range-diff.c | 29 +++++++++++++++++++++++++----\n 1 file changed, 25 insertions(+), 4 deletions(-)\n\n-- \n2.18.0.597.ga71716f1ad-goog\n\n"},{"id":"355069","messageId":"20180810001010.58870-2-sbeller@google.com","threadId":"48944","inReplyTo":"20180810001010.58870-1-sbeller@google.com","subject":"[PATCH 1/2] WIP: range-diff: take extra arguments for different diffs.","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-10T00:10:09Z","receivedAt":"2018-08-10T00:12:42Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"We can use the range-diff on the same range to examine differences in the\ndiff algorithm.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n range-diff.c | 20 ++++++++++++++++----\n 1 file changed, 16 insertions(+), 4 deletions(-)\n\ndiff --git a/range-diff.c b/range-diff.c\nindex 347b4a79f25..a977289b7dc 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -28,7 +28,8 @@ struct patch_util {\n  * Reads the patches into a string list, with the `util` field being populated\n  * as struct object_id (will need to be free()d).\n  */\n-static int read_patches(const char *range, struct string_list *list)\n+static int read_patches(const char *range, struct string_list *list,\n+\t\t\tstruct argv_array *extra_log_args)\n {\n \tstruct child_process cp = CHILD_PROCESS_INIT;\n \tFILE *in;\n@@ -36,7 +37,12 @@ static int read_patches(const char *range, struct string_list *list)\n \tstruct patch_util *util = NULL;\n \tint in_header = 1;\n \n-\targv_array_pushl(&cp.args, \"log\", \"--no-color\", \"-p\", \"--no-merges\",\n+\targv_array_pushl(&cp.args, \"log\", \"--no-color\", \"-p\", \"--no-merges\", NULL);\n+\n+\tif (extra_log_args)\n+\t\targv_array_pushv(&cp.args, extra_log_args->argv);\n+\n+\targv_array_pushl(&cp.args,\n \t\t\t\"--reverse\", \"--date-order\", \"--decorate=no\",\n \t\t\t\"--no-abbrev-commit\", range,\n \t\t\tNULL);\n@@ -419,14 +425,20 @@ int show_range_diff(const char *range1, const char *range2,\n {\n \tint res = 0;\n \n+\tstruct argv_array extra = ARGV_ARRAY_INIT;\n+\n \tstruct string_list branch1 = STRING_LIST_INIT_DUP;\n \tstruct string_list branch2 = STRING_LIST_INIT_DUP;\n \n-\tif (read_patches(range1, &branch1))\n+\targv_array_push(&extra, \"--diff-algorithm=patience\");\n+\targv_array_push(&extra, \"--indent-heuristic\");\n+\n+\tif (read_patches(range1, &branch1, NULL))\n \t\tres = error(_(\"could not parse log for '%s'\"), range1);\n-\tif (!res && read_patches(range2, &branch2))\n+\tif (!res && read_patches(range2, &branch2, &extra))\n \t\tres = error(_(\"could not parse log for '%s'\"), range2);\n \n+\tdiffopt->color_moved = COLOR_MOVED_DEFAULT;\n \tif (!res) {\n \t\tfind_exact_matches(&branch1, &branch2);\n \t\tget_correspondences(&branch1, &branch2, creation_factor);\n-- \n2.18.0.597.ga71716f1ad-goog\n\n"},{"id":"355070","messageId":"20180810001010.58870-3-sbeller@google.com","threadId":"48944","inReplyTo":"20180810001010.58870-1-sbeller@google.com","subject":"[PATCH 2/2] WIP range-diff: print some statistics about the range","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-10T00:10:10Z","receivedAt":"2018-08-10T00:12:42Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Signed-off-by: Stefan Beller <sbeller@google.com>\n---\n range-diff.c | 9 +++++++++\n 1 file changed, 9 insertions(+)\n\ndiff --git a/range-diff.c b/range-diff.c\nindex a977289b7dc..fbabce5f91f 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -264,6 +264,8 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \tfree(b2a);\n }\n \n+int completely_different, slightly_different, same;\n+\n static void output_pair_header(struct diff_options *diffopt,\n \t\t\t       int patch_no_width,\n \t\t\t       struct strbuf *buf,\n@@ -288,15 +290,19 @@ static void output_pair_header(struct diff_options *diffopt,\n \tif (!b_util) {\n \t\tcolor = color_old;\n \t\tstatus = '<';\n+\t\tslightly_different++;\n \t} else if (!a_util) {\n \t\tcolor = color_new;\n \t\tstatus = '>';\n+\t\tcompletely_different++;\n \t} else if (strcmp(a_util->patch, b_util->patch)) {\n \t\tcolor = color_commit;\n \t\tstatus = '!';\n+\t\tslightly_different++;\n \t} else {\n \t\tcolor = color_commit;\n \t\tstatus = '=';\n+\t\tsame++;\n \t}\n \n \tstrbuf_reset(buf);\n@@ -439,12 +445,15 @@ int show_range_diff(const char *range1, const char *range2,\n \t\tres = error(_(\"could not parse log for '%s'\"), range2);\n \n \tdiffopt->color_moved = COLOR_MOVED_DEFAULT;\n+\n \tif (!res) {\n \t\tfind_exact_matches(&branch1, &branch2);\n \t\tget_correspondences(&branch1, &branch2, creation_factor);\n \t\toutput(&branch1, &branch2, diffopt);\n \t}\n \n+\tprintf(\"patch ranges are %d same, %d slightly different and %d completely different\\n\", same, slightly_different, completely_different);\n+\n \tstring_list_clear(&branch1, 1);\n \tstring_list_clear(&branch2, 1);\n \n-- \n2.18.0.597.ga71716f1ad-goog\n\n"},{"id":"355193","messageId":"20180810221857.87399-1-sbeller@google.com","threadId":"48944","inReplyTo":"CAGZ79kZR_gj00JORH3WB_T+_mgtQm5PGt6+DSMFUbJM+C4FxVw@mail.gmail.com","subject":"[PATCH] Documentation/diff-options: explain different diff algorithms","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-10T22:18:57Z","receivedAt":"2018-08-10T22:19:04Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"As a user I wondered what the diff algorithms are about. Offer at least\na basic explanation on the differences of the diff algorithms.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n\n Not sure if this is finished, I just want to put out the state that I\n have sitting on my disk.\n\n Documentation/diff-options.txt | 10 +++--\n Documentation/git-diff.txt     | 72 ++++++++++++++++++++++++++++++++++\n 2 files changed, 79 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex f394608b42c..00684b8936f 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -91,14 +91,18 @@ appearing as a deletion or addition in the output. It uses the \"patience\n diff\" algorithm internally.\n \n --diff-algorithm={patience|minimal|histogram|myers}::\n-\tChoose a diff algorithm. The variants are as follows:\n+\tChoose a diff algorithm. See the DIFF ALGORITHMS section\n+ifndef::git-diff[]\n+\tin linkgit:git-diff[1]\n+endif::git-diff[]\n+\tfor more discussion. The variants are as follows:\n +\n --\n `default`, `myers`;;\n \tThe basic greedy diff algorithm. Currently, this is the default.\n `minimal`;;\n-\tSpend extra time to make sure the smallest possible diff is\n-\tproduced.\n+\tThe same algorithm as `myers`, but spend extra time to make\n+\tsure the smallest possible diff is produced.\n `patience`;;\n \tUse \"patience diff\" algorithm when generating patches.\n `histogram`;;\ndiff --git a/Documentation/git-diff.txt b/Documentation/git-diff.txt\nindex b180f1fa5bf..8837492ed05 100644\n--- a/Documentation/git-diff.txt\n+++ b/Documentation/git-diff.txt\n@@ -119,6 +119,78 @@ include::diff-options.txt[]\n \n include::diff-format.txt[]\n \n+DIFF ALGORITHMS\n+---------------\n+\n+This section explains background on the diff algorithms. All of them\n+operate on two input sequences of symbols. In Git each symbol is\n+represented by a line of a file unless the option to diff based on\n+words is given. The following diff algorithms are available:\n+\n+`Myers`\n+\n+A diff as produced by the basic greedy algorithm described in\n+link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations].\n+with a run time of O(M + N + D^2). To understand this algorithm, one\n+can imagine a table spanned by the two input sequences with slides\n+where there are the same symbols. For example the sequences 'ABCD' and 'ADB'\n+the graph would look like\n+\n+\tS | A | B | C | A\n+\t---------------------\n+\tA | \\ |   |   | \\ |\n+\t---------------------\n+\tD |   |   |   |   |\n+\t---------------------\n+\tB |   | \\ |   |   |\n+\t---------------------\n+\t  |   |   |   |   |F\n+\n+and a greedy algorithm is used to find the cheapest path from start S to\n+finish F, with each horizontal and vertical step having a cost of one and\n+the diagonal slides having a cost of zero.\n+\n+This is simplified as the real algorithm only needs O(N+M) in terms of memory.\n+In addition it employs a heuristic to allow for a faster diff at the small\n+cost of diff size. The `minimal` algorithm has that heuristic turned off.\n+\n+`Minimal`\n+The exact algorithm as described in the `Myers` paper without the heuristic\n+that trades execution time for slightly worse diffs.\n+\n+`Patience`\n+\n+This algorithm by Bram Cohen originally for the bzr version control\n+system matches the longest common subsequence of unique lines on\n+both sides, recursively. It obtained its name by the way the longest\n+subsequence is found, as that is a byproduct of the patience sorting\n+algorithm. If there are no unique lines left it falls back to `myers`.\n+Empirically this algorithm produces a more readable output for code,\n+but it does not guarantee the shortest output.\n+\n+`Histogram`\n+\n+This algorithm by Shawn Pearce, originally implemented for\n+JGit, finds the longest common substring and recursively\n+diffs the content before and after the longest common substring.\n+If there are no common substrings left, fall back to `myers`.\n+This is often the fastest, but in corner cases (when there are\n+many common substrings of the same length) it produces unexpected\n+results as seen in:\n+\n+\tseq 1 100 >one\n+\techo 99 > two\n+\tseq 1 2 98 >>two\n+\tgit diff --no-index --histogram one two\n+\n+\n+Note how both `patience` and `histogram` use a concept that is abbreviated\n+as 'LCS' (longest common subsequence and longest common substring).\n+The longest common subsequence is a sequence of symbols that are found\n+on both sides in the same order. The symbols do not need to be adjacent.\n+The longest common substring is a sequence of adjacent symbols in order\n+on both sides.\n+\n EXAMPLES\n --------\n \n-- \n2.18.0.865.gffc8e1a3cd6-goog\n\n"}]}