pack-object mystery explained

pack-object mystery explained

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 7928 bytes --]

As Junio certainly knows since he added it himself, there is some code 
currently surrounded with #if 0 ... #endif in pack-objects.c that was 
meant to improve delta window usage.

The idea was to _not_ keep any object in the object window which delta 
depth reached the maximum depth since it obviously cannot be used as a 
base for any further deltification anyway.  In doing so the object 
window would always be filled only with objects that are not too deep 
and therefore increase the possibility for better delta match.

In theory... only.

Because, in practice, doing so produces pack files that are between 20% 
to 60% *larger* than without this "optimization".

This is just so counter-intuitive that I wanted to find out why.  So I 
added a few lines to output the target object sha1, and the sha1 of each 
object in the object window as well as the return code from try_delta(), 
the object depth and the size of the best delta, something like the 
attached patch.  Then diffing the output between a run with the code as 
is and another run with the "optimization" enabled produce a really 
interesting result.

Looking at the diff:

--- /tmp/l1      2006-05-13 22:38:06.000000000 -0400
+++ /tmp/l2     2006-05-13 23:04:53.000000000 -0400
@@ -1255,7 +1255,6 @@
  0 src 57cefdea530171c71c72229a85aa0212dedb2c5a depth 5 delta_sz 115
 nbdelta = 34 deltasz = 25794
 trg f24cfd2b46a65bde53610eecb6998fa615b62363
- 0 src 0b90fb9ae3396d0f2b0a9ebf9acad8374f3db317 depth 10 delta_sz 0
  1 src 8866189332568a317183f6f895014519515f67e7 depth 9 delta_sz 20146
  1 src 4c1b0c3039a84c4c786a09ba70a84df46f995186 depth 8 delta_sz 3357
  0 src 226d71966d4a0e8a8611ea09e35719688a987ceb depth 7 delta_sz 3357
@@ -1265,10 +1264,10 @@
  0 src e44310f5a8115011eafce41362d1752c4ee0f72f depth 3 delta_sz 1365
  0 src b35d400ee1a2e8b5c97ca6ad82f6d91818519456 depth 2 delta_sz 1365
  0 src b60fa8d2417c32cf72331e9869d4d3a3208e953f depth 2 delta_sz 1365
+ 0 src 57cefdea530171c71c72229a85aa0212dedb2c5a depth 5 delta_sz 1365
 nbdelta = 35 deltasz = 27159
 trg 553e1e1749ab537a71c7a1cfb97f18f85dc9ef1f
  1 src f24cfd2b46a65bde53610eecb6998fa615b62363 depth 6 delta_sz 990
- 0 src 0b90fb9ae3396d0f2b0a9ebf9acad8374f3db317 depth 10 delta_sz 990
  0 src 8866189332568a317183f6f895014519515f67e7 depth 9 delta_sz 990
  0 src 4c1b0c3039a84c4c786a09ba70a84df46f995186 depth 8 delta_sz 990
  0 src 226d71966d4a0e8a8611ea09e35719688a987ceb depth 7 delta_sz 990
@@ -1277,11 +1276,11 @@
  0 src 42b0d59e8c15dff0d72b0d3a486d0248bd767dfe depth 4 delta_sz 248
  0 src e44310f5a8115011eafce41362d1752c4ee0f72f depth 3 delta_sz 248
  0 src b35d400ee1a2e8b5c97ca6ad82f6d91818519456 depth 2 delta_sz 248
+ 0 src b60fa8d2417c32cf72331e9869d4d3a3208e953f depth 2 delta_sz 248
 nbdelta = 36 deltasz = 27407
[...]

So the object that reached a delta depth of 10 is clearly not added to 
the window in the second log.

But here's the interesting part:

 trg f3c92c971e65e9df72fafdab52b4935866a0a794
