From: Brian Downing <hidden> Date: 2016-06-15 22:43:21
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
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:43:21
On Thu, 12 Jul 2007, Brian Downing wrote:
On Thu, Jul 12, 2007 at 02:38:30AM -0400, Nicolas Pitre wrote:
quoted
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.
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
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:43:21
We already apply a bias on the initial delta attempt with max_size being
a function of the base object depth. This has the effect of favoring
shallower deltas even if deeper deltas could be smaller, and therefore
creating a wider delta tree (see commits 4e8da195 and c3b06a69).
This principle should also be applied to all delta attempts for the same
object and not only the first attempt. With this the criteria for the
best delta is not only its size but also its depth, so that a shallower
delta might be selected even if it is larger than a deeper one. Even if
some deltas get larger, they allow for wider delta trees making the
depth limit less quickly reached and therefore better deltas can be
subsequently found, keeping the resulting pack size even smaller.
Runtime access to the pack should also benefit from shallower deltas.
Testing on different repositories showed slighter faster repacks,
smaller resulting packs, and a much nicer curve for delta depth
distribution with no more peak at the maximum depth level.
Improvements are even more significant with smaller depth limits.
Signed-off-by: Nicolas Pitre <redacted>
---
No, I wonn't provide the full test results again. Yes, they're
different and even slightly better with this version, but I can't be
bothered to run them all and wait for the results again. You'll have to
take my word or do your own.