{"thread":{"id":"4030","subject":"[PATCH] improve diff-delta with sparse and/or repetitive data","startedAt":"2006-05-03T03:31:00Z","lastAt":"2006-05-03T03:46:51Z","messageCount":2,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"19399","messageId":"Pine.LNX.4.64.0605022226070.28543@localhost.localdomain","threadId":"4030","inReplyTo":null,"subject":"[PATCH] improve diff-delta with sparse and/or repetitive data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-03T03:31:00Z","receivedAt":"2006-05-03T03:31:00Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"It is useless to preserve multiple hash entries for consecutive blocks \nwith the same hash.  Keeping only the first one will allow for matching \nthe longest string of identical bytes while subsequent blocks will only \nallow for shorter matches.  The backward matching code will match the \nend of it as necessary.\n\nThis improves both performances (no repeated string compare with long \nsuccessions of identical bytes, or even small group of bytes), as well \nas compression (less likely to need random hash bucket entry culling), \nespecially with sparse files.\n\nWith well behaved data sets this patch doesn't change much.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 35e517d..c618875 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -136,11 +136,12 @@ struct delta_index {\n \n struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n {\n-\tunsigned int i, hsize, hmask, entries, *hash_count;\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 \tvoid *mem;\n+\tunsigned long memsize;\n \n \tif (!buf || !bufsize)\n \t\treturn NULL;\n@@ -155,9 +156,10 @@ struct delta_index * create_delta_index(\n \thmask = hsize - 1;\n \n \t/* allocate lookup index */\n-\tmem = malloc(sizeof(*index) +\n-\t\t     sizeof(*hash) * hsize +\n-\t\t     sizeof(*entry) * entries);\n+\tmemsize = sizeof(*index) +\n+\t\t  sizeof(*hash) * hsize +\n+\t\t  sizeof(*entry) * entries;\n+\tmem = malloc(memsize);\n \tif (!mem)\n \t\treturn NULL;\n \tindex = mem;\n@@ -179,18 +181,26 @@ struct delta_index * create_delta_index(\n \t}\n \n \t/* then populate the index */\n-\tdata = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;\n-\twhile (data >= buffer) {\n+\tprev_val = ~0;\n+\tfor (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;\n+\t     data >= buffer;\n+\t     data -= RABIN_WINDOW) {\n \t\tunsigned int val = 0;\n \t\tfor (i = 1; i <= RABIN_WINDOW; i++)\n \t\t\tval = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];\n-\t\ti = val & hmask;\n-\t\tentry->ptr = data + RABIN_WINDOW;\n-\t\tentry->val = val;\n-\t\tentry->next = hash[i];\n-\t\thash[i] = entry++;\n-\t\thash_count[i]++;\n-\t\tdata -= RABIN_WINDOW;\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} 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\tentries--;\n+\t\t}\n \t}\n \n \t/*\n@@ -220,6 +230,10 @@ struct delta_index * create_delta_index(\n \t}\n \tfree(hash_count);\n \n+\t/* If we didn't use all hash entries, free the unused memory. */\n+\tif (entries)\n+\t\tindex = realloc(index, memsize - entries * sizeof(*entry));\n+\n \treturn index;\n }\n \n"},{"id":"19400","messageId":"Pine.LNX.4.64.0605022336551.28543@localhost.localdomain","threadId":"4030","inReplyTo":"Pine.LNX.4.64.0605022226070.28543@localhost.localdomain","subject":"[PATCH] tiny optimization to diff-delta","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-03T03:46:51Z","receivedAt":"2006-05-03T03:46:51Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This is my assembly freak side looking at generated code again.  And \nsince create_delta() is certainly pretty high on the radar every bits \ncount.  In this case shorter code is generated if hash_mask is not \ncopied to a local variable.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 26540d8..c618875 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -253,7 +253,7 @@ create_delta(const struct delta_index *i\n \t     const void *trg_buf, unsigned long trg_size,\n \t     unsigned long *delta_size, unsigned long max_size)\n {\n-\tunsigned int i, outpos, outsize, hash_mask, val;\n+\tunsigned int i, outpos, outsize, val;\n \tint inscnt;\n \tconst unsigned char *ref_data, *ref_top, *data, *top;\n \tunsigned char *out;\n@@ -289,7 +289,6 @@ create_delta(const struct delta_index *i\n \tref_top = ref_data + index->src_size;\n \tdata = trg_buf;\n \ttop = trg_buf + trg_size;\n-\thash_mask = index->hash_mask;\n \n \toutpos++;\n \tval = 0;\n@@ -304,7 +303,7 @@ create_delta(const struct delta_index *i\n \t\tstruct index_entry *entry;\n \t\tval ^= U[data[-RABIN_WINDOW]];\n \t\tval = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];\n-\t\ti = val & hash_mask;\n+\t\ti = val & index->hash_mask;\n \t\tfor (entry = index->hash[i]; entry; entry = entry->next) {\n \t\t\tconst unsigned char *ref = entry->ptr;\n \t\t\tconst unsigned char *src = data;\n"}]}