Re: [PATCH] improved delta support for git

From: Dan Holmsand <holmsand@gmail.com>
Date: May 18, 2005, 08:54 UTC
Message-ID: <d6evrk$jv2$1@sea.gmane.org>
In-Reply-To: <Pine.LNX.4.62.0505180005230.20274@localhost.localdomain>

Nicolas Pitre wrote:

Show 7 quoted lines

> 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).

Well, any kind of deltafication of, say, the complete kernel history pretty much has to run overnight anyway :-)

Show 5 quoted lines

> 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.

It's probably better to skip deltafication of very small files altogether. Big pain for small gain, and all that.

Show 7 quoted lines

>>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...

That's not true if you want to keep the delta chain length down (and thus performance up).

Then, the most efficient approach is to generate many deltas against the same base file (otherwise, you only get 50% delta files with a maximum delta depth of 1).

But in this case, the trick is to know when to stop deltafying against one base file, and start over with another. If you switch to a new keyframe too often, you obviously lose some potential savings. But if you don't switch often enough, you end up repeating the same data in too many delta files.

A maximum delta size of 10% turned out to be ideal for at least the "fs" 
  tree. 8% was significantly worse, as was 15%. (The ideal size depends 
on  how big the average change is: the smaller the average change, the 
smaller the max delta size should be).

Show 5 quoted lines

> ... 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.

Yeah. But then you lose the ability to do incremental deltafication, or deltafication on-the-fly. And it would be really, really nice to have git do deltas at commit time - that way you could keep the very cool "immutable objects" property of git, while still saving a lot of space.

> I will look at it and merge the good stuff.

Cool! Thanks!

/dan