git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: GNU diff and git diff - difference on myers algorithm?

From
Johannes Schindelin <johannes.schindelin@gmx.de>
Date
Jun 9, 2015, 08:25 UTC
Message-ID
<0add7d95076f5b112af90d8566c29203@www.dscho.org>
In-Reply-To
<CAB=NE6XRnKAY6t+dxT7vO_4wqngXvULh-CqezEAs2r99FkNCTg@mail.gmail.com>
Hi Luis,
On 2015-06-08 20:34, Luis R. Rodriguez wrote:
> Based on a cursory review of the git code I get the impression that
> GNU diff and git 'diff' do not share any code for the possible diff
> algorithms.
Indeed, Git's diff machinery is based[*1*] ofn libxdiff[*2*], not on GNU diff.
> I'm in particularly curious more about the default "myers"
> algorithm.
Are you looking for a freely available implementation of the Myers algorithm? Or are you interested in understanding it?
Please note that Myers' algorithm is just one first step in most diff implementations (and that other diff algorithms have become popular, in particular because comparing strings can be accelerated by hashing the text lines first, and those hashes can also be used to identify matching pairs of unique lines, giving rise to yet another huge performance boost for typical uses).
The reason why Myers' algorithm is not sufficient for diff implementations is that it only optimizes the "edit distance", i.e. the amount of added/removed lines, while patches should be readable, too, i.e. prefer *consecutive* edits to disjunct ones.
Just to mention one post-processing technique that is so useful that I implemented it for Git[*3*]: the "patience diff" algorithm of Bram Cohen (of BitTorrent fame) finds matching pairs of unique lines -- think of a function from which another function is refactored, for example, intuitively you want the diff to keep the signature of the original function as a context line.
Disclaimer: While it is true that Gene and I shared an office for one month, and that I am once again working in the same institute as he does, all my knowledge about this algorithm stems from my reading his paper and implementing the algorithm in Java for use in JGit[*3*].
> I can take time to do a precise code review of the
> algorithms used on both GNU diff and git but if someone can already
> vet for any differences that'd be appreciated as it would save time.
Again, I am curious what your goal is? I am sure I can support your quest better when I understand what the purpose of this code review should be.

Ciao, Johannes

Footnote *1*: https://github.com/git/git/commit/3443546f6ef57fe28ea5cca232df8e400bfc3883 Footnote *2*: http://www.xmailserver.org/xdiff-lib.html Footnote *3*: https://github.com/git/git/blob/master/xdiff/xpatience.c Footnote *4*: https://github.com/eclipse/jgit/blob/master/org.eclipse.jgit/src/org/eclipse/jgit/diff/MyersDiff.java

Previous: Luis R. RodriguezNext: Luis R. Rodriguez
Message 2 of 6 in “GNU diff and git diff - difference on myers algorithm?”
  1. Luis R. RodriguezJun 8, 2015
  2. Johannes SchindelinJun 9, 2015
  3. Luis R. RodriguezJun 12, 2015
  4. Luis R. RodriguezJul 16, 2015
  5. Jacob KellerJul 17, 2015
  6. Jacob KellerJul 17, 2015

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.