{"thread":{"id":"9829","subject":"[PATCH] diff-delta.c: rename {a,}{entry,hash} to {,u}{entry,hash}","startedAt":"2007-09-08T08:54:03Z","lastAt":"2007-09-09T00:38:03Z","messageCount":6,"participants":["David Kastrup","Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"52983","messageId":"f1161c08aeeca60b6c33af34ccea68fd99b9ea4e.1189243702.git.dak@gnu.org","threadId":"9829","inReplyTo":"0cd39105dcd57a60eca290db598613aafcc8c577.1189243702.git.dak@gnu.org","subject":"[PATCH] diff-delta.c: rename {a,}{entry,hash} to {,u}{entry,hash}","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-08T08:54:03Z","receivedAt":"2007-09-08T08:54:03Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"The variables for the packed entries are now called just entry and\nhash rather than aentry+ahash, and those for the unpacked entries have\nbeen renamed to uentry and uhash from the original entry and hash.\n\nWhile this makes the diff to the unchanged code larger, it matches the\ntype declarations better.\n\nSigned-off-by: David Kastrup <dak@gnu.org>\n---\n diff-delta.c |   65 ++++++++++++++++++++++++++++-----------------------------\n 1 files changed, 32 insertions(+), 33 deletions(-)\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 1b4b1c1..e7c33aa 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -135,8 +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 unpacked_index_entry *entry, **hash;\n-\tstruct index_entry *aentry, **ahash;\n+\tstruct unpacked_index_entry *uentry, **uhash;\n+\tstruct index_entry *entry, **hash;\n \tvoid *mem;\n \tunsigned long memsize;\n \n@@ -153,21 +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(*hash) * hsize +\n-\t\t  sizeof(*entry) * entries;\n+\tmemsize = sizeof(*uhash) * hsize +\n+\t\t  sizeof(*uentry) * entries;\n \tmem = malloc(memsize);\n \tif (!mem)\n \t\treturn NULL;\n-\thash = mem;\n-\tmem = hash + hsize;\n-\tentry = mem;\n+\tuhash = mem;\n+\tmem = uhash + hsize;\n+\tuentry = mem;\n \n-\tmemset(hash, 0, hsize * sizeof(*hash));\n+\tmemset(uhash, 0, hsize * sizeof(*uhash));\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(hash);\n+\t\tfree(uhash);\n \t\treturn NULL;\n \t}\n \n@@ -181,15 +181,15 @@ 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].entry.ptr = data + RABIN_WINDOW;\n+\t\t\tuentry[-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->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\tuentry->entry.ptr = data + RABIN_WINDOW;\n+\t\t\tuentry->entry.val = val;\n+\t\t\tuentry->next = uhash[i];\n+\t\t\tuhash[i] = uentry++;\n \t\t\thash_count[i]++;\n \t\t}\n \t}\n@@ -209,17 +209,17 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \tfor (i = 0; i < hsize; i++) {\n \t\tif (hash_count[i] < HASH_LIMIT)\n \t\t\tcontinue;\n-\t\tentry = hash[i];\n+\t\tuentry = uhash[i];\n \t\tdo {\n-\t\t\tstruct unpacked_index_entry *keep = entry;\n+\t\t\tstruct unpacked_index_entry *keep = uentry;\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\tuentry = uentry->next;\n+\t\t\t} while(--skip && uentry);\n \t\t\t++entries;\n-\t\t\tkeep->next = entry;\n-\t\t} while(entry);\n+\t\t\tkeep->next = uentry;\n+\t\t} while(uentry);\n \t}\n \tfree(hash_count);\n \n@@ -227,13 +227,12 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \t * linked lists */\n \n \tmemsize = sizeof(*index)\n-\t\t+ sizeof(*ahash) * (hsize+1)\n-\t\t+ sizeof(*aentry) * entries;\n-\n+\t\t+ sizeof(*hash) * (hsize+1)\n+\t\t+ sizeof(*entry) * entries;\n \tmem = malloc(memsize);\n \n \tif (!mem) {\n-\t\tfree(hash);\n+\t\tfree(uhash);\n \t\treturn NULL;\n \t}\n \n@@ -244,25 +243,25 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \tindex->hash_mask = hmask;\n \n \tmem = index + 1;\n-\tahash = mem;\n-\tmem = ahash + (hsize+1);\n-\taentry = mem;\n+\thash = mem;\n+\tmem = hash + (hsize+1);\n+\tentry = mem;\n \n \t/* Coalesce all entries belonging to one linked list into\n \t * consecutive array entries */\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\thash[i] = entry;\n+\t\tfor (uentry = uhash[i]; uentry; uentry = uentry->next)\n+\t\t\t*entry++ = uentry->entry;\n \t}\n \n \t/* Sentinel value to indicate the length of the last hash\n \t * bucket */\n \n-\tahash[hsize] = aentry;\n-\tassert(aentry - (struct index_entry *)mem == entries);\n-\tfree(hash);\n+\thash[hsize] = entry;\n+\tassert(entry - (struct index_entry *)mem == entries);\n+\tfree(uhash);\n \n \treturn index;\n }\n-- \n1.5.3.GIT\n"},{"id":"52984","messageId":"0cd39105dcd57a60eca290db598613aafcc8c577.1189243702.git.dak@gnu.org","threadId":"9829","inReplyTo":null,"subject":"[PATCH] diff-delta.c: pack the index structure","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-08T09:31:31Z","receivedAt":"2007-09-08T09:31:31Z","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 |   74 +++++++++++++++++++++++++++++++++++++++++++++------------\n 1 files changed, 58 insertions(+), 16 deletions(-)\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 0dde2f2..1b4b1c1 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,16 +211,59 @@ 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 \n+\t/* Now create the packed index in array form rather than\n+\t * linked lists */\n+\n+\tmemsize = sizeof(*index)\n+\t\t+ sizeof(*ahash) * (hsize+1)\n+\t\t+ sizeof(*aentry) * entries;\n+\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+\t/* Coalesce all entries belonging to one linked list into\n+\t * consecutive array entries */\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+\n+\t/* Sentinel value to indicate the length of the last hash\n+\t * bucket */\n+\n+\tahash[hsize] = aentry;\n+\tassert(aentry - (struct index_entry *)mem == entries);\n+\tfree(hash);\n+\n \treturn index;\n }\n \n@@ -302,7 +344,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":"53004","messageId":"85zlzxt063.fsf@lola.goethe.zz","threadId":"9829","inReplyTo":"f1161c08aeeca60b6c33af34ccea68fd99b9ea4e.1189243702.git.dak@gnu.org","subject":"[PATCH] diff-delta.c: Rationalize culling of hash buckets","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-08T19:41:24Z","receivedAt":"2007-09-08T19:41:24Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"The previous hash bucket culling resulted in a somewhat unpredictable\nnumber of hash bucket entries in the order of magnitude of HASH_LIMIT.\n\nReplace this with a Bresenham-like algorithm leaving us with exactly\nHASH_LIMIT entries by uniform culling.\n---\n\nThis is assuming that the previous patch series has been applied\n(lacking any final comments or Acks on it; but I think I addressed the\nissues).  The hash bucket code culling has really annoyed me with its\nunintuitive results.  If the preceding patch series is thrown out (I\ncan't think why it would), one could rework this to fit the current\nmaster if really needed.\n\n diff-delta.c |   41 +++++++++++++++++++++++++++++++----------\n 1 files changed, 31 insertions(+), 10 deletions(-)\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex e7c33aa..98795c6 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -207,19 +207,40 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \t * the reference buffer.\n \t */\n \tfor (i = 0; i < hsize; i++) {\n-\t\tif (hash_count[i] < HASH_LIMIT)\n+\t\tint acc;\n+\n+\t\tif (hash_count[i] <= HASH_LIMIT)\n \t\t\tcontinue;\n+\n+\t\tentries -= hash_count[i] - HASH_LIMIT;\n+\t\t/* We leave exactly HASH_LIMIT entries in the bucket */\n+\n \t\tuentry = uhash[i];\n+\t\tacc = 0;\n \t\tdo {\n-\t\t\tstruct unpacked_index_entry *keep = uentry;\n-\t\t\tint skip = hash_count[i] / HASH_LIMIT;\n-\t\t\tdo {\n-\t\t\t\t--entries;\n-\t\t\t\tuentry = uentry->next;\n-\t\t\t} while(--skip && uentry);\n-\t\t\t++entries;\n-\t\t\tkeep->next = uentry;\n-\t\t} while(uentry);\n+\t\t\tacc += hash_count[i] - HASH_LIMIT;\n+\t\t\tif (acc > 0) {\n+\t\t\t\tstruct unpacked_index_entry *keep = uentry;\n+\t\t\t\tdo {\n+\t\t\t\t\tuentry = uentry->next;\n+\t\t\t\t\tacc -= HASH_LIMIT;\n+\t\t\t\t} while (acc > 0);\n+\t\t\t\tkeep->next = uentry->next;\n+\t\t\t}\n+\t\t\tuentry = uentry->next;\n+\t\t} while (uentry);\n+\n+\t\t/* Assume that this loop is gone through exactly\n+\t\t * HASH_LIMIT times and is entered and left with\n+\t\t * acc==0.  So the first statement in the loop\n+\t\t * contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT\n+\t\t * to the accumulator, and the inner loop consequently\n+\t\t * is run (hash_count[i]-HASH_LIMIT) times, removing\n+\t\t * one element from the list each time.  Since acc\n+\t\t * balances out to 0 at the final run, the inner loop\n+\t\t * body can't be left with uentry==NULL.  So we indeed\n+\t\t * encounter uentry==NULL in the outer loop only.\n+\t\t */\n \t}\n \tfree(hash_count);\n \n-- \n1.5.3.GIT\n"},{"id":"53007","messageId":"alpine.LFD.0.9999.0709081648281.21186@xanadu.home","threadId":"9829","inReplyTo":"f1161c08aeeca60b6c33af34ccea68fd99b9ea4e.1189243702.git.dak@gnu.org","subject":"Re: [PATCH] diff-delta.c: rename {a,}{entry,hash} to {,u}{entry,hash}","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-08T20:52:04Z","receivedAt":"2007-09-08T20:52:04Z","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> The variables for the packed entries are now called just entry and\n> hash rather than aentry+ahash, and those for the unpacked entries have\n> been renamed to uentry and uhash from the original entry and hash.\n> \n> While this makes the diff to the unchanged code larger, it matches the\n> type declarations better.\n\nSince the packed version is used less often, could you rename that one \ninstead, and use packed_entry and packed_hash forclarity.\n\nAlso please fold this with your other patch (not the culling one).\n\nThen you can add my ACK.\n\n\nNicolas\n"},{"id":"53008","messageId":"85abrwuas8.fsf@lola.goethe.zz","threadId":"9829","inReplyTo":"alpine.LFD.0.9999.0709081648281.21186@xanadu.home","subject":"Re: [PATCH] diff-delta.c: rename {a,}{entry,hash} to {,u}{entry,hash}","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-09-08T21:06:47Z","receivedAt":"2007-09-08T21:06:47Z","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>> The variables for the packed entries are now called just entry and\n>> hash rather than aentry+ahash, and those for the unpacked entries have\n>> been renamed to uentry and uhash from the original entry and hash.\n>> \n>> While this makes the diff to the unchanged code larger, it matches the\n>> type declarations better.\n>\n> Since the packed version is used less often, could you rename that one \n> instead, and use packed_entry and packed_hash forclarity.\n>\n> Also please fold this with your other patch (not the culling one).\n\nUh, what other patch?  If I don't do the renames in the second patch,\nthen only the first patch remains.  Which I'll change to use the\nproposed names.  Hope that's what you meant.\n\n> Then you can add my ACK.\n\nI'll do that, and rework the culling patch on top of that (unacked for\nnow).\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"53030","messageId":"alpine.LFD.0.9999.0709082036040.21186@xanadu.home","threadId":"9829","inReplyTo":"85abrwuas8.fsf@lola.goethe.zz","subject":"Re: [PATCH] diff-delta.c: rename {a,}{entry,hash} to {,u}{entry,hash}","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-09-09T00:38:03Z","receivedAt":"2007-09-09T00:38:03Z","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> Nicolas Pitre <nico@cam.org> writes:\n> \n> > On Sat, 8 Sep 2007, David Kastrup wrote:\n> >\n> >> The variables for the packed entries are now called just entry and\n> >> hash rather than aentry+ahash, and those for the unpacked entries have\n> >> been renamed to uentry and uhash from the original entry and hash.\n> >> \n> >> While this makes the diff to the unchanged code larger, it matches the\n> >> type declarations better.\n> >\n> > Since the packed version is used less often, could you rename that one \n> > instead, and use packed_entry and packed_hash forclarity.\n> >\n> > Also please fold this with your other patch (not the culling one).\n> \n> Uh, what other patch?  If I don't do the renames in the second patch,\n> then only the first patch remains.  Which I'll change to use the\n> proposed names.  Hope that's what you meant.\n\nYes, that's what I meant.\n\n> > Then you can add my ACK.\n> \n> I'll do that, and rework the culling patch on top of that (unacked for\n> now).\n\nI'm looking at it atm.\n\n\nNicolas\n"}]}