[PATCH] simple euristic for further free packing improvements

From: Nicolas Pitre <nico@cam.org>
Date: May 15, 2006, 15:40 UTC
Message-ID: <Pine.LNX.4.64.0605151129540.18071@localhost.localdomain>
In-Reply-To: <Pine.LNX.4.64.0605132305580.18071@localhost.localdomain>

Given that the early eviction of objects with maximum delta depth may exhibit bad packing on its own, why not considering a bias against deep base objects in try_delta() to mitigate that bad behavior.

This patch adjust the MAX_size allowed for a delta based on the depth of the base object as well as enabling the early eviction of max depth objects from the object window. When used separately, those two things produce slightly better and much worse results respectively. But their combined effect is a surprising significant packing improvement.

With this really simple patch the GIT repo gets nearly 15% smaller, and the Linux kernel repo about 5% smaller, with no significantly measurable CPU usage difference.

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

---

diff --git a/pack-objects.c b/pack-objects.c
index 523a1c7..b0388d7 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr
 
 	/* Now some size filtering euristics. */
 	size = trg_entry->size;
-	max_size = size / 2 - 20;
-	if (trg_entry->delta)
+	max_size = (size/2 - 20) / (src_entry->depth + 1);
+	if (trg_entry->delta && trg_entry->delta_size <= max_size)
 		max_size = trg_entry->delta_size-1;
 	src_size = src_entry->size;
 	sizediff = src_size < size ? size - src_size : 0;
@@ -1128,15 +1128,12 @@ static void find_deltas(struct object_en
 			if (try_delta(n, m, m->index, depth) < 0)
 				break;
 		}
-#if 0
 		/* if we made n a delta, and if n is already at max
 		 * depth, leaving it in the window is pointless.  we
 		 * should evict it first.
-		 * ... in theory only; somehow this makes things worse.
 		 */
 		if (entry->delta && depth <= entry->depth)
 			continue;
-#endif
 		idx++;
 		if (idx >= window)
 			idx = 0;