{"thread":{"id":"3486","subject":"[PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","startedAt":"2006-02-28T04:09:55Z","lastAt":"2006-03-04T06:21:43Z","messageCount":10,"participants":["Nicolas Pitre","Junio C Hamano","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"16880","messageId":"Pine.LNX.4.64.0602272110320.25336@localhost.localdomain","threadId":"3486","inReplyTo":null,"subject":"[PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-28T04:09:55Z","receivedAt":"2006-02-28T04:09:55Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"The diff-delta code can exhibit O(m*n) behavior with some patological \ndata set where most hash entries end up in the same hash bucket.\n\nThe latest code rework reduced the block size making it particularly \nvulnerable to this issue, but the issue was always there and can be \ntriggered regardless of the block size.\n\nThis patch does two things:\n\n1) the hashing has been reworked to offer a better distribution to \n atenuate the problem a bit, and\n\n2) a limit is imposed to the number of entries that can exist in the \n same hash bucket.\n\nBecause of the above the code is a bit more expensive on average, but \nthe problematic samples used to diagnoze the issue are now orders of \nmagnitude less expensive to process with only a slight loss in \ncompression.\n\nSigned-off-by: Nicolas Pitre \n\n---\n\nFor example, Carl Baldwin provided me with a couple 20MB files, and \ndeltifying one against another one with test-delta takes around \nSEVENTEEN MINUTES for only one delta on my P4 @ 3GHz when using the \noriginal adler32 version with 16 byte blocks. With the latest delta \ncode in the pu branch it simply takes forever (I interrupted it after 20 \nminutes of processing). now imagine using git-repack -a with a window \nof 10. With this patch on top of the small block patch (still in the pu \nbranch) this time dropped to only 10 seconds. And the resulting delta \nis still smaller than the 16 byte adler32 based version:\n\nblob 02220dae8cd219916ce52a12cda67322659e0e57 ->\nblob af8f99dd11ca288f4e4a08f2626af2de8b3ecfd2\nsize (21187748 -> 19424744)\ndelta size (16 byte blocks): 5238542 in 16m55\ndelta size (3 byte blocks): [interrupted after 20 minutes]\ndelta size (3 byte blocks + this patch): 4910988 in 9.69 secs\n\nOther data points from the Linux kernel repository:\n\nblob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f ->\nblob dfc9cd58dc065d17030d875d3fea6e7862ede143\nsize (491102 -> 496045)\ndelta size (16 byte blocks): 248899 in less than 0.1 sec\ndelta size (3 byte blocks): 136000 in 11.8 secs\ndelta size (3 byte blocks + this patch): 171688 in 0.79 sec\n\nblob 4917ec509720a42846d513addc11cbd25e0e3c4f ->\nblob dfc9cd58dc065d17030d875d3fea6e7862ede143\nsize (495831 -> 496045)\ndelta size (16 byte blocks): 226218 in less than 0.1 sec\ndelta size (3 byte blocks): 120948 in 11.7 secs\ndelta size (3 byte blocks + this patch): 157135 in 0.77 sec\n\n\n diff-delta.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++-----------\n 1 files changed, 56 insertions(+), 13 deletions(-)\n\n1682f4b1b2899288d7761844a4cfd02772c464d1\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 27f83a0..bb07926 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -30,19 +30,20 @@ struct index {\n \n static struct index ** delta_index(const unsigned char *buf,\n \t\t\t\t unsigned long bufsize,\n+\t\t\t\t unsigned long trg_bufsize,\n \t\t\t\t unsigned int *hash_shift)\n {\n \tunsigned long hsize;\n-\tunsigned int hshift, i;\n+\tunsigned int i, hshift, hlimit, *hash_count;\n \tconst unsigned char *data;\n \tstruct index *entry, **hash;\n \tvoid *mem;\n \n \t/* determine index hash size */\n \thsize = bufsize / 4;\n-\tfor (i = 8; (1 << i) < hsize && i < 16; i++);\n+\tfor (i = 8; (1 << i) < hsize && i < 24; i += 2);\n \thsize = 1 << i;\n-\thshift = i - 8;\n+\thshift = (i - 8) / 2;\n \t*hash_shift = hshift;\n \n \t/* allocate lookup index */\n@@ -53,15 +54,59 @@ static struct index ** delta_index(const\n \tentry = mem + hsize * sizeof(*hash);\n \tmemset(hash, 0, hsize * sizeof(*hash));\n \n-\t/* then populate it */\n+\t/* allocate an array to count hash entries */\n+\thash_count = calloc(hsize, sizeof(*hash_count));\n+\tif (!hash_count) {\n+\t\tfree(hash);\n+\t\treturn NULL;\n+\t}\n+\n+\t/* then populate the index */\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\ti = data[0] ^ ((data[1] ^ (data[2] << hshift)) << hshift);\n \t\tentry->next = hash[i];\n \t\thash[i] = entry++;\n+\t\thash_count[i]++;\n \t}\n \n+\t/*\n+\t * Determine a limit on the number of entries in the same hash\n+\t * bucket. This guard us against patological data sets causing\n+\t * really bad hash distribution with most entries in the same hash\n+\t * bucket that would bring us to O(m*n) computing costs (m and n\n+\t * corresponding to reference and target buffer sizes).\n+\t *\n+\t * The more the target buffer is large, the more it is important to\n+\t * have small entry lists for each hash buckets. With such a limit\n+\t * the cost is bounded to something more like O(m+n). \n+\t */\n+\thlimit = (1 << 26) / trg_bufsize;\n+\tif (hlimit < 16)\n+\t\thlimit = 16;\n+\n+\t/*\n+\t * Now make sure none of the hash buckets has more entries than\n+\t * we're willing to test. Otherwise we short-circuit the entry\n+\t * list uniformly to still preserve a good repartition across\n+\t * the reference buffer.\n+\t */\n+\tfor (i = 0; i < hsize; i++) {\n+\t\tif (hash_count[i] < hlimit)\n+\t\t\tcontinue;\n+\t\tentry = hash[i];\n+\t\tdo {\n+\t\t\tstruct index *keep = entry;\n+\t\t\tint skip = hash_count[i] / hlimit / 2;\n+\t\t\tdo {\n+\t\t\t\tentry = entry->next;\n+\t\t\t} while(--skip && entry);\n+\t\t\tkeep->next = entry;\n+\t\t} while(entry);\n+\t}\n+\tfree(hash_count);\n+\n \treturn hash;\n }\n \n@@ -85,7 +130,7 @@ void *diff_delta(void *from_buf, unsigne\n \n \tif (!from_size || !to_size)\n \t\treturn NULL;\n-\thash = delta_index(from_buf, from_size, &hash_shift);\n+\thash = delta_index(from_buf, from_size, to_size, &hash_shift);\n \tif (!hash)\n \t\treturn NULL;\n \n@@ -126,8 +171,8 @@ void *diff_delta(void *from_buf, unsigne\n \n \twhile (data < top) {\n \t\tunsigned int moff = 0, msize = 0;\n-\t\tif (data + 2 < top) {\n-\t\t\ti = data[0] ^ data[1] ^ (data[2] << hash_shift);\n+\t\tif (data + 3 <= top) {\n+\t\t\ti = data[0] ^ ((data[1] ^ (data[2] << hash_shift)) << 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@@ -138,11 +183,9 @@ void *diff_delta(void *from_buf, unsigne\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 (*ref != *src)\n+\t\t\t\t\tcontinue;\n+\t\t\t\twhile (ref_size-- && *++src == *++ref);\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-- \n1.2.3.g8fcf1-dirty\n"},{"id":"16889","messageId":"7vhd6kq8lc.fsf@assigned-by-dhcp.cox.net","threadId":"3486","inReplyTo":"Pine.LNX.4.64.0602272110320.25336@localhost.localdomain","subject":"Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-28T06:51:43Z","receivedAt":"2006-02-28T06:51:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> The diff-delta code can exhibit O(m*n) behavior with some patological \n> data set where most hash entries end up in the same hash bucket.\n\n> Other data points from the Linux kernel repository:\n>\n> blob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f ->\n> blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n> size (491102 -> 496045)\n> delta size (16 byte blocks): 248899 in less than 0.1 sec\n> delta size (3 byte blocks): 136000 in 11.8 secs\n> delta size (3 byte blocks + this patch): 171688 in 0.79 sec\n\nThese numbers are misleading.\n\nThe 36K objects pack I used in my previous tests gives 9971223\n(from \"next\" branch) vs 9664546 (this patch) final pack size.\nThe wallclock time on my machine is 1m35 vs 3m30. I doubt many\npeople are willing to pay 100% more waiting time for 3% tighter\npack.\n\nAlthough I do not mean to rain on your effort and substantial\nimprovement you made with this patch, we need to admit that\nimproving pathological corner case has quite a diminishing\neffect in the overall picture.\n\nBut this definitely is an improvement nevertheless. I should\ntry this on my wife's AMD64 (Cygwin). The same datasets I used\nin my previous complaint still seem to take a couple of seconds\n(or more) each on my Duron 750 X-<.\n\nA handful additional ideas.\n\n * Lower the hash limit a bit more (obvious). That might have\n detrimental effect in the general case.\n\n * Study the hash bucket distribution for the pathological case\n and see if we can cheaply detect a pattern. I suspect these\n cases have relatively few but heavily collided buckets with\n mostly sparse other entries. If there is such an easily\n detectable pattern, maybe we can look for such a pattern at\n runtime, and cull hash entries more aggressively in such a\n case?\n\n * Try checking the target buffer to see if it would have many\n hits on the heavily collided hash entries from the source\n (maybe hash_count the target buffer as well).\n\n * Have pack-object detect a pathological blob (the test patch I\n sent you previously uses the eye-candy timer for this\n purpose, but we could getrusage() if we want to be more\n precise) by observing how much time is spent for a single\n round, and mark the blob as such, so we do not delta against\n it with other blobs in find_deltas, when we are packing many\n objects. It does not really matter in the big picture if we\n choose not to delta the pathological ones tightly, as long as\n they are relatively few.\n\n * Also in pack-object, have an optional backing-store to write\n out deltified representations for results that took more than\n certain amount of time to produce in find_deltas(), and reuse\n them in write_object().\n\nIf anybody is interested, here are some other interesting pairs\nfrom the Linux 2.6 repositories.\n\n 2645d6239b74 cb968e7a0fcd\n 357980942d73 5bb837052ef1\n 5412dcb4b6d0 ac07e18abb1d\n 5bb837052ef1 1f8744ad9cde\n 63d827d7da07 5bb837052ef1\n 9af06ba723df 1896a0eea7e5\n cb968e7a0fcd 97b5578ae9b1\n d8c5a8dbd086 97b5578ae9b1\n d8c5a8dbd086 cb968e7a0fcd\n dfc9cd58dc06 1896a0eea7e5\n fa0f82ec9fa0 b611e27470e1\n"},{"id":"16890","messageId":"7vbqwrq4yi.fsf@assigned-by-dhcp.cox.net","threadId":"3486","inReplyTo":"7vhd6kq8lc.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-28T08:10:13Z","receivedAt":"2006-02-28T08:10:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Nicolas Pitre writes:\n>\n>> blob 9af06ba723df75fed49f7ccae5b6c9c34bc5115f ->\n>> blob dfc9cd58dc065d17030d875d3fea6e7862ede143\n>> size (491102 -> 496045)\n>> delta size (16 byte blocks): 248899 in less than 0.1 sec\n>> delta size (3 byte blocks): 136000 in 11.8 secs\n>> delta size (3 byte blocks + this patch): 171688 in 0.79 sec\n>\n> These numbers are misleading.\n>\n> The 36K objects pack I used in my previous tests gives 9971223\n> (from \"next\" branch) vs 9664546 (this patch) final pack size.\n> The wallclock time on my machine is 1m35 vs 3m30. I doubt many\n> people are willing to pay 100% more waiting time for 3% tighter\n> pack.\n\nI tried an experimental patch to cull collided hash buckets\nvery aggressively. I haven't applied your last \"reuse index\"\npatch, though -- I think that is orthogonal and I'd like to\nleave that to the next round.\n\nWith the same dataset: resulting pack is 9651096 vs 9664546\n(your patch) final pack size, with wallclock 2m45s (user 2m31).\nStill not good enough, and at the same time I wonder why it gets\n_smaller_ results than yours. But the generated pack unpacked\ncleanly in a cloned linux-2.6 repository (having objects and\nrefs up to v2.6.14) and the result was fsck-objects clean.\n\nI'd appreciate it if you can test it on the 20MB blobs and see\nwhat happens if you have time.\n\nBTW, the benchmark I've been doing is with this dataset:\n\n\tgit rev-list --objects-edge v2.6.14..v2.6.15-rc1 >RL-N\n time git pack-objects next;\n-\t\t\t} while(--skip && entry);\n-\t\t\tkeep->next = entry;\n-\t\t} while(entry);\n+\t\t\n+\t\tbucket = NULL;\n+\t\tlist = &bucket;\n+\t\tremaining = hash[i];\n+\t\tcnt = 0;\n+\t\twhile (cnt < hlimit && remaining) {\n+\t\t\tstruct index *this = remaining, *that;\n+\t\t\tremaining = remaining->next;\n+\t\t\tfor (that = bucket; that; that = that->next) {\n+\t\t\t\tif (!memcmp(that->ptr, this->ptr, 3))\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (that)\n+\t\t\t\tcontinue; /* discard */\n+\t\t\tcnt++;\n+\t\t\t*list = this;\n+\t\t\tlist = &(this->next);\n+\t\t\tthis->next = NULL;\n+\t\t}\n+\t\thash[i] = bucket;\n \t}\n \tfree(hash_count);\n \n"},{"id":"16912","messageId":"Pine.LNX.4.64.0602281017241.25336@localhost.localdomain","threadId":"3486","inReplyTo":"7vbqwrq4yi.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-28T17:05:59Z","receivedAt":"2006-02-28T17:05:59Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 27 Feb 2006, Junio C Hamano wrote:\n\n> Although I do not mean to rain on your effort and substantial\n> improvement you made with this patch, we need to admit that\n> improving pathological corner case has quite a diminishing\n> effect in the overall picture.\n\nIt does, unfortunately.\n\nThe problem is that the code in diff_delta() is highly solicited during \na pack generation. Just the simple hashing change from this patch that \ninvolves two shifts instead of only one increased the CPU time to \ngenerate a pack quite appreciably. This is just to say that this code \nis pretty sensitive to even small details.\n\n> But this definitely is an improvement nevertheless. I should\n> try this on my wife's AMD64 (Cygwin). The same datasets I used\n> in my previous complaint still seem to take a couple of seconds\n> (or more) each on my Duron 750 X-<.\n\nThere is no miracle. To prevent the extreme cases additional tests have \nto be performed in all cases, and therefore performance for all cases is \naffected.\n\n> A handful additional ideas.\n> \n> * Lower the hash limit a bit more (obvious). That might have\n> detrimental effect in the general case.\n\nIt does. The current parameters are what I think is the best compromize \nbetween cost and compression. And still 99% of the cases don't need \na lower hash limit since their hash lists are already way below the \nlimit. For the cases where it makes a difference, well lowering the \nhash limit also increase the cost associated with the reworking of the \nhash list so there comes a point where you actually increase the \nresulting delta size while the CPU time stays constant.\n\n> * Study the hash bucket distribution for the pathological case\n> and see if we can cheaply detect a pattern. I suspect these\n> cases have relatively few but heavily collided buckets with\n> mostly sparse other entries. If there is such an easily\n> detectable pattern, maybe we can look for such a pattern at\n> runtime, and cull hash entries more aggressively in such a\n> case?\n\nSame issue as above. And \"looking for such a pattern\" really does \nincrease the CPU time in _all_ cases. So that looking for patological \ncases has to be as cheap as possible which I think is the case right \nnow (and it is still too costly for my taste already). And yet I don't \nthink there is really a need for further reduction of the hash list at \nthis point since the patological cases are really handled gracefully \nwith this patch even with a nice and pretty packed delta.\n\n> * Try checking the target buffer to see if it would have many\n> hits on the heavily collided hash entries from the source\n> (maybe hash_count the target buffer as well).\n\nAgain that'd add another significant CPU cost to all cases, even those \nthat don't need it at all. The problem is not about those patological \ncases anymore since I think they are well under control now. It is the \noverhead those few patological cases impose on the other 180000 good \nbehaving objects that is a problem.\n\n> * Have pack-object detect a pathological blob (the test patch I\n> sent you previously uses the eye-candy timer for this\n> purpose, but we could getrusage() if we want to be more\n> precise) by observing how much time is spent for a single\n> round, and mark the blob as such, so we do not delta against\n> it with other blobs in find_deltas, when we are packing many\n> objects. It does not really matter in the big picture if we\n> choose not to delta the pathological ones tightly, as long as\n> they are relatively few.\n\nThat is one solution, but that doesn't handle the root of the problem \nwhich is the cost of detecting those cases in the first place.\n\n> * Also in pack-object, have an optional backing-store to write\n> out deltified representations for results that took more than\n> certain amount of time to produce in find_deltas(), and reuse\n> them in write_object().\n\nThe pack reusing code is pretty effective in doing so already, isn't it? \nSince using git-repack -f should not be the common case then those \npatological cases (now taking one second instead of 60 or more) should \nbe reused most of the time.\n\n> I tried an experimental patch to cull collided hash buckets\n> very aggressively. I haven't applied your last \"reuse index\"\n> patch, though -- I think that is orthogonal and I'd like to\n> leave that to the next round.\n\nIt is indeed orthogonal and I think you could apply it to the next \nbranch without the other patches (it should apply with little problems). \nThis is an obvious and undisputable gain, even more if pack-objects is \nreworked to reduce memory usage by keeping only one live index for \nmultiple consecutive deltaattempts.\n\n> With the same dataset: resulting pack is 9651096 vs 9664546\n> (your patch) final pack size, with wallclock 2m45s (user 2m31).\n> Still not good enough, and at the same time I wonder why it gets\n> _smaller_ results than yours.\n\nIt really becomes hard to find the best balance especially when the \nresulting delta is then fed through zlib. Sometimes a larger delta will \ncompress better, sometimes not. My test bench was the whole git \nrepository and the kernel repository, and with such large number of \nobjects it seems that smaller deltas always translate into smaller \npacks. But it might not necessarily always be the case.\n\n> I'd appreciate it if you can test it on the 20MB blobs and see\n> what happens if you have time.\n\nBefore your patch:\nuser 0m9.713s, delta size = 4910988 bytes, or 1744110 compressed.\n\nWith your patch:\nuser 0m3.948s, delta size = 6753517 bytes, or 1978803 once compressed.\n\nBTW there is another potential for improvement in the delta code (but I \nhave real work to do now so)...\n\nLet's suppose the reference buffer has:\n\n \n***********************************************************************/\n\nThis is common with some comment block styles. Now that line will end \nup with multiple blocks that will hash to the same thing and linked \nsuccessively in the same hash bucket except for the last ones where the \n'/' is involved in the hashing.\n\nNow if the target buffer also contains a line similar to the above but \none '*' character longer. The first \"***\" will be hashed to x, then x \nwill be looked up in the reference index, and the first entry \ncorresponding to the first character of the line above will be returned. \nAt that point a search forward is started to find out how much matches. \nIn this case it will match up to the '/' in the reference buffer while \nthe target will have another '*'. The length will be recorded as the \nbest match, so far so good.\n\nNow the next entry from the same hash bucket will be tested in case it \nmight provide a starting point for a longer match. But we know in this \ncase that the location of the second '*' in the reference buffer will be \nreturned. And we obviously know that this cannot match more data than \nthe previous attempt, in fact it'll match one byte less. And the hash \nentry to follow will return the location of the third '*' for another \nbyte less to match. Then the fourth '*' for yet another shorter match. \nAnd so on repeating those useless string comparisons multiple times.\n\nOne improvement might consist of counting the number of consecutive \nidentical bytes when starting a compare, and manage to skip as many hash \nentries (minus the block size) before looping again with more entries in \nthe same hash bucket.\n\nThe other case to distinguish is when the target buffer has instead a \n_shorter_ line, say 5 fewer '*''s before the final '/'. Here we would \nloop 4 times matching only a bunch of '*' before we finally match the \n'/' as well on the fifth attempt becoming the best match. In this case \nwe could test if the repeated byte we noticed from the start is present \nfurther away in the reference buffer, and if so simply skip hash entries \nwhile searching forward in the reference buffer. When the reference \nbuffer doesn't match the repeated character then the comparison is \nresumed with the target buffer, and in this case the '/' would match \nright away, avoiding those four extra loops recomparing all those '*' \nneedlessly.\n\nSuch improvements added to the search algorithm might make it \nsignificantly faster, even in the presence of multiple hash entries all \nlocated in the same bucket. Or maybe not if the data set has few \nrepeated characters. And this is probably worthwhile only on top of my \nsmall block patch. Only experimentation could tell. Someone willing to \ntry?\n\n\nNicolas\n"},{"id":"16937","messageId":"7vmzgajvpl.fsf@assigned-by-dhcp.cox.net","threadId":"3486","inReplyTo":"Pine.LNX.4.64.0602281017241.25336@localhost.localdomain","subject":"Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-01T10:38:46Z","receivedAt":"2006-03-01T10:38:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n>> I tried an experimental patch to cull collided hash buckets\n>> very aggressively. I haven't applied your last \"reuse index\"\n>> patch, though -- I think that is orthogonal and I'd like to\n>> leave that to the next round.\n>\n> It is indeed orthogonal and I think you could apply it to the next \n> branch without the other patches (it should apply with little problems). \n> This is an obvious and undisputable gain, even more if pack-objects is \n> reworked to reduce memory usage by keeping only one live index for \n> multiple consecutive deltaattempts.\n\nUmm. The hash-index is rather huge, isn't it? I did not\nrealize it was two-pointer structure for every byte in the\nsource material, and we typically delta from larger to smaller,\nso we will keep about 10x the unpacked source. Until we swap\nthe windowing around, that means about 100x the unpacked source\nwith the default window size.\n\nAlso, I am not sure which one is more costly: hash-index\nbuilding or use of that to search inside target. I somehow got\nan impression that the former is relatively cheap, and that is\nwhat is being cached here.\n\n> Let's suppose the reference buffer has:\n> \n> ***********************************************************************/\n>...\n> One improvement might consist of counting the number of consecutive \n> identical bytes when starting a compare, and manage to skip as many hash \n> entries (minus the block size) before looping again with more entries in \n> the same hash bucket.\n\nUmm, again. Consecutive identical bytes (BTW, I think \"* * *\"\nand \"** ** **\" patterns have the same collision issues without\nbeing consecutive bytes, so such an optimization may be trickier\nand cost more), when emitted as literals, would compress well,\nwouldn't they? At the end of the day, I think what matters is\nthe size of deflated delta, since going to disk to read it out\nis more expensive than deflating and applying. I think you made\na suggestion along the same line, capping the max delta used by\ntry_delta() more precisely by taking the deflated size into\naccount.\n"},{"id":"16959","messageId":"Pine.LNX.4.64.0603011211370.29834@localhost.localdomain","threadId":"3486","inReplyTo":"7vmzgajvpl.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-03-01T17:22:22Z","receivedAt":"2006-03-01T17:22:22Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 1 Mar 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> >> I tried an experimental patch to cull collided hash buckets\n> >> very aggressively. I haven't applied your last \"reuse index\"\n> >> patch, though -- I think that is orthogonal and I'd like to\n> >> leave that to the next round.\n> >\n> > It is indeed orthogonal and I think you could apply it to the next \n> > branch without the other patches (it should apply with little problems). \n> > This is an obvious and undisputable gain, even more if pack-objects is \n> > reworked to reduce memory usage by keeping only one live index for \n> > multiple consecutive deltaattempts.\n> \n> Umm. The hash-index is rather huge, isn't it? I did not\n> realize it was two-pointer structure for every byte in the\n> source material, and we typically delta from larger to smaller,\n> so we will keep about 10x the unpacked source. Until we swap\n> the windowing around, that means about 100x the unpacked source\n> with the default window size.\n\nThat's why I said that the window reversal has to be done as well to be \neffective. As for the index itself it can be reduced to a single \npointer since the \"ptr\" value can be deduced from the offset of the \nindex entry.\n\n> Also, I am not sure which one is more costly: hash-index\n> building or use of that to search inside target. I somehow got\n> an impression that the former is relatively cheap, and that is\n> what is being cached here.\n\nYes, but caching it saves 10% on CPU time, probably more when the window \nis swapped around due to less memory usage.\n\n> > Let's suppose the reference buffer has:\n> > \n> > ***********************************************************************/\n> >...\n> > One improvement might consist of counting the number of consecutive \n> > identical bytes when starting a compare, and manage to skip as many hash \n> > entries (minus the block size) before looping again with more entries in \n> > the same hash bucket.\n> \n> Umm, again. Consecutive identical bytes (BTW, I think \"* * *\"\n> and \"** ** **\" patterns have the same collision issues without\n> being consecutive bytes, so such an optimization may be trickier\n> and cost more),\n\nFirst, those \"** ** **\" are less frequent in general. Next, they will be \nspread amongst 3 hash buckets instead of all the same one. And with \nlarge binary files with lots of zeroes then scanning over those areas in \none pass instead of iterating over them from every offset would help \nenormously as well, even without limiting the hash list length.\n\n when emitted as literals, would compress well,\n> wouldn't they? At the end of the day, I think what matters is\n> the size of deflated delta, since going to disk to read it out\n> is more expensive than deflating and applying. I think you made\n> a suggestion along the same line, capping the max delta used by\n> try_delta() more precisely by taking the deflated size into\n> account.\n\nYes. But deflating a bunch of characters will never be as dense as a 4 \nbyte delta sequence that might expand to hundreds.\n\n\nNicolas\n"},{"id":"17128","messageId":"7vfylzx7t3.fsf@assigned-by-dhcp.cox.net","threadId":"3486","inReplyTo":"7vbqwrq4yi.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-04T02:28:08Z","receivedAt":"2006-03-04T02:28:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n>> These numbers are misleading.\n>>\n>> The 36K objects pack I used in my previous tests gives 9971223\n>> (from \"next\" branch) vs 9664546 (this patch) final pack size.\n>> The wallclock time on my machine is 1m35 vs 3m30. I doubt many\n>> people are willing to pay 100% more waiting time for 3% tighter\n>> pack.\n\n\tI started to suspect that the above benchmark was\nunreliable, because I do not know how the original linux-2.6\nrepository I used for my testing were packed, and I was letting\nthe delta reusing to do its thing, so the times were probably\noff (the 3-byte finer grained deltifier would have spent a lot\nmore time during the initial packing) and the result size were\ntoo (the finer grained one would have packed things a lot more\ntightly if the delta it was allowed to reuse was made by itself,\nnot by the old one).\n\n\tSo I tried a fresh packing without reusing delta at all,\nwith three variants: the original 16-byte one (master), 3-byte\nfiner grained one with your hash limit (nico), and 3-byte finer\ngrained one with my more aggressive hash limit (jc). The\nbenchmark is not meant to be scientific, but to see how well it\nserves the kernel community ;-).\n\n\n\tThe first round. The set of objects packed were from\ntoday's Linus tip (everything down to epoch v2.6.12-rc2), 193309\nobjects in total, on my Duron 750 with slow disks.\n\n\treal\t\tuser\t\tsys\t\tbytes\t\tsavings\nmaster\t11m17.121s\t10m23.280s\t0m47.290s 109045599\tN/A\nnico\t25m37.058s\t23m0.770s 2m20.460s\t104401392\t4.25%\njc\t24m12.072s\t21m45.120s\t2m16.400s\t104409761\t4.25%\n\nMy hack does not change things much in the overall picture\ncompared to yours, although it does cut down runtime by about\n5%. We can immediately see that finer grained ones are\nsignificantly more expensive than the original loose one either\nway.\n\n\n\tThe next round of test is to place the \"full pack\"\ngenerated in the previous experiment in .git/objects/pack and\ngenerate packs by reusing delta. When testing the \"master\"\nversion, I move the pack produced above with \"master\" under\n.git/objects/pack, and run this to emulate pack generation for\ndownloader who has v2.6.14 and wants v2.6.15-rc1 (the same 36K\nobjects test I did previously):\n\n\tgit rev-list --objects-edge v2.6.14..v2.6.15-rc1 |\n time git-pack-objects --stdout | wc -c\n\nWhen switching to test \"nico\" deltifier implementation, I start\nwith the full pack generated by \"nico\" in .git/object/pack to\nmake comparison fair. Here is the result:\n\n\treal\t\tuser\t\tsys\t\tbytes\t\tsavings\nmaster\t1m37.703s 1m28.970s\t0m5.860s 9968386\t\tN/A\nnico\t3m39.982s\t3m24.420s\t0m14.380s\t9182761\t\t7.88%\njc\t3m0.434s\t2m35.940s\t0m13.730s 9139460\t\t8.31%\n\nIn thin transfer, base object is omitted, so the generated pack\nhas higher delta to non-delta ratio than usual -- and that is\nthe reason we see much more savings. Still, we are paying quite\na lot of overhead by finer grained delta code.\n\n\n\tThe last test is not to do a thin pack but still reusing\ndelta. This is to emulate \"git repack\" performance. Again, I\nhad the matching pack in .git/objects/pack to make the\ncompararison fair:\n\n\tgit rev-list --objects v2.6.14..v2.6.15-rc1 |\n time git-pack-objects --stdout | wc -c\n\nAnd here is the result:\n\n\treal\t\tuser\t\tsys\t\tbytes\t\tsavings\nmaster\t1m0.866s\t0m57.590s\t0m2.810s\t34601417\tN/A\nnico\t2m8.059s\t2m0.360s\t0m6.350s\t33888419\t2.06%\njc\t1m49.894s\t1m42.250s\t0m6.780s\t33838262\t2.20%\n\nThis one is not getting much savings compared to the full pack\ncase, but still spending about twice the time.\n\n\n\tIn short, I'd love to get a tighter packing, but as it\ncurrently stands, I do not think 5% resulting packsize reduction\nwarrants making 100% slower operation the default. And the\nexperiment I did does not account for the memory pressure the\nnew delitifier imposes us (two pointers per every byte of source\nmaterial -- it could be reduced to one pointer though), so when\nwe start talking about huge files I am not sure we can manage to\nkeep the runtime reasonably low.\n\n\tIt maybe is an option to have a flag to tell \"I want a\nlot tighter pack made; you can spend all the time while I am\nsleeping\" and switch between two deltifiers, but otherwise...\n\n\tOne thing I do not understand is why my patch improves\nthe compressed result size. The patch was primarily to brutally\npessimize the selection of \"copied from source\" to avoid the\ncorner case performance problems, so I would understand why it\nis faster than yours, but I expected it to *always* create a\nlooser pack. I am puzzled.\n\n\tSwapping window scan order is orthogonal to this, so\nmaybe we could do it first and make it work, then start reusing\nthe refindex to see how well things improve. But we should be\nreminded of the recent report that pack-object ran out of space\neven with the current code that does not reuse the refindex when\npacking 8 huge objects X-<.\n"},{"id":"17129","messageId":"7vbqwnx79y.fsf@assigned-by-dhcp.cox.net","threadId":"3486","inReplyTo":"7vfylzx7t3.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-04T02:39:37Z","receivedAt":"2006-03-04T02:39:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> \tThe first round. The set of objects packed were from\n> today's Linus tip (everything down to epoch v2.6.12-rc2), 193309\n> objects in total, on my Duron 750 with slow disks.\n>\n> \t real\t\tuser\t\tsys\t\tbytes\t\tsavings\n> master 11m17.121s\t10m23.280s\t0m47.290s 109045599\tN/A\n> nico\t 25m37.058s\t23m0.770s 2m20.460s\t104401392\t4.25%\n> jc\t 24m12.072s\t21m45.120s\t2m16.400s\t104409761\t4.25%\n\nMinor correction in numbers. The size for nico and jc are\nswapped. jc variant created the smallest pack in this\nexperiment.\n\nWhich puzzles me even more...\n"},{"id":"17130","messageId":"Pine.LNX.4.64.0603032158250.1859@localhost.localdomain","threadId":"3486","inReplyTo":"7vfylzx7t3.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-03-04T03:01:33Z","receivedAt":"2006-03-04T03:01:33Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 3 Mar 2006, Junio C Hamano wrote:\n\n> \tIn short, I'd love to get a tighter packing, but as it\n> currently stands, I do not think 5% resulting packsize reduction\n> warrants making 100% slower operation the default.\n\nAgreed. Please just drop that one patch for now.\n\nI'll rework the hash limiting patch so the 16-byte block version behaves \nbetter with the large 20MB files.\n\n\nNicolas\n"},{"id":"17138","messageId":"Pine.LNX.4.64.0603032217470.22647@g5.osdl.org","threadId":"3486","inReplyTo":"7vfylzx7t3.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-04T06:21:43Z","receivedAt":"2006-03-04T06:21:43Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 3 Mar 2006, Junio C Hamano wrote:\n> \n> \tThe first round. The set of objects packed were from\n> today's Linus tip (everything down to epoch v2.6.12-rc2), 193309\n> objects in total, on my Duron 750 with slow disks.\n> \n> \treal\t\tuser\t\tsys\t\tbytes\t\tsavings\n> master\t11m17.121s\t10m23.280s\t0m47.290s 109045599\tN/A\n> nico\t25m37.058s\t23m0.770s 2m20.460s\t104401392\t4.25%\n> jc\t24m12.072s\t21m45.120s\t2m16.400s\t104409761\t4.25%\n\nOuch.\n\nBtw, it's often worth using /usr/bin/time instead of the bash built-in \ntime. Why? Because /usr/bin/time reports one absolutely _hugely_ important \nnumber (maybe more important than almost any of the other numbers in \nthere).\n\nWhich one? It's the \"minor pagefaults\". That's a very good approximation \nof memory usage overhead. \n\nWe've already had one person report that they ran out of memory when \npacking. So memory usage is actually a problem.\n\nAnyway, it looks like the 16-byte window is the way to go, even regardless \nof any memory use issue.\n\n\t\tLinus\n"}]}