- 0 src e85f1c17089a1da95b264909cfc50235c74471da depth 10 delta_sz 0
- 0 src 134d405ba2e6dd41c7501aa9e078a8879ba8025f depth 10 delta_sz 0
- 0 src 6a241aab054a8d6b5c021aba77bba795d7684196 depth 10 delta_sz 0
- 0 src 85cd595802ca565f380a9851efd5a3551c959db0 depth 10 delta_sz 0
- 0 src 89fda42efb678d2f9f9e802454fe561b4452a167 depth 10 delta_sz 0
- 0 src c10067c17ff9eef3ce0f01e5c14ba86bd2273d54 depth 10 delta_sz 0
- 0 src 8e953a67596cf0f5c12f2d8c66055759a7d2201c depth 10 delta_sz 0
  1 src 553e1e1749ab537a71c7a1cfb97f18f85dc9ef1f depth 6 delta_sz 6223
  0 src f24cfd2b46a65bde53610eecb6998fa615b62363 depth 6 delta_sz 6223
- 0 src 0b90fb9ae3396d0f2b0a9ebf9acad8374f3db317 depth 10 delta_sz 6223
-nbdelta = 44 deltasz = 40076
+ 1 src 8866189332568a317183f6f895014519515f67e7 depth 9 delta_sz 5135
+ 0 src 4c1b0c3039a84c4c786a09ba70a84df46f995186 depth 8 delta_sz 5135
+ 0 src 226d71966d4a0e8a8611ea09e35719688a987ceb depth 7 delta_sz 5135
+ 0 src 78129ec0cd5fb9767caefee8a8dc1a17dc095bdb depth 6 delta_sz 5135
+ 0 src 93a50b4444e3bba210f6879795979d0894ad5aaf depth 5 delta_sz 5135
+ 0 src 42b0d59e8c15dff0d72b0d3a486d0248bd767dfe depth 4 delta_sz 5135
+ 0 src e44310f5a8115011eafce41362d1752c4ee0f72f depth 3 delta_sz 5135
+ 0 src b35d400ee1a2e8b5c97ca6ad82f6d91818519456 depth 2 delta_sz 5135
+nbdelta = 44 deltasz = 38988
 trg fe925609b4024119c6171dd32350a6570bea8516
- 1 src f3c92c971e65e9df72fafdab52b4935866a0a794 depth 7 delta_sz 99
- 0 src e85f1c17089a1da95b264909cfc50235c74471da depth 10 delta_sz 99
- 0 src 134d405ba2e6dd41c7501aa9e078a8879ba8025f depth 10 delta_sz 99
- 0 src 6a241aab054a8d6b5c021aba77bba795d7684196 depth 10 delta_sz 99
- 0 src 85cd595802ca565f380a9851efd5a3551c959db0 depth 10 delta_sz 99
- 0 src 89fda42efb678d2f9f9e802454fe561b4452a167 depth 10 delta_sz 99
- 0 src c10067c17ff9eef3ce0f01e5c14ba86bd2273d54 depth 10 delta_sz 99
- 0 src 8e953a67596cf0f5c12f2d8c66055759a7d2201c depth 10 delta_sz 99
- 0 src 553e1e1749ab537a71c7a1cfb97f18f85dc9ef1f depth 6 delta_sz 99
- 0 src f24cfd2b46a65bde53610eecb6998fa615b62363 depth 6 delta_sz 99
-nbdelta = 45 deltasz = 40175
+ 1 src 553e1e1749ab537a71c7a1cfb97f18f85dc9ef1f depth 6 delta_sz 6006
+ 0 src f24cfd2b46a65bde53610eecb6998fa615b62363 depth 6 delta_sz 6006
+ 1 src 8866189332568a317183f6f895014519515f67e7 depth 9 delta_sz 5027
+ 0 src 4c1b0c3039a84c4c786a09ba70a84df46f995186 depth 8 delta_sz 5027
+ 0 src 226d71966d4a0e8a8611ea09e35719688a987ceb depth 7 delta_sz 5027
+ 0 src 78129ec0cd5fb9767caefee8a8dc1a17dc095bdb depth 6 delta_sz 5027
+ 0 src 93a50b4444e3bba210f6879795979d0894ad5aaf depth 5 delta_sz 5027
+ 0 src 42b0d59e8c15dff0d72b0d3a486d0248bd767dfe depth 4 delta_sz 5027
+ 0 src e44310f5a8115011eafce41362d1752c4ee0f72f depth 3 delta_sz 5027
+ 0 src b35d400ee1a2e8b5c97ca6ad82f6d91818519456 depth 2 delta_sz 5027
+nbdelta = 45 deltasz = 44015
[...]

