{"thread":{"id":"3667","subject":"[PATCH] 3% tighter packs for free","startedAt":"2006-03-18T03:45:07Z","lastAt":"2006-03-18T19:24:37Z","messageCount":4,"participants":["Nicolas Pitre","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"17635","messageId":"Pine.LNX.4.64.0603172205490.4889@localhost.localdomain","threadId":"3667","inReplyTo":null,"subject":"[PATCH] 3% tighter packs for free","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-03-18T03:45:07Z","receivedAt":"2006-03-18T03:45:07Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nThis patch makes for 3.4% smaller pack with the git repository, and\na bit more than 3% smaller pack with the kernel repository.\n\nAnd so with _no_ measurable CPU difference.\n\nSigned-off-by: Nicolas Pitre \n\n---\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex aaee7be..1188b31 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -136,7 +136,8 @@ void *diff_delta(void *from_buf, unsigne\n \t\t unsigned long *delta_size,\n \t\t unsigned long max_size)\n {\n-\tunsigned int i, outpos, outsize, inscnt, hash_shift;\n+\tunsigned int i, outpos, outsize, hash_shift;\n+\tint inscnt;\n \tconst unsigned char *ref_data, *ref_top, *data, *top;\n \tunsigned char *out;\n \tstruct index *entry, **hash;\n@@ -222,6 +223,20 @@ void *diff_delta(void *from_buf, unsigne\n \t\t\tunsigned char *op;\n \n \t\t\tif (inscnt) {\n+\t\t\t\twhile (moff && ref_data[moff-1] == data[-1]) {\n+\t\t\t\t\tif (msize == 0x10000)\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t/* we can match one byte back */\n+\t\t\t\t\tmsize++;\n+\t\t\t\t\tmoff--;\n+\t\t\t\t\tdata--;\n+\t\t\t\t\toutpos--;\n+\t\t\t\t\tif (--inscnt)\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t\toutpos--; /* remove count slot */\n+\t\t\t\t\tinscnt--; /* make it -1 */\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t\tout[outpos - inscnt - 1] = inscnt;\n \t\t\t\tinscnt = 0;\n \t\t\t}\n"},{"id":"17641","messageId":"7vwtesxloi.fsf@assigned-by-dhcp.cox.net","threadId":"3667","inReplyTo":"Pine.LNX.4.64.0603172205490.4889@localhost.localdomain","subject":"Re: [PATCH] 3% tighter packs for free","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-18T07:21:33Z","receivedAt":"2006-03-18T07:21:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> \t\t\tif (inscnt) {\n> +\t\t\t\twhile (moff && ref_data[moff-1] == data[-1]) {\n> +\t\t\t\t\tif (msize == 0x10000)\n> +\t\t\t\t\t\tbreak;\n> +\t\t\t\t\t/* we can match one byte back */\n> ...\n> +\t\t\t\t\tbreak;\n> +\t\t\t\t}\n> \t\t\t\tout[outpos - inscnt - 1] = inscnt;\n\nOnce you make it into a patch form, it is plainly obvious that\nthis is a good optimization. Since our BLK_SIZE is 16 bytes,\nyou are grabbing up to 15 more bytes (on average 8 more bytes or\nso) for every match after a partially modified block.\n\nVery nice. I wonder if a larger BLK_SIZE (say 32 bytes) would\ngive us faster packing without losing much compression if we use\nthis idea.\n"},{"id":"17654","messageId":"Pine.LNX.4.64.0603181315060.4889@localhost.localdomain","threadId":"3667","inReplyTo":"7vwtesxloi.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] 3% tighter packs for free","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-03-18T18:23:37Z","receivedAt":"2006-03-18T18:23:37Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 17 Mar 2006, Junio C Hamano wrote:\n\n> Once you make it into a patch form, it is plainly obvious that\n> this is a good optimization. Since our BLK_SIZE is 16 bytes,\n> you are grabbing up to 15 more bytes (on average 8 more bytes or\n> so) for every match after a partially modified block.\n> \n> Very nice. I wonder if a larger BLK_SIZE (say 32 bytes) would\n> give us faster packing without losing much compression if we use\n> this idea.\n\nTried that long ago. As BLK_SIZE is increased the adler32 cost, which \nhas to be computed for every offset in the target buffer, increases \naccordingly. So you end up with both worse compression and more CPU \nusage.\n\n\nNicolas\n"},{"id":"17655","messageId":"7vhd5vwo7e.fsf@assigned-by-dhcp.cox.net","threadId":"3667","inReplyTo":"Pine.LNX.4.64.0603181315060.4889@localhost.localdomain","subject":"Re: [PATCH] 3% tighter packs for free","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-18T19:24:37Z","receivedAt":"2006-03-18T19:24:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Tried that long ago. As BLK_SIZE is increased the adler32 cost, which \n> has to be computed for every offset in the target buffer, increases \n> accordingly. So you end up with both worse compression and more CPU \n> usage.\n\nAh, I was not paying enough attention. I did not realize\ndestination scanning was done for every byte.\n"}]}