Re: Preferring shallower deltas on repack

From: Junio C Hamano <gitster@pobox.com>
Date: Jul 9, 2007, 05:31 UTC
Message-ID: <7v1wfixhvk.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <20070709044326.GH4087@lavos.net>

bdowning@lavos.net (Brian Downing) writes:

Show 19 quoted lines

> I modified this to prefer shallower deltas of the same size.  This made
> the deltas for this file a very wide tree with a maximum depth of about
> 65.  Other (much smaller) improvements were seen elsewhere in the pack.
> Runtime does not seem to have been affected, as most of the work had
> already been done when it was tossing deltas before.
>
> Some simple statistics:
>
> SBCL, standard pack-objects, window 100, depth 1000:
>   Max depth: 980
>   Mean depth: 100.223622114502
>   Median depth: 12
>   Standard deviation: 188.214331919176
>
> SBCL, patched pack-objects, window 100, depth 1000:
>   Max depth: 787
>   Mean depth: 61.5669990817656
>   Median depth: 11
>   Standard deviation: 127.644652607399

Putting aside a potential argument that the way the file in question, version.lisp-expr, is kept track of might be insane, this is an interesting topic.

In addition to the above stats, it may be interesting to know:

 - pack generation time and memory footprint (/usr/bin/time);

   I suspect you would have to try_delta more candidates, so
   this may degrade a bit, but that is done for getting a better
   deltification, so we would need to see if the extra cost is
   within reason and worth spending.

 - resulting pack size (ls -l pack-*.pack)

   I do not expect your change would degrade in this area, as
   you are currently not trading size with shallower delta
   depth.

Regarding your patch, I think it does not look too bad, as you never pick delta that is larger than the best-so-far in favor of shallower depth.

It would become worrysome (*BUT* infinitely more interesting) once you start talking about a tradeoff between slightly larger delta and much shorter delta. Such a tradeoff, if done right, would make a lot of sense, but I do not offhand think of a way to strike a proper balance between them efficiently.