{"thread":{"id":"27560","subject":"diff'ing files ...","startedAt":"2011-06-06T18:49:04Z","lastAt":"2011-06-12T01:02:37Z","messageCount":8,"participants":["Albretch Mueller","Jeff King","Nicolas Pitre","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"169389","messageId":"BANLkTi=1vaoLVmhyahDttmUmqw7RTp=8-A@mail.gmail.com","threadId":"27560","inReplyTo":null,"subject":"diff'ing files ...","fromName":"Albretch Mueller","fromEmail":"lbrtchx@gmail.com","sentAt":"2011-06-06T18:49:04Z","receivedAt":"2011-06-06T18:49:04Z","isPatch":false,"sender":{"key":"lbrtchx@gmail.com","avatar":null},"body":" I research on collaborative editing/revision control utilities\n(related mostly to NLP) and at the corpora list\n~\n http://listserv.linguistlist.org/cgi-bin/wa?A1=ind1106&L=CORPORA#18\n~\n ([Corpora-List] Managing texts and their edition history ...) they\ntold me they use git. However at:\n~\n http://git-scm.com/documentation\n~\n I could not find specific information on what diff'ing algorithm does\ngit use. Any white papers about git internals, mostly about its\ndiff'ing and synching algorithm? (and I am not scared at all of\n\"Directed Acyclic Graph\" or any kind of Math terminology; in fact, I\nlove it ;-))\n~\n Also, of the wave of git related or general books coming out, which\none actually explains the general concepts behind distributed version\nControl? Again, my ultimate interest is not computer\nprogramming/compiler-fed languages, but there is much that can be\nlearned from them\n~\n Thank you\n lbrtchx\n"},{"id":"169419","messageId":"20110606224356.GC13697@sigill.intra.peff.net","threadId":"27560","inReplyTo":"BANLkTi=1vaoLVmhyahDttmUmqw7RTp=8-A@mail.gmail.com","subject":"Re: diff'ing files ...","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-06-06T22:43:56Z","receivedAt":"2011-06-06T22:43:56Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 06, 2011 at 06:49:04PM +0000, Albretch Mueller wrote:\n\n>  I could not find specific information on what diff'ing algorithm does\n> git use. Any white papers about git internals, mostly about its\n> diff'ing and synching algorithm? (and I am not scared at all of\n> \"Directed Acyclic Graph\" or any kind of Math terminology; in fact, I\n> love it ;-))\n\nIt depends on what level you want to talk about. Each commit has a tree\nstate represented by a single \"tree object\". Each tree object is a list\nof paths mapping to more objects, each of which may be a binary stream\nof data (\"blob\") or another tree object (i.e., a subtree).\n\nDiffing commits means diffing their trees. Diffing trees means looking\nfor blobs at the same path in each commit and diffing them[1]. How we\ndiff the content in the blobs depends on:\n\n  1. any external diff configuration (e.g., GIT_EXTERNAL_DIFF in the\n     environment, or a per-file diff driver; see \"git help attributes\").\n     In that case, we just show whatever output the external diff\n     produces.\n\n  2. We use xdiff by default, which does a line-oriented diff using the\n     Myers algorithm (just like most \"diff\" implementations). See\n     xdiff/xdiffi.c in the git source, or Myers \"An O(ND) Difference\n     Algorith and its Variations\".\n\n  3. If you give the --patience option, we use the patience algorithm\n     instead:\n\n       http://bramcohen.livejournal.com/73318.html\n\n     That's the inventor's original description, but you can find other\n     discussion by googling for \"patience diff\".\n\n  4. If you use --word-diff (or --color-words), we find differences by\n     line, and then break lines down by configurable delimiters into\n     words, and then do a Myers diff on the resulting list of words.\n\n  5. If files are not text, we usually just say \"Binary files differ\"\n     (like most diff implementations). We can also generate binary\n     diffs, though I don't know offhand the details of the algorithm.\n\nI think that more or less covers 2-way diffing. There's also a 3-way\ncomparison when merging, both at the tree level and at the blob level.\nSyncing actually has very little to do with our regular diffing. We\ngenerate compact binary deltas (just like in (5) above) between objects,\nregardless of their path, and send the other side a set of needed\nobjects. This is the same format used for compact \"packfile\" storage.\nIf the last bit of that paragraph didn't make any sense, then read up on\ngit's object model in something like \"Pro Git\":\n\n  http://progit.org/book/ch9-0.html\n\n-Peff\n\n[1] Actually, tree comparisons are a little more complex than I made\nthem out to be. For instance, a path might exist on only one side (which\nwe usually show as a comparison to an empty blob), or might exist as a\ntree on one side and a blob on the other. We also look for renames of\npaths at the blob level by looking for similar blobs.\n"},{"id":"169511","messageId":"BANLkTinwSembzVk4gSYSvsRdHhDfqizkyg@mail.gmail.com","threadId":"27560","inReplyTo":"20110606224356.GC13697@sigill.intra.peff.net","subject":"Re: diff'ing files ...","fromName":"Albretch Mueller","fromEmail":"lbrtchx@gmail.com","sentAt":"2011-06-07T22:12:35Z","receivedAt":"2011-06-07T22:12:35Z","isPatch":false,"sender":{"key":"lbrtchx@gmail.com","avatar":null},"body":"> ... binary diffs, though I don't know offhand the details of the algorithm.\n~\n this is the part that I need ;-)\n~\n Reading the source code without knowing the basic underlying\nideas/algorithm (just an outline if possible) won't help much\n~\n Thank you\n lbrtchx\n"},{"id":"169512","messageId":"20110607221948.GA10104@sigill.intra.peff.net","threadId":"27560","inReplyTo":"BANLkTinwSembzVk4gSYSvsRdHhDfqizkyg@mail.gmail.com","subject":"Re: diff'ing files ...","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-06-07T22:19:48Z","receivedAt":"2011-06-07T22:19:48Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 07, 2011 at 10:12:35PM +0000, Albretch Mueller wrote:\n\n> > ... binary diffs, though I don't know offhand the details of the algorithm.\n> ~\n>  this is the part that I need ;-)\n> ~\n>  Reading the source code without knowing the basic underlying\n> ideas/algorithm (just an outline if possible) won't help much\n\nYou could read the comments in the source:\n\n  $ head -n 7 diff-delta.c\n  /*\n   * diff-delta.c: generate a delta between two buffers\n   *\n   * This code was greatly inspired by parts of LibXDiff from Davide Libenzi\n   * http://www.xmailserver.org/xdiff-lib.html\n   *\n   * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007\n\nAccording to the xdiff page linked:\n\n  For binary files, LibXDiff implements both (with some modification)\n  the algorithm described in File System Support for Delta Compression\n  by Joshua P.  MacDonald, and the algorithm described in Fingerprinting\n  By Random Polynomials by Michael O. Rabin.\n\nNicolas (cc'd) might be able to say what, if any, substantive changes\nwere made from those works.\n\n-Peff\n"},{"id":"169831","messageId":"alpine.LFD.2.00.1106092145390.2142@xanadu.home","threadId":"27560","inReplyTo":"20110607221948.GA10104@sigill.intra.peff.net","subject":"Re: diff'ing files ...","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2011-06-10T02:19:54Z","receivedAt":"2011-06-10T02:19:54Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 7 Jun 2011, Jeff King wrote:\n\n> On Tue, Jun 07, 2011 at 10:12:35PM +0000, Albretch Mueller wrote:\n> \n> > > ... binary diffs, though I don't know offhand the details of the algorithm.\n> > ~\n> >  this is the part that I need ;-)\n> > ~\n> >  Reading the source code without knowing the basic underlying\n> > ideas/algorithm (just an outline if possible) won't help much\n> \n> You could read the comments in the source:\n> \n>   $ head -n 7 diff-delta.c\n>   /*\n>    * diff-delta.c: generate a delta between two buffers\n>    *\n>    * This code was greatly inspired by parts of LibXDiff from Davide Libenzi\n>    * http://www.xmailserver.org/xdiff-lib.html\n>    *\n>    * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007\n> \n> According to the xdiff page linked:\n> \n>   For binary files, LibXDiff implements both (with some modification)\n>   the algorithm described in File System Support for Delta Compression\n>   by Joshua P.  MacDonald, and the algorithm described in Fingerprinting\n>   By Random Polynomials by Michael O. Rabin.\n> \n> Nicolas (cc'd) might be able to say what, if any, substantive changes\n> were made from those works.\n\nThe libxdiff code was pretty generic so to be highly portable and usable \nfor many application types.  What I did is to get rid of everything that \ngit strictly didn't need in order to make the code as simple as \npossible, and most importantly as fast as possible.  And then the code \nwas optimized even further, sacrificing on clarity a bit, to make it \neven faster.  Since this code is the very inner loop of every delta \nsearch for best delta matches, every bit of optimization counts.\n\nAnd then further modifications were made to avoid pathological corner \ncases which were taking too much time for little gain in the Git \ncontext.\n\nI also changed the output encoding to make it tighter.\n\nSo, strictly speaking, the current code in Git doesn't bear any \nresemblance with the libxdiff code at all.  However the basic algorithm \nbehind both implementations is the same.  Studying the libxdiff version \nis probably easier in order to gain an understanding of how this works.\n\n\nNicolas\n"},{"id":"169844","messageId":"m34o3xesqn.fsf@localhost.localdomain","threadId":"27560","inReplyTo":"alpine.LFD.2.00.1106092145390.2142@xanadu.home","subject":"Re: diff'ing files ...","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-06-10T13:12:29Z","receivedAt":"2011-06-10T13:12:29Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Nicolas Pitre <nico@fluxnic.net> writes:\n> On Tue, 7 Jun 2011, Jeff King wrote:\n> > On Tue, Jun 07, 2011 at 10:12:35PM +0000, Albretch Mueller wrote:\n> > \n> > > > ... binary diffs, though I don't know offhand the details of the algorithm.\n> > > ~\n> > >  this is the part that I need ;-)\n\n[...]\n\n> > According to the xdiff page linked:\n> > \n> >   For binary files, LibXDiff implements both (with some modification)\n> >   the algorithm described in File System Support for Delta Compression\n> >   by Joshua P.  MacDonald, and the algorithm described in Fingerprinting\n> >   By Random Polynomials by Michael O. Rabin.\n> > \n> > Nicolas (cc'd) might be able to say what, if any, substantive changes\n> > were made from those works.\n> \n> The libxdiff code was pretty generic so to be highly portable and usable \n> for many application types.  What I did is to get rid of everything that \n> git strictly didn't need in order to make the code as simple as \n> possible, and most importantly as fast as possible. [...]\n> \n> And then further modifications were made to avoid pathological corner \n> cases which were taking too much time for little gain in the Git \n> context.\n> \n> I also changed the output encoding to make it tighter.\n\nNicolas, do you know how binary diff used by git compares with respect\nto performance and compression with other binary diff algorithms:\n\n  * original LibXDiff\n  * bsdiff\n  * xdelta (vcdif algorithm)\n  * vbindiff\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"169861","messageId":"alpine.LFD.2.00.1106101612060.2142@xanadu.home","threadId":"27560","inReplyTo":"m34o3xesqn.fsf@localhost.localdomain","subject":"Re: diff'ing files ...","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2011-06-10T20:37:32Z","receivedAt":"2011-06-10T20:37:32Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 10 Jun 2011, Jakub Narebski wrote:\n\n> Nicolas Pitre <nico@fluxnic.net> writes:\n> > The libxdiff code was pretty generic so to be highly portable and usable \n> > for many application types.  What I did is to get rid of everything that \n> > git strictly didn't need in order to make the code as simple as \n> > possible, and most importantly as fast as possible. [...]\n> > \n> > And then further modifications were made to avoid pathological corner \n> > cases which were taking too much time for little gain in the Git \n> > context.\n> > \n> > I also changed the output encoding to make it tighter.\n> \n> Nicolas, do you know how binary diff used by git compares with respect\n> to performance and compression with other binary diff algorithms:\n> \n>   * original LibXDiff\n>   * bsdiff\n>   * xdelta (vcdif algorithm)\n>   * vbindiff\n\nNo idea.  But you can test that pretty easily if you wish.  I would be \ninterested in the results of course. Just do:\n\n\tmake test-delta\n\nand then, to compress something:\n\n\t./test-delta -d <input_file> <reference_file> <output_file>\n\nOf course this will produce <output_file> which is only the bare binary \ndiff annotation data against the reference file.  In Git that output is \nalso deflated with zlib, before it is stored in a pack.  The other \nbinary diff tools are usually doing a similar post-deflation pass as \nwell.\n\nIt should be noted that the algorithm that Git uses won't produce the \nabsolute smallest output.  When I tried that, computation time went up \nof course, but surprizingly the final deflated result was slightly \n_larger_ as well, probably due to the fact that zlib was less efficient \nwith the increased randomness in the tighter delta output to deflate.\n\n\nNicolas\n"},{"id":"169884","messageId":"BANLkTinpYMdLLOj62O=3=ALWsdBiECHR1g@mail.gmail.com","threadId":"27560","inReplyTo":"alpine.LFD.2.00.1106101612060.2142@xanadu.home","subject":"Re: diff'ing files ...","fromName":"Albretch Mueller","fromEmail":"lbrtchx@gmail.com","sentAt":"2011-06-12T01:02:37Z","receivedAt":"2011-06-12T01:02:37Z","isPatch":false,"sender":{"key":"lbrtchx@gmail.com","avatar":null},"body":"> further modifications were made to avoid pathological corner cases ...\n~\n Nicolas, did you keep test samples of those pathological corner cases\nyou would share?\n~\n lbrtchx\n"}]}