On Mon, 27 Aug 2007, Junio C Hamano wrote:
> Junio C Hamano <gitster@xxxxxxxxx> 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.
[...]
> 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;
<ranting again>
I cannot do otherwise but hate this notation. Just for this one I had
to spend at least 5 seconds thinking about it before I could convince
myself it is OK. It annoyed me so much that I switched the condition
around in my local copy. I acknowledge your maintainer priviledges, but
I couldn't stop myself making noise about this again anyway.
</ranting again>
> + /*
> + * 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;
This condition will never occur because, upon entering this function,
idx points to the _current_
object which is never considered as a base (can't deltify against self).
So you probably should avoid increasing idx.
Yet I think it would be clearer if you had this instead (assuming idx
unchanged):
/* How far is the good base from the front of the window? */
good_dist = (window + idx - good_base) % window;
/* If it is already at the furthest edge, nothing needs to be done. */
if (good_dist <= 1)
return;
/* Otherwise, stash it away, shift the others down and swap it in. */
swap = array[good_base];
dst = good_base;
while (--good_dist > 0) {
src = (dst + 1) % window;
array[dst] = array[src];
dst = src;
}
array[dst] = swap;
> + swap = array[good_base];
> +
> + while (good_at < window) {
This also had the effect of moving down the current object, i.e. the one
that was just deltified. Maybe this is a good thing, in which case the
"if (good_dist <= 1)" above can be deleted and "while (good_dist-- > 0)"
used instead.
Nicolas
-
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
