Re: Preferring shallower deltas on repack

[Nicolas Pitre <nico@cam.org>]

On Sun, 8 Jul 2007, Junio C Hamano wrote:

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

We already do something similar to that with max_size being a function 
of the delta depth.  This already has the effect of favoring shalower 
deltas even if deeper deltas could be smaller, and therefore creating a 
wider delta tree (see commits 4e8da195 and c3b06a69).

Maybe this max_size curve could be modified a bit to increase the bias 
towards shallow deltas even in the case where a delta was already found 
instead of the current constant flat curve.

[...]

OK here it is.  And results on the GIT repo and another patalogical test 
repo I keep around are actually really nice!  Not only the pack itself 
is a bit smaller, but the delta depth distribution as shown by 
git-verify-pack -v is much nicer with the bulk of deltas in the low 
depth end of the spectrum and no more peak at the max depth level.

Signed-off-by: Nicolas Pitre <nico@cam.org>
---

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 54b9d26..1eb86ed 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -1332,12 +1332,14 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
 
 	/* Now some size filtering heuristics. */
 	trg_size = trg_entry->size;
-	max_size = trg_size/2 - 20;
+	if (!trg_entry->delta)
+		max_size = trg_size/2 - 20;
+	else
+		max_size = trg_entry->delta_size * max_depth /
+				(max_depth - trg_entry->depth + 1);
 	max_size = max_size * (max_depth - src_entry->depth) / max_depth;
 	if (max_size == 0)
 		return 0;
-	if (trg_entry->delta && trg_entry->delta_size <= max_size)
-		max_size = trg_entry->delta_size;
 	src_size = src_entry->size;
 	sizediff = src_size < trg_size ? trg_size - src_size : 0;
 	if (sizediff >= max_size)