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

From: Nicolas Pitre <nico@cam.org>
Date: Jul 12, 2007, 16:27 UTC
Message-ID: <alpine.LFD.0.999.0707121146550.32552@xanadu.home>
In-Reply-To: <20070712152016.GB19073@lavos.net>

On Thu, 12 Jul 2007, Brian Downing wrote:

Show 31 quoted lines

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

Hmmm... Integer truncation errors.

In theory, the allowed max_size should be slightly higher than what we got in the depth 5 case because this case is less deep. So...

    max_size = trg_entry->delta_size * max_depth /
                    (max_depth - trg_entry->depth + 1);
    max_size = 11 * 100 / (100 - 5 + 1) = 11.4583

    max_size = max_size * (max_depth - src_entry->depth) / max_depth;
    max_size = 11.4583 * (100 - 2) / 100 = 11.2292

So the max_size, because the depth is less, is slightly higher.

Show 6 quoted lines

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

Better yet, the integer truncation error should be compensated for, with this:

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

Nicolas