{"thread":{"id":"3432","subject":"[PATCH] diff-delta: produce optimal pack data","startedAt":"2006-02-22T01:45:36Z","lastAt":"2006-03-08T14:17:09Z","messageCount":35,"participants":["Nicolas Pitre","Junio C Hamano","Carl Baldwin","Linus Torvalds","Johannes Schindelin","Sergey Vlasov"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"16554","messageId":"Pine.LNX.4.64.0602212043260.5606@localhost.localdomain","threadId":"3432","inReplyTo":null,"subject":"[PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-22T01:45:36Z","receivedAt":"2006-02-22T01:45:36Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nIndexing based on adler32 has a match precision based on the block size \n(currently 16). Lowering the block size would produce smaller deltas \nbut the indexing memory and computing cost increases significantly.\n\nFor optimal delta result the indexing block size should be 3 with an \nincrement of 1 (instead of 16 and 16). With such low params the adler32 \nbecomes a clear overhead increasing the time for git-repack by a factor \nof 3. And with such small blocks the adler 32 is not very useful as the \nwhole of the block bits can be used directly.\n\nThis patch replaces the adler32 with an open coded index value based on \n3 characters directly. This gives sufficient bits for hashing and \nallows for optimal delta with reasonable CPU cycles.\n\nThe resulting packs are 6% smaller on average. The increase in CPU time \nis about 25%. But this cost is now hidden by the delta reuse patch \nwhile the saving on data transfers is always there.\n\nSigned-off-by: Nicolas Pitre \n\n---\n\n diff-delta.c | 77 +++++++++++++++++++++++-----------------------------------\n 1 files changed, 30 insertions(+), 47 deletions(-)\n\n54aa50fb403981a9292453b76d894a79da9698de\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 2ed5984..27f83a0 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -20,21 +20,11 @@\n \n #include \n #include \n-#include \n #include \"delta.h\"\n \n \n-/* block size: min = 16, max = 64k, power of 2 */\n-#define BLK_SIZE 16\n-\n-#define MIN(a, b) ((a) < (b) ? (a) : (b))\n-\n-#define GR_PRIME 0x9e370001\n-#define HASH(v, shift) (((unsigned int)(v) * GR_PRIME) >> (shift))\n-\n struct index {\n \tconst unsigned char *ptr;\n-\tunsigned int val;\n \tstruct index *next;\n };\n \n@@ -42,21 +32,21 @@ static struct index ** delta_index(const\n \t\t\t\t unsigned long bufsize,\n \t\t\t\t unsigned int *hash_shift)\n {\n-\tunsigned int hsize, hshift, entries, blksize, i;\n+\tunsigned long hsize;\n+\tunsigned int hshift, i;\n \tconst unsigned char *data;\n \tstruct index *entry, **hash;\n \tvoid *mem;\n \n \t/* determine index hash size */\n-\tentries = (bufsize + BLK_SIZE - 1) / BLK_SIZE;\n-\thsize = entries / 4;\n-\tfor (i = 4; (1 << i) < hsize && i < 16; i++);\n+\thsize = bufsize / 4;\n+\tfor (i = 8; (1 << i) < hsize && i < 16; i++);\n \thsize = 1 << i;\n-\thshift = 32 - i;\n+\thshift = i - 8;\n \t*hash_shift = hshift;\n \n \t/* allocate lookup index */\n-\tmem = malloc(hsize * sizeof(*hash) + entries * sizeof(*entry));\n+\tmem = malloc(hsize * sizeof(*hash) + bufsize * sizeof(*entry));\n \tif (!mem)\n \t\treturn NULL;\n \thash = mem;\n@@ -64,17 +54,12 @@ static struct index ** delta_index(const\n \tmemset(hash, 0, hsize * sizeof(*hash));\n \n \t/* then populate it */\n-\tdata = buf + entries * BLK_SIZE - BLK_SIZE;\n-\tblksize = bufsize - (data - buf);\n-\twhile (data >= buf) {\n-\t\tunsigned int val = adler32(0, data, blksize);\n-\t\ti = HASH(val, hshift);\n-\t\tentry->ptr = data;\n-\t\tentry->val = val;\n+\tdata = buf + bufsize - 2;\n+\twhile (data > buf) {\n+\t\tentry->ptr = --data;\n+\t\ti = data[0] ^ data[1] ^ (data[2] << hshift);\n \t\tentry->next = hash[i];\n \t\thash[i] = entry++;\n-\t\tblksize = BLK_SIZE;\n-\t\tdata -= BLK_SIZE;\n \t}\n \n \treturn hash;\n@@ -141,29 +126,27 @@ void *diff_delta(void *from_buf, unsigne\n \n \twhile (data < top) {\n \t\tunsigned int moff = 0, msize = 0;\n-\t\tunsigned int blksize = MIN(top - data, BLK_SIZE);\n-\t\tunsigned int val = adler32(0, data, blksize);\n-\t\ti = HASH(val, hash_shift);\n-\t\tfor (entry = hash[i]; entry; entry = entry->next) {\n-\t\t\tconst unsigned char *ref = entry->ptr;\n-\t\t\tconst unsigned char *src = data;\n-\t\t\tunsigned int ref_size = ref_top - ref;\n-\t\t\tif (entry->val != val)\n-\t\t\t\tcontinue;\n-\t\t\tif (ref_size > top - src)\n-\t\t\t\tref_size = top - src;\n-\t\t\twhile (ref_size && *src++ == *ref) {\n-\t\t\t\tref++;\n-\t\t\t\tref_size--;\n-\t\t\t}\n-\t\t\tref_size = ref - entry->ptr;\n-\t\t\tif (ref_size > msize) {\n-\t\t\t\t/* this is our best match so far */\n-\t\t\t\tmoff = entry->ptr - ref_data;\n-\t\t\t\tmsize = ref_size;\n-\t\t\t\tif (msize >= 0x10000) {\n-\t\t\t\t\tmsize = 0x10000;\n+\t\tif (data + 2 < top) {\n+\t\t\ti = data[0] ^ data[1] ^ (data[2] << hash_shift);\n+\t\t\tfor (entry = hash[i]; entry; entry = entry->next) {\n+\t\t\t\tconst unsigned char *ref = entry->ptr;\n+\t\t\t\tconst unsigned char *src = data;\n+\t\t\t\tunsigned int ref_size = ref_top - ref;\n+\t\t\t\tif (ref_size > top - src)\n+\t\t\t\t\tref_size = top - src;\n+\t\t\t\tif (ref_size > 0x10000)\n+\t\t\t\t\tref_size = 0x10000;\n+\t\t\t\tif (ref_size <= msize)\n \t\t\t\t\tbreak;\n+\t\t\t\twhile (ref_size && *src++ == *ref) {\n+\t\t\t\t\tref++;\n+\t\t\t\t\tref_size--;\n+\t\t\t\t}\n+\t\t\t\tref_size = ref - entry->ptr;\n+\t\t\t\tif (msize < ref - entry->ptr) {\n+\t\t\t\t\t/* this is our best match so far */\n+\t\t\t\t\tmsize = ref - entry->ptr;\n+\t\t\t\t\tmoff = entry->ptr - ref_data;\n \t\t\t\t}\n \t\t\t}\n \t\t}\n-- \n1.2.2.g6643-dirty\n"},{"id":"16659","messageId":"7v4q2pf8fq.fsf@assigned-by-dhcp.cox.net","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602212043260.5606@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-24T08:49:13Z","receivedAt":"2006-02-24T08:49:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Indexing based on adler32 has a match precision based on the block size \n> (currently 16). Lowering the block size would produce smaller deltas \n> but the indexing memory and computing cost increases significantly.\n\nIndeed.\n\nI had this patch in my personal tree for a while. I was\nwondring why sometimes progress indication during \"Deltifying\"\nstage stops for literally several seconds, or more.\n\nIn Linux 2.6 repository, these object pairs take forever to\ndelta.\n\n blob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f -> \n blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n size (491102 -> 496045)\n 58 seconds\n\n blob 4917ec509720a42846d513addc11cbd25e0e3c4f -> \n blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n size (495831 -> 496045)\n 64 seconds\n\nAdmittedly, these are *BAD* input samples (a binary firmware\nblob with many similar looking \", 0x\" sequences). I can see\nthat trying to reuse source materials really hard would take\nsignificant computation.\n\nHowever, this is simply unacceptable.\n\nThe new algoritm takes 58 seconds to produce 136000 bytes of\ndelta, while the old takes 0.25 seconds to produce 248899 (I am\nusing the test-delta program in git.git distribution). The\ncompression ratio is significantly better, but this is unusable\neven for offline archival use (remember, pack delta selection\nneeds to do window=10 such deltification trials to come up with\nthe best delta, so you are spending 10 minutes to save 100k from\none oddball blob), let alone on-the-fly pack generation for\nnetwork transfer.\n\nMaybe we would want two implementation next to each other, and\ninternally see if it is taking too much cycles compared to the\ninput size then switch to cheaper version?\n"},{"id":"16679","messageId":"Pine.LNX.4.64.0602241029360.23719@localhost.localdomain","threadId":"3432","inReplyTo":"7v4q2pf8fq.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-24T15:37:46Z","receivedAt":"2006-02-24T15:37:46Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > Indexing based on adler32 has a match precision based on the block size \n> > (currently 16). Lowering the block size would produce smaller deltas \n> > but the indexing memory and computing cost increases significantly.\n> \n> Indeed.\n> \n> I had this patch in my personal tree for a while. I was\n> wondring why sometimes progress indication during \"Deltifying\"\n> stage stops for literally several seconds, or more.\n\nNote that above I'm saying that _keeping_ adler32 for small blocks is \neven longer. In other words, for small blocks, the version not using \nadler32 is about 3 times faster. \n\nI also noticed the significant slowdown after I made the \nimproved progress patch. The idea now has to do with detecting \npatological cases and breaking out of them early.\n\n> In Linux 2.6 repository, these object pairs take forever to\n> delta.\n> \n> blob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f -> \n> blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n> size (491102 -> 496045)\n> 58 seconds\n> \n> blob 4917ec509720a42846d513addc11cbd25e0e3c4f -> \n> blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n> size (495831 -> 496045)\n> 64 seconds\n\nThanks for this. I'll see what I can do to tweak the code to better \ncope with those. Just keep my fourth delta patch in the pu branch for \nnow.\n\n\nNicolas\n"},{"id":"16688","messageId":"20060224174422.GA13367@hpsvcnb.fc.hp.com","threadId":"3432","inReplyTo":"7v4q2pf8fq.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Carl Baldwin","fromEmail":"cnb@fc.hp.com","sentAt":"2006-02-24T17:44:22Z","receivedAt":"2006-02-24T17:44:22Z","isPatch":true,"sender":{"key":"cnb@fc.hp.com","avatar":null},"body":"Junio,\n\nThis message came to me at exactly the right time. Yesterday I was\nexploring using git as the content storage back-end for some binary\nfiles. Up until now I've only used it for software projects.\n\nI found the largest RCS file that we had in our current back-end. It\ncontained twelve versions of a binary file. Each version averaged about\n20 MB. The ,v file from RCS was about 250MB. I did some experiments on\nthese binary files.\n\nFirst, gzip consistantly is able to compress these files to about 10%\ntheir original size. So, they are quite inflated. Second, xdelta would\nproduce a delta between two neighboring revisions of about 2.5MB in size\nthat would compress down to about 2MB. (about the same size as the next\nrevision compressed without deltification so packing is ineffective\nhere).\n\nI added these 12 revisions to several version control back-ends\nincluding subversion and git. Git produced a much smaller repository\nsize than the others simply due to the compression that it applies to\nobjects. It also was at least as fast as the others.\n\nThe problem came when I tried to clone this repository.\ngit-pack-objects chewed on these 12 revisions for over an hour before I\nfinally interrupted it. As far as I could tell, it hadn't made much\nprogress.\n\nMy other complaint was that git prune ran slow (~8 seconds on my very\nfast machine with fast disk access) on a repository with only these\ntwelve revisions in it (37 total objects in the object store). This is\nbecause 'git prune' actually ends up running fsck on all of the objects\nwhich verifies the sha1 of each object. This seems like a lot of work\njust to prune unwanted objects. What would you say to a --fast option\nto git-prune that would avoid most of what fsck does including verifying\nsha1 for each object?\n\nAnyway, that was a tangent. I looked into to overriding the --depth\noption to git-pack-objects and set it to 0. However, this isn't\ntrivial. git-pack-objects is never called directly by the user. It is\nonly called through things like 'git clone', 'git push' and 'git\nrepack'. What do you think about this? Could we add a configuration\noption that could be set for the repository? Something smarter like\nwhat you suggest where git would pack small text files but give up on\nlarge binaries would be optimal.\n\nI've already determined that packing a repository with this type of\nlargish binary file doesn't do any good but there doesn't seem to be a\nway to avoid packing when doing network operations.\n\nThoughts?\nCarl\n\nOn Fri, Feb 24, 2006 at 12:49:13AM -0800, Junio C Hamano wrote:\n> Nicolas Pitre writes:\n> \n> > Indexing based on adler32 has a match precision based on the block size \n> > (currently 16). Lowering the block size would produce smaller deltas \n> > but the indexing memory and computing cost increases significantly.\n> \n> Indeed.\n> \n> I had this patch in my personal tree for a while. I was\n> wondring why sometimes progress indication during \"Deltifying\"\n> stage stops for literally several seconds, or more.\n> \n> In Linux 2.6 repository, these object pairs take forever to\n> delta.\n> \n> blob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f -> \n> blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n> size (491102 -> 496045)\n> 58 seconds\n> \n> blob 4917ec509720a42846d513addc11cbd25e0e3c4f -> \n> blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n> size (495831 -> 496045)\n> 64 seconds\n> \n> Admittedly, these are *BAD* input samples (a binary firmware\n> blob with many similar looking \", 0x\" sequences). I can see\n> that trying to reuse source materials really hard would take\n> significant computation.\n> \n> However, this is simply unacceptable.\n> \n> The new algoritm takes 58 seconds to produce 136000 bytes of\n> delta, while the old takes 0.25 seconds to produce 248899 (I am\n> using the test-delta program in git.git distribution). The\n> compression ratio is significantly better, but this is unusable\n> even for offline archival use (remember, pack delta selection\n> needs to do window=10 such deltification trials to come up with\n> the best delta, so you are spending 10 minutes to save 100k from\n> one oddball blob), let alone on-the-fly pack generation for\n> network transfer.\n> \n> Maybe we would want two implementation next to each other, and\n> internally see if it is taking too much cycles compared to the\n> input size then switch to cheaper version?\n> \n> -\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n> \n\n-- \n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n Carl Baldwin RADCAD (R&D CAD)\n Hewlett Packard Company\n MS 88 work: 970 898-1523\n 3404 E. Harmony Rd. work: Carl.N.Baldwin@hp.com\n Fort Collins, CO 80525 home: Carl@ecBaldwin.net\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n"},{"id":"16690","messageId":"Pine.LNX.4.64.0602241252300.31162@localhost.localdomain","threadId":"3432","inReplyTo":"20060224174422.GA13367@hpsvcnb.fc.hp.com","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-24T17:56:04Z","receivedAt":"2006-02-24T17:56:04Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Carl Baldwin wrote:\n\n> Junio,\n> \n> This message came to me at exactly the right time. Yesterday I was\n> exploring using git as the content storage back-end for some binary\n> files. Up until now I've only used it for software projects.\n> \n> I found the largest RCS file that we had in our current back-end. It\n> contained twelve versions of a binary file. Each version averaged about\n> 20 MB. The ,v file from RCS was about 250MB. I did some experiments on\n> these binary files.\n> \n> First, gzip consistantly is able to compress these files to about 10%\n> their original size. So, they are quite inflated. Second, xdelta would\n> produce a delta between two neighboring revisions of about 2.5MB in size\n> that would compress down to about 2MB. (about the same size as the next\n> revision compressed without deltification so packing is ineffective\n> here).\n> \n> I added these 12 revisions to several version control back-ends\n> including subversion and git. Git produced a much smaller repository\n> size than the others simply due to the compression that it applies to\n> objects. It also was at least as fast as the others.\n> \n> The problem came when I tried to clone this repository.\n> git-pack-objects chewed on these 12 revisions for over an hour before I\n> finally interrupted it. As far as I could tell, it hadn't made much\n> progress.\n\nI must ask if you had applied my latest delta patches?\n\nAlso did you use a recent version of git that implements pack data \nreuse?\n\n\nNicolas\n"},{"id":"16694","messageId":"20060224183554.GA31247@hpsvcnb.fc.hp.com","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241252300.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Carl Baldwin","fromEmail":"cnb@fc.hp.com","sentAt":"2006-02-24T18:35:54Z","receivedAt":"2006-02-24T18:35:54Z","isPatch":true,"sender":{"key":"cnb@fc.hp.com","avatar":null},"body":"On Fri, Feb 24, 2006 at 12:56:04PM -0500, Nicolas Pitre wrote:\nMy version is 1.2.1. I have not been following your work. When was\npack data reuse introduced? From where can I obtain your delta patches?\n\nThere is really no opportunity for pack-data reuse in this case. The\nrepository had never been packed or cloned in the first place. As I\nsaid, I do not intend to pack these binary files at all since there is\nno benefit in this case.\n\nThe delta patches may help but I can't say for sure since I don't know\nanything about them. Let me know where I can get them.\n\nCarl\n\n> \n> I must ask if you had applied my latest delta patches?\n> \n> Also did you use a recent version of git that implements pack data \n> reuse?\n> \n> \n> Nicolas\n> -\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n> \n\n-- \n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n Carl Baldwin RADCAD (R&D CAD)\n Hewlett Packard Company\n MS 88 work: 970 898-1523\n 3404 E. Harmony Rd. work: Carl.N.Baldwin@hp.com\n Fort Collins, CO 80525 home: Carl@ecBaldwin.net\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n"},{"id":"16695","messageId":"20060224184934.GA387@hpsvcnb.fc.hp.com","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241252300.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Carl Baldwin","fromEmail":"cnb@fc.hp.com","sentAt":"2006-02-24T18:49:34Z","receivedAt":"2006-02-24T18:49:34Z","isPatch":true,"sender":{"key":"cnb@fc.hp.com","avatar":null},"body":"I've updated to a very current master branch. This seems to include the\npack data reuse stuff. I've not made an attempt yet to apply your delta\npatches.\n\ngit-repack quickly gets up to 5% (2/36) and hangs there. I'll let it\nrun for a while just to see how far it claims to get. I'm not hopeful.\n\nMaybe your patches can help?\n\nCarl\n\nOn Fri, Feb 24, 2006 at 12:56:04PM -0500, Nicolas Pitre wrote:\n> On Fri, 24 Feb 2006, Carl Baldwin wrote:\n> \n> > Junio,\n> > \n> > This message came to me at exactly the right time. Yesterday I was\n> > exploring using git as the content storage back-end for some binary\n> > files. Up until now I've only used it for software projects.\n> > \n> > I found the largest RCS file that we had in our current back-end. It\n> > contained twelve versions of a binary file. Each version averaged about\n> > 20 MB. The ,v file from RCS was about 250MB. I did some experiments on\n> > these binary files.\n> > \n> > First, gzip consistantly is able to compress these files to about 10%\n> > their original size. So, they are quite inflated. Second, xdelta would\n> > produce a delta between two neighboring revisions of about 2.5MB in size\n> > that would compress down to about 2MB. (about the same size as the next\n> > revision compressed without deltification so packing is ineffective\n> > here).\n> > \n> > I added these 12 revisions to several version control back-ends\n> > including subversion and git. Git produced a much smaller repository\n> > size than the others simply due to the compression that it applies to\n> > objects. It also was at least as fast as the others.\n> > \n> > The problem came when I tried to clone this repository.\n> > git-pack-objects chewed on these 12 revisions for over an hour before I\n> > finally interrupted it. As far as I could tell, it hadn't made much\n> > progress.\n> \n> I must ask if you had applied my latest delta patches?\n> \n> Also did you use a recent version of git that implements pack data \n> reuse?\n> \n> \n> Nicolas\n> -\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n> \n\n-- \n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n Carl Baldwin RADCAD (R&D CAD)\n Hewlett Packard Company\n MS 88 work: 970 898-1523\n 3404 E. Harmony Rd. work: Carl.N.Baldwin@hp.com\n Fort Collins, CO 80525 home: Carl@ecBaldwin.net\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n"},{"id":"16696","messageId":"Pine.LNX.4.64.0602241350190.31162@localhost.localdomain","threadId":"3432","inReplyTo":"20060224183554.GA31247@hpsvcnb.fc.hp.com","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-24T18:57:20Z","receivedAt":"2006-02-24T18:57:20Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Carl Baldwin wrote:\n\n> My version is 1.2.1. I have not been following your work. When was\n> pack data reuse introduced?\n\nTry out version 1.2.3.\n\n> From where can I obtain your delta patches?\n\nForget them for now -- they won't help you.\n\n> There is really no opportunity for pack-data reuse in this case. The\n> repository had never been packed or cloned in the first place. As I\n> said, I do not intend to pack these binary files at all since there is\n> no benefit in this case.\n\nYes there is, as long as you have version 1.2.3. The clone logic will \nsimply reuse already packed data without attempting to recompute it.\n\n> The delta patches may help but I can't say for sure since I don't know\n> anything about them.\n\nThey (actually the last one) might help reduce the size of resulting \npacks but it currently has performance problems with some patological \ndata sets.\n\nI think you really should try git version 1.2.3 with a packed \nrepository. It might handle your special case just fine.\n\n\nNicolas\n"},{"id":"16697","messageId":"Pine.LNX.4.64.0602241358070.31162@localhost.localdomain","threadId":"3432","inReplyTo":"20060224184934.GA387@hpsvcnb.fc.hp.com","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-24T19:03:29Z","receivedAt":"2006-02-24T19:03:29Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Carl Baldwin wrote:\n\n> I've updated to a very current master branch. This seems to include the\n> pack data reuse stuff. I've not made an attempt yet to apply your delta\n> patches.\n> \n> git-repack quickly gets up to 5% (2/36) and hangs there. I'll let it\n> run for a while just to see how far it claims to get. I'm not hopeful.\n\nIt should complete sometimes, probably after the same amount of time \nneeded by your previous clone attempt. But after that any clone \noperation should be quick. This is clearly unacceptable but at least \nwith the pack data reuse you should suffer only once for the initial \nrepack.\n\n> Maybe your patches can help?\n\nNo. They actually make things worse performance wise, much worse in \nsome special cases.\n\nIs it possible for me to have access to 2 consecutive versions of your \nbig binary file?\n\n\nNicolas\n"},{"id":"16699","messageId":"20060224192354.GC387@hpsvcnb.fc.hp.com","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241350190.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Carl Baldwin","fromEmail":"cnb@fc.hp.com","sentAt":"2006-02-24T19:23:54Z","receivedAt":"2006-02-24T19:23:54Z","isPatch":true,"sender":{"key":"cnb@fc.hp.com","avatar":null},"body":"On Fri, Feb 24, 2006 at 01:57:20PM -0500, Nicolas Pitre wrote:\n> On Fri, 24 Feb 2006, Carl Baldwin wrote:\n> \n> > My version is 1.2.1. I have not been following your work. When was\n> > pack data reuse introduced?\n> \n> Try out version 1.2.3.\n\nI'm on it now.\n\n> > From where can I obtain your delta patches?\n> \n> Forget them for now -- they won't help you.\n\nAh, I have been looking at your patches and clearly they will not help.\n\n> > There is really no opportunity for pack-data reuse in this case. The\n> > repository had never been packed or cloned in the first place. As I\n> > said, I do not intend to pack these binary files at all since there is\n> > no benefit in this case.\n> \n> Yes there is, as long as you have version 1.2.3. The clone logic will \n> simply reuse already packed data without attempting to recompute it.\n\nI meant that there is no benefit in disk space usage. Packing may\nactually increase my disk space usage in this case. Refer to what I\nsaid about experimentally running gzip and xdelta on the files\nindependantly of git.\n\nI see what you're saying about this data reuse helping to speed up\nsubsequent cloning operations. However, if packing takes this long and\ndoesn't give me any disk space savings then I don't want to pay the very\nheavy price of packing these files even the first time nor do I want to\npay the price incrementally.\n\nThe most I would tolerate for the first pack is a few seconds. The most\nI would tolerate for any incremental pack is about 1 second.\n\nBTW, git repack has been going for 30 minutes and has packed 4/36\nobjects. :-)\n\n> I think you really should try git version 1.2.3 with a packed \n> repository. It might handle your special case just fine.\n\nNo, not when I'm not willing to pay the price to pack even once. This\nisn't a case where I have one such repository and 'once its been packed\nthen its packed'. This is only one example of such a repository. I am\nlooking for a process for revisioning this type of data that will be\nused over and over. Git may not be the answer here but it sure is\nlooking good in many other ways.\n\nI think the right answer would be for git to avoid trying to pack files\nlike this. Junio mentioned something like this in his message.\n\nThanks for your input.\n\nCheers,\nCarl\n\n-- \n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n Carl Baldwin RADCAD (R&D CAD)\n Hewlett Packard Company\n MS 88 work: 970 898-1523\n 3404 E. Harmony Rd. work: Carl.N.Baldwin@hp.com\n Fort Collins, CO 80525 home: Carl@ecBaldwin.net\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n"},{"id":"16702","messageId":"Pine.LNX.4.64.0602241438521.31162@localhost.localdomain","threadId":"3432","inReplyTo":"20060224192354.GC387@hpsvcnb.fc.hp.com","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-24T20:02:07Z","receivedAt":"2006-02-24T20:02:07Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Carl Baldwin wrote:\n\n> I see what you're saying about this data reuse helping to speed up\n> subsequent cloning operations. However, if packing takes this long and\n> doesn't give me any disk space savings then I don't want to pay the very\n> heavy price of packing these files even the first time nor do I want to\n> pay the price incrementally.\n\nOf course. There is admitedly a problem here. I'm just abusing a bit \nof your time to properly identify its parameters.\n\n> The most I would tolerate for the first pack is a few seconds. The most\n> I would tolerate for any incremental pack is about 1 second.\n\nWell that is probably a bit tight. Ideally it should be linear with the \nsize of the data set to process. If you have 10 files 10MB each it \nshould take about the same time to pack than 10000 files of 10KB each. \nOf course incrementally packing one additional 10MB file might take more \nthan a second although it is only one file.\n \n> BTW, git repack has been going for 30 minutes and has packed 4/36\n> objects. :-)\n\nPathetic.\n\n> I think the right answer would be for git to avoid trying to pack files\n> like this. Junio mentioned something like this in his message.\n\nYes. First we could add an additional parameter to the repacking \nstrategy which is the undeltified but deflated size of an object. That \nwould prevent any deltas to become bigger than the simply deflated \nversion.\n\nRemains the delta performance issue. I think I know what the problem \nis. I'm not sure I know what the best solution would be though. The \npatological data set is easy to identify quickly and one strategy might \nsimply to bail out early when it happens and therefore not attempt any \ndelta.\n\nHowever, if you could let me play with two samples of your big file I'd \nbe grateful. If so I'd like to make git work well with your data set \ntoo which is not that uncommon after all.\n\n\nNicolas\n"},{"id":"16704","messageId":"Pine.LNX.4.64.0602241152290.22647@g5.osdl.org","threadId":"3432","inReplyTo":"20060224192354.GC387@hpsvcnb.fc.hp.com","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-24T20:02:51Z","receivedAt":"2006-02-24T20:02:51Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 24 Feb 2006, Carl Baldwin wrote:\n> \n> I meant that there is no benefit in disk space usage. Packing may\n> actually increase my disk space usage in this case. Refer to what I\n> said about experimentally running gzip and xdelta on the files\n> independantly of git.\n\nYes. The deltas tend to compress a lot less well than \"normal\" files.\n\n> I see what you're saying about this data reuse helping to speed up\n> subsequent cloning operations. However, if packing takes this long and\n> doesn't give me any disk space savings then I don't want to pay the very\n> heavy price of packing these files even the first time nor do I want to\n> pay the price incrementally.\n\nI would look at tuning the heuristics in \"try_delta()\" (pack-objects.c) a \nbit. That's the place that decides whether to even bother trying to make a \ndelta, and how big a delta is acceptable. For example, looking at them, I \nalready see one bug:\n\n\t..\n sizediff = oldsize > size ? oldsize - size : size - oldsize;\n if (sizediff > size / 8)\n return -1;\n\t..\n\nwe really should compare sizediff to the _smaller_ of the two sizes, and \nskip the delta if the difference in sizes is bound to be bigger than that.\n\nHowever, the \"size / 8\" thing isn't a very strict limit anyway, so this \nprobably doesn't matter (and I think Nico already removed it as part of \nhis patches: the heuristic can make us avoid some deltas that would be \nok).\n\nThe other thing to look at is \"max_size\": right now it initializes that to \n\"size / 2 - 20\", which just says that we don't ever want a delta that is \nlarger than about half the result (plus the 20 byte overhead for pointing \nto the thing we delta against). Again, if you feel that normal compression \ncompresses better than half, you could try changing that to\n\n\t..\n\tmax_size = size / 4 - 20;\n\t..\n\nor something like that instead (but then you need to check that it's still \npositive - otherwise the comparisons with unsigned later on are screwed \nup. Right now that value is guaranteed to be positive if only because we \nalready checked\n\n\t..\n\tif (size < 50)\n\t\treturn -1;\n\t..\n\nearlier).\n\nNOTE! Every SINGLE one of those heuristics are just totally made up by \nyours truly, and have no testing behind them. They're more of the type \n\"that sounds about right\" than \"this is how it must be\". As mentioned, \nNico has already been playing with the heuristics - but he wanted better \npacks, not better CPU usage, so he went the other way from what you would \nwant to try..\n\n\t\tLinus\n"},{"id":"16705","messageId":"Pine.LNX.4.64.0602241509050.31162@localhost.localdomain","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241152290.22647@g5.osdl.org","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-24T20:19:39Z","receivedAt":"2006-02-24T20:19:39Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Linus Torvalds wrote:\n\n> The other thing to look at is \"max_size\": right now it initializes that to \n> \"size / 2 - 20\", which just says that we don't ever want a delta that is \n> larger than about half the result (plus the 20 byte overhead for pointing \n> to the thing we delta against). Again, if you feel that normal compression \n> compresses better than half, you could try changing that to\n> \n> \t..\n> \tmax_size = size / 4 - 20;\n> \t..\n\nLike I mentioned, max_size should also be caped with the deflated \nundeltified object \nsize. This value is easy to get since plain objects are already \ndeflated.\n\n> NOTE! Every SINGLE one of those heuristics are just totally made up by \n> yours truly, and have no testing behind them. They're more of the type \n> \"that sounds about right\" than \"this is how it must be\". As mentioned, \n> Nico has already been playing with the heuristics - but he wanted better \n> packs, not better CPU usage, so he went the other way from what you would \n> want to try..\n\nActually it's a good balance I'm after.\n\nUsing 30% more CPU for 10% smaller packs is OK I'd say.\n\nUsing 100 times the CPU for 50% saving on only one particular delta is \nnot acceptable.\n\nAnd using more than one hour for 200MB of data with the current window \ndefault is not acceptable either.\n\n\nNicolas\n"},{"id":"16706","messageId":"20060224204022.GA15962@hpsvcnb.fc.hp.com","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241438521.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Carl Baldwin","fromEmail":"cnb@fc.hp.com","sentAt":"2006-02-24T20:40:22Z","receivedAt":"2006-02-24T20:40:22Z","isPatch":true,"sender":{"key":"cnb@fc.hp.com","avatar":null},"body":"On Fri, Feb 24, 2006 at 03:02:07PM -0500, Nicolas Pitre wrote:\n> Well that is probably a bit tight. Ideally it should be linear with the \n> size of the data set to process. If you have 10 files 10MB each it \n> should take about the same time to pack than 10000 files of 10KB each. \n> Of course incrementally packing one additional 10MB file might take more \n> than a second although it is only one file.\n\nWell, I might not have been fair here. I tried an experiment where I\npacked each of the twelve large blob objects explicitly one-by-one using\ngit-pack-objects. Incrementally packing each single object was very\nfast. Well under a second per object on my machine.\n\nAfter the twelve large objects were packed into individual packs the\nrest of the packing went very quickly and git v1.2.3's date reuse worked\nvery well. This was sort of my attempt at simulating how things would\nbe if git avoided deltification of each of these large files. I'm sorry\nto have been so harsh earlier I just didn't understand that\nincrementally packing one-by-one was going to help this much.\n\nThis gives me hope that if somehow git were to not attempt to deltify\nthese objects then performance would be much better than acceptible.\n\n[snip]\n> However, if you could let me play with two samples of your big file I'd \n> be grateful. If so I'd like to make git work well with your data set \n> too which is not that uncommon after all.\n\nI would be happy to do this. I will probably need to scrub a bit and\nmake sure that the result shows the same characteristics. How would you\nlike me to deliver these files to you? They are about 25 MB deflated.\n\nCarl\n\n-- \n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n Carl Baldwin RADCAD (R&D CAD)\n Hewlett Packard Company\n MS 88 work: 970 898-1523\n 3404 E. Harmony Rd. work: Carl.N.Baldwin@hp.com\n Fort Collins, CO 80525 home: Carl@ecBaldwin.net\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n"},{"id":"16708","messageId":"7vpslc8oni.fsf@assigned-by-dhcp.cox.net","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241152290.22647@g5.osdl.org","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-24T20:53:05Z","receivedAt":"2006-02-24T20:53:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> NOTE! Every SINGLE one of those heuristics are just totally made up by \n> yours truly, and have no testing behind them. They're more of the type \n> \"that sounds about right\" than \"this is how it must be\". As mentioned, \n> Nico has already been playing with the heuristics - but he wanted better \n> packs, not better CPU usage, so he went the other way from what you would \n> want to try..\n\nI haven't looked at Nico's original or updated code closely at\nall, but two things come to mind.\n\n(1) if we could tell the particular data is intrinsically\n diff_delta unfriendly and diff_delta would waste too much\n time when tried to delta against almost _any_ other blob,\n then it might help to give an interface in diff-delta.c for\n the caller to check for such a blob without even trying\n diff_delta.\n\n(2) otherwise, if diff_delta could detect it would spend too\n many cycles to finish its work for a particular input early\n on, we might want it to bail out instead of trying a\n complete job.\n"},{"id":"16709","messageId":"Pine.LNX.4.64.0602241544270.31162@localhost.localdomain","threadId":"3432","inReplyTo":"20060224204022.GA15962@hpsvcnb.fc.hp.com","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-24T21:12:14Z","receivedAt":"2006-02-24T21:12:14Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Carl Baldwin wrote:\n\n> On Fri, Feb 24, 2006 at 03:02:07PM -0500, Nicolas Pitre wrote:\n> > Well that is probably a bit tight. Ideally it should be linear with the \n> > size of the data set to process. If you have 10 files 10MB each it \n> > should take about the same time to pack than 10000 files of 10KB each. \n> > Of course incrementally packing one additional 10MB file might take more \n> > than a second although it is only one file.\n> \n> Well, I might not have been fair here. I tried an experiment where I\n> packed each of the twelve large blob objects explicitly one-by-one using\n> git-pack-objects. Incrementally packing each single object was very\n> fast. Well under a second per object on my machine.\n> \n> After the twelve large objects were packed into individual packs the\n> rest of the packing went very quickly and git v1.2.3's date reuse worked\n> very well. This was sort of my attempt at simulating how things would\n> be if git avoided deltification of each of these large files. I'm sorry\n> to have been so harsh earlier I just didn't understand that\n> incrementally packing one-by-one was going to help this much.\n\nHmmmmmmm....\n\nI don't think I understand what is going on here.\n\nYou say that, if you add those big files and incrementally repack after \neach commit using git repack with no option, then it requires only about \none second each time. Right?\n\nBut if you use \"git-repack -a -f\" then it is gone for more than an hour?\n\nI'd expect something like 2 * (sum i for i = 1 to 10) i.e. in the 110 \nsecond range due to the combinatorial effect when repacking everything. \nThis is far from one hour and something appears to be really really \nwrong.\n\nHow many files besides those 12 big blobs do you have?\n\n> This gives me hope that if somehow git were to not attempt to deltify\n> these objects then performance would be much better than acceptible.\n> \n> [snip]\n> > However, if you could let me play with two samples of your big file I'd \n> > be grateful. If so I'd like to make git work well with your data set \n> > too which is not that uncommon after all.\n> \n> I would be happy to do this. I will probably need to scrub a bit and\n> make sure that the result shows the same characteristics. How would you\n> like me to deliver these files to you? They are about 25 MB deflated.\n\nIf you can add them into a single .tgz with instructions on how \nto reproduce the issue and provide me with an URL where I can fetch it \nthat'd be perfect.\n\n\nNicolas\n"},{"id":"16710","messageId":"Pine.LNX.4.64.0602241613030.31162@localhost.localdomain","threadId":"3432","inReplyTo":"7vpslc8oni.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-24T21:39:42Z","receivedAt":"2006-02-24T21:39:42Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Junio C Hamano wrote:\n\n> I haven't looked at Nico's original or updated code closely at\n> all, but two things come to mind.\n> \n> (1) if we could tell the particular data is intrinsically\n> diff_delta unfriendly and diff_delta would waste too much\n> time when tried to delta against almost _any_ other blob,\n> then it might help to give an interface in diff-delta.c for\n> the caller to check for such a blob without even trying\n> diff_delta.\n> \n> (2) otherwise, if diff_delta could detect it would spend too\n> many cycles to finish its work for a particular input early\n> on, we might want it to bail out instead of trying a\n> complete job.\n\nI have a patch that implements an hybrid approach.\n\nCurrently, diff-delta takes blocks of data in the reference file and \nhash them. When the target file is scanned, it uses the hash to match \nblocks from the target file with the reference file.\n\nIf blocks are hashed evenly the cost of producing a delta is at most \nO(n+m) where n and m are the size of the reference and target files \nrespectively. In other words, with good data set the cost is linear.\n\nBut if many blocks from the reference buffer do hash to the same bucket \nthen for each block in the target file many blocks from the reference \nbuffer have to be tested against, making it tend towards O(n^m) which is \npretty highly exponential.\n\nThe solution I'm investigating is to put a limit on the number of \nentries in the same hash bucket so to bring the cost back to something \nmore linear. That means the delta might miss on better matches that \nhave not been hashed but still benefit from a limited set. Experience \nseems to show that the time to deltify the first two blobs you found to \nbe problematic can be reduced by 2 orders of magnitude with about only \n10% increase in the resulting delta size, and still nearly 40% smaller \nthan what the current delta code produces.\n\nThe question is how to determine the best limit on the number of entries \nin the same hash bucket.\n\n\nNicolas\n"},{"id":"16712","messageId":"Pine.LNX.4.64.0602241647250.31162@localhost.localdomain","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241613030.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-24T21:48:54Z","receivedAt":"2006-02-24T21:48:54Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Nicolas Pitre wrote:\n\n> If blocks are hashed evenly the cost of producing a delta is at most \n> O(n+m) where n and m are the size of the reference and target files \n> respectively. In other words, with good data set the cost is linear.\n> \n> But if many blocks from the reference buffer do hash to the same bucket \n> then for each block in the target file many blocks from the reference \n> buffer have to be tested against, making it tend towards O(n^m) which is \n> pretty highly exponential.\n\nWell, actually this is rather O(n*m) not O(n^m), but bad nevertheless.\n\n\nNicolas\n"},{"id":"16716","messageId":"20060224225023.GA28538@hpsvcnb.fc.hp.com","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241544270.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Carl Baldwin","fromEmail":"cnb@fc.hp.com","sentAt":"2006-02-24T22:50:23Z","receivedAt":"2006-02-24T22:50:23Z","isPatch":true,"sender":{"key":"cnb@fc.hp.com","avatar":null},"body":"On Fri, Feb 24, 2006 at 04:12:14PM -0500, Nicolas Pitre wrote:\n> On Fri, 24 Feb 2006, Carl Baldwin wrote:\n> > After the twelve large objects were packed into individual packs the\n> > rest of the packing went very quickly and git v1.2.3's date reuse worked\n> > very well. This was sort of my attempt at simulating how things would\n> > be if git avoided deltification of each of these large files. I'm sorry\n> > to have been so harsh earlier I just didn't understand that\n> > incrementally packing one-by-one was going to help this much.\n> \n> Hmmmmmmm....\n> \n> I don't think I understand what is going on here.\n> \n> You say that, if you add those big files and incrementally repack after \n> each commit using git repack with no option, then it requires only about \n> one second each time. Right?\n\nWell, actually I was packing them individually by calling\ngit-pack-objects directly on each blob.\n\nI'll try doing it exactly as you describe...\n\nOk, I tried it. Basically I do the following.\n\n% mkdir test\n% cd test\n% git init-db\n% cp ../files/binfile.1 binfile\n% time git add binfile\n\nreal 0m2.459s\nuser 0m2.443s\nsys 0m0.019s\n% git commit -a -m \"Rev 1\"\n% time git repack\n[snip]\n\nreal 0m1.111s\nuser 0m1.046s\nsys 0m0.061s\n% for i in $(seq 2 12); do\n cp ../files/binfile.$i binfile\n time git commit -a -m \"Rev $i\"\n time git repack\ndone\n\nEach commit takes around 2.8-3.5 seconds and each repack takes about\n1.2-1.5 seconds. These are prettly reasonable.\n\nNow, I try 'git repack -a -f' (or even without -f) and it goes out to\nlunch. I think it would take on the order of a day to actually finish\nbecause it wasn't very far after an hour.\n\n[snip]\n> How many files besides those 12 big blobs do you have?\n\nThis repository has been completely stripped to the 12 revisions of the\none file. So, there are 36 objects.\n\n12 blobs.\n12 trees.\n12 commits.\n\nThat is all.\n\n[snip]\n> If you can add them into a single .tgz with instructions on how \n> to reproduce the issue and provide me with an URL where I can fetch it \n> that'd be perfect.\n\nI will do this in an email off of the list because these files really\nshouldn't be available on a public list.\n\nCarl\n\n-- \n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n Carl Baldwin RADCAD (R&D CAD)\n Hewlett Packard Company\n MS 88 work: 970 898-1523\n 3404 E. Harmony Rd. work: Carl.N.Baldwin@hp.com\n Fort Collins, CO 80525 home: Carl@ecBaldwin.net\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n"},{"id":"16718","messageId":"7vfym88g74.fsf@assigned-by-dhcp.cox.net","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241029360.23719@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-24T23:55:43Z","receivedAt":"2006-02-24T23:55:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Fri, 24 Feb 2006, Junio C Hamano wrote:\n>\n>> In Linux 2.6 repository, these object pairs take forever to\n>> delta.\n>> \n>> blob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f -> \n>> blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n>> size (491102 -> 496045)\n>> 58 seconds\n>> \n>> blob 4917ec509720a42846d513addc11cbd25e0e3c4f -> \n>> blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n>> size (495831 -> 496045)\n>> 64 seconds\n>\n> Thanks for this. I'll see what I can do to tweak the code to better \n> cope with those. Just keep my fourth delta patch in the pu branch for \n> now.\n\nIf apply this on top of pack-objects.c, you can find more of\nthem yourself.\n\n---\ndiff --git a/pack-objects.c b/pack-objects.c\nindex be7a200..3f88e86 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -62,6 +62,7 @@ static const char *base_name;\n static unsigned char pack_file_sha1[20];\n static int progress = 1;\n static volatile int progress_update = 0;\n+static volatile int progress_update_cnt = 0;\n \n /*\n * The object names in objects array are hashed with this hashtable,\n@@ -826,6 +827,7 @@ static int try_delta(struct unpacked *cu\n \tstruct object_entry *old_entry = old->entry;\n \tint old_preferred = (old_entry->preferred_base ||\n \t\t\t old_entry->based_on_preferred);\n+\tint last_up;\n \tunsigned long size, oldsize, delta_size, sizediff;\n \tlong max_size;\n \tvoid *delta_buf;\n@@ -890,8 +892,17 @@ static int try_delta(struct unpacked *cu\n \t}\n \tif (sizediff >= max_size)\n \t\treturn -1;\n+\tlast_up = progress_update_cnt;\n \tdelta_buf = diff_delta(old->data, oldsize,\n \t\t\t cur->data, size, &delta_size, max_size);\n+\tif (last_up + 1 < progress_update_cnt) {\n+\t\t/* It took more than one second */\n+\t\tfprintf(stderr, \"%d -> %d: %s -> \",\n+\t\t\tlast_up, progress_update_cnt,\n+\t\t\tsha1_to_hex(old_entry->sha1));\n+\t\tfprintf(stderr, \"%s (%lu -> %lu)\\n\",\n+\t\t\tsha1_to_hex(cur_entry->sha1), oldsize, size);\n+\t}\n \tif (!delta_buf)\n \t\treturn 0;\n \tcur_entry->delta = old_entry;\n@@ -906,6 +917,7 @@ static void progress_interval(int signum\n {\n \tsignal(SIGALRM, progress_interval);\n \tprogress_update = 1;\n+\tprogress_update_cnt++;\n }\n \n static void find_deltas(struct object_entry **list, int window, int depth)\n"},{"id":"16719","messageId":"Pine.LNX.4.64.0602241637480.22647@g5.osdl.org","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241613030.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-25T00:45:23Z","receivedAt":"2006-02-25T00:45:23Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 24 Feb 2006, Nicolas Pitre wrote:\n> \n> Currently, diff-delta takes blocks of data in the reference file and \n> hash them. When the target file is scanned, it uses the hash to match \n> blocks from the target file with the reference file.\n> \n> If blocks are hashed evenly the cost of producing a delta is at most \n> O(n+m) where n and m are the size of the reference and target files \n> respectively. In other words, with good data set the cost is linear.\n\nAssuming the hash is good, of course.\n\nI think this was the problem with you trying something simpler than \nadler32..\n\n> But if many blocks from the reference buffer do hash to the same bucket \n> then for each block in the target file many blocks from the reference \n> buffer have to be tested against, making it tend towards O(n^m) which is \n> pretty highly exponential.\n> \n> The solution I'm investigating is to put a limit on the number of \n> entries in the same hash bucket so to bring the cost back to something \n> more linear. That means the delta might miss on better matches that \n> have not been hashed but still benefit from a limited set.\n\nSounds fair enough.\n\nHowever, you migt also want to consider another approach..\n\nOne of the biggest costs for the xdelta algorithm is probably just the \n\"delta_prepare()\", but at the same time, that is constant wrt the source \nbuffer.\n\nNow, the sad part is that when I wrote pack-objects, I didn't really \nunderstand the diff-delta algorithm, I just plugged it in. Which means \nthat when I did it, I made the (obvious and simple) decision to keep the \n_result_ that we are looking at constant, and try to delta against \ndifferent sources.\n\nHOWEVER.\n\nI suspect you already see where this is going..\n\nWe _could_ switch the \"pack-objects\" window handling around, and instead \nof looking at the object we want to pack, and looking at the ten (or \n\"window\") previous objects to delta against, we could do it the other way \naround: keep the object we delta against constant, and see what deltas we \ncould prepare for the ten next objects.\n\nAnd since the source would now be constant, you'd need to do the \n\"delta_prepare()\" just _once_ per window, instead of every single time.\n\nNow, I haven't done any profiling on the diff-delta code, and maybe my \nguess that delta_prepare() is a pretty expensive part is wrong, and maybe \nit wouldn't help to switch the window probing around. But I thought I'd \nmention it as one thing to explore..\n\n\t\tLinus\n"},{"id":"16721","messageId":"Pine.LNX.4.64.0602242130030.31162@localhost.localdomain","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241637480.22647@g5.osdl.org","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-25T03:07:29Z","receivedAt":"2006-02-25T03:07:29Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Linus Torvalds wrote:\n\n> \n> \n> On Fri, 24 Feb 2006, Nicolas Pitre wrote:\n> > \n> > Currently, diff-delta takes blocks of data in the reference file and \n> > hash them. When the target file is scanned, it uses the hash to match \n> > blocks from the target file with the reference file.\n> > \n> > If blocks are hashed evenly the cost of producing a delta is at most \n> > O(n+m) where n and m are the size of the reference and target files \n> > respectively. In other words, with good data set the cost is linear.\n> \n> Assuming the hash is good, of course.\n> \n> I think this was the problem with you trying something simpler than \n> adler32..\n\nWell, that's the compromize to make. By default the version with \nadler32 used 16 byte blocks to index the reference buffer. That means \nyou can match target data against the reference only if whole 16 byte \nblocks match. Then, if you fix a typo in the target buffer then you'll \ninevitably need 16 literal bytes in the delta instead of only \none because you won't be able to resynchronize with the reference buffer \nuntil the next 16 byte block.\n\nWhat I've made in my last delta patch is to reduce that 16 byte block to \nonly 3 bytes. Why 3 bytes? Because less than that produces smaller \ndelta data if done with literal bytes directly, and 3 bytes provided \nenough bits to hash. I also made those 3 byte blocks overlap so \nindexing would start at any offset with byte precision. This really \nallows for optimal deltas so that they cannot be smaller.\n\nNow the problem comes when indexing a reference file full of:\n\n 0x46f8, 0x000b, 0x42fe, 0x0000, 0xffc0, 0x0001, 0xff00, 0x0008,\n 0x03e0, 0x0009, 0x0f01, 0x0003, 0x8072, 0x0000, 0x0400, 0x0000,\n 0x0046, 0x0003, 0x9180, 0x0001, 0x0003, 0x0008, 0x02eb, 0x0003,\n 0x8072, 0x0000, 0x0400, 0x0000, 0x8010, 0x0008, 0x0010, 0x0000,\n 0x0361, 0x0003, 0x037e, 0x0004, 0x3941, 0x0002, 0x0b0f, 0x0003,\n 0x8072, 0x0000, 0x0400, 0x0000, 0x000a, 0x000b, 0x0346, 0x000c,\n 0x11fe, 0x0000, 0x3717, 0x0003, 0x8072, 0x0000, 0x0400, 0x0000,\n 0x8010, 0x0008, 0x000e, 0x0000, 0x0361, 0x0003, 0x8060, 0x0000,\n\nThere is a bunch of \", 0x\" that get hashed to the same thing. And when \nthe second phase i.e. trying to find the best match into the reference \nbuffer for each occurrence of the same many \", 0x\" in the target buffer \nyou get a conbinatorial explosion.\n\nThe adler32 made that particular example a non issue since the \nlikelyhood of many 16 byte blocks to be the same is pretty low in this \ncase. But the flaw remains if for example there is lots of similar 16 \nbyte blocks, like a binary file with lots of zeroes for example. In \nfact, the performance problem Carl is having does use the diff-delta \nversion still using adler32.\n\n> > But if many blocks from the reference buffer do hash to the same bucket \n> > then for each block in the target file many blocks from the reference \n> > buffer have to be tested against, making it tend towards O(n^m) which is \n> > pretty highly exponential.\n> > \n> > The solution I'm investigating is to put a limit on the number of \n> > entries in the same hash bucket so to bring the cost back to something \n> > more linear. That means the delta might miss on better matches that \n> > have not been hashed but still benefit from a limited set.\n> \n> Sounds fair enough.\n\nTesting appear to show that this is a worthwhile safety valve. And in \nmost case that safety valve should not be activated at all.\n\n> However, you migt also want to consider another approach..\n> \n> One of the biggest costs for the xdelta algorithm is probably just the \n> \"delta_prepare()\", but at the same time, that is constant wrt the source \n> buffer.\n\nActually it is not that costly. Much much less than computing the sha1 \nof the same buffer for example.\n\n> Now, the sad part is that when I wrote pack-objects, I didn't really \n> understand the diff-delta algorithm, I just plugged it in. Which means \n> that when I did it, I made the (obvious and simple) decision to keep the \n> _result_ that we are looking at constant, and try to delta against \n> different sources.\n> \n> HOWEVER.\n> \n> I suspect you already see where this is going..\n> \n> We _could_ switch the \"pack-objects\" window handling around, and instead \n> of looking at the object we want to pack, and looking at the ten (or \n> \"window\") previous objects to delta against, we could do it the other way \n> around: keep the object we delta against constant, and see what deltas we \n> could prepare for the ten next objects.\n> \n> And since the source would now be constant, you'd need to do the \n> \"delta_prepare()\" just _once_ per window, instead of every single time.\n\nMight be worth trying. Actually, this can be tested without even \nchanging the window handling just yet, since diff-delta() could return \nthe index data instead of freeing it, and pack-objects can store it \nalong side with the object data it tries to delta against. That \nwouldn't be memory efficient, but at least that would give an idea of \nthe magnitude of the saving on CPU time. But I really doubt that'll \nsave more than a few percent.\n\n\n\n\n\n> \n> Now, I haven't done any profiling on the diff-delta code, and maybe my \n> guess that delta_prepare() is a pretty expensive part is wrong, and maybe \n> it wouldn't help to switch the window probing around. But I thought I'd \n> mention it as one thing to explore..\n\nJust to give you an idea, the bulk of my current \"prepare\" code looks \nlike this:\n\n /* then populate the index */\n data = buf + bufsize - 2;\n while (data > buf) {\n entry->ptr = --data;\n i = (data[0] << hshift) ^ data[1];\n i ^= (i << hshift) ^ data[2];\n entry->next = hash[i];\n hash[i] = entry++;\n }\n\nAs you can see it is pretty lightweight.\n\nBut that would probably be a worthwhile optimization to have even if it \nsaves 10% of CPU time.\n\n\nNicolas\n"},{"id":"16722","messageId":"Pine.LNX.4.64.0602242242380.31162@localhost.localdomain","threadId":"3432","inReplyTo":"20060224225023.GA28538@hpsvcnb.fc.hp.com","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-25T03:53:09Z","receivedAt":"2006-02-25T03:53:09Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Carl Baldwin wrote:\n\n> > If you can add them into a single .tgz with instructions on how \n> > to reproduce the issue and provide me with an URL where I can fetch it \n> > that'd be perfect.\n> \n> I will do this in an email off of the list because these files really\n> shouldn't be available on a public list.\n\nOK I have the files, and I can confirm that your problem is of the same \ncombinatorial explosion type I already talked about, _even_ with the \nversion using adler32. This is really O(m*n) where m and n being the \nsize of two consecutive versions of the files. But since m and n are \nboth _huge_ then the delta code really goes out to lunch.\n\nI'm working on a patch to cap this to something like O(m+n).\n\nStay tuned.\n\n\nNicolas\n"},{"id":"16723","messageId":"Pine.LNX.4.64.0602241952140.22647@g5.osdl.org","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602242130030.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-25T04:05:06Z","receivedAt":"2006-02-25T04:05:06Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 24 Feb 2006, Nicolas Pitre wrote:\n> \n> Well, that's the compromize to make. By default the version with \n> adler32 used 16 byte blocks to index the reference buffer. That means \n> you can match target data against the reference only if whole 16 byte \n> blocks match. Then, if you fix a typo in the target buffer then you'll \n> inevitably need 16 literal bytes in the delta instead of only \n> one because you won't be able to resynchronize with the reference buffer \n> until the next 16 byte block.\n\nThat shouldn't be true. Once you find a 16-byte match, you can search \nforward (in theory you should be able to search backwards too, but by that \ntime we've already expanded the non-matching previous bytes, I think).\n\nBut I'm no xdelta expert, so I migt be wrong.\n\n> What I've made in my last delta patch is to reduce that 16 byte block to \n> only 3 bytes. Why 3 bytes? Because less than that produces smaller \n> delta data if done with literal bytes directly, and 3 bytes provided \n> enough bits to hash.\n\nOn the other hand, the cost is that your lookups _are_ going to be more \nexpensive. Regardless of how good the hash is, basically you have 16/3 \nmore hash-entries to look up, so you've made compression more expensive in \nfootprint, at least (I assume you've made the hash appropriately larger).\n\nAlso, at 3 bytes, insertion is at least equally dense (three bytes of data \nvs three bytes of offset into the source), and can be worse (the offset \nmight be 5 bytes, no?). So it would seem like you'd be better off with 4+ \nbytes, at which point the delta should be a win.\n\nHave you tried some half-way point, like ~8 bytes?\n\n> Now the problem comes when indexing a reference file full of:\n> \n> 0x46f8, 0x000b, 0x42fe, 0x0000, 0xffc0, 0x0001, 0xff00, 0x0008,\n...\n> \n> There is a bunch of \", 0x\" that get hashed to the same thing.\n\nYou'll find a lot of that in any file: three or four bytes of similarity \njust doesn't sound worthwhile to go digging after. \n\n> The adler32 made that particular example a non issue since the \n> likelyhood of many 16 byte blocks to be the same is pretty low in this \n> case. But the flaw remains if for example there is lots of similar 16 \n> byte blocks, like a binary file with lots of zeroes for example. In \n> fact, the performance problem Carl is having does use the diff-delta \n> version still using adler32.\n\nAgreed. I think limiting the hash length is a fine idea regardless, I just \nthink it sounds dangerous with the three-byte thing where a lot of matches \nshould be expected (never mind \", 0x\", just things like newlines and tabs \nin source code).\n\nOnly considering 16-byte sequences of similarities is a trade-off of \npacking cost vs win.. Not saying other block-sizes aren't worth testing, \nbut I suspect trying too hard is going to be too costly.\n\nEspecially as deltas compress _worse_ the smaller they are. Bigger \n\"insert\" chunks probably compress a lot better than a copy chunk. \n\nHave you looked at the delta size vs compression?\n\n\t\tLinus\n"},{"id":"16724","messageId":"Pine.LNX.4.64.0602242326381.31162@localhost.localdomain","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602241952140.22647@g5.osdl.org","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-25T05:10:54Z","receivedAt":"2006-02-25T05:10:54Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 24 Feb 2006, Linus Torvalds wrote:\n\n> \n> \n> On Fri, 24 Feb 2006, Nicolas Pitre wrote:\n> > \n> > Well, that's the compromize to make. By default the version with \n> > adler32 used 16 byte blocks to index the reference buffer. That means \n> > you can match target data against the reference only if whole 16 byte \n> > blocks match. Then, if you fix a typo in the target buffer then you'll \n> > inevitably need 16 literal bytes in the delta instead of only \n> > one because you won't be able to resynchronize with the reference buffer \n> > until the next 16 byte block.\n> \n> That shouldn't be true. Once you find a 16-byte match, you can search \n> forward (in theory you should be able to search backwards too, but by that \n> time we've already expanded the non-matching previous bytes, I think).\n\nObviously, but that's not my point. What I mean is that small changes \nwill kind of sabotage the match since you'll have to scan forward \n(adding literal bytes to the delta output in the mean time) until you \nfind another 16 byte block that matches. This is harder to find than a \n3 byte block. Hence you'll end up adding more literal bytes (up to 16 \nof them) until you can match the reference buffer again even if you only \nflipped one byte in the target buffer. In some cases that makes up for \ndeltas that are twice as large.\n\n> > What I've made in my last delta patch is to reduce that 16 byte block to \n> > only 3 bytes. Why 3 bytes? Because less than that produces smaller \n> > delta data if done with literal bytes directly, and 3 bytes provided \n> > enough bits to hash.\n> \n> On the other hand, the cost is that your lookups _are_ going to be more \n> expensive. Regardless of how good the hash is, basically you have 16/3 \n> more hash-entries to look up, so you've made compression more expensive in \n> footprint, at least (I assume you've made the hash appropriately larger).\n\nYes, the hash is larger. There is a cost in memory usage but not really \nin CPU cycles.\n\n> Also, at 3 bytes, insertion is at least equally dense (three bytes of data \n> vs three bytes of offset into the source), and can be worse (the offset \n> might be 5 bytes, no?). So it would seem like you'd be better off with 4+ \n> bytes, at which point the delta should be a win.\n\nThe code already discriminate the space of a block copy notation given \nthe offset and size vs the space for the equivalent literal bytes. So \nthe optimal encoding is always chosen already.\n\nIn fact, if you want to copy up to 15 bytes from offset 0 that will be \nencoded with only 2 bytes in the delta. The only case that is \nsuboptimal is when you want to copy only two bytes from offset 0 (2 \ndelta bytes) but only two bytes is mever matched by the hash lookup \nsince the hash is computed with 3 bytes. In that case 2 literal bytes \nwill be added to the delta plus opcode = 3 bytes. I considered that \nspecial case not worth it. However copying a block of 3 bytes that gets \nencoded into 3 bytes of delta is quite common (that'd take 4 bytes of \ndelta if they were literals).\n\nAs for using more bytes for block hashing, that increase thenumber of \ncycles to compute the hash. The adler32 version reads 16 bytes for \nevery byte offset in the target file while my latest version only reads \n3 bytes for every byte offset. So in effect my target hash computation \nis faster than the adler32 one. However there is potentially more \nentries in the same hash bucket to validate especially with repetitive \ndata.\n\n> Have you tried some half-way point, like ~8 bytes?\n\nYes, and while the needed cycles tend to remain the same on average, the \nresulting pack gets larger.\n\n> > Now the problem comes when indexing a reference file full of:\n> > \n> > 0x46f8, 0x000b, 0x42fe, 0x0000, 0xffc0, 0x0001, 0xff00, 0x0008,\n> ...\n> > \n> > There is a bunch of \", 0x\" that get hashed to the same thing.\n> \n> You'll find a lot of that in any file: three or four bytes of similarity \n> just doesn't sound worthwhile to go digging after. \n\nWell after having experimented a lot with multiple parameters I think \nthey are worth it after all. Not only they provide for optimal deltas, \nbut their hash is faster to compute than larger blocks which seems to \ncounter balance for the cost of increased hash list.\n\n> > The adler32 made that particular example a non issue since the \n> > likelyhood of many 16 byte blocks to be the same is pretty low in this \n> > case. But the flaw remains if for example there is lots of similar 16 \n> > byte blocks, like a binary file with lots of zeroes for example. In \n> > fact, the performance problem Carl is having does use the diff-delta \n> > version still using adler32.\n> \n> Agreed. I think limiting the hash length is a fine idea regardless, I just \n> think it sounds dangerous with the three-byte thing where a lot of matches \n> should be expected (never mind \", 0x\", just things like newlines and tabs \n> in source code).\n\nThey are usually less than the number of lines. Yet if you have a 1000 \nline source file and let's suppose that we keep only 50 hashed \"\\n\\t\\t\" \nthis is sufficient to provide enough opportunities for matching that \nplus common patterns like a following \"if (\" for example.\n\n> Only considering 16-byte sequences of similarities is a trade-off of \n> packing cost vs win.. Not saying other block-sizes aren't worth testing, \n> but I suspect trying too hard is going to be too costly.\n\nI of course looked at the time to pack vs the size reduction in my \ntests. And really like I said above the cost is well balanced. The \nonly issue is that smaller blocks are more likely to trap into \npatological data sets. But that problem does exist with larger blocks \ntoo, to a lesser degree of course but still. For example, using a 16 \nblock size with adler32, computing a delta between two files \n\n> Especially as deltas compress _worse_ the smaller they are. Bigger \n> \"insert\" chunks probably compress a lot better than a copy chunk. \n\nYes, but given that we favor deltas from larger to smaller already those \ninserts are already not making much differences. They have to be quite \nlarge to effectively provide better zlib compression.\n\n> Have you looked at the delta size vs compression?\n\nThat's certainly an additional test worth adding to try_delta(). \nmax_size should be smaller than the original object deflated size making \nsure we won't store deltas that might end up larger than the undeltified \nobject.\n\n\nNicolas\n"},{"id":"16725","messageId":"Pine.LNX.4.64.0602250012230.31162@localhost.localdomain","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602242326381.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-25T05:35:26Z","receivedAt":"2006-02-25T05:35:26Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nOOps.... Forgot to complete one paragraph.\n\nOn Sat, 25 Feb 2006, Nicolas Pitre wrote:\n\n> I of course looked at the time to pack vs the size reduction in my \n> tests. And really like I said above the cost is well balanced. The \n> only issue is that smaller blocks are more likely to trap into \n> patological data sets. But that problem does exist with larger blocks \n> too, to a lesser degree of course but still. For example, using a 16 \n> block size with adler32, computing a delta between two files \n\n... as provided by Carl takes up to _nine_ minutes for a _single_ delta !\n\nSo regardless of the block size used, the issue right now has more to do \nwith that combinatorial explosion than the actual block size. And \npreventing that patological case from expending out of bounds is pretty \neasy to do.\n\nOK I just tested a tentative patch to trap that case and the time to \ndelta those two 20MB files passed from over 9 minutes to only 36 seconds \nhere, with less than 10% in delta size difference. So I think I might \nbe on the right track. Further tuning might help even further.\n\n\nNicolas\n"},{"id":"16731","messageId":"Pine.LNX.4.64.0602251114070.22647@g5.osdl.org","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602242326381.31162@localhost.localdomain","subject":"Re: [PATCH] diff-delta: produce optimal pack data","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-25T19:18:59Z","receivedAt":"2006-02-25T19:18:59Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Feb 2006, Nicolas Pitre wrote:\n> \n> Yes, the hash is larger. There is a cost in memory usage but not really \n> in CPU cycles.\n\nNote that memory usage translates almost 1:1 (or worse) to CPU cycles in \nalmost all real-life behaviours. Only in carefully tuned benchmarks does \nit not.\n\nIncreased memory usage means more paging, and worse cache behaviour. Now, \nhashes aren't wonderful for caches in the first place, but imagine the \nhump you pass when the data doesn't fit in a 64kB L1 any more (or a 256kB \nL2). Huge.\n\n> > You'll find a lot of that in any file: three or four bytes of similarity \n> > just doesn't sound worthwhile to go digging after. \n> \n> Well after having experimented a lot with multiple parameters I think \n> they are worth it after all. Not only they provide for optimal deltas, \n> but their hash is faster to compute than larger blocks which seems to \n> counter balance for the cost of increased hash list.\n\nHey, numbers talk. If you've got the numbers, I'll just shut up ;)\n\n\t\tLinus\n"},{"id":"17315","messageId":"7vzmk1izpa.fsf_-_@assigned-by-dhcp.cox.net","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0602250012230.31162@localhost.localdomain","subject":"[RFH] zlib gurus out there?","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-07T23:48:17Z","receivedAt":"2006-03-07T23:48:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I've been staring at reusing existing data while packing, and\nthis occurred to me...\n\nDuring packing, suppose that we chose to store an object in\nbase form, undeltified. And also suppose we have that object\nloose in .git/objects/??/ directory. We already have it in\ndeflated form, but with its own header. I started wondering if\nwe can somehow reuse this.\n\nA short object format brush-up lesson is in order here. \n\n* An undeltified object in a pack is represented like this:\n\n (1) the header is a dense variable size binary data, that\n encodes type and inflated length;\n (2) deflated data immediately follows the header.\n\n* On the other hand, a loose object is represented like this:\n\n (1) the header looks like sprintf(\"%s %lu%c\", type, len, 0);\n (2) concatenate the data to the header;\n (3) SHA1 checksum of the above becomes the object name.\n (4) deflate the header and data using the same z_stream, in two\n steps, like this (sha1_file.c::write_sha1_file):\n\n\t/* Compress it */\n\tstream.next_out = compressed;\n\tstream.avail_out = size;\n\n\t/* First header.. */\n\tstream.next_in = hdr;\n\tstream.avail_in = hdrlen;\n\twhile (deflate(&stream, 0) == Z_OK)\n\t\t/* nothing */;\n\n\t/* Then the data itself.. */\n\tstream.next_in = buf;\n\tstream.avail_in = len;\n\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n\t\t/* nothing */;\n\tdeflateEnd(&stream);\n\tsize = stream.total_out;\n\nSo I thought... if we cause a full flush after the header part,\nI can find the flush boundaries from a loose object file and\ncopy the rest into a packfile I am generating, after placing the\nbinary encoded header. If this works, we do not have to inflate\nloose object to read it and deflate it to store that in the\npack. We will get a better packing as well, since we deflate\nloose objects with Z_BEST_COMPRESSION, while packs are done with\nZ_DEFAULT_COMPRESSION. While pack-objects read from a loose\nobject, if we can detect that there is no full flush after the\nheader, we would do the traditional inflate-deflate cycle, so\nthis would be backward compatible.\n\nHowever, I am stuck with the first step, which is to do a full\nflush after the header. An obvious change to the code quoted\nabove writes out a corrupt object:\n\n\t/* First header.. */\n\tstream.next_in = hdr;\n\tstream.avail_in = hdrlen;\n-\twhile (deflate(&stream, 0) == Z_OK)\n+\twhile (deflate(&stream, Z_FULL_FLUSH) == Z_OK)\n\t\t/* nothing */;\n\ngit-fsck-objects complains that sha1 does not match. It appears\nthat the sha1_file.c::unpack_sha1_rest() somehow barfs upon\nseeing the full flush, but I haven't dug into it yet.\n\nWould anybody with more experience with zlib want to help?\n"},{"id":"17317","messageId":"Pine.LNX.4.64.0603071658300.32577@g5.osdl.org","threadId":"3432","inReplyTo":"7vzmk1izpa.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [RFH] zlib gurus out there?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-08T00:59:49Z","receivedAt":"2006-03-08T00:59:49Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 7 Mar 2006, Junio C Hamano wrote:\n> \n> However, I am stuck with the first step, which is to do a full\n> flush after the header. An obvious change to the code quoted\n> above writes out a corrupt object:\n> \n> \t/* First header.. */\n> \tstream.next_in = hdr;\n> \tstream.avail_in = hdrlen;\n> -\twhile (deflate(&stream, 0) == Z_OK)\n> +\twhile (deflate(&stream, Z_FULL_FLUSH) == Z_OK)\n> \t\t/* nothing */;\n\nNo, I don't think that's good. You're only doing a partial deflate, you \ncan't ask for a Z_FULL_FLUSH. That only works if you give it the whole \nbuffer, and you don't.\n\niirc, wtf, wdik, and ianal.\n\n\t\tLinus\n"},{"id":"17318","messageId":"7vslptivbg.fsf@assigned-by-dhcp.cox.net","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0603071658300.32577@g5.osdl.org","subject":"Re: [RFH] zlib gurus out there?","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-08T01:22:59Z","receivedAt":"2006-03-08T01:22:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Tue, 7 Mar 2006, Junio C Hamano wrote:\n>> \n>> However, I am stuck with the first step, which is to do a full\n>> flush after the header. An obvious change to the code quoted\n>> above writes out a corrupt object:\n>> \n>> \t/* First header.. */\n>> \tstream.next_in = hdr;\n>> \tstream.avail_in = hdrlen;\n>> -\twhile (deflate(&stream, 0) == Z_OK)\n>> +\twhile (deflate(&stream, Z_FULL_FLUSH) == Z_OK)\n>> \t\t/* nothing */;\n>\n> No, I don't think that's good. You're only doing a partial deflate, you \n> can't ask for a Z_FULL_FLUSH. That only works if you give it the whole \n> buffer, and you don't.\n\nSo, in short there is no way to create:\n\n hdr part deflated.\n flush.\n data part deflated independently.\n\nand have the current sha1_read_file() not to notice that flush,\nwhile I can inspect the deflated stream to find the \"flush\", and\ncopy only the defalted data part into a pack? Bummer... I was\nreally shooting for full backward compatibility.\n"},{"id":"17321","messageId":"Pine.LNX.4.64.0603071753370.32577@g5.osdl.org","threadId":"3432","inReplyTo":"7vslptivbg.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] zlib gurus out there?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-08T02:00:35Z","receivedAt":"2006-03-08T02:00:35Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 7 Mar 2006, Junio C Hamano wrote:\n> >\n> > No, I don't think that's good. You're only doing a partial deflate, you \n> > can't ask for a Z_FULL_FLUSH. That only works if you give it the whole \n> > buffer, and you don't.\n\nActually, I misread what you were trying to do, and thought this was the \ninflate phase, not the deflate. Now that I understand what you want, \n\n> So, in short there is no way to create:\n> \n> hdr part deflated.\n> flush.\n> data part deflated independently.\n> \n> and have the current sha1_read_file() not to notice that flush,\n\nActually, try the patch you already tried, except you'll need to add a \n\n\tdeflateEnd(&stream);\n\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n\t.. set up output parameters again ..\n\nand you need to change the initial \n\n\tsize = deflateBound(&stream, len+hdrlen);\n\nto\n\n\tsize = deflateBound(&stream, len) + deflateBound(&stream, hdrlen);\n\nand then you might be ok.\n\nThat said, I'm not sure I agree with what you're trying to do. \n\n\t\tLinus\n"},{"id":"17325","messageId":"Pine.LNX.4.63.0603081042320.906@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"3432","inReplyTo":"Pine.LNX.4.64.0603071753370.32577@g5.osdl.org","subject":"Re: [RFH] zlib gurus out there?","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-03-08T09:46:16Z","receivedAt":"2006-03-08T09:46:16Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 7 Mar 2006, Linus Torvalds wrote:\n\n> On Tue, 7 Mar 2006, Junio C Hamano wrote:\n> > >\n> > > No, I don't think that's good. You're only doing a partial deflate, you \n> > > can't ask for a Z_FULL_FLUSH. That only works if you give it the whole \n> > > buffer, and you don't.\n> \n> Actually, I misread what you were trying to do, and thought this was the \n> inflate phase, not the deflate.\n\nI don't think it matters if it is inflate or deflate. ZLib keeps an \ninternal state depending on the data. That is the whole reason why the \npacking is so good: it uses the redundancy in the data already seen to \nconstruct a codebook. (And that's also the reason why you can't start to \ndeflate in the middle.)\n\nCiao,\nDscho\n"},{"id":"17327","messageId":"20060308134519.78ea313d.vsu@altlinux.ru","threadId":"3432","inReplyTo":"7vzmk1izpa.fsf_-_@assigned-by-dhcp.cox.net","subject":"[PATCH] write_sha1_file(): Perform Z_FULL_FLUSH between header and data","fromName":"Sergey Vlasov","fromEmail":"vsu@altlinux.ru","sentAt":"2006-03-08T10:45:19Z","receivedAt":"2006-03-08T10:45:19Z","isPatch":true,"sender":{"key":"vsu@altlinux.ru","avatar":"https://avatars.githubusercontent.com/u/616082?v=4"},"body":"Data after Z_FULL_FLUSH will be compressed independently of the\nheader, and could therefore be reused without recompressing when\ncreating a pack.\n\n---\n\nThis passes \"make test\" and unpacking of the whole git repo with\ngit-fsck-objects afterwards.\n\nHowever, a straight reuse still will not be possible, because\nsha1write_compressed() uses deflateInit(&stream, Z_DEFAULT_COMPRESSION),\nwhich writes zlib headers around the deflate stream, and the zlib footer\ncontains adler32 checksum. So, as a minimum, you will need to\ndecompress the object data, calculate its adler32 checksum and write the\nzlib header yourself.\n\n sha1_file.c | 7 ++++++-\n 1 files changed, 6 insertions(+), 1 deletions(-)\n\n8b12d9a58e87a4c5b5a2a7b20d06fe29a5afb903\ndiff --git a/sha1_file.c b/sha1_file.c\nindex a80d849..34d4da4 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1399,7 +1399,8 @@ int write_sha1_file(void *buf, unsigned \n \t/* Set it up */\n \tmemset(&stream, 0, sizeof(stream));\n \tdeflateInit(&stream, Z_BEST_COMPRESSION);\n-\tsize = deflateBound(&stream, len+hdrlen);\n+\t/* Additional 6 bytes for the Z_FULL_FLUSH marker */\n+\tsize = deflateBound(&stream, hdrlen) + 6 + deflateBound(&stream, len);\n \tcompressed = xmalloc(size);\n \n \t/* Compress it */\n@@ -1412,6 +1413,10 @@ int write_sha1_file(void *buf, unsigned \n \twhile (deflate(&stream, 0) == Z_OK)\n \t\t/* nothing */;\n \n+\t/* Flush before data */\n+\twhile (deflate(&stream, Z_FULL_FLUSH) == Z_OK)\n+\t\t/* nothing */;\n+\n \t/* Then the data itself.. */\n \tstream.next_in = buf;\n \tstream.avail_in = len;\n-- \n1.2.GIT\n"},{"id":"17328","messageId":"7vhd69i4ep.fsf@assigned-by-dhcp.cox.net","threadId":"3432","inReplyTo":"20060308134519.78ea313d.vsu@altlinux.ru","subject":"Re: [PATCH] write_sha1_file(): Perform Z_FULL_FLUSH between header and data","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-08T11:04:14Z","receivedAt":"2006-03-08T11:04:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sergey Vlasov writes:\n\n> However, a straight reuse still will not be possible, because\n> sha1write_compressed() uses deflateInit(&stream, Z_DEFAULT_COMPRESSION),\n> which writes zlib headers around the deflate stream, and the zlib footer\n> contains adler32 checksum. So, as a minimum, you will need to\n> decompress the object data, calculate its adler32 checksum and write the\n> zlib header yourself.\n\nHmph. Thanks for helping, but it sounds like my original plan\nwas not useful at all. Probably inflating would be still\ncheaper than inflating and then deflating, but it would not be\nas cool as a straight copy. Sigh...\n"},{"id":"17331","messageId":"20060308141709.GB9555@procyon.home","threadId":"3432","inReplyTo":"7vhd69i4ep.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] write_sha1_file(): Perform Z_FULL_FLUSH between header and data","fromName":"Sergey Vlasov","fromEmail":"vsu@altlinux.ru","sentAt":"2006-03-08T14:17:09Z","receivedAt":"2006-03-08T14:17:09Z","isPatch":true,"sender":{"key":"vsu@altlinux.ru","avatar":"https://avatars.githubusercontent.com/u/616082?v=4"},"body":"On Wed, Mar 08, 2006 at 03:04:14AM -0800, Junio C Hamano wrote:\n> Sergey Vlasov writes:\n> > However, a straight reuse still will not be possible, because\n> > sha1write_compressed() uses deflateInit(&stream, Z_DEFAULT_COMPRESSION),\n> > which writes zlib headers around the deflate stream, and the zlib footer\n> > contains adler32 checksum. So, as a minimum, you will need to\n> > decompress the object data, calculate its adler32 checksum and write the\n> > zlib header yourself.\n> \n> Hmph. Thanks for helping, but it sounds like my original plan\n> was not useful at all. Probably inflating would be still\n> cheaper than inflating and then deflating, but it would not be\n> as cool as a straight copy. Sigh...\n\nActually you can calculate adler32 checksum of object data from\nadler32(header+data) (available at the end of the loose object file),\nadler32(header) (which you will need to calculate) and len(data)\n(which is available in the header):\n\n#define ADLER32_BASE\t65521UL\n\nunsigned int adler32_split(unsigned int adler_full, unsigned int adler_1,\n\t\t\t unsigned long len_2)\n{\n\tunsigned long s1_1 = adler_1 & 0xffff;\n\tunsigned long s1_2 = (adler_1 >> 16) & 0xffff;\n\tunsigned long rem = len_2 % ADLER32_BASE;\n\tunsigned long s_1_offset = (s1_1 + ADLER32_BASE - 1) % ADLER32_BASE;\n\tunsigned long s_2_offset = (s1_2 + s_1_offset*rem) % ADLER32_BASE;\n\tunsigned long sf_1 = adler_full & 0xffff;\n\tunsigned long sf_2 = (adler_full >> 16) & 0xffff;\n\tunsigned long s2_1 = (sf_1 + ADLER32_BASE - s_1_offset) % ADLER32_BASE;\n\tunsigned long s2_2 = (sf_2 + ADLER32_BASE - s_2_offset) % ADLER32_BASE;\n\treturn (s2_2 << 16) | s2_1;\n}\n\nHowever, the resulting code probably won't be pretty...\n"}]}