On Wed, 29 Aug 2007, Junio C Hamano wrote:
> Nicolas Pitre <nico@xxxxxxx> writes:
>
> >> > 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)
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
