{"thread":{"id":"3602","subject":"[PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior","startedAt":"2006-03-08T19:32:50Z","lastAt":"2006-03-08T19:32:50Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"17342","messageId":"Pine.LNX.4.64.0603081319220.1859@localhost.localdomain","threadId":"3602","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-03-08T19:32:50Z","receivedAt":"2006-03-08T19:32:50Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nThe 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\nTo prevent this, a limit is imposed to the number of entries that can \nexist in the same hash bucket.\n\nBecause of the above the code is a tiny bit more expensive on average, \neven if some small optimizations were added as well to atenuate the \noverhead. But the problematic samples used to diagnoze the issue are now \norders of magnitude less expensive to process with only a slight loss in \ncompression.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\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 \nTEN MINUTES for only one delta on my P4 @ 3GHz.\n\nNnow imagine using git-repack -a with a default window\nof 10 ... \n\nWith this patch the test-delta time dropped to only 9 seconds.  And the \nresulting delta, once compressed, is about 2% larger.\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 2ed5984..aaee7be 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -40,17 +40,18 @@ 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 int hsize, hshift, entries, blksize, i;\n+\tunsigned int i, hsize, hshift, hlimit, entries, *hash_count;\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+\tentries = bufsize  / BLK_SIZE;\n \thsize = entries / 4;\n-\tfor (i = 4; (1 << i) < hsize && i < 16; i++);\n+\tfor (i = 4; (1 << i) < hsize && i < 31; i++);\n \thsize = 1 << i;\n \thshift = 32 - i;\n \t*hash_shift = hshift;\n@@ -63,20 +64,62 @@ 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 + 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\tunsigned int val = adler32(0, data, BLK_SIZE);\n \t\ti = HASH(val, hshift);\n \t\tentry->ptr = data;\n \t\tentry->val = val;\n \t\tentry->next = hash[i];\n \t\thash[i] = entry++;\n-\t\tblksize = BLK_SIZE;\n+\t\thash_count[i]++;\n \t\tdata -= BLK_SIZE;\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 < 4*BLK_SIZE)\n+\t\thlimit = 4*BLK_SIZE;\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 cull the entry list\n+\t * 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@@ -100,7 +143,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@@ -141,29 +184,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 + BLK_SIZE <= top) {\n+\t\t\tunsigned int val = adler32(0, data, BLK_SIZE);\n+\t\t\ti = HASH(val, 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 (entry->val != val)\n+\t\t\t\t\tcontinue;\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\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"}]}