[PATCH] 3% tighter packs for free

[PATCH] 3% tighter packs for free

[Nicolas Pitre]

This patch makes for 3.4% smaller pack with the git repository, and
a bit more than 3% smaller pack with the kernel repository.

And so with _no_ measurable CPU difference.

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

---

diff --git a/diff-delta.c b/diff-delta.c
index aaee7be..1188b31 100644
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -136,7 +136,8 @@ void *diff_delta(void *from_buf, unsigne
 		 unsigned long *delta_size,
 		 unsigned long max_size)
 {
-	unsigned int i, outpos, outsize, inscnt, hash_shift;
+	unsigned int i, outpos, outsize, hash_shift;
+	int inscnt;
 	const unsigned char *ref_data, *ref_top, *data, *top;
 	unsigned char *out;
 	struct index *entry, **hash;
@@ -222,6 +223,20 @@ void *diff_delta(void *from_buf, unsigne
 			unsigned char *op;
 
 			if (inscnt) {
+				while (moff && ref_data[moff-1] == data[-1]) {
+					if (msize == 0x10000)
+						break;
+					/* we can match one byte back */
+					msize++;
+					moff--;
+					data--;
+					outpos--;
+					if (--inscnt)
+						continue;
+					outpos--;  /* remove count slot */
+					inscnt--;  /* make it -1 */
+					break;
+				}
 				out[outpos - inscnt - 1] = inscnt;
 				inscnt = 0;
 			}

Re: [PATCH] 3% tighter packs for free

[Junio C Hamano]

Nicolas Pitre <nico@cam.org> writes:

>  			if (inscnt) {
> +				while (moff && ref_data[moff-1] == data[-1]) {
> +					if (msize == 0x10000)
> +						break;
> +					/* we can match one byte back */
> ...
> +					break;
> +				}
>  				out[outpos - inscnt - 1] = inscnt;

Once you make it into a patch form, it is plainly obvious that
this is a good optimization.  Since our BLK_SIZE is 16 bytes,
you are grabbing up to 15 more bytes (on average 8 more bytes or
so) for every match after a partially modified block.

Very nice.  I wonder if a larger BLK_SIZE (say 32 bytes) would
give us faster packing without losing much compression if we use
this idea.

Re: [PATCH] 3% tighter packs for free

[Nicolas Pitre]

On Fri, 17 Mar 2006, Junio C Hamano wrote:

> Once you make it into a patch form, it is plainly obvious that
> this is a good optimization.  Since our BLK_SIZE is 16 bytes,
> you are grabbing up to 15 more bytes (on average 8 more bytes or
> so) for every match after a partially modified block.
> 
> Very nice.  I wonder if a larger BLK_SIZE (say 32 bytes) would
> give us faster packing without losing much compression if we use
> this idea.

Tried that long ago.  As BLK_SIZE is increased the adler32 cost, which 
has to be computed for every offset in the target buffer, increases 
accordingly.  So you end up with both worse compression and more CPU 
usage.


Nicolas

Re: [PATCH] 3% tighter packs for free

[Junio C Hamano]

Nicolas Pitre <nico@cam.org> writes:

> Tried that long ago.  As BLK_SIZE is increased the adler32 cost, which 
> has to be computed for every offset in the target buffer, increases 
> accordingly.  So you end up with both worse compression and more CPU 
> usage.

Ah, I was not paying enough attention.  I did not realize
destination scanning was done for every byte.