Here we can see that f3c92c97 benefits from a window that has none of 
those objects with a depth of 10 so it can find a better delta base.  
But in doing so it becomes itself depth 10 and is therefore discarded 
from the object window right away.  And the unfortunate fact is that 
f3c92c97 would have been the best base for the next object (fe925609) by 
far with a delta size of 99 bytes instead of 5027 bytes.

And then the story repeats itself for a while since fe925609 also 
becomes depth 10 which means the object window doesn't get refreshed as 
long as best match are based on 88661893 with a delta size around 5000 
bytes instead of 100 bytes if f3c92c97 didn't reach depth 10 initially.

So it is like a priority inversion problem. Instead of evicting max 
depth objects early to always have a full window of potential usable 
base object to delta against andimprove the delta packing, this early 
eviction of objects with max depth may enter a perverse state where the 
object window is not recycled with new objects for a while, which is 
especially bad if the window content is the source of suboptimal delta 
matches.  And that perverse state will remain until the delta match 
becomes bad enough to break the link with 88661893.

I thought about recording the second best delta base for any object that 
reached maximum delta depth and reverting to that base whenever an 
object of maximum depth would allow for a delta of greater saving if it 
wasn't of max depth already and could be used as a delta base again.  
But this quickly gets complicated if we want to retroactively consider 
previous objects that didn't constitute a good enough saving to motivate 
the switch of given object to its second best base but could benefit 
from such a switch if some other objects are making that switch anyway, 
and then it would be necessary to make sure not to exceed the depth of 
objects already deltified from the object we're considering moving, 
etc.  In short it gets really twisted for an incertain gain.

But... there is still a way to improve things with a really really 
simple euristic...


Nicolas

