{"thread":{"id":"3487","subject":"[PATCH] diff-delta: allow reusing of the reference buffer index","startedAt":"2006-02-28T04:38:28Z","lastAt":"2006-02-28T04:38:28Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"16881","messageId":"Pine.LNX.4.64.0602272315370.25336@localhost.localdomain","threadId":"3487","inReplyTo":null,"subject":"[PATCH] diff-delta: allow reusing of the reference buffer index","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-28T04:38:28Z","receivedAt":"2006-02-28T04:38:28Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nWhen a reference buffer is used multiple times then its index can be \ncomputed only once and reused multiple times.  This patch adds an extra \npointer to a pointer argument (from_index) to diff_delta() for this.\n\nIf from_index is NULL then everything is like before.\n\nIf from_index is non NULL and *from_index is NULL then the index is \ncreated and its location stored to *from_index.  In this case the caller \nhas the responsibility to free the memory pointed to by *from_index.\n\nIf from_index and *from_index are non NULL then the index is reused as \nis.\n\nThis currently saves about 10% of CPU time to repack the git archive.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\nThis is partly what Linus suggested recently.  However I only made the \nminimum changes to pack-objects.c to try it out and demonstrate how it \nworks.  I however don't feel confortable enough with the changes \nrequired to implement the full solution which is to turn the window \nprocessing around i.e. keep the reference buffer stable while different \ntargets are tested against this reference.  This is something worth \ndoing since that would reduce memory usage significantly.  But Like I \nsaid, pack-objects as grown more complex with Junio latest additions \nso...\n\n delta.h           |    3 ++-\n diff-delta.c      |   41 +++++++++++++++++++++++++++--------------\n diffcore-break.c  |    2 +-\n diffcore-rename.c |    2 +-\n pack-objects.c    |   11 ++++++++---\n test-delta.c      |    2 +-\n 6 files changed, 40 insertions(+), 21 deletions(-)\n\nf660c44250f5c02a7e773ed991316f7f16950f3e\ndiff --git a/delta.h b/delta.h\nindex a15350d..00fef0b 100644\n--- a/delta.h\n+++ b/delta.h\n@@ -4,7 +4,8 @@\n /* handling of delta buffers */\n extern void *diff_delta(void *from_buf, unsigned long from_size,\n \t\t\tvoid *to_buf, unsigned long to_size,\n-\t\t        unsigned long *delta_size, unsigned long max_size);\n+\t\t        unsigned long *delta_size, unsigned long max_size,\n+\t\t\tvoid **from_index);\n extern void *patch_delta(void *src_buf, unsigned long src_size,\n \t\t\t void *delta_buf, unsigned long delta_size,\n \t\t\t unsigned long *dst_size);\ndiff --git a/diff-delta.c b/diff-delta.c\nindex bb07926..67561cd 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -30,8 +30,7 @@ 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+\t\t\t\t   unsigned long trg_bufsize)\n {\n \tunsigned long hsize;\n \tunsigned int i, hshift, hlimit, *hash_count;\n@@ -44,14 +43,17 @@ static struct index ** delta_index(const\n \tfor (i = 8; (1 << i) < hsize && i < 24; i += 2);\n \thsize = 1 << i;\n \thshift = (i - 8) / 2;\n-\t*hash_shift = hshift;\n \n-\t/* allocate lookup index */\n-\tmem = malloc(hsize * sizeof(*hash) + bufsize * sizeof(*entry));\n+\t/*\n+\t * Allocate lookup index.  Note the first hash pointer\n+\t * is used to store the hash shift value.\n+\t */\n+\tmem = malloc((1 + hsize) * sizeof(*hash) + bufsize * sizeof(*entry));\n \tif (!mem)\n \t\treturn NULL;\n \thash = mem;\n-\tentry = mem + hsize * sizeof(*hash);\n+\t*hash++ = (void *)hshift;\n+\tentry = mem + (1 + hsize) * sizeof(*hash);\n \tmemset(hash, 0, hsize * sizeof(*hash));\n \n \t/* allocate an array to count hash entries */\n@@ -107,7 +109,7 @@ static struct index ** delta_index(const\n \t}\n \tfree(hash_count);\n \n-\treturn hash;\n+\treturn hash-1;\n }\n \n /* provide the size of the copy opcode given the block offset and size */\n@@ -121,7 +123,8 @@ static struct index ** delta_index(const\n void *diff_delta(void *from_buf, unsigned long from_size,\n \t\t void *to_buf, unsigned long to_size,\n \t\t unsigned long *delta_size,\n-\t\t unsigned long max_size)\n+\t\t unsigned long max_size,\n+\t\t void **from_index)\n {\n \tunsigned int i, outpos, outsize, inscnt, hash_shift;\n \tconst unsigned char *ref_data, *ref_top, *data, *top;\n@@ -130,9 +133,16 @@ 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, to_size, &hash_shift);\n-\tif (!hash)\n-\t\treturn NULL;\n+\tif (from_index && *from_index) {\n+\t\thash = *from_index;\n+\t} else {\n+\t\thash = delta_index(from_buf, from_size, to_size);\n+\t\tif (!hash)\n+\t\t\treturn NULL;\n+\t\tif (from_index)\n+\t\t\t*from_index = hash;\n+\t}\n+\thash_shift = (unsigned int)(*hash++);\n \n \toutpos = 0;\n \toutsize = 8192;\n@@ -140,7 +150,8 @@ void *diff_delta(void *from_buf, unsigne\n \t\toutsize = max_size + MAX_OP_SIZE + 1;\n \tout = malloc(outsize);\n \tif (!out) {\n-\t\tfree(hash);\n+\t\tif (!from_index)\n+\t\t\tfree(hash-1);\n \t\treturn NULL;\n \t}\n \n@@ -241,7 +252,8 @@ void *diff_delta(void *from_buf, unsigne\n \t\t\t\tout = realloc(out, outsize);\n \t\t\tif (!out) {\n \t\t\t\tfree(tmp);\n-\t\t\t\tfree(hash);\n+\t\t\t\tif (!from_index)\n+\t\t\t\t\tfree(hash-1);\n \t\t\t\treturn NULL;\n \t\t\t}\n \t\t}\n@@ -250,7 +262,8 @@ void *diff_delta(void *from_buf, unsigne\n \tif (inscnt)\n \t\tout[outpos - inscnt - 1] = inscnt;\n \n-\tfree(hash);\n+\tif (!from_index)\n+\t\tfree(hash-1);\n \t*delta_size = outpos;\n \treturn out;\n }\ndiff --git a/diffcore-break.c b/diffcore-break.c\nindex c57513a..6dc22d5 100644\n--- a/diffcore-break.c\n+++ b/diffcore-break.c\n@@ -67,7 +67,7 @@ static int should_break(struct diff_file\n \n \tdelta = diff_delta(src->data, src->size,\n \t\t\t   dst->data, dst->size,\n-\t\t\t   &delta_size, 0);\n+\t\t\t   &delta_size, 0, NULL);\n \tif (!delta)\n \t\treturn 0; /* error but caught downstream */\n \ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 39d9126..5b4cde4 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -168,7 +168,7 @@ static int estimate_similarity(struct di\n \tdelta_limit = base_size * (MAX_SCORE-minimum_score) / MAX_SCORE;\n \tdelta = diff_delta(src->data, src->size,\n \t\t\t   dst->data, dst->size,\n-\t\t\t   &delta_size, delta_limit);\n+\t\t\t   &delta_size, delta_limit, NULL);\n \tif (!delta)\n \t\t/* If delta_limit is exceeded, we have too much differences */\n \t\treturn 0;\ndiff --git a/pack-objects.c b/pack-objects.c\nindex ceb107f..2b2d9a9 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -202,7 +202,7 @@ static void *delta_against(void *buf, un\n \tif (!otherbuf)\n \t\tdie(\"unable to read %s\", sha1_to_hex(entry->delta->sha1));\n         delta_buf = diff_delta(otherbuf, othersize,\n-\t\t\t       buf, size, &delta_size, 0);\n+\t\t\t       buf, size, &delta_size, 0, NULL);\n         if (!delta_buf || delta_size != entry->delta_size)\n         \tdie(\"delta size changed\");\n         free(buf);\n@@ -707,6 +707,7 @@ static int type_size_sort(const struct o\n struct unpacked {\n \tstruct object_entry *entry;\n \tvoid *data;\n+\tvoid **delta_index;\n };\n \n /*\n@@ -789,7 +790,8 @@ static int try_delta(struct unpacked *cu\n \tif (sizediff >= max_size)\n \t\treturn -1;\n \tdelta_buf = diff_delta(old->data, oldsize,\n-\t\t\t       cur->data, size, &delta_size, max_size);\n+\t\t\t       cur->data, size, &delta_size,\n+\t\t\t       max_size, old->delta_index);\n \tif (!delta_buf)\n \t\treturn 0;\n \tcur_entry->delta = old_entry;\n@@ -830,6 +832,7 @@ static void find_deltas(struct object_en\n \t\t\t */\n \t\t\tcontinue;\n \n+\t\tfree(n->delta_index);\n \t\tfree(n->data);\n \t\tn->entry = entry;\n \t\tn->data = read_sha1_file(entry->sha1, type, &size);\n@@ -853,8 +856,10 @@ static void find_deltas(struct object_en\n \t\t\tidx = 0;\n \t}\n \n-\tfor (i = 0; i < window; ++i)\n+\tfor (i = 0; i < window; ++i) {\n+\t\tfree(array[i].delta_index);\n \t\tfree(array[i].data);\n+\t}\n \tfree(array);\n }\n \ndiff --git a/test-delta.c b/test-delta.c\nindex 1be8ee0..89eb68e 100644\n--- a/test-delta.c\n+++ b/test-delta.c\n@@ -63,7 +63,7 @@ int main(int argc, char *argv[])\n \tif (argv[1][1] == 'd')\n \t\tout_buf = diff_delta(from_buf, from_size,\n \t\t\t\t     data_buf, data_size,\n-\t\t\t\t     &out_size, 0);\n+\t\t\t\t     &out_size, 0, NULL);\n \telse\n \t\tout_buf = patch_delta(from_buf, from_size,\n \t\t\t\t      data_buf, data_size,\n-- \n1.2.3.g8fcf1-dirty\n"}]}