{"thread":{"id":"9825","subject":"[PATCH] diff-delta.c: pack the index structure","startedAt":"2007-09-07T23:38:20Z","lastAt":"2007-09-08T20:50:20Z","messageCount":5,"participants":["David Kastrup","Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"52962","messageId":"85fy1q11xv.fsf@lola.goethe.zz","threadId":"9825","inReplyTo":null,"subject":"[PATCH] diff-delta.c: pack the index structure","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-07T23:38:20Z","receivedAt":"2007-09-07T23:38:20Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"In normal use cases, the performance wins are not overly impressive:\nwe get something like 5-10% due to the slightly better locality of\nmemory accesses using the packed structure.\n\nHowever, since the data structure for index entries saves 33% of\nmemory on 32-bit platforms and 40% on 64-bit platforms, the behavior\nwhen memory gets limited should be nicer.\n\nThis is a rather well-contained change.  One obvious improvement would\nbe sorting the elements in one bucket according to their hash, then\nusing binary probing to find the elements with the right hash value.\n\nAs it stands, the output should be strictly the same as previously\nunless one uses the option for limiting the amount of used memory, in\nwhich case the created packs might be better.\n\nSigned-off-by: David Kastrup <dak@gnu.org>\n---\n diff-delta.c |   62 +++++++++++++++++++++++++++++++++++++++++++---------------\n 1 files changed, 46 insertions(+), 16 deletions(-)\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 0dde2f2..cf0136f 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -115,9 +115,13 @@ static const unsigned int U[256] = {\n struct index_entry {\n \tconst unsigned char *ptr;\n \tunsigned int val;\n-\tstruct index_entry *next;\n };\n \n+struct unpacked_index_entry {\n+\tstruct index_entry entry;\n+\tstruct unpacked_index_entry *next;\n+};\t\n+\n struct delta_index {\n \tunsigned long memsize;\n \tconst void *src_buf;\n@@ -131,7 +135,8 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \tunsigned int i, hsize, hmask, entries, prev_val, *hash_count;\n \tconst unsigned char *data, *buffer = buf;\n \tstruct delta_index *index;\n-\tstruct index_entry *entry, **hash;\n+\tstruct unpacked_index_entry *entry, **hash;\n+\tstruct index_entry *aentry, **ahash;\n \tvoid *mem;\n \tunsigned long memsize;\n \n@@ -148,28 +153,21 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \thmask = hsize - 1;\n \n \t/* allocate lookup index */\n-\tmemsize = sizeof(*index) +\n-\t\t  sizeof(*hash) * hsize +\n+\tmemsize = sizeof(*hash) * hsize +\n \t\t  sizeof(*entry) * entries;\n \tmem = malloc(memsize);\n \tif (!mem)\n \t\treturn NULL;\n-\tindex = mem;\n-\tmem = index + 1;\n \thash = mem;\n \tmem = hash + hsize;\n \tentry = mem;\n \n-\tindex->memsize = memsize;\n-\tindex->src_buf = buf;\n-\tindex->src_size = bufsize;\n-\tindex->hash_mask = hmask;\n \tmemset(hash, 0, hsize * sizeof(*hash));\n \n \t/* allocate an array to count hash entries */\n \thash_count = calloc(hsize, sizeof(*hash_count));\n \tif (!hash_count) {\n-\t\tfree(index);\n+\t\tfree(hash);\n \t\treturn NULL;\n \t}\n \n@@ -183,12 +181,13 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \t\t\tval = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];\n \t\tif (val == prev_val) {\n \t\t\t/* keep the lowest of consecutive identical blocks */\n-\t\t\tentry[-1].ptr = data + RABIN_WINDOW;\n+\t\t\tentry[-1].entry.ptr = data + RABIN_WINDOW;\n+\t\t\t--entries;\n \t\t} else {\n \t\t\tprev_val = val;\n \t\t\ti = val & hmask;\n-\t\t\tentry->ptr = data + RABIN_WINDOW;\n-\t\t\tentry->val = val;\n+\t\t\tentry->entry.ptr = data + RABIN_WINDOW;\n+\t\t\tentry->entry.val = val;\n \t\t\tentry->next = hash[i];\n \t\t\thash[i] = entry++;\n \t\t\thash_count[i]++;\n@@ -212,15 +211,46 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \t\t\tcontinue;\n \t\tentry = hash[i];\n \t\tdo {\n-\t\t\tstruct index_entry *keep = entry;\n+\t\t\tstruct unpacked_index_entry *keep = entry;\n \t\t\tint skip = hash_count[i] / HASH_LIMIT;\n \t\t\tdo {\n+\t\t\t\t--entries;\n \t\t\t\tentry = entry->next;\n \t\t\t} while(--skip && entry);\n+\t\t\t++entries;\n \t\t\tkeep->next = entry;\n \t\t} while(entry);\n \t}\n \tfree(hash_count);\n+\tmemsize = sizeof(*index)\n+\t\t+sizeof(*ahash) * (hsize+1) +\n+\t\t+sizeof(*aentry) * entries;\n+\tmem=malloc(memsize);\n+\n+\tif (!mem) {\n+\t\tfree(hash);\n+\t\treturn NULL;\n+\t}\n+\n+\tindex = mem;\n+\tindex->memsize = memsize;\n+\tindex->src_buf = buf;\n+\tindex->src_size = bufsize;\n+\tindex->hash_mask = hmask;\n+\n+\tmem = index+1;\n+\tahash = mem;\n+\tmem = ahash + (hsize+1);\n+\taentry = mem;\n+\n+\tfor (i=0; i<hsize; i++) {\n+\t\tahash[i] = aentry;\n+\t\tfor (entry=hash[i]; entry; entry=entry->next)\n+\t\t\t*aentry++ = entry->entry;\n+\t}\n+\tahash[hsize] = aentry;\n+\tassert(aentry-(struct index_entry *)mem == entries);\n+\tfree(hash);\n \n \treturn index;\n }\n@@ -302,7 +332,7 @@ create_delta(const struct delta_index *index,\n \t\t\tval ^= U[data[-RABIN_WINDOW]];\n \t\t\tval = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];\n \t\t\ti = val & index->hash_mask;\n-\t\t\tfor (entry = index->hash[i]; entry; entry = entry->next) {\n+\t\t\tfor (entry = index->hash[i]; entry<index->hash[i+1]; entry++) {\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-- \n1.5.3.GIT\n"},{"id":"52969","messageId":"alpine.LFD.0.9999.0709072215420.21186@xanadu.home","threadId":"9825","inReplyTo":"85fy1q11xv.fsf@lola.goethe.zz","subject":"Re: [PATCH] diff-delta.c: pack the index structure","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-08T02:34:47Z","receivedAt":"2007-09-08T02:34:47Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 8 Sep 2007, David Kastrup wrote:\n\n> In normal use cases, the performance wins are not overly impressive:\n> we get something like 5-10% due to the slightly better locality of\n> memory accesses using the packed structure.\n\nThe gain is probably counterbalanced by the fact that you're copying the \nwhole index when packing it, which is unfortunate.\n\nAlso, could you provide actual test results backing your performance \nclaim?  5-10% is still not negligible.\n\n> -\tstruct index_entry *entry, **hash;\n> +\tstruct unpacked_index_entry *entry, **hash;\n> +\tstruct index_entry *aentry, **ahash;\n\nWhat does the \"a\" stand for?\n\n> +\tmem = index+1;\n[...]\n> +\tfor (i=0; i<hsize; i++) {\n[...]\n> +\t\tfor (entry=hash[i]; entry; entry=entry->next)\n\nMinor style nit: please add spaces around \"+\", \"=\", \"<\", etc. for \nconsistency.\n\nOtherwise that looks fine to me.\n\n\nNicolas\n"},{"id":"52981","messageId":"85vealzm7q.fsf@lola.goethe.zz","threadId":"9825","inReplyTo":"alpine.LFD.0.9999.0709072215420.21186@xanadu.home","subject":"Re: [PATCH] diff-delta.c: pack the index structure","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-08T06:48:41Z","receivedAt":"2007-09-08T06:48:41Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> On Sat, 8 Sep 2007, David Kastrup wrote:\n>\n>> In normal use cases, the performance wins are not overly impressive:\n>> we get something like 5-10% due to the slightly better locality of\n>> memory accesses using the packed structure.\n>\n> The gain is probably counterbalanced by the fact that you're copying\n> the whole index when packing it, which is unfortunate.\n\nIt was a design choice (I don't particularly like it myself).  An\nindex is created once, used a dozen times.  Doing the packing in-place\nimplies using realloc on the finished index.  I consider the\nlikelihood of permanent memory fragmentation higher when doing that\nrather than when allocating a fresh area of the same size.\n\nAlso a repack in-place is going to cost more operations and have quite\nmore complicated code.\n\n> Also, could you provide actual test results backing your performance \n> claim?  5-10% is still not negligible.\n\nI did in my git repository\n\nfor i in .git/objects/[0-9a-f][0-9a-f]/[0-9a-f]*;do echo $i;done|sed 's+.*ts/\\(..\\)/+\\1+' > /tmp/objlist\n\nand then something like\n\ndak@lola:/usr/local/tmp/git$ time ./git-pack-objects </tmp/objlist --stdout|dd of=/dev/null\n4099+2 records in\n4100+1 records out\n2099205 bytes (2.1 MB) copied, 3.99295 seconds, 526 kB/s\n\nreal\t0m4.023s\nuser\t0m3.812s\nsys\t0m0.168s\ndak@lola:/usr/local/tmp/git$ time git-pack-objects </tmp/objlist --stdout|dd of=/dev/null\n4099+2 records in\n4100+1 records out\n2099205 bytes (2.1 MB) copied, 4.18734 seconds, 501 kB/s\n\nreal\t0m4.218s\nuser\t0m4.012s\nsys\t0m0.160s\ndak@lola:/usr/local/tmp/git$ \n\nrepeatedly on a warm cache.  Results were pretty much comparable:\nconsistently my version was faster, but never more than 10%.\n\n>> -\tstruct index_entry *entry, **hash;\n>> +\tstruct unpacked_index_entry *entry, **hash;\n>> +\tstruct index_entry *aentry, **ahash;\n>\n> What does the \"a\" stand for?\n\narray (as opposed to linked list).  Was the first thing coming into my\nmind.  Maybe I should have gone for \"p\" for packed, but I shied from\nit because it often is meant to imply \"pointer\".\n\nAlternatively I could replace \"entry\" with \"uentry\", but that affects\nmore lines.\n\nWhat do you propose?\n\n>> +\tmem = index+1;\n> [...]\n>> +\tfor (i=0; i<hsize; i++) {\n> [...]\n>> +\t\tfor (entry=hash[i]; entry; entry=entry->next)\n>\n> Minor style nit: please add spaces around \"+\", \"=\", \"<\", etc. for \n> consistency.\n\nCan do.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"52980","messageId":"854pi5zh8q.fsf@lola.goethe.zz","threadId":"9825","inReplyTo":"alpine.LFD.0.9999.0709072215420.21186@xanadu.home","subject":"Re: [PATCH] diff-delta.c: pack the index structure","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-08T08:36:05Z","receivedAt":"2007-09-08T08:36:05Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"\nI answered this post already, but the answer seems to have disappeared\ninto a black hole.  What a nuisance.\n\nNicolas Pitre <nico@cam.org> writes:\n\n> On Sat, 8 Sep 2007, David Kastrup wrote:\n>\n>> In normal use cases, the performance wins are not overly impressive:\n>> we get something like 5-10% due to the slightly better locality of\n>> memory accesses using the packed structure.\n>\n> The gain is probably counterbalanced by the fact that you're copying\n> the whole index when packing it, which is unfortunate.\n\nThe alternative would be packing in-place.  That's actually a rather\ncontorted operation, and the gains from packing would then have to be\nclaimed by \"realloc\".  I think that realloc is more likely to leave a\nfragmented address space (giving the reclaimed memory to the heap\nrather than back to the system), but I'd have to check glibc for\ndetails at least on GNU/Linux.\n\nAnother option avoiding the realloc would be not to use linked lists\nat all but just collect all entries sequentually in \"packed\" form, and\nsort them into order afterwards.  That's an O(n lg n) operation with a\nlarge n.  Even if one has a sorting algorithm with good memory\nlocality, I doubt that the locality would compensate for the lg n\nfactor, even when taking into account that we save ourselves the\ncopying.  And that is not even taken the possibility of having to cull\nsome buckets into account, another O(n) operation (which amounts to\ncopying everything once, too).\n\n> Also, could you provide actual test results backing your performance \n> claim?  5-10% is still not negligible.\n\n\ndak@lola:/usr/local/tmp/git$ for i in .git/objects/[0-9a-f][0-9a-f]/[0-9a-f]*;do echo $i;done|sed 's+.*ts/\\(..\\)/+\\1+' > /tmp/objlist\ndak@lola:/usr/local/tmp/git$ time ./git-pack-objects </tmp/objlist --stdout|dd of=/dev/null\n4099+2 records in\n4100+1 records out\n2099205 bytes (2.1 MB) copied, 4.01225 seconds, 523 kB/s\n\nreal\t0m4.043s\nuser\t0m3.836s\nsys\t0m0.164s\ndak@lola:/usr/local/tmp/git$ time git-pack-objects </tmp/objlist --stdout|dd of=/dev/null\n4099+2 records in\n4100+1 records out\n2099205 bytes (2.1 MB) copied, 4.34936 seconds, 483 kB/s\n\nreal\t0m4.381s\nuser\t0m4.056s\nsys\t0m0.176s\ndak@lola:/usr/local/tmp/git$ \n\nOf course, on a warm file system.\n\n>> -\tstruct index_entry *entry, **hash;\n>> +\tstruct unpacked_index_entry *entry, **hash;\n>> +\tstruct index_entry *aentry, **ahash;\n>\n> What does the \"a\" stand for?\n\narray (rather than linked list).  Should I rather rename entry and\nhash to uentry and uhash (for unpacked)?\n\n>> +\tmem = index+1;\n> [...]\n>> +\tfor (i=0; i<hsize; i++) {\n> [...]\n>> +\t\tfor (entry=hash[i]; entry; entry=entry->next)\n>\n> Minor style nit: please add spaces around \"+\", \"=\", \"<\", etc. for \n> consistency.\n\nWill do.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"53006","messageId":"85hcm4ubjn.fsf@lola.goethe.zz","threadId":"9825","inReplyTo":"854pi5zh8q.fsf@lola.goethe.zz","subject":"Re: [PATCH] diff-delta.c: pack the index structure","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-08T20:50:20Z","receivedAt":"2007-09-08T20:50:20Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"David Kastrup <dak@gnu.org> writes:\n\n> Another option avoiding the realloc would be not to use linked lists\n> at all but just collect all entries sequentually in \"packed\" form,\n> and sort them into order afterwards.  That's an O(n lg n) operation\n> with a large n.  Even if one has a sorting algorithm with good\n> memory locality, I doubt that the locality would compensate for the\n> lg n factor, even when taking into account that we save ourselves\n> the copying.  And that is not even taken the possibility of having\n> to cull some buckets into account, another O(n) operation (which\n> amounts to copying everything once, too).\n\nAs an illustration, I have implemented a proof-of-concept.  This is a\npatch (not formatted for submission) against the current master.  It\ntakes about a 20% performance hit on the whole git-pack-objects run,\nso the diffing code itself is likely affected worse.  For the\nproof-of-concept I did not do the hash bucket collision culling, nor\ndid I realloc to the possibly reduced size.  So a fairer comparison\nwould likely involve removing the culling code from master (or\nimplementing the culling in the proof-of-concept, but I am too lazy\nfor that).\n\nI hope this addresses the not-in-place complaint.  It is conceivable\nthat under tight memory conditions, this approach might actually work\nout better.  However, the glibc qsort implementation (at least it did\nso at one time) reverts to a mergesort for large numbers, and\nallocates a temporary buffer of the same size as the original data.\nIf that is still the case, the memory impact would actually be worse\nhere.  One would need to implement a custom _real_ in place sorter to\nget around this.  All in all, I don't think this approach is worth the\ntrouble: the sorting overhead factor of lg n is just too much.\n\n\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 0dde2f2..f6e2416 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -115,7 +115,6 @@ static const unsigned int U[256] = {\n struct index_entry {\n \tconst unsigned char *ptr;\n \tunsigned int val;\n-\tstruct index_entry *next;\n };\n \n struct delta_index {\n@@ -126,12 +125,24 @@ struct delta_index {\n \tstruct index_entry *hash[FLEX_ARRAY];\n };\n \n+static unsigned int cmp_hmask;\n+\n+static int cmp_index_entry(const void *va, const void *vb)\n+{\n+\tconst struct index_entry *a = va, *b = vb;\n+\tif ((a->val & cmp_hmask) != (b->val & cmp_hmask))\n+\t\treturn (a->val & cmp_hmask) < (b->val & cmp_hmask) ? -1 : 1;\n+\tif (a->val != b->val)\n+\t\treturn a->val < b->val ? -1 : 1;\n+\treturn a->ptr < b->ptr ? -1 : 1;\n+}\n+\n struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n {\n-\tunsigned int i, hsize, hmask, entries, prev_val, *hash_count;\n+\tunsigned int i, hsize, hmask, entries, prev_val, ihash;\n \tconst unsigned char *data, *buffer = buf;\n \tstruct delta_index *index;\n-\tstruct index_entry *entry, **hash;\n+\tstruct index_entry *entry, **hash, *entry_base;\n \tvoid *mem;\n \tunsigned long memsize;\n \n@@ -149,7 +160,7 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \n \t/* allocate lookup index */\n \tmemsize = sizeof(*index) +\n-\t\t  sizeof(*hash) * hsize +\n+\t\t  sizeof(*hash) * (hsize + 1) +\n \t\t  sizeof(*entry) * entries;\n \tmem = malloc(memsize);\n \tif (!mem)\n@@ -157,21 +168,14 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \tindex = mem;\n \tmem = index + 1;\n \thash = mem;\n-\tmem = hash + hsize;\n-\tentry = mem;\n+\tmem = hash + hsize + 1;\n+\tentry_base = mem;\n+\tentry = entry_base;\n \n \tindex->memsize = memsize;\n \tindex->src_buf = buf;\n \tindex->src_size = bufsize;\n \tindex->hash_mask = hmask;\n-\tmemset(hash, 0, hsize * sizeof(*hash));\n-\n-\t/* allocate an array to count hash entries */\n-\thash_count = calloc(hsize, sizeof(*hash_count));\n-\tif (!hash_count) {\n-\t\tfree(index);\n-\t\treturn NULL;\n-\t}\n \n \t/* then populate the index */\n \tprev_val = ~0;\n@@ -184,29 +188,33 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \t\tif (val == prev_val) {\n \t\t\t/* keep the lowest of consecutive identical blocks */\n \t\t\tentry[-1].ptr = data + RABIN_WINDOW;\n+\t\t\t--entries;\n \t\t} else {\n \t\t\tprev_val = val;\n \t\t\ti = val & hmask;\n \t\t\tentry->ptr = data + RABIN_WINDOW;\n \t\t\tentry->val = val;\n-\t\t\tentry->next = hash[i];\n-\t\t\thash[i] = entry++;\n-\t\t\thash_count[i]++;\n+\t\t\tentry++;\n \t\t}\n \t}\n+\tcmp_hmask = hmask;\n+\tqsort(entry_base, entries, sizeof(struct index_entry), cmp_index_entry);\n+\tihash = 0;\n+\t\n+\tfor (i=0; i<entries; i++) {\n+\t\tentry = &entry_base[i];\n+\t\tif ((entry->val & hmask) >= ihash) {\n+\t\t\t/* cull here */\n+\t\t\tdo {\n+\t\t\t\thash[ihash++] = entry;\n+\t\t\t} while ((entry->val & hmask) >= ihash);\n+\t\t}\n+\t}\n+\twhile (ihash <= hsize) {\n+\t\thash[ihash++] = &entry_base[entries];\n+\t}\n \n-\t/*\n-\t * Determine a limit on the number of entries in the same hash\n-\t * bucket.  This guards us against pathological 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 * 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+#if 0\n \tfor (i = 0; i < hsize; i++) {\n \t\tif (hash_count[i] < HASH_LIMIT)\n \t\t\tcontinue;\n@@ -221,6 +229,7 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \t\t} while(entry);\n \t}\n \tfree(hash_count);\n+#endif\n \n \treturn index;\n }\n@@ -302,7 +311,7 @@ create_delta(const struct delta_index *index,\n \t\t\tval ^= U[data[-RABIN_WINDOW]];\n \t\t\tval = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];\n \t\t\ti = val & index->hash_mask;\n-\t\t\tfor (entry = index->hash[i]; entry; entry = entry->next) {\n+\t\t\tfor (entry = index->hash[i]; entry < index->hash[i+1]; entry++) {\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\n\n\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"}]}