[-- Attachment #2: Type: TEXT/PLAIN, Size: 1108 bytes --]

diff --git a/pack-objects.c b/pack-objects.c
index 523a1c7..8ff7f30 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -1116,8 +1116,10 @@ static void find_deltas(struct object_en
 		if (!n->index)
 			die("out of memory");
 
+fprintf(stderr, "trg %s\n", sha1_to_hex(entry->sha1));
 		j = window;
 		while (--j > 0) {
+			int rc;
 			unsigned int other_idx = idx + j;
 			struct unpacked *m;
 			if (other_idx >= window)
@@ -1125,10 +1127,15 @@ static void find_deltas(struct object_en
 			m = array + other_idx;
 			if (!m->entry)
 				break;
-			if (try_delta(n, m, m->index, depth) < 0)
+			rc = try_delta(n, m, m->index, depth);
+fprintf(stderr, "% d src %s depth %d delta_sz %d\n", rc, sha1_to_hex(m->entry->sha1), m->entry->depth, n->entry->delta_size);
+			if (rc < 0)
 				break;
 		}
+static int nbdelta=0, deltasz=0;
+if (n->entry->delta) nbdelta++, deltasz += n->entry->delta_size;
+fprintf(stderr, "nbdelta = %d deltasz = %d\n", nbdelta, deltasz);
 #if 1
 		/* if we made n a delta, and if n is already at max
 		 * depth, leaving it in the window is pointless.  we
 		 * should evict it first.

[PATCH] simple euristic for further free packing improvements

[Nicolas Pitre]

Given that the early eviction of objects with maximum delta depth 
may exhibit bad packing on its own, why not considering a bias against 
deep base objects in try_delta() to mitigate that bad behavior.

This patch adjust the MAX_size allowed for a delta based on the depth of 
the base object as well as enabling the early eviction of max depth 
objects from the object window.  When used separately, those two things 
produce slightly better and much worse results respectively.  But their 
combined effect is a surprising significant packing improvement.

With this really simple patch the GIT repo gets nearly 15% smaller, and 
the Linux kernel repo about 5% smaller, with no significantly measurable 
CPU usage difference.

Signed-off-by: Nicolas Pitre <nico@cam.org>

---

diff --git a/pack-objects.c b/pack-objects.c
index 523a1c7..b0388d7 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr
 
 	/* Now some size filtering euristics. */
 	size = trg_entry->size;
-	max_size = size / 2 - 20;
-	if (trg_entry->delta)
+	max_size = (size/2 - 20) / (src_entry->depth + 1);
+	if (trg_entry->delta && trg_entry->delta_size <= max_size)
 		max_size = trg_entry->delta_size-1;
 	src_size = src_entry->size;
 	sizediff = src_size < size ? size - src_size : 0;
@@ -1128,15 +1128,12 @@ static void find_deltas(struct object_en
 			if (try_delta(n, m, m->index, depth) < 0)
 				break;
 		}
-#if 0
 		/* if we made n a delta, and if n is already at max
 		 * depth, leaving it in the window is pointless.  we
 		 * should evict it first.
-		 * ... in theory only; somehow this makes things worse.
 		 */
 		if (entry->delta && depth <= entry->depth)
 			continue;
-#endif
 		idx++;
 		if (idx >= window)
 			idx = 0;

Re: [PATCH] simple euristic for further free packing improvements

[Junio C Hamano]

Nicolas Pitre <nico@cam.org> writes:

> Given that the early eviction of objects with maximum delta depth 
> may exhibit bad packing on its own, why not considering a bias against 
> deep base objects in try_delta() to mitigate that bad behavior.

This is really a good stuff.  Thanks.  Oh, and thanks for
noticing my puzzlement expressed with "#if 0" ;-).

> @@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr
>  
>  	/* Now some size filtering euristics. */
>  	size = trg_entry->size;
> -	max_size = size / 2 - 20;
> -	if (trg_entry->delta)
> +	max_size = (size/2 - 20) / (src_entry->depth + 1);
> +	if (trg_entry->delta && trg_entry->delta_size <= max_size)
>  		max_size = trg_entry->delta_size-1;
>  	src_size = src_entry->size;
>  	sizediff = src_size < size ? size - src_size : 0;

At the first glance, this seems rather too agressive.  It makes
me wonder if it is a good balance to penalize the second
generation base by requiring it to produce a small delta that is
at most half as we normally would (and the third generation a
third), or maybe the penalty should kick in more gradually, like
e.g. ((max_depth * 2 - src_entry->depth) / (max_depth * 2).

Having said that, judging from your past patches, I learned to
trust that you have tried tweaking this part and settled on this
simplicity and elegance, so I'll take the patch as is -- if
somebody wants to play with it that can always be done to
further improve things.

Re: [PATCH] simple euristic for further free packing improvements

[Nicolas Pitre]

On Mon, 15 May 2006, Junio C Hamano wrote:

> Nicolas Pitre <nico@cam.org> writes:
> 
> > @@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr
> >  
> >  	/* Now some size filtering euristics. */
> >  	size = trg_entry->size;
> > -	max_size = size / 2 - 20;
> > -	if (trg_entry->delta)
> > +	max_size = (size/2 - 20) / (src_entry->depth + 1);
> > +	if (trg_entry->delta && trg_entry->delta_size <= max_size)
> >  		max_size = trg_entry->delta_size-1;
> >  	src_size = src_entry->size;
> >  	sizediff = src_size < size ? size - src_size : 0;
> 
> At the first glance, this seems rather too agressive.  It makes
> me wonder if it is a good balance to penalize the second
> generation base by requiring it to produce a small delta that is
> at most half as we normally would (and the third generation a
> third), or maybe the penalty should kick in more gradually, like
> e.g. ((max_depth * 2 - src_entry->depth) / (max_depth * 2).
> 
> Having said that, judging from your past patches, I learned to
> trust that you have tried tweaking this part and settled on this
> simplicity and elegance, so I'll take the patch as is -- if
> somebody wants to play with it that can always be done to
> further improve things.

Actually I didn't play with that part that much.  The only thing I tried 
besides this version was (size - 20) / (src_entry->depth + 1) but it 
produced larger packs than the current version.

So I thought it was better to provide a simple initial rule and leave 
possible improvements for later.


Nicolas

[PATCH] improve depth heuristic for maximum delta size

[Nicolas Pitre]

This provides a linear decrement on the penalty related to delta depth
instead of being an 1/x function.  With this another 5% reduction is 
observed on packs for both the GIT repo and the Linux kernel repo, as 
well as fixing a pack size regression in another sample repo I have.

Signed-off-by: Nicolas Pitre <nico@cam.org>

---

On Mon, 15 May 2006, Junio C Hamano wrote:

> Nicolas Pitre <nico@cam.org> writes:
> 
> > @@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr
> >  
> >  	/* Now some size filtering euristics. */
> >  	size = trg_entry->size;
> > -	max_size = size / 2 - 20;
> > -	if (trg_entry->delta)
> > +	max_size = (size/2 - 20) / (src_entry->depth + 1);
> > +	if (trg_entry->delta && trg_entry->delta_size <= max_size)
> >  		max_size = trg_entry->delta_size-1;
> >  	src_size = src_entry->size;
> >  	sizediff = src_size < size ? size - src_size : 0;
> 
> At the first glance, this seems rather too agressive.  It makes
> me wonder if it is a good balance to penalize the second
> generation base by requiring it to produce a small delta that is
> at most half as we normally would (and the third generation a
> third), or maybe the penalty should kick in more gradually, like
> e.g. ((max_depth * 2 - src_entry->depth) / (max_depth * 2).

You are right.  However your formula converge towards 0.5 which is not 
enough to be sure the bad effect with early eviction of max depth object 
from the object window won't come back.  I prefer this patch with a 
formula converging toward 0.

diff --git a/pack-objects.c b/pack-objects.c
index 566a2a2..3116020 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -1036,9 +1036,12 @@ static int try_delta(struct unpacked *tr
 	if (src_entry->depth >= max_depth)
 		return 0;
 
-	/* Now some size filtering euristics. */
+	/* Now some size filtering heuristics. */
 	size = trg_entry->size;
-	max_size = (size/2 - 20) / (src_entry->depth + 1);
+	max_size = size/2 - 20;
+	max_size = max_size * (max_depth - src_entry->depth) / max_depth;
+	if (max_size == 0)
+		return 0;
 	if (trg_entry->delta && trg_entry->delta_size <= max_size)
 		max_size = trg_entry->delta_size-1;
 	src_size = src_entry->size;

Re: [PATCH] improve depth heuristic for maximum delta size

[Junio C Hamano]

Nicolas Pitre <nico@cam.org> writes:

> This provides a linear decrement on the penalty related to delta depth
> instead of being an 1/x function.  With this another 5% reduction is 
> observed on packs for both the GIT repo and the Linux kernel repo, as 
> well as fixing a pack size regression in another sample repo I have.

Good job, and it does not seem to spend too many more cycles
either (it does slow it down a bit because it needs to do more
deltas, but that is to be expected).

Here is the average chain length and resulting pack size from
full repacking of git.git repository, with three versions.

        Avg 6.20   6516kB (master)
        Avg 5.97   5784kB (next, has 1/x version)
        Avg 6.89   5536kB (this patch on top of next)

What's interesting is that the 1/x version shortens the chain
(i.e. decreased runtime cost) while producing smaller results,
compared to the master version.  The story is the same on the
kernel archive.

	Avg 5.82 113808kB (master)
	Avg 4.76 108044kB (next, has 1/x version)
	Avg 5.81 105768kB (this patch on top of next)