# [PATCH] 3% tighter packs for free 4 messages from 2006-03-18 to 2006-03-18. Participants: Nicolas Pitre, Junio C Hamano. Thread: https://gitlist.dev/t/3667 ## Nicolas Pitre, 2006-03-18 03:45 Subject: [PATCH] 3% tighter packs for free Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0603172205490.4889%40localhost.localdomain ``` 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 --- 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, 2006-03-18 07:21 Subject: Re: [PATCH] 3% tighter packs for free Message-ID: <7vwtesxloi.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vwtesxloi.fsf%40assigned-by-dhcp.cox.net In-Reply-To: ``` Nicolas Pitre 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. ``` ## Nicolas Pitre, 2006-03-18 18:23 Subject: Re: [PATCH] 3% tighter packs for free Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0603181315060.4889%40localhost.localdomain In-Reply-To: <7vwtesxloi.fsf@assigned-by-dhcp.cox.net> ``` 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 ``` ## Junio C Hamano, 2006-03-18 19:24 Subject: Re: [PATCH] 3% tighter packs for free Message-ID: <7vhd5vwo7e.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vhd5vwo7e.fsf%40assigned-by-dhcp.cox.net In-Reply-To: ``` Nicolas Pitre 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. ```