Re: [PATCH] apply delta depth bias to already deltified objects

From: Brian Downing <bdowning@lavos.net>
Date: Jul 12, 2007, 15:20 UTC
Message-ID: <20070712152016.GB19073@lavos.net>
In-Reply-To: <alpine.LFD.0.999.0707120049120.32552@xanadu.home>

On Thu, Jul 12, 2007 at 02:38:30AM -0400, Nicolas Pitre wrote:

> This apparently makes BRian's patological case worse (although better 
> than before his same-size-shallower patch), but I think that the 
> improvement in the general case is worth it.  Even Brian's pack gets 
> smaller so...

I've found why this makes my case worse, and I think it's correctable and will benefit everything when fixed:

Let's say we've currently got a delta match of 11 bytes at depth 5. So trg_entry->delta_size = 11 and trg_entry->depth = 5. max_depth is 100.

Now let's say the next object we're comparing against is at depth 2 (src_entry->depth = 2). Even if we can find a delta of the same size we should take it.

Now, with Nico's new patch:

		max_size = trg_entry->delta_size * max_depth /
				(max_depth - trg_entry->depth + 1);

max_size is now 11.  So far so good.

Now, however, the other bias happens:

	max_size = max_size * (max_depth - src_entry->depth) / max_depth;

    max_size = 11 * (100 - 2) / 100;
    max_size = 1078 / 100;
    max_size = 10;

This was okay when max_size was always (trg_size/2 - 20) here, but now it's cutting it off too much. max_size is now 10, and we can't make a better depth match of the same size anymore.

I think the second bias equation should be scaled so as not to take effect unless (src_entry->depth [+ 1?] > trg_entry->depth).

Other than this flaw I think this patch looks great.

-bcd