Re: [PATCH] improved delta support for git

From: Nicolas Pitre <nico@cam.org>
Date: May 18, 2005, 04:32 UTC
Message-ID: <Pine.LNX.4.62.0505180005230.20274@localhost.localdomain>
In-Reply-To: <d6dohe$dql$1@sea.gmane.org>

On Tue, 17 May 2005, Dan Holmsand wrote:

> I've been trying out your delta stuff as well. It was a bit
> disappointing at first, but some tweaking payed off in the end...

Cool!

My goal is to provide the mechanism that can be used by a higher level implementing the deltafication policy. I only provided one script as an example, but it turns out that you found a way to achieve better space saving. And I bet you that there is probably ways to do even better with more exhaustive delta targets. For example you could try all possible combinations on an object list for each file (and let it run overnight).

> 1) Too many deltas get too big and/or compress badly.

One thing I've been wondering about is whether gzipping small deltas is actually a gain. For very small files it seems that gzip is adding more overhead making the compressed file actually larger. Might be worth storing some deltas uncompressed if the compressed version turns out to be larger.

> 2) Trees take up a big chunk of total space.

Tree objects can be deltafied as well, but I didn't had time to script it. A large space saving can be expected there as well, especially for changesets that modify only a few files deep down the tree hierarchy.

Show 6 quoted lines

> Therefore, I tried some other approaches. This one seemed to work
> best:
> 
> 1) I limit the maximum size of any delta to 10% of the size of the new
> version. That guarantees a big saving, as long as any delta is
> produced.

Well, any delta object smaller than its original object saves space, even if it's 75% of the original size. But...

Show 6 quoted lines

> 2) If the "previous" version of a blob is a delta, I produce the new
> delta form the old deltas base version. This works surprisingly well.
> I'm guessing the reason for this is that most changes are really
> small, and they tend to be in the same area as a previous change (as
> in "Commit new feature. Commit bugfix for new feature. Commit fix for
> bugfix of new feature. Delete new feature as it doesn't work...").

... but then the ultimate solution is to try out all possible references within a given list. My git-deltafy-script already finds out the list of objects belonging to the same file. Maybe git-mkdelta should try all combinations between them. This way a deeper delta chain could be allowed for maximum space saving.

> 3) I use the same method for all tree objects.

Yup.

> Attached is a patch (against current cogito). It is basically the same
> as yours, Nicolas, except for some hackery to make the above possible.
> I'm sure I've made lots of stupid mistakes in it (and the 10% limit is
> hardcoded right now; I'm lazy).

I will look at it and merge the good stuff.

Thanks for testing!

Nicolas