On Tue, 12 Feb 2008, Jon Smirl wrote:
quoted text
>
> How many diffs should it take to compress a 2000 delta chain with
> window/depth=250?

There's no fixed answer. We do various culling heurstics to avoid actually 
generating a diff at all if it looks unlikely to succeed etc. But in 
general, the way the window works is that 
 (a) we only need to generate the _unpacked_ object once
 (b) we compare each object to the "window-1" preceding objects, which is 
     how I got the O(windowsize^2) 
 (c) but then that "compare" relatively seldom involves actually 
     generating a whole diff!

So the answer is: in _theory_ each object may be compared to 
(windowsize-1) other objects, but in practice it's much less than that.

			Linus
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html