Re: Huge win, compressing a window of delta runs as a unit

From: Shawn Pearce <spearce@spearce.org>
Date: Aug 21, 2006, 07:06 UTC
Message-ID: <20060821070609.GC24054@spearce.org>
In-Reply-To: <Pine.LNX.4.64.0608181057440.11359@localhost.localdomain>

Nicolas Pitre <nico@cam.org> wrote:

Show 12 quoted lines

> On Fri, 18 Aug 2006, Jon Smirl wrote:
> 
> > On 8/18/06, Nicolas Pitre <nico@cam.org> wrote:
> > > A better way to get such a size saving is to increase the window and
> > > depth parameters.  For example, a window of 20 and depth of 20 can
> > > usually provide a pack size saving greater than 11% with none of the
> > > disadvantages mentioned above.
> > 
> > Our window size is effectively infinite. I am handing him all of the
> > revisions from a single file in optimal order. This includes branches.
> 
> In GIT packing terms this is infinite delta _depth_ not _window_.

We're not using infinite anything.

fast-import is basically doing window=1 and depth=10.

We only examine the last blob to see if we can get a delta against it. If we do we write that delta out; otherwise we reset our delta chain and write the complete object. We also reset our chain after writing out 10 deltas, each of which used the immediately prior object as its base.

Since I just found out that in some cases the Mozilla repository has
1000s of revisions per file[*1*] and in others only 1 revision per
file we probably should be adjusting this depth to have a maximum
of 500 while also having the frontend send us a "I'm switching
files now" marker so we know to not even bother trying to delta
the new blob against the last blob as they are likely to not
delta well[*2*].

> Default delta params (window=10 depth=10) : 122103455 
> Agressive deltas (window=50 depth=5000) : 105870516
> Agressive and grouped deltas (window=50 depth=5000 : 99860685

Although complex the aggressive and grouped deltas appears to have saved you 18.2% on this repository. That's not something to ignore. A reasonably optimal local pack dictionary could save at least 4%[*3*]. Whacking 22% off a 400 MB pack is saving 88 MB. Transferring that over the network on an initial clone is like downloading all of Eclipse. Or an uncompressed kernel tarball...

[*1*] Jon noted this in another email in this thread but I'm too
      lazy to lookup the hyperlink right now.

[*2*] Granted in some cases they may delta very well against each
      other but I think the probablity of that occuring is low
	  enough that its not worth worrying about in fast-import.c;
	  we can let repack's strategy deal with it instead.

[*3*] I wrote a brain-dead simple local dictionary selecter in Perl.
      Its horribly far from being ideal.  But it is consistently
      saving us 4% on the GIT and the Mozilla repository and its
	  pretty darn fast.  Shockingly the C keywords didn't gain
	  us very much here; its project specific text that's the
	  real win.

	  Looking at chunks which are frequently copied in deltas
	  from base objects and breaking those chunks up into
	  smaller common chunks, then loading those most frequent
	  common chunks into the pack dictionary would most likely
	  produce far better results.

-- 
Shawn.