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

From

Junio C Hamano <gitster@pobox.com>

Date

Aug 27, 2007, 12:12 UTC

Message-ID

<7vy7fxyy52.fsf@gitster.siamese.dyndns.org>

In-Reply-To

<7v3ay5l5wq.fsf@gitster.siamese.dyndns.org>

Junio C Hamano <gitster@pobox.com> writes:

> Martin Koegler <mkoegler@auto.tuwien.ac.at> writes:
>
>> Keeping the last used delta base object, if it would be dropped,
>> supports creating smaller packs with shorter delta chains.
>
> 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.  

---

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 9b3ef94..2a5ea29 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -1439,6 +1439,61 @@ static void free_unpacked(struct unpacked *n)
 	n->depth = 0;
 }
 
+static void shift_base(int idx, int window, struct unpacked *array, struct object_entry *delta_base)
+{
+	/*
+	 * The delta_base was a useful one to deltify the object at
+	 * idx (circular).  Shift the contents of array (circular
+	 * buffer) so that it will be evicted last.
+	 */
+	int good_base, good_at;
+	struct unpacked swap;
+
+	for (good_base = 0; good_base < window; good_base++)
+		if (array[good_base].entry == delta_base)
+			break;
+	if (window <= good_base)
+		die("Junio is an idiot");
+
+	if (window <= ++idx)
+		idx = 0;
+	/*
+	 * The entry at idx modulo window will be evicted first during
+	 * the next round.  Where in the next window is the good_base
+	 * found?
+	 */
+	good_at = (good_base + window - idx) % window;
+
+	/*
+	 * If it is already at the furthest edge, nothing needs to be done.
+	 */
+	if (good_at == window - 1)
+		return;
+
+	/*
+	 * Otherwise, stash it away, shift the others down and swap it in.
+	 */
+	swap = array[good_base];
+
+	while (good_at < window) {
+		int dst, src;
+
+		dst = good_at + idx;
+		if (window <= dst)
+			dst -= window;
+		src = dst + 1;
+		if (window <= src)
+			src -= window;
+		array[dst] = array[src];
+		good_at++;
+	}
+
+	good_at = idx + window - 1;
+	if (window <= good_at)
+		good_at -= window;
+	array[good_at] = swap;
+}
+
 static void find_deltas(struct object_entry **list, int window, int depth)
 {
 	uint32_t i = nr_objects, idx = 0, count = 0, processed = 0;
@@ -1519,6 +1574,13 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 		if (entry->delta && depth <= n->depth)
 			continue;
 
+		/*
+		 * The delta base was a useful one.  Move it up in the
+		 * window to keep it longer.
+		 */
+		if (entry->delta)
+			shift_base(idx, window, array, entry->delta);
+
 		next:
 		idx++;
 		if (count + 1 < window)