Keep last used delta base in the delta window

This is based on Martin Koegler's idea to keep the object that
was successfully used as the base of the delta when it is about
to fall off the edge of the window.  Instead of doing so only
for the objects at the edge of the window, this makes the window
a lru eviction mechanism.  If an entry is used as a base, it is
moved to the last of the queue to be evicted.

This is a quick-and-dirty implementation, as it keeps the original
implementation of the data structure used for the window.  This
originally was done as an array, not as an array of pointers,
because it was meant to be used as a cyclic FIFO buffer and a
plain array avoids an extra pointer indirection, while its FIFOness
eant that we are not "moving" the entries like this patch does.

The runtime from three versions were comparable.  It seems to
make the resulting chain even shorter, which can only be good.

(stock "master") 15782196 bytes
chain length = 1: 2972 objects
chain length = 2: 2651 objects
chain length = 3: 2369 objects
chain length = 4: 2121 objects
chain length = 5: 1877 objects
...
chain length = 46: 490 objects
chain length = 47: 515 objects
chain length = 48: 527 objects
chain length = 49: 570 objects
chain length = 50: 408 objects

(with your patch) 15745736 bytes (0.23% smaller)
chain length = 1: 3137 objects
chain length = 2: 2688 objects
chain length = 3: 2322 objects
chain length = 4: 2146 objects
chain length = 5: 1824 objects
...
chain length = 46: 503 objects
chain length = 47: 509 objects
chain length = 48: 536 objects
chain length = 49: 588 objects
chain length = 50: 357 objects

(with this patch) 15612086 bytes (1.08% smaller)
chain length = 1: 4831 objects
chain length = 2: 3811 objects
chain length = 3: 2964 objects
chain length = 4: 2352 objects
chain length = 5: 1944 objects
...
chain length = 46: 327 objects
chain length = 47: 353 objects
chain length = 48: 304 objects
chain length = 49: 298 objects
chain length = 50: 135 objects

[jc: this is with code simplification follow-up from Nico]

Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 23 insertions, 2 deletions

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 12509faa77..e64e3a03a0 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -1460,7 +1460,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 	do {
 		struct object_entry *entry = list[--i];
 		struct unpacked *n = array + idx;
-		int j;
+		int j, best_base = -1;
 
 		if (!entry->preferred_base)
 			processed++;
@@ -1505,6 +1505,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 
 		j = window;
 		while (--j > 0) {
+			int ret;
 			uint32_t other_idx = idx + j;
 			struct unpacked *m;
 			if (other_idx >= window)
@@ -1512,8 +1513,11 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 			m = array + other_idx;
 			if (!m->entry)
 				break;
-			if (try_delta(n, m, max_depth) < 0)
+			ret = try_delta(n, m, max_depth);
+			if (ret < 0)
 				break;
+			else if (ret > 0)
+				best_base = other_idx;
 		}
 
 		/* if we made n a delta, and if n is already at max
@@ -1523,6 +1527,23 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 		if (entry->delta && depth <= n->depth)
 			continue;
 
+		/*
+		 * Move the best delta base up in the window, after the
+		 * currently deltified object, to keep it longer.  It will
+		 * be the first base object to be attempted next.
+		 */
+		if (entry->delta) {
+			struct unpacked swap = array[best_base];
+			int dist = (window + idx - best_base) % window;
+			int dst = best_base;
+			while (dist--) {
+				int src = (dst + 1) % window;
+				array[dst] = array[src];
+				dst = src;
+			}
+			array[dst] = swap;
+		}
+
 		next:
 		idx++;
 		if (count + 1 < window)