{"thread":{"id":"29875","subject":"storing pre-computed fine-grained diffs","startedAt":"2012-03-07T23:41:43Z","lastAt":"2012-03-08T01:04:41Z","messageCount":2,"participants":["ecloud","David Barr"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"186361","messageId":"1331163703976-7353466.post@n2.nabble.com","threadId":"29875","inReplyTo":null,"subject":"storing pre-computed fine-grained diffs","fromName":"ecloud","fromEmail":"shawn.t.rutledge@gmail.com","sentAt":"2012-03-07T23:41:43Z","receivedAt":"2012-03-07T23:41:43Z","isPatch":false,"sender":{"key":"shawn.t.rutledge@gmail.com","avatar":null},"body":"The thing about git, as well as all version control systems I have known so\nfar which store diffs, is that computing the diff means post-analyzing a\nsaved file.  That is, you use any editor you like, and after making a whole\nbatch of changes you manually commit to the repository, and the diff\nalgorithm figures out what you changed.  Some information is already lost\nabout what order you made the changes and what the logical chunks actually\nwere.  But what if there was an editor that could save each individual\nchange as a separate version?  You put the cursor at one point in the file,\nand type some text; then you click elsewhere, and the editor does a \"git\ncommit this-file\" automatically.  Then you select some other text and delete\nit, and it does a commit again.  It would be nice in that case to avoid\ndoing the diff at all, because the editor already knows exactly what the\nchange was.  Would it be possible to store these fine-grained changes\ndirectly in a packfile, efficiently?  Or would it require a different\nstorage format?  I know the diff algorithm used is already much smarter than\na line-by-line diff, but is the storage format capable of representing\nchanges over ranges of characters without \"extra context\" like the\nline-by-line diffs usually have?\n\n--\nView this message in context: http://git.661346.n2.nabble.com/storing-pre-computed-fine-grained-diffs-tp7353466p7353466.html\nSent from the git mailing list archive at Nabble.com.\n"},{"id":"186367","messageId":"CAFfmPPNjzyDXH+CQr39wcsGEOj9g=fgon==7WyOD=kTDT9MpEg@mail.gmail.com","threadId":"29875","inReplyTo":"1331163703976-7353466.post@n2.nabble.com","subject":"Re: storing pre-computed fine-grained diffs","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2012-03-08T01:04:41Z","receivedAt":"2012-03-08T01:04:41Z","isPatch":false,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"Hi Shawn,\n\nOn Thu, Mar 8, 2012 at 10:41 AM, ecloud <shawn.t.rutledge@gmail.com> wrote:\n> The thing about git, as well as all version control systems I have known so\n> far which store diffs, is that computing the diff means post-analyzing a\n> saved file.  That is, you use any editor you like, and after making a whole\n> batch of changes you manually commit to the repository, and the diff\n> algorithm figures out what you changed.  Some information is already lost\n> about what order you made the changes and what the logical chunks actually\n> were.  But what if there was an editor that could save each individual\n> change as a separate version?  You put the cursor at one point in the file,\n> and type some text; then you click elsewhere, and the editor does a \"git\n> commit this-file\" automatically.\n\nI'm going to skip discussing whether this approach is desirable.\nAll further comment will assume that it is worthwhile.\n\n> Then you select some other text and delete\n> it, and it does a commit again.  It would be nice in that case to avoid\n> doing the diff at all, because the editor already knows exactly what the\n> change was.\n\nThis is just a performance consideration. Two relevant facts are that\nthe delta computation in git is at its fastest when the difference is\nsmall and that SHA1 computation imposes a per-change cost proportional\nto the length of the blob.\n\n> Would it be possible to store these fine-grained changes\n> directly in a packfile, efficiently?  Or would it require a different\n> storage format?  I know the diff algorithm used is already much smarter than\n> a line-by-line diff, but is the storage format capable of representing\n> changes over ranges of characters without \"extra context\" like the\n> line-by-line diffs usually have?\n\nThe current pack format for git has quite an efficient delta\nrepresentation. It uses a byte-wise binary diff, so there is no\ncontext in the physical representation. It is possible to build a pack\nas described using the fast-import interface, and it would be\nstraightforward to write an editor backend that persisted via\nfast-import. (Assuming that you are hacking on an editor.)\n\n--\nDavid Barr\n"}]}