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

[Nicolas Pitre <nico@cam.org>]

On Mon, 27 Aug 2007, Junio C Hamano wrote:

> Junio C Hamano <gitster@pobox.com> 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