threads / patch / 3667

patch3% tighter packs for free

Subject: [PATCH] 3% tighter packs for free

## tl;dr

4 messages between Mar 18, 2006 and Mar 18, 2006. Diffs are folded; open one to read it.

replies: 3people: 2as markdown or json

Nicolas Pitre· Mar 18, 2006, 03:45 UTC · lore

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>
---
Show changes to diff-delta.c +16 −1
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;
 			}
Junio C Hamano· Mar 18, 2006, 07:21 UTC · re: Nicolas Pitre · lore

Re: [PATCH] 3% tighter packs for free

Nicolas Pitre <nico@cam.org> writes:
Show 9 quoted lines
>  			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.

Nicolas Pitre· Mar 18, 2006, 18:23 UTC · re: Junio C Hamano · lore

Re: [PATCH] 3% tighter packs for free

On Fri, 17 Mar 2006, Junio C Hamano wrote:
Show 8 quoted lines
> 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
Junio C Hamano· Mar 18, 2006, 19:24 UTC · re: Nicolas Pitre · lore

Re: [PATCH] 3% tighter packs for free

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.

← back to recent threads