Re: [PATCH] Keep last used delta base in the delta window

Nicolas Pitre [off-list ref] writes:

quoted

quoted

Instead of treating the "the last used one happened to be on the
horizon -- try not to drop it" special case, I wonder if it
makes sense to float the last used delta base object early in
the window _after_ it is used.  Wouldn't we keep more than one
very recently used delta base objects in the window that way?

The attached is my quick-and-dirty one.  

I like this.  A LRU sorting of base objects is obviously a good thing to 
do.  Some comments below.

Well, I said it is Q&D, because _I_ didn't like what I did ;-).

The original implementation of window as a plain array of
"struct unpacked" made perfect sense because its use was strict
FIFO.  Adding new element and expiring oldest element was just
an increment of the "idx" integer, and there was no memmove
overhead.

If we are to make this into LRU (which I _do_ like), however,
the data structure's circular FIFO origin makes the code
unnecessary complex and inefficient, I think.

 - We can always say 0 is the bottom and (window-1) is the top.
   Then ((idx+1)%window) becomes unnecessary.  As a bonus, we do
   not have to disagree if it should be (window <= idx) or (idx
   >= window).

 - Shifting elements down to make room can become a single
   memmove() if we remove the circular FIFO origin from the
   window implementation.  The Q&D one has tons of structure
   assignments in each iteration.  It might even make sense to
   change the window itself an array of "struct unpacked *" and
   make LRU management into just memmove() of bunch of pointers.

On Wed, 29 Aug 2007, Junio C Hamano wrote:

Nicolas Pitre [off-list ref] writes:

quoted

quoted

quoted

Instead of treating the "the last used one happened to be on the
horizon -- try not to drop it" special case, I wonder if it
makes sense to float the last used delta base object early in
the window _after_ it is used.  Wouldn't we keep more than one
very recently used delta base objects in the window that way?

The attached is my quick-and-dirty one.  

I like this.  A LRU sorting of base objects is obviously a good thing to 
do.  Some comments below.

Well, I said it is Q&D, because _I_ didn't like what I did ;-).

The original implementation of window as a plain array of
"struct unpacked" made perfect sense because its use was strict
FIFO.  Adding new element and expiring oldest element was just
an increment of the "idx" integer, and there was no memmove
overhead.

If we are to make this into LRU (which I _do_ like), however,
the data structure's circular FIFO origin makes the code
unnecessary complex and inefficient, I think.

 - We can always say 0 is the bottom and (window-1) is the top.
   Then ((idx+1)%window) becomes unnecessary.  As a bonus, we do
   not have to disagree if it should be (window <= idx) or (idx
   >= window).

 - Shifting elements down to make room can become a single
   memmove() if we remove the circular FIFO origin from the
   window implementation.  The Q&D one has tons of structure
   assignments in each iteration.  It might even make sense to
   change the window itself an array of "struct unpacked *" and
   make LRU management into just memmove() of bunch of pointers.

Right.

In the mean time, here's a simplification of your code.  Given that 
runtime appears to be unchanged, this could be used as is and a separate 
patch to clean LRU handling.

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 9b3ef94..c33d00f 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c

@@ -1456,7 +1456,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++;

@@ -1501,6 +1501,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)

@@ -1508,8 +1509,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

@@ -1519,6 +1523,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)