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

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

[Martin Koegler]

Keeping the last used delta base object, if it would be dropped,
supports creating smaller packs with shorter delta chains.

The runtime impact is minimal, as it only skips slots in the delta window.

Original (for git.git repository):
$ echo | time /data/git/bin/git-pack-objects --non-empty --all --reflog --unpacked=pack-a19e665cf563f4ca8ce2306eeb4bfb78815882a5.pack --no-reuse-object .git/objects/.tmp-29631-pack
Generating pack...
Counting objects: 9846
Done counting 56224 objects.
Deltifying 56224 objects...
 100% (56224/56224) done
Writing 56224 objects...
1d3d374f6b9f9f8882ce3a47bab6976702aca35d

Total 56224 (delta 37798), reused 0 (delta 0)
57.19user 0.90system 1:00.39elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (6major+33878minor)pagefaults 0swaps

Pack size: 14655528
Pack stat:
      all sizes: count 56224 total 26029188 min 0 max 220191 mean 462.96 median 59 std_dev 3065.89
 all path sizes: count 56224 total 756044939 min 0 max 254816 mean 13447.01 median 6291 std_dev 26983.93
     tree sizes: count 18426 total 26029188 min 0 max 279666 mean 1412.63 median 451 std_dev 7242.15
tree path sizes: count 18426 total 756044939 min 0 max 30327513 mean 41031.42 median 457 std_dev 563089.70
         depths: count 56224 total 713895 min 0 max 50 mean 12.70 median 5 std_dev 15.85

chain length >= 40: 6271 objects
chain length = 1: 2615 objects
chain length = 2: 2350 objects
chain length = 3: 2073 objects
chain length = 4: 1809 objects
chain length = 5: 1578 objects
chain length = 6: 1384 objects
chain length = 7: 1242 objects
chain length = 8: 1119 objects
chain length = 9: 1060 objects
chain length = 10: 975 objects
chain length = 11: 904 objects
chain length = 12: 816 objects
chain length = 13: 778 objects
chain length = 14: 776 objects
chain length = 15: 709 objects
chain length = 16: 671 objects
chain length = 17: 651 objects
chain length = 18: 645 objects
chain length = 19: 674 objects
chain length = 20: 603 objects
chain length = 21: 563 objects
chain length = 22: 537 objects
chain length = 23: 530 objects
chain length = 24: 485 objects
chain length = 25: 473 objects
chain length = 26: 452 objects
chain length = 27: 427 objects
chain length = 28: 439 objects
chain length = 29: 420 objects
chain length = 30: 416 objects
chain length = 31: 387 objects
chain length = 32: 407 objects
chain length = 33: 387 objects
chain length = 34: 377 objects
chain length = 35: 354 objects
chain length = 36: 367 objects
chain length = 37: 364 objects
chain length = 38: 359 objects
chain length = 39: 351 objects

With the patch:
$ echo | time ./git-pack-objects --non-empty --all --reflog --unpacked=pack-a19e665cf563f4ca8ce2306eeb4bfb78815882a5.pack --no-reuse-object .git/objects/.tmp-29638-pack
Generating pack...
Counting objects: 9806
Done counting 56224 objects.
Deltifying 56224 objects...
 100% (56224/56224) done
Writing 56224 objects...
1d3d374f6b9f9f8882ce3a47bab6976702aca35d

Total 56224 (delta 37871), reused 0 (delta 0)
57.67user 1.08system 1:00.73elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+32236minor)pagefaults 0swaps

Pack size: 14306798
Pack stat:
      all sizes: count 56224 total 25299924 min 0 max 220191 mean 449.98 median 58 std_dev 2968.96
 all path sizes: count 56224 total 773260074 min 0 max 272126 mean 13753.20 median 6320 std_dev 27370.12
     tree sizes: count 18353 total 25299924 min 0 max 279899 mean 1378.52 median 450 std_dev 7097.53
tree path sizes: count 18353 total 773260074 min 0 max 28995033 mean 42132.63 median 455 std_dev 594290.34
         depths: count 56224 total 664005 min 0 max 50 mean 11.81 median 4 std_dev 14.85

chain length >= 40: 5056 objects
chain length = 1: 3174 objects
chain length = 2: 2613 objects
chain length = 3: 2209 objects
chain length = 4: 1918 objects
chain length = 5: 1565 objects
chain length = 6: 1412 objects
chain length = 7: 1211 objects
chain length = 8: 1090 objects
chain length = 9: 1001 objects
chain length = 10: 950 objects
chain length = 11: 893 objects
chain length = 12: 803 objects
chain length = 13: 772 objects
chain length = 14: 787 objects
chain length = 15: 691 objects
chain length = 16: 656 objects
chain length = 17: 624 objects
chain length = 18: 619 objects
chain length = 19: 591 objects
chain length = 20: 569 objects
chain length = 21: 552 objects
chain length = 22: 525 objects
chain length = 23: 509 objects
chain length = 24: 506 objects
chain length = 25: 479 objects
chain length = 26: 462 objects
chain length = 27: 472 objects
chain length = 28: 479 objects
chain length = 29: 475 objects
chain length = 30: 464 objects
chain length = 31: 446 objects
chain length = 32: 426 objects
chain length = 33: 433 objects
chain length = 34: 427 objects
chain length = 35: 412 objects
chain length = 36: 405 objects
chain length = 37: 393 objects
chain length = 38: 394 objects
chain length = 39: 408 objects

Signed-off-by: Martin Koegler <mkoegler@auto.tuwien.ac.at>
---
 builtin-pack-objects.c |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 77481df..24e8719 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -1438,6 +1438,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 	uint32_t i = nr_objects, idx = 0, count = 0, processed = 0;
 	unsigned int array_size = window * sizeof(struct unpacked);
 	struct unpacked *array;
+	struct object_entry *last_base = 0;
 	int max_depth;
 
 	if (!nr_objects)
@@ -1470,6 +1471,13 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 		if (entry->no_try_delta)
 			continue;
 
+		if (last_base && n->entry == last_base) {
+			idx ++;
+			if (idx >= window)
+				idx = 0;
+			n = array + idx;
+		}
+
 		free_unpacked(n);
 		n->entry = entry;
 
@@ -1513,6 +1521,7 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 		if (entry->delta && depth <= n->depth)
 			continue;
 
+		last_base = entry->delta;
 		next:
 		idx++;
 		if (count + 1 < window)
-- 
1.4.4.4

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

[Junio C Hamano]

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?

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

[David Kastrup]

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?

Well, given the little amount of spare time I have for personal
projects, I should not go flaunting them too much, but anyway...

I am just drafting implementing a delta-diff size estimator: for every
hash value it does not store hash chains or pointers to memory images,
but just a bit map of at most 32 (possibly 64 where ulong delivers it,
possibly even just 16 bits when one restricts oneself to 16 element
windows in order to save memory) delta window files, telling which of
the files show such a hash value anywhere.  When a file is considered
for deltaing, it is run once against this delta-diff estimator which
does not even look at the files again.  This delivers a lower bound
for the size a delta towards each of the delta candidates can take.
The candidates are then sorted in increasing size of expected delta
size and are considered in turn.  Once a delta has a lower size than
the lowest bound for further delta candidates, no further candidates
need to get considered.

Also the calculation of a delta can get aborted once it exceeds the
size of a previous delta.  Somewhat more complex and error-prone would
be to abort based on continually correcting the estimated lower bound
from the estimator while one is creating a delta and dropping out as
soon as it becomes impossible to beat a previous delta.

The nice thing about this is that one can start out with a simplistic
estimator as long as it is guaranteed never to deliver an estimate
that is too high.  As long as that is the case, the packs will never
get worse than they are now: a bad estimator will just mean that more
elements of the window need to be considered before the conclusion is
reached.

Since the estimator data structure does not point into any
memory-mapped files or hash chains scattered through memory, it should
be comparatively light (in comparison to an actual delta) on page
thrashing which appears to me one of the main performance problems,
while delivering a reasonably useful lower bound for all deltas in the
window at once.

Its size needs to be large enough so that the bit maps will be
dominated by zeros: hash collisions not actually corresponding to
matching data lead to underestimates.  If those become too many, the
pruning of comparisons will become ineffective:

A match implies that the next 2*RABIN_SIZE-1 (31) bytes at least could
possibly be expressed as a delta, and every match after another
RABIN_SIZE implies another RABIN_SIZE bytes might get folded into the
previous delta.

So false positives seriously distort the estimate.  There is still a
good chance that a good candidate will land early in the sort order
due to such an estimate and thus other candidates will have their
deltaing cut off early, but of course it is quite more effective if
their deltaing does not even have to start.

-- 
David Kastrup

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

[Martin Koegler]

On Mon, Aug 27, 2007 at 12:07:58PM +0200, David Kastrup wrote:
> Well, given the little amount of spare time I have for personal
> projects, I should not go flaunting them too much, but anyway...
> 
> I am just drafting implementing a delta-diff size estimator: for every
> hash value it does not store hash chains or pointers to memory images,
> but just a bit map of at most 32 (possibly 64 where ulong delivers it,
> possibly even just 16 bits when one restricts oneself to 16 element
> windows in order to save memory) delta window files, telling which of
> the files show such a hash value anywhere. 

How do you want to select these few hash values? 

I eg. dump database tables as SQL statements in per table files and
commit all changes. All lines in each file share a common prefix
(INSERT INTO tablename (COL1, COL2, ...) VALUES). Statistics showed, that up
to 50% of the hash elements of the delta index were dropped, because
they had eqal has values.

With you apropach:

If rare used values are selected as the 32 hash values, you will
probably regard files, which contain different tables (and therefore a
different prefix), as "similar", although the files have not very much
similarity otherwise.

If you select the hash values of the prefixes, you will create for each
table one cluster (if the table count is < 32/64). This already happens
by using the hash value of the path name in the sorting.

I don't belive, that your idea will improve very much in this case.
I fear, that it will be even worser than the current algorithm.

> When a file is considered
> for deltaing, it is run once against this delta-diff estimator which
> does not even look at the files again.  This delivers a lower bound
> for the size a delta towards each of the delta candidates can take.
> The candidates are then sorted in increasing size of expected delta
> size and are considered in turn.  Once a delta has a lower size than
> the lowest bound for further delta candidates, no further candidates
> need to get considered.

So this means, that we have to hash the target entry too (which could
be merged with creating the delta index). We currently only hash an
entry, if it is really needed as source in a delta-diff.

On bigger blobs, this could slow the process down.

> Also the calculation of a delta can get aborted once it exceeds the
> size of a previous delta. 

This already happens.

> Somewhat more complex and error-prone would
> be to abort based on continually correcting the estimated lower bound
> from the estimator while one is creating a delta and dropping out as
> soon as it becomes impossible to beat a previous delta.
> 
> The nice thing about this is that one can start out with a simplistic
> estimator as long as it is guaranteed never to deliver an estimate
> that is too high.  As long as that is the case, the packs will never
> get worse than they are now: a bad estimator will just mean that more
> elements of the window need to be considered before the conclusion is
> reached.
> 
> Since the estimator data structure does not point into any
> memory-mapped files or hash chains scattered through memory, it should
> be comparatively light (in comparison to an actual delta) on page
> thrashing which appears to me one of the main performance problems,
> while delivering a reasonably useful lower bound for all deltas in the
> window at once.

Do you want to do your estimations only against a small window of objects
or all objects?

mfg Martin Kögler

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

[David Kastrup]

mkoegler@auto.tuwien.ac.at (Martin Koegler) writes:

> On Mon, Aug 27, 2007 at 12:07:58PM +0200, David Kastrup wrote:
>> Well, given the little amount of spare time I have for personal
>> projects, I should not go flaunting them too much, but anyway...
>> 
>> I am just drafting implementing a delta-diff size estimator: for every
>> hash value it does not store hash chains or pointers to memory images,
>> but just a bit map of at most 32 (possibly 64 where ulong delivers it,
>> possibly even just 16 bits when one restricts oneself to 16 element
>> windows in order to save memory) delta window files, telling which of
>> the files show such a hash value anywhere. 
>
> How do you want to select these few hash values?

Hm?  Are you familiar with diff-delta.c?  I was not going to change
the hash value computation in there.  It is a 32bit CRC over 16byte
passages: the delta source is checksummed with a stride of 16 bytes
and the resulting CRC values are masked to a convenient number of bits
and used as index into a hash table with disambiguation to actual code
passages using linked lists.  Then the destination delta is
checksummed in the same manner but with a stride of 1, and the sums
are looked up in the hash until a matching prefix is found.

So I was going to do the same calculation, but look up a bit mask
rather than a linked list (namely calculating under the assumption
that a hash hit implies an actual match).

> I eg. dump database tables as SQL statements in per table files and
> commit all changes. All lines in each file share a common prefix
> (INSERT INTO tablename (COL1, COL2, ...) VALUES). Statistics showed,
> that up to 50% of the hash elements of the delta index were dropped,
> because they had equal hash values.

Yes, I am aware of that.  One somewhat crazy consequence of that is
that git's deltaing works better on Linux style indentation than on
GNU style indentation.

> With you apropach:
>
> If rare used values are selected as the 32 hash values, you will
> probably regard files, which contain different tables (and therefore
> a different prefix), as "similar", although the files have not very
> much similarity otherwise.

It's statistics.  Random matches will tend to level out.

> If you select the hash values of the prefixes, you will create for
> each table one cluster (if the table count is < 32/64). This already
> happens by using the hash value of the path name in the sorting.
>
> I don't belive, that your idea will improve very much in this case.
> I fear, that it will be even worser than the current algorithm.

Huh?  I am not replacing the current algorithm.  I am doing some
upfront estimates for getting a good order for doing the current
algorithm, so that I might abort parts of it early when I know they
can't improve things.  If the estimates are completely random and/or
useless, it will mean that you get a slowdown by a comparatively small
constant factor.

>> When a file is considered for deltaing, it is run once against this
>> delta-diff estimator which does not even look at the files again.
>> This delivers a lower bound for the size a delta towards each of
>> the delta candidates can take.  The candidates are then sorted in
>> increasing size of expected delta size and are considered in turn.
>> Once a delta has a lower size than the lowest bound for further
>> delta candidates, no further candidates need to get considered.
>
> So this means, that we have to hash the target entry too (which
> could be merged with creating the delta index).

Huh?  I don't see what you are getting at.

> We currently only hash an entry, if it is really needed as source in
> a delta-diff.

Why would you want to hash a non-candidate?

>> Also the calculation of a delta can get aborted once it exceeds the
>> size of a previous delta.
>
> This already happens.

Ah yes.  Overlooked this.  Presorting the candidates should be helpful
right away then.

> Do you want to do your estimations only against a small window of
> objects or all objects?

The estimates are made against the candidates in the window.  When a
candidate leaves the window, its bit in the bit masks gets reused for
the next candidate entering the window.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

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

[Junio C Hamano]

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.  

I had a bit more objects (59140) than you did in my repository.
The runtime from three versions were comparable.  It seems to
make the resulting chain even shorter, which can only be good.

(stock "master") 15782196 bytes
chain length = 1: 2972 objects
chain length = 2: 2651 objects
chain length = 3: 2369 objects
chain length = 4: 2121 objects
chain length = 5: 1877 objects
chain length = 6: 1715 objects
chain length = 7: 1469 objects
chain length = 8: 1296 objects
chain length = 9: 1185 objects
chain length = 10: 1111 objects
...
chain length = 46: 490 objects
chain length = 47: 515 objects
chain length = 48: 527 objects
chain length = 49: 570 objects
chain length = 50: 408 objects

(with your patch) 15745736 bytes (0.23% smaller)
chain length = 1: 3137 objects
chain length = 2: 2688 objects
chain length = 3: 2322 objects
chain length = 4: 2146 objects
chain length = 5: 1824 objects
chain length = 6: 1664 objects
chain length = 7: 1462 objects
chain length = 8: 1329 objects
chain length = 9: 1201 objects
chain length = 10: 1126 objects
...
chain length = 46: 503 objects
chain length = 47: 509 objects
chain length = 48: 536 objects
chain length = 49: 588 objects
chain length = 50: 357 objects

(with this patch) 15612086 bytes (1.08% smaller)
chain length = 1: 4831 objects
chain length = 2: 3811 objects
chain length = 3: 2964 objects
chain length = 4: 2352 objects
chain length = 5: 1944 objects
chain length = 6: 1667 objects
chain length = 7: 1465 objects
chain length = 8: 1267 objects
chain length = 9: 1210 objects
chain length = 10: 1050 objects
...
chain length = 46: 327 objects
chain length = 47: 353 objects
chain length = 48: 304 objects
chain length = 49: 298 objects
chain length = 50: 135 objects

---
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)

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

[Nicolas Pitre]

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

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

[Junio C Hamano]

Nicolas Pitre <nico@cam.org> 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.

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

[Nicolas Pitre]

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

> Nicolas Pitre <nico@cam.org> 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)