Re: storing pre-computed fine-grained diffs

From: David Barr <davidbarr@google.com>
Date: Mar 8, 2012, 01:04 UTC
Message-ID: <CAFfmPPNjzyDXH+CQr39wcsGEOj9g=fgon==7WyOD=kTDT9MpEg@mail.gmail.com>
In-Reply-To: <1331163703976-7353466.post@n2.nabble.com>

Hi Shawn,

On Thu, Mar 8, 2012 at 10:41 AM, ecloud <shawn.t.rutledge@gmail.com> wrote:

Show 10 quoted lines

> The thing about git, as well as all version control systems I have known so
> far which store diffs, is that computing the diff means post-analyzing a
> saved file.  That is, you use any editor you like, and after making a whole
> batch of changes you manually commit to the repository, and the diff
> algorithm figures out what you changed.  Some information is already lost
> about what order you made the changes and what the logical chunks actually
> were.  But what if there was an editor that could save each individual
> change as a separate version?  You put the cursor at one point in the file,
> and type some text; then you click elsewhere, and the editor does a "git
> commit this-file" automatically.

I'm going to skip discussing whether this approach is desirable. All further comment will assume that it is worthwhile.

> Then you select some other text and delete
> it, and it does a commit again.  It would be nice in that case to avoid
> doing the diff at all, because the editor already knows exactly what the
> change was.

This is just a performance consideration. Two relevant facts are that the delta computation in git is at its fastest when the difference is small and that SHA1 computation imposes a per-change cost proportional to the length of the blob.

Show 6 quoted lines

> Would it be possible to store these fine-grained changes
> directly in a packfile, efficiently?  Or would it require a different
> storage format?  I know the diff algorithm used is already much smarter than
> a line-by-line diff, but is the storage format capable of representing
> changes over ranges of characters without "extra context" like the
> line-by-line diffs usually have?

The current pack format for git has quite an efficient delta representation. It uses a byte-wise binary diff, so there is no context in the physical representation. It is possible to build a pack as described using the fast-import interface, and it would be straightforward to write an editor backend that persisted via fast-import. (Assuming that you are hacking on an editor.)

-- David Barr