{"thread":{"id":"10407","subject":"[PATCH, take 1] Linear-time/space rename logic (exact renames only)","startedAt":"2007-10-21T23:59:03Z","lastAt":"2007-10-22T22:54:55Z","messageCount":13,"participants":["Linus Torvalds","David Symonds","Jeff King","Sven Verdoolaege","Alex Riesen"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"56791","messageId":"alpine.LFD.0.999.0710211603200.10525@woody.linux-foundation.org","threadId":"10407","inReplyTo":null,"subject":"[PATCH, take 1] Linear-time/space rename logic (exact renames only)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-21T23:59:03Z","receivedAt":"2007-10-21T23:59:03Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis is a first effort at avoiding various O(n*m) effects in the rename \ndetection. Right now it does so only for the exact renames, which is \nadmittedly a rather easier case to handle, but having emailed a bit with \nAndy Chu, I think it's possible to do even the non-exact renames using a \nsimilar approach.\n\nThis depends on the previous diffcore-rename() cleanup, and introduces a \nnew set of helpers for doing hash tables (hash.[ch]). We could probably \nmove some of the other of our hash table users over to this (it's designed \nto be fairly generic), but that's a separate issue.\n\nWhat it does is to rather than iterate over all sources and destinations \nand checking if they are identical (which is O(src*dst)), it hashes each \nof the sources and destinations into a hash table, using the SHA1 hash of \nthe contents as the hash. That's O(n+m). It then walks the hash table \n(which is also O(m+n) in size), and only pairs up files for comparison \nthat hashed to the same spot.\n\nDoing this for more than just the exact same contents would be basically \nthe same thing, except it starts hashing up fingerprints of the contents \nand linking up file pairs that get linked up by those fingerprints. More \ninvolved, but not impossible.\n\nI tried a trivial case where I moved 100,000 files from one directory to \nanother, and this patch speeds that up from ~13s to just under 2s for me.\n\nHowever! Please note:\n - it looks ok, and I've tested it some, but this needs more people \n   looking at it.\n - because it only helps the exact rename case, it by no means \"solves\" \n   the rename cost issue. It just makes one particular case go much \n   faster.\n - in fact, the big optimization isn't the actual hash table, but the \n   independent and much simpler \"diff_filespec->used\" optimization for a \n   deleted filename that was used for a rename/copy.\n\nBut I'd like to have people give it a look,\n\n\t\tLinus\n\n---\n\n Makefile          |    4 +-\n diffcore-rename.c |  214 ++++++++++++++++++++++++++++++++++------------------\n diffcore.h        |    1 +\n hash.c            |  110 +++++++++++++++++++++++++++\n hash.h            |   43 +++++++++++\n 5 files changed, 296 insertions(+), 76 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 8db4dbe..17c31ba 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -291,7 +291,7 @@ LIB_H = \\\n \trun-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \\\n \ttree-walk.h log-tree.h dir.h path-list.h unpack-trees.h builtin.h \\\n \tutf8.h reflog-walk.h patch-ids.h attr.h decorate.h progress.h \\\n-\tmailmap.h remote.h\n+\tmailmap.h remote.h hash.o\n \n DIFF_OBJS = \\\n \tdiff.o diff-lib.o diffcore-break.o diffcore-order.o \\\n@@ -301,7 +301,7 @@ DIFF_OBJS = \\\n LIB_OBJS = \\\n \tblob.o commit.o connect.o csum-file.o cache-tree.o base85.o \\\n \tdate.o diff-delta.o entry.o exec_cmd.o ident.o \\\n-\tinterpolate.o \\\n+\tinterpolate.o hash.o \\\n \tlockfile.o \\\n \tpatch-ids.o \\\n \tobject.o pack-check.o pack-write.o patch-delta.o path.o pkt-line.o \\\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 2077a9b..05d39db 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -4,6 +4,7 @@\n #include \"cache.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n+#include \"hash.h\"\n \n /* Table of rename/copy destinations */\n \n@@ -96,29 +97,6 @@ static struct diff_rename_src *register_rename_src(struct diff_filespec *one,\n \treturn &(rename_src[first]);\n }\n \n-static int is_exact_match(struct diff_filespec *src,\n-\t\t\t  struct diff_filespec *dst,\n-\t\t\t  int contents_too)\n-{\n-\tif (src->sha1_valid && dst->sha1_valid &&\n-\t    !hashcmp(src->sha1, dst->sha1))\n-\t\treturn 1;\n-\tif (!contents_too)\n-\t\treturn 0;\n-\tif (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))\n-\t\treturn 0;\n-\tif (src->size != dst->size)\n-\t\treturn 0;\n-\tif (src->sha1_valid && dst->sha1_valid)\n-\t    return !hashcmp(src->sha1, dst->sha1);\n-\tif (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0))\n-\t\treturn 0;\n-\tif (src->size == dst->size &&\n-\t    !memcmp(src->data, dst->data, src->size))\n-\t\treturn 1;\n-\treturn 0;\n-}\n-\n static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n {\n \tint src_len = strlen(src->path), dst_len = strlen(dst->path);\n@@ -216,6 +194,7 @@ static void record_rename_pair(int dst_index, int src_index, int score)\n \t\tdie(\"internal error: dst already matched.\");\n \n \tsrc = rename_src[src_index].one;\n+\tsrc->used = 1;\n \tone = alloc_filespec(src->path);\n \tfill_filespec(one, src->sha1, src->mode);\n \n@@ -262,56 +241,152 @@ static int compute_stays(struct diff_queue_struct *q,\n \treturn 1;\n }\n \n+struct file_similarity {\n+\tint src_dst, index;\n+\tstruct diff_filespec *filespec;\n+\tstruct file_similarity *next;\n+};\n+\n+static int find_identical_files(struct file_similarity *src,\n+\t\t\t\tstruct file_similarity *dst)\n+{\n+\tint renames = 0;\n+\tdo {\n+\t\tstruct diff_filespec *one = src->filespec;\n+\t\tstruct file_similarity *p, *best;\n+\t\tint i = 100;\n+\n+\t\tbest = NULL;\n+\t\tfor (p = dst; p; p = p->next) {\n+\t\t\tstruct diff_filespec *two = p->filespec;\n+\n+\t\t\t/* Already picked as a destination? */\n+\t\t\tif (!p->src_dst)\n+\t\t\t\tcontinue;\n+\t\t\t/* False hash collission? */\n+\t\t\tif (hashcmp(one->sha1, two->sha1))\n+\t\t\t\tcontinue;\n+\t\t\tbest = p;\n+\t\t\tif (basename_same(one, two))\n+\t\t\t\tbreak;\n+\n+\t\t\t/* Too many identical alternatives? Pick one */\n+\t\t\tif (!--i)\n+\t\t\t\tbreak;\n+\t\t}\n+\t\tif (best) {\n+\t\t\tbest->src_dst = 0;\n+\t\t\trecord_rename_pair(best->index, src->index, MAX_SCORE);\n+\t\t\trenames++;\n+\t\t}\n+\t} while ((src = src->next) != NULL);\n+\treturn renames;\n+}\n+\n+static int find_same_files(void *ptr)\n+{\n+\tstruct file_similarity *p = ptr;\n+\tstruct file_similarity *src = NULL, *dst = NULL;\n+\n+\t/* Split the hash list up into sources and destinations */\n+\tdo {\n+\t\tstruct file_similarity *entry = p;\n+\t\tp = p->next;\n+\t\tif (entry->src_dst < 0) {\n+\t\t\tentry->next = src;\n+\t\t\tsrc = entry;\n+\t\t} else {\n+\t\t\tentry->next = dst;\n+\t\t\tdst = entry;\n+\t\t}\n+\t} while (p);\n+\n+\t/*\n+\t * If we have both sources *and* destinations, see if\n+\t * we can match them up\n+\t */\n+\treturn (src && dst) ? find_identical_files(src, dst) : 0;\n+}\n+\n+/*\n+ * Note: the rest of the rename logic depends on this\n+ * phase also populating all the filespecs for any\n+ * entry that isn't matched up with an exact rename.\n+ */\n+static int free_file_table(void *ptr)\n+{\n+\tstruct file_similarity *p = ptr;\n+\tdo {\n+\t\tstruct file_similarity *entry = p;\n+\t\tp = p->next;\n+\n+\t\t/* Stupid special case, see note above! */\n+\t\tdiff_populate_filespec(entry->filespec, 0);\n+\t\tfree(entry);\n+\t} while (p);\n+\treturn 0;\n+}\n+\n+static unsigned int hash_filespec(struct diff_filespec *filespec)\n+{\n+\tunsigned int hash;\n+\tif (!filespec->sha1_valid) {\n+\t\tif (diff_populate_filespec(filespec, 0))\n+\t\t\treturn 0;\n+\t\thash_sha1_file(filespec->data, filespec->size, \"blob\", filespec->sha1);\n+\t}\n+\tmemcpy(&hash, filespec->sha1, sizeof(hash));\n+\treturn hash;\n+}\n+\n+static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec)\n+{\n+\tvoid **pos;\n+\tunsigned int hash;\n+\tstruct file_similarity *entry = xmalloc(sizeof(*entry));\n+\n+\tentry->src_dst = src_dst;\n+\tentry->index = index;\n+\tentry->filespec = filespec;\n+\tentry->next = NULL;\n+\n+\thash = hash_filespec(filespec);\n+\tpos = insert_hash(hash, entry, table);\n+\n+\t/* We already had an entry there? */\n+\tif (pos) {\n+\t\tentry->next = *pos;\n+\t\t*pos = entry;\n+\t}\n+}\n+\n /*\n  * Find exact renames first.\n  *\n  * The first round matches up the up-to-date entries,\n  * and then during the second round we try to match\n  * cache-dirty entries as well.\n- *\n- * Note: the rest of the rename logic depends on this\n- * phase also populating all the filespecs for any\n- * entry that isn't matched up with an exact rename,\n- * see \"is_exact_match()\".\n  */\n static int find_exact_renames(void)\n {\n-\tint rename_count = 0;\n-\tint contents_too;\n-\n-\tfor (contents_too = 0; contents_too < 2; contents_too++) {\n-\t\tint i;\n-\n-\t\tfor (i = 0; i < rename_dst_nr; i++) {\n-\t\t\tstruct diff_filespec *two = rename_dst[i].two;\n-\t\t\tint j;\n-\n-\t\t\tif (rename_dst[i].pair)\n-\t\t\t\tcontinue; /* dealt with an earlier round */\n-\t\t\tfor (j = 0; j < rename_src_nr; j++) {\n-\t\t\t\tint k;\n-\t\t\t\tstruct diff_filespec *one = rename_src[j].one;\n-\t\t\t\tif (!is_exact_match(one, two, contents_too))\n-\t\t\t\t\tcontinue;\n-\n-\t\t\t\t/* see if there is a basename match, too */\n-\t\t\t\tfor (k = j; k < rename_src_nr; k++) {\n-\t\t\t\t\tone = rename_src[k].one;\n-\t\t\t\t\tif (basename_same(one, two) &&\n-\t\t\t\t\t\tis_exact_match(one, two,\n-\t\t\t\t\t\t\tcontents_too)) {\n-\t\t\t\t\t\tj = k;\n-\t\t\t\t\t\tbreak;\n-\t\t\t\t\t}\n-\t\t\t\t}\n-\n-\t\t\t\trecord_rename_pair(i, j, (int)MAX_SCORE);\n-\t\t\t\trename_count++;\n-\t\t\t\tbreak; /* we are done with this entry */\n-\t\t\t}\n-\t\t}\n-\t}\n-\treturn rename_count;\n+\tint i;\n+\tstruct hash_table file_table;\n+\n+\tinit_hash(&file_table);\n+\tfor (i = 0; i < rename_src_nr; i++)\n+\t\tinsert_file_table(&file_table, -1, i, rename_src[i].one);\n+\n+\tfor (i = 0; i < rename_dst_nr; i++)\n+\t\tinsert_file_table(&file_table, 1, i, rename_dst[i].two);\n+\n+\t/* Find the renames */\n+\ti = for_each_hash(&file_table, find_same_files);\n+\n+\t/* .. and free the hash data structures */\n+\tfor_each_hash(&file_table, free_file_table);\n+\tfree_hash(&file_table);\n+\n+\treturn i;\n }\n \n void diffcore_rename(struct diff_options *options)\n@@ -474,16 +549,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\n \t\t\telse {\n-\t\t\t\tfor (j = 0; j < rename_dst_nr; j++) {\n-\t\t\t\t\tif (!rename_dst[j].pair)\n-\t\t\t\t\t\tcontinue;\n-\t\t\t\t\tif (strcmp(rename_dst[j].pair->\n-\t\t\t\t\t\t   one->path,\n-\t\t\t\t\t\t   p->one->path))\n-\t\t\t\t\t\tcontinue;\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t\tif (j < rename_dst_nr)\n+\t\t\t\tif (p->one->used)\n \t\t\t\t\t/* this path remains */\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\ndiff --git a/diffcore.h b/diffcore.h\nindex eb618b1..a58d345 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -40,6 +40,7 @@ struct diff_filespec {\n \tunsigned should_munmap : 1; /* data should be munmap()'ed */\n \tunsigned checked_attr : 1;\n \tunsigned is_binary : 1; /* data should be considered \"binary\" */\n+\tunsigned used : 1;\t/* this pathspec was used for copy/delete */\n };\n \n extern struct diff_filespec *alloc_filespec(const char *);\ndiff --git a/hash.c b/hash.c\nnew file mode 100644\nindex 0000000..7b492d4\n--- /dev/null\n+++ b/hash.c\n@@ -0,0 +1,110 @@\n+/*\n+ * Some generic hashing helpers.\n+ */\n+#include \"cache.h\"\n+#include \"hash.h\"\n+\n+/*\n+ * Look up a hash entry in the hash table. Return the pointer to\n+ * the existing entry, or the empty slot if none existed. The caller\n+ * can then look at the (*ptr) to see whether it existed or not.\n+ */\n+static struct hash_table_entry *lookup_hash_entry(unsigned int hash, struct hash_table *table)\n+{\n+\tunsigned int size = table->size, nr = hash % size;\n+\tstruct hash_table_entry *array = table->array;\n+\n+\twhile (array[nr].ptr) {\n+\t\tif (array[nr].hash == hash)\n+\t\t\tbreak;\n+\t\tnr++;\n+\t\tif (nr >= size)\n+\t\t\tnr = 0;\n+\t}\n+\treturn array + nr;\n+}\n+\n+\n+/*\n+ * Insert a new hash entry pointer into the table.\n+ *\n+ * If that hash entry already existed, return the pointer to\n+ * the existing entry (and the caller can create a list of the\n+ * pointers or do anything else). If it didn't exist, return\n+ * NULL (and the caller knows the pointer has been inserted).\n+ */\n+static void **insert_hash_entry(unsigned int hash, void *ptr, struct hash_table *table)\n+{\n+\tstruct hash_table_entry *entry = lookup_hash_entry(hash, table);\n+\n+\tif (!entry->ptr) {\n+\t\tentry->ptr = ptr;\n+\t\tentry->hash = hash;\n+\t\ttable->nr++;\n+\t\treturn NULL;\n+\t}\n+\treturn &entry->ptr;\n+}\n+\n+static void grow_hash_table(struct hash_table *table)\n+{\n+\tunsigned int i;\n+\tunsigned int old_size = table->size, new_size;\n+\tstruct hash_table_entry *old_array = table->array, *new_array;\n+\n+\tnew_size = alloc_nr(old_size);\n+\tnew_array = xcalloc(sizeof(struct hash_table_entry), new_size);\n+\ttable->size = new_size;\n+\ttable->array = new_array;\n+\ttable->nr = 0;\n+\tfor (i = 0; i < old_size; i++) {\n+\t\tunsigned int hash = old_array[i].hash;\n+\t\tvoid *ptr = old_array[i].ptr;\n+\t\tif (ptr)\n+\t\t\tinsert_hash_entry(hash, ptr, table);\n+\t}\n+\tfree(old_array);\n+}\n+\n+void *lookup_hash(unsigned int hash, struct hash_table *table)\n+{\n+\tif (!table->array)\n+\t\treturn NULL;\n+\treturn &lookup_hash_entry(hash, table)->ptr;\n+}\n+\n+void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)\n+{\n+\tunsigned int nr = table->nr;\n+\tif (nr >= table->size/2)\n+\t\tgrow_hash_table(table);\n+\treturn insert_hash_entry(hash, ptr, table);\n+}\n+\n+int for_each_hash(struct hash_table *table, int (*fn)(void *))\n+{\n+\tint sum = 0;\n+\tunsigned int i;\n+\tunsigned int size = table->size;\n+\tstruct hash_table_entry *array = table->array;\n+\n+\tfor (i = 0; i < size; i++) {\n+\t\tvoid *ptr = array->ptr;\n+\t\tarray++;\n+\t\tif (ptr) {\n+\t\t\tint val = fn(ptr);\n+\t\t\tif (val < 0)\n+\t\t\t\treturn val;\n+\t\t\tsum += val;\n+\t\t}\n+\t}\n+\treturn sum;\n+}\n+\n+void free_hash(struct hash_table *table)\n+{\n+\tfree(table->array);\n+\ttable->array = NULL;\n+\ttable->size = 0;\n+\ttable->nr = 0;\n+}\ndiff --git a/hash.h b/hash.h\nnew file mode 100644\nindex 0000000..5056c9a\n--- /dev/null\n+++ b/hash.h\n@@ -0,0 +1,43 @@\n+#ifndef HASH_H\n+#define HASH_H\n+\n+/*\n+ * These are some simple generic hash table helper functions.\n+ * Not necessarily suitable for all users, but good for things\n+ * where you want to just keep track of a list of things, and\n+ * have a good hash to use on them.\n+ *\n+ * It keeps the hash table at roughly 50-75% free, so the memory\n+ * cost of the hash table itself is roughly\n+ *\n+ *\t3 * 2*sizeof(void *) * nr_of_objects\n+ *\n+ * bytes. \n+ *\n+ * FIXME: on 64-bit architectures, we waste memory. It would be\n+ * good to have just 32-bit pointers, requiring a special allocator\n+ * for hashed entries or something.\n+ */\n+struct hash_table_entry {\n+\tunsigned int hash;\n+\tvoid *ptr;\n+};\n+\n+struct hash_table {\n+\tunsigned int size, nr;\n+\tstruct hash_table_entry *array;\n+};\n+\n+extern void *lookup_hash(unsigned int hash, struct hash_table *table);\n+extern void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table);\n+extern int for_each_hash(struct hash_table *table, int (*fn)(void *));\n+extern void free_hash(struct hash_table *table);\n+\n+static inline void init_hash(struct hash_table *table)\n+{\n+\ttable->size = 0;\n+\ttable->nr = 0;\n+\ttable->array = NULL;\n+}\n+\n+#endif\n"},{"id":"56793","messageId":"ee77f5c20710211731n2646ae11jd2fb2c0be12494ac@mail.gmail.com","threadId":"10407","inReplyTo":"alpine.LFD.0.999.0710211603200.10525@woody.linux-foundation.org","subject":"Re: [PATCH, take 1] Linear-time/space rename logic (exact renames only)","fromName":"David Symonds","fromEmail":"dsymonds@gmail.com","sentAt":"2007-10-22T00:31:03Z","receivedAt":"2007-10-22T00:31:03Z","isPatch":true,"sender":{"key":"dsymonds@gmail.com","avatar":"https://gravatar.com/avatar/b22f5051cbfc11836e36cf7a690e6cde4e225d835e13295ff98d15c7a9ee3c0f?d=mp&s=160"},"body":"On 22/10/2007, Linus Torvalds <torvalds@linux-foundation.org> wrote:\n>\n> diff --git a/Makefile b/Makefile\n> index 8db4dbe..17c31ba 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -291,7 +291,7 @@ LIB_H = \\\n>         run-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \\\n>         tree-walk.h log-tree.h dir.h path-list.h unpack-trees.h builtin.h \\\n>         utf8.h reflog-walk.h patch-ids.h attr.h decorate.h progress.h \\\n> -       mailmap.h remote.h\n> +       mailmap.h remote.h hash.o\n\nI assume that should be \"hash.h\", not \"hash.o\"?\n\n\nDave.\n"},{"id":"56813","messageId":"alpine.LFD.0.999.0710212241180.10525@woody.linux-foundation.org","threadId":"10407","inReplyTo":"ee77f5c20710211731n2646ae11jd2fb2c0be12494ac@mail.gmail.com","subject":"Re: [PATCH, take 1] Linear-time/space rename logic (exact renames only)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-22T05:41:29Z","receivedAt":"2007-10-22T05:41:29Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 22 Oct 2007, David Symonds wrote:\n> > @@ -291,7 +291,7 @@ LIB_H = \\\n> >         run-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \\\n> >         tree-walk.h log-tree.h dir.h path-list.h unpack-trees.h builtin.h \\\n> >         utf8.h reflog-walk.h patch-ids.h attr.h decorate.h progress.h \\\n> > -       mailmap.h remote.h\n> > +       mailmap.h remote.h hash.o\n> \n> I assume that should be \"hash.h\", not \"hash.o\"?\n\nOops.\n\nYes.\n\n\t\tLinus\n"},{"id":"56828","messageId":"20071022064723.GA2737@coredump.intra.peff.net","threadId":"10407","inReplyTo":"alpine.LFD.0.999.0710211603200.10525@woody.linux-foundation.org","subject":"Re: [PATCH, take 1] Linear-time/space rename logic (exact renames only)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-22T06:47:23Z","receivedAt":"2007-10-22T06:47:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Oct 21, 2007 at 04:59:03PM -0700, Linus Torvalds wrote:\n\n> What it does is to rather than iterate over all sources and destinations \n> and checking if they are identical (which is O(src*dst)), it hashes each \n> of the sources and destinations into a hash table, using the SHA1 hash of \n> the contents as the hash. That's O(n+m). It then walks the hash table \n> (which is also O(m+n) in size), and only pairs up files for comparison \n> that hashed to the same spot.\n> \n> Doing this for more than just the exact same contents would be basically \n> the same thing, except it starts hashing up fingerprints of the contents \n> and linking up file pairs that get linked up by those fingerprints. More \n> involved, but not impossible.\n\nHrm. For the inexact case, it seems like you should be able to do\nsomething like this:\n\n 1. put the content fingerprint hashes in a hash table\n 2. create a single src * dst table of scores\n 3. walk the hash table; for each bucket in which there are collisions,\n    find every pair in that bucket, and add to the similarity score in\n    the big score table\n 4. for each src in the similarity table, find the maximum dest\n\nStep 1 is clearly O(n+m). Step 2 allocates O(n*m) memory, but we only\nneed a single integer in each slot. The outer walk in step 3 is\nO(fingerprints), which is, O(content_size * (n+m)). The inner loop can\nactually be worst case O(n*m), but is more likely to be a handful of\npairs (assuming that for any fingerprint chunk, it is only going to\nexist in a few files; you would get worst case if you were comparing a\nbunch of files with identical contents). And step 4 is actually going to\nend up being O(n*m), since you have to find the best match for each.\n\nSo there is actually still O(n*m) behavior, but I wonder if we are\ntightening the O(n*m) loop enough that we will see improvement.\n\nHrm. I wonder if we could keep a \"best\" pointer for each src file, and\nwhen we update the score for a given src/dest pair, check for a new\nbest. That would add more to step 3, but make step 4 O(n).\n\nAnd of course the n*m memory is going to bottleneck. I think for 1000 *\n1000, it should be fine, but if you want to try 100,000 * 100,000, you\nare going to need tens of gigabytes. And it's going to be very sparse.\nSo perhaps a hash table with keys of src+dst mapped to scores. And then\nwe could sort the whole table afterwards, and just run through it\nlinearly, which helps step 4.\n\n>  - it looks ok, and I've tested it some, but this needs more people \n>    looking at it.\n\nOverall it looks like a sane approach. My comments are below.\n\n>  - in fact, the big optimization isn't the actual hash table, but the \n>    independent and much simpler \"diff_filespec->used\" optimization for a \n>    deleted filename that was used for a rename/copy.\n\nDo you have separate timings? The \"diff_filespec->used\" optimization\nappears to be cutting out an O(n*m) strcmp. If it is most of the\noptimization, I wonder if the complexity of the hash change is worth it\n(although I find the new code easier to read, so maybe it is worth it on\nthose grounds alone).\n\n> +struct file_similarity {\n> +\tint src_dst, index;\n\nIt took me a while to figure out all of the meanings of src_dst; maybe a\ncomment is in order?\n\n> +static int find_identical_files(struct file_similarity *src,\n> +\t\t\t\tstruct file_similarity *dst)\n\nYour function naming is a bit confusing. You have find_identical_files,\nfind_same_files, and find_exact_renames, all of which do the same thing,\nbut for different levels of input. Perhaps the names should reflect how\nthey are different?\n\n> +static int find_identical_files(struct file_similarity *src,\n> +\t\t\t\tstruct file_similarity *dst)\n> +{\n> +\tint renames = 0;\n> +\tdo {\n> +\t\tstruct diff_filespec *one = src->filespec;\n> +\t\tstruct file_similarity *p, *best;\n> +\t\tint i = 100;\n> +\n> +\t\tbest = NULL;\n> +\t\tfor (p = dst; p; p = p->next) {\n> +\t\t\tstruct diff_filespec *two = p->filespec;\n> +\n> +\t\t\t/* Already picked as a destination? */\n> +\t\t\tif (!p->src_dst)\n> +\t\t\t\tcontinue;\n> +\t\t\t/* False hash collission? */\n> +\t\t\tif (hashcmp(one->sha1, two->sha1))\n> +\t\t\t\tcontinue;\n> +\t\t\tbest = p;\n> +\t\t\tif (basename_same(one, two))\n> +\t\t\t\tbreak;\n> +\n> +\t\t\t/* Too many identical alternatives? Pick one */\n> +\t\t\tif (!--i)\n> +\t\t\t\tbreak;\n> +\t\t}\n> +\t\tif (best) {\n> +\t\t\tbest->src_dst = 0;\n> +\t\t\trecord_rename_pair(best->index, src->index, MAX_SCORE);\n> +\t\t\trenames++;\n> +\t\t}\n> +\t} while ((src = src->next) != NULL);\n> +\treturn renames;\n> +}\n\nThe \"too many identical alternatives\" sanity check is interesting. It\ncan produce suboptimal results if, e.g., the 101st entry has the same\nbasename. I suppose it is necessary to prevent a worst case \"oops, all\nof these files are identical\" O(n*m) behavior. But generally I would\nfavor \"always correct, pathological cases slow\" to \"always fast,\npathological cases incorrect\". But maybe the basename heuristic isn't\nworth considering \"correct\" in this case (and honestly, I doubt anyone\nwill hit the 100 limit anyway).\n\n> +/*\n> + * Note: the rest of the rename logic depends on this\n> + * phase also populating all the filespecs for any\n> + * entry that isn't matched up with an exact rename.\n> + */\n> +static int free_file_table(void *ptr)\n> +{\n> +\tstruct file_similarity *p = ptr;\n> +\tdo {\n> +\t\tstruct file_similarity *entry = p;\n> +\t\tp = p->next;\n> +\n> +\t\t/* Stupid special case, see note above! */\n> +\t\tdiff_populate_filespec(entry->filespec, 0);\n> +\t\tfree(entry);\n> +\t} while (p);\n> +\treturn 0;\n> +}\n\ndiff_populate_filespec knows whether or not it needs to do any work. I\nwonder if those parts of the rename process that need it should just\ncall it unconditionally. It seems like a fragile dependency. Besides\nwhich...\n\n> +static unsigned int hash_filespec(struct diff_filespec *filespec)\n> +{\n> +\tunsigned int hash;\n> +\tif (!filespec->sha1_valid) {\n> +\t\tif (diff_populate_filespec(filespec, 0))\n> +\t\t\treturn 0;\n> +\t\thash_sha1_file(filespec->data, filespec->size, \"blob\", filespec->sha1);\n> +\t}\n> +\tmemcpy(&hash, filespec->sha1, sizeof(hash));\n> +\treturn hash;\n> +}\n\n...if everything has been through this hash function, why do we need to\npopulate again upon freeing?\n\n> +static struct hash_table_entry *lookup_hash_entry(unsigned int hash, struct hash_table *table)\n> +{\n> +\tunsigned int size = table->size, nr = hash % size;\n> +\tstruct hash_table_entry *array = table->array;\n> +\n> +\twhile (array[nr].ptr) {\n> +\t\tif (array[nr].hash == hash)\n> +\t\t\tbreak;\n> +\t\tnr++;\n> +\t\tif (nr >= size)\n> +\t\t\tnr = 0;\n> +\t}\n> +\treturn array + nr;\n> +}\n\nRather than having buckets where collisions extend in a list within the\nbucket, it looks like you are just overflowing into the next bucket.\nIt seems like you could end up with pretty bad \"runs\" of full buckets.\nE.g., bucket 1 has a collision, so it bleeds into bucket 2.  Now when we\nplace something in bucket 2, it has to skip past bucket 1's overflow.\nAnd a collision in bucket 2 means we have to skip the overflow for\nbuckets 1 _and_ 2. And so on, until we can resync by finding enough free\nbuckets to accept all of our collisions. So it depends on keeping a lot\nof holes in the hash structure, which I see that you do, but I wonder\nwhat the optimal value is.\n\nI assume you chose this method to reduce memory fragmentation, which\nmakes sense. And maybe there is a simple answer that \"50-75% free gives\ngood results over evenly distributed hashes.\" Though perhaps we should\nalso consider clustered hashes (especially if we want to put the\nfingerprint hashes directly in here).\n\n> +/*\n> + * Insert a new hash entry pointer into the table.\n> + *\n> + * If that hash entry already existed, return the pointer to\n> + * the existing entry (and the caller can create a list of the\n> + * pointers or do anything else). If it didn't exist, return\n> + * NULL (and the caller knows the pointer has been inserted).\n> + */\n> +static void **insert_hash_entry(unsigned int hash, void *ptr, struct hash_table *table)\n\nThis calling convention seems a bit clunky. Since all callers have to\ncheck for hash collision anyway, why not just unconditionally return the\npointer to the data ptr (which will itself be NULL if this is the first\nentry)? Then you can drop the conditional, and:\n\n  pos = insert_hash(hash, entry, table);\n  if (pos) {\n    entry->next = *pos;\n    *pos = entry;\n  }\n\ncan simply become:\n\n  pos = insert_hash(hash, table);\n  entry->next = *pos;\n  *pos = entry;\n\n> +void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)\n> +{\n> +\tunsigned int nr = table->nr;\n> +\tif (nr >= table->size/2)\n> +\t\tgrow_hash_table(table);\n> +\treturn insert_hash_entry(hash, ptr, table);\n> +}\n\nStyle nitpick: the local \"nr\" is rather pointless.\n\n-Peff\n"},{"id":"56831","messageId":"20071022070750.GM1179MdfPADPa@greensroom.kotnet.org","threadId":"10407","inReplyTo":"alpine.LFD.0.999.0710211603200.10525@woody.linux-foundation.org","subject":"Re: [PATCH, take 1] Linear-time/space rename logic (exact renames only)","fromName":"Sven Verdoolaege","fromEmail":"skimo@kotnet.org","sentAt":"2007-10-22T07:07:50Z","receivedAt":"2007-10-22T07:07:50Z","isPatch":true,"sender":{"key":"skimo@kotnet.org","avatar":null},"body":"On Sun, Oct 21, 2007 at 04:59:03PM -0700, Linus Torvalds wrote:\n> +static int find_same_files(void *ptr)\n> +{\n> +\tstruct file_similarity *p = ptr;\n> +\tstruct file_similarity *src = NULL, *dst = NULL;\n> +\n> +\t/* Split the hash list up into sources and destinations */\n> +\tdo {\n> +\t\tstruct file_similarity *entry = p;\n> +\t\tp = p->next;\n> +\t\tif (entry->src_dst < 0) {\n> +\t\t\tentry->next = src;\n> +\t\t\tsrc = entry;\n> +\t\t} else {\n> +\t\t\tentry->next = dst;\n> +\t\t\tdst = entry;\n> +\t\t}\n> +\t} while (p);\n\nAren't you truncating the ptr list after the first entry here?\n(While you still need the whole list in free_file_table.)\n\nskimo\n"},{"id":"56833","messageId":"20071022072153.GA6205@coredump.intra.peff.net","threadId":"10407","inReplyTo":"20071022070750.GM1179MdfPADPa@greensroom.kotnet.org","subject":"Re: [PATCH, take 1] Linear-time/space rename logic (exact renames only)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-22T07:21:53Z","receivedAt":"2007-10-22T07:21:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 22, 2007 at 09:07:50AM +0200, Sven Verdoolaege wrote:\n\n> Aren't you truncating the ptr list after the first entry here?\n> (While you still need the whole list in free_file_table.)\n\nYes, good eyes. And because we actually reverse the list, it's not as\nsimple as just sticking the two broken up pieces together again; the\noriginal head must end up as the head of the list after they are glued\ntogether again, but it is actually the tail of one of the lists.\n\n-Peff\n"},{"id":"56893","messageId":"alpine.LFD.0.999.0710220932150.10525@woody.linux-foundation.org","threadId":"10407","inReplyTo":"20071022070750.GM1179MdfPADPa@greensroom.kotnet.org","subject":"Re: [PATCH, take 1] Linear-time/space rename logic (exact renames only)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-22T16:33:06Z","receivedAt":"2007-10-22T16:33:06Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 22 Oct 2007, Sven Verdoolaege wrote:\n> \n> Aren't you truncating the ptr list after the first entry here?\n> (While you still need the whole list in free_file_table.)\n\nYes. I didn't have that bug in the first version (I didn't do a separate \n\"free_file_table()\" at all - I just free'd the src/dst pointer lists at \nthe end of that function). But I wanted to \"clean up\" the thing. Duh.\n\n\t\tLinus\n"},{"id":"56898","messageId":"alpine.LFD.0.999.0710221009580.10525@woody.linux-foundation.org","threadId":"10407","inReplyTo":"alpine.LFD.0.999.0710220932150.10525@woody.linux-foundation.org","subject":"[PATCH, take 2] Linear-time/space rename logic (exact renames only)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-22T17:29:16Z","receivedAt":"2007-10-22T17:29:16Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOk, as some people notices, there were a few bugs in the previous patch. I \ndidn't free the hashes correctly (stupid) and the Makefile had \"hash.o\" \ninstead of \"hash.h\".\n\nBut more importantly, my \"testing\" had been totally broken, because I had \nforgotten to actually move the rename limiting code to after the exact \nrename phase, so when I tested the 100,000 file rename, almost none of the \nnew code triggered, so my performance testing was totally bogus.\n\nWhen fixing that, I noticed that while my new exact rename detection was \nessentially instantaneous, there were some O(n*m) effects in the generic \ndiff code from the extremely stupid way we handled the \"was it a copy or a \nrename\" issue.\n\nTo fix that, I just made the \"was the path used by a rename\" be a counter \ninstead of a single \"it was used\"\n\nWith that in place, I could actually time the rename detection of 100,000 \nfiles in my big-rename test repository. This is what it looks like when \nyou rename a hundred thousand files:\n\n\t[torvalds@woody big-rename]$ time ~/git/git show -C | wc -l\n\t400006\n\n\treal    0m2.675s\n\tuser    0m2.148s\n\tsys     0m0.540s\n\n(each renamed file is 4 lines: they looks like\n\n\tdiff --git a/really-big-dir/file-1-1-1-1-1 b/moved-big-dir/file-1-1-1-1-1\n\tsimilarity index 100%\n\trename from really-big-dir/file-1-1-1-1-1\n\trename to moved-big-dir/file-1-1-1-1-1\n\nand the extra six lines is from a one-liner commit message and all the \ncommit information and spacing).\n\nSo two seconds to do that exact rename detection.\n\nNow, I can't really compare it to the \"before\" stage, because that is just \nso horrible. The rename detection limit triggers, so you never even get \nany renames, but if I were to move the limit check later (like I do in \nthis patch) without my other fixes, it would take hours. Trying to do ten \nbillion (100k x 100k) SHA1 and pathname compares simply isn't going to \nwork.\n\nBut I *can* compare it to the old code *with* the rename limiting, which \nstill wastes all the time on the whole \"copy usage\" crap. So here are the \nnumbers on that repo without the patch:\n\n\t[torvalds@woody big-rename]$ time git show -C | wc -l\n\t1400006\n\t\n\treal    0m12.383s\n\tuser    0m12.365s\n\tsys     0m0.160s\n\nThat's right: we used to take 12 seconds and not even do renames (now you \nsee fourteen lines per file moved: seven lines each for the delete and the \ncreate of a one-liner file, and the same extra six lines of commit \ninformation).\n\nSo it not only makes the rename detection possible in the first place, it \nremoves some stupid code that made it take a long time even when it \nfailed!\n\nNow, I'd still be careful with this patch, and I'd really like people to \ndouble-check all my logic, but I think it's worthy of some 'pu' love.\n\n\t\tLinus\n---\n\n Makefile          |    4 +-\n diff.c            |   24 +----\n diffcore-rename.c |  275 ++++++++++++++++++++++++++++++----------------------\n diffcore.h        |    2 +-\n hash.c            |  110 +++++++++++++++++++++\n hash.h            |   43 ++++++++\n 6 files changed, 321 insertions(+), 137 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 8db4dbe..b1ca186 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -291,7 +291,7 @@ LIB_H = \\\n \trun-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \\\n \ttree-walk.h log-tree.h dir.h path-list.h unpack-trees.h builtin.h \\\n \tutf8.h reflog-walk.h patch-ids.h attr.h decorate.h progress.h \\\n-\tmailmap.h remote.h\n+\tmailmap.h remote.h hash.h\n \n DIFF_OBJS = \\\n \tdiff.o diff-lib.o diffcore-break.o diffcore-order.o \\\n@@ -301,7 +301,7 @@ DIFF_OBJS = \\\n LIB_OBJS = \\\n \tblob.o commit.o connect.o csum-file.o cache-tree.o base85.o \\\n \tdate.o diff-delta.o entry.o exec_cmd.o ident.o \\\n-\tinterpolate.o \\\n+\tinterpolate.o hash.o \\\n \tlockfile.o \\\n \tpatch-ids.o \\\n \tobject.o pack-check.o pack-write.o patch-delta.o path.o pkt-line.o \\\ndiff --git a/diff.c b/diff.c\nindex 6648e01..e892030 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2586,9 +2586,9 @@ void diff_debug_filepair(const struct diff_filepair *p, int i)\n {\n \tdiff_debug_filespec(p->one, i, \"one\");\n \tdiff_debug_filespec(p->two, i, \"two\");\n-\tfprintf(stderr, \"score %d, status %c stays %d broken %d\\n\",\n+\tfprintf(stderr, \"score %d, status %c rename_used %d broken %d\\n\",\n \t\tp->score, p->status ? p->status : '?',\n-\t\tp->source_stays, p->broken_pair);\n+\t\tp->rename_used, p->broken_pair);\n }\n \n void diff_debug_queue(const char *msg, struct diff_queue_struct *q)\n@@ -2606,8 +2606,8 @@ void diff_debug_queue(const char *msg, struct diff_queue_struct *q)\n \n static void diff_resolve_rename_copy(void)\n {\n-\tint i, j;\n-\tstruct diff_filepair *p, *pp;\n+\tint i;\n+\tstruct diff_filepair *p;\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \n \tdiff_debug_queue(\"resolve-rename-copy\", q);\n@@ -2629,27 +2629,15 @@ static void diff_resolve_rename_copy(void)\n \t\t * either in-place edit or rename/copy edit.\n \t\t */\n \t\telse if (DIFF_PAIR_RENAME(p)) {\n-\t\t\tif (p->source_stays) {\n-\t\t\t\tp->status = DIFF_STATUS_COPIED;\n-\t\t\t\tcontinue;\n-\t\t\t}\n \t\t\t/* See if there is some other filepair that\n \t\t\t * copies from the same source as us.  If so\n \t\t\t * we are a copy.  Otherwise we are either a\n \t\t\t * copy if the path stays, or a rename if it\n \t\t\t * does not, but we already handled \"stays\" case.\n \t\t\t */\n-\t\t\tfor (j = i + 1; j < q->nr; j++) {\n-\t\t\t\tpp = q->queue[j];\n-\t\t\t\tif (strcmp(pp->one->path, p->one->path))\n-\t\t\t\t\tcontinue; /* not us */\n-\t\t\t\tif (!DIFF_PAIR_RENAME(pp))\n-\t\t\t\t\tcontinue; /* not a rename/copy */\n-\t\t\t\t/* pp is a rename/copy from the same source */\n+\t\t\tif (--p->one->rename_used > 0)\n \t\t\t\tp->status = DIFF_STATUS_COPIED;\n-\t\t\t\tbreak;\n-\t\t\t}\n-\t\t\tif (!p->status)\n+\t\t\telse\n \t\t\t\tp->status = DIFF_STATUS_RENAMED;\n \t\t}\n \t\telse if (hashcmp(p->one->sha1, p->two->sha1) ||\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 2077a9b..cc105db 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -4,6 +4,7 @@\n #include \"cache.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n+#include \"hash.h\"\n \n /* Table of rename/copy destinations */\n \n@@ -55,12 +56,10 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n static struct diff_rename_src {\n \tstruct diff_filespec *one;\n \tunsigned short score; /* to remember the break score */\n-\tunsigned src_path_left : 1;\n } *rename_src;\n static int rename_src_nr, rename_src_alloc;\n \n static struct diff_rename_src *register_rename_src(struct diff_filespec *one,\n-\t\t\t\t\t\t   int src_path_left,\n \t\t\t\t\t\t   unsigned short score)\n {\n \tint first, last;\n@@ -92,33 +91,9 @@ static struct diff_rename_src *register_rename_src(struct diff_filespec *one,\n \t\t\t(rename_src_nr - first - 1) * sizeof(*rename_src));\n \trename_src[first].one = one;\n \trename_src[first].score = score;\n-\trename_src[first].src_path_left = src_path_left;\n \treturn &(rename_src[first]);\n }\n \n-static int is_exact_match(struct diff_filespec *src,\n-\t\t\t  struct diff_filespec *dst,\n-\t\t\t  int contents_too)\n-{\n-\tif (src->sha1_valid && dst->sha1_valid &&\n-\t    !hashcmp(src->sha1, dst->sha1))\n-\t\treturn 1;\n-\tif (!contents_too)\n-\t\treturn 0;\n-\tif (diff_populate_filespec(src, 1) || diff_populate_filespec(dst, 1))\n-\t\treturn 0;\n-\tif (src->size != dst->size)\n-\t\treturn 0;\n-\tif (src->sha1_valid && dst->sha1_valid)\n-\t    return !hashcmp(src->sha1, dst->sha1);\n-\tif (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0))\n-\t\treturn 0;\n-\tif (src->size == dst->size &&\n-\t    !memcmp(src->data, dst->data, src->size))\n-\t\treturn 1;\n-\treturn 0;\n-}\n-\n static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n {\n \tint src_len = strlen(src->path), dst_len = strlen(dst->path);\n@@ -216,6 +191,7 @@ static void record_rename_pair(int dst_index, int src_index, int score)\n \t\tdie(\"internal error: dst already matched.\");\n \n \tsrc = rename_src[src_index].one;\n+\tsrc->rename_used++;\n \tone = alloc_filespec(src->path);\n \tfill_filespec(one, src->sha1, src->mode);\n \n@@ -229,7 +205,6 @@ static void record_rename_pair(int dst_index, int src_index, int score)\n \t\tdp->score = rename_src[src_index].score;\n \telse\n \t\tdp->score = score;\n-\tdp->source_stays = rename_src[src_index].src_path_left;\n \trename_dst[dst_index].pair = dp;\n }\n \n@@ -247,19 +222,127 @@ static int score_compare(const void *a_, const void *b_)\n \treturn b->score - a->score;\n }\n \n-static int compute_stays(struct diff_queue_struct *q,\n-\t\t\t struct diff_filespec *one)\n+struct file_similarity {\n+\tint src_dst, index;\n+\tstruct diff_filespec *filespec;\n+\tstruct file_similarity *next;\n+};\n+\n+static int find_identical_files(struct file_similarity *src,\n+\t\t\t\tstruct file_similarity *dst)\n {\n-\tint i;\n-\tfor (i = 0; i < q->nr; i++) {\n-\t\tstruct diff_filepair *p = q->queue[i];\n-\t\tif (strcmp(one->path, p->two->path))\n-\t\t\tcontinue;\n-\t\tif (DIFF_PAIR_RENAME(p)) {\n-\t\t\treturn 0; /* something else is renamed into this */\n+\tint renames = 0;\n+\tdo {\n+\t\tstruct diff_filespec *one = src->filespec;\n+\t\tstruct file_similarity *p, *best;\n+\t\tint i = 100;\n+\n+\t\tbest = NULL;\n+\t\tfor (p = dst; p; p = p->next) {\n+\t\t\tstruct diff_filespec *two = p->filespec;\n+\n+\t\t\t/* Already picked as a destination? */\n+\t\t\tif (!p->src_dst)\n+\t\t\t\tcontinue;\n+\t\t\t/* False hash collission? */\n+\t\t\tif (hashcmp(one->sha1, two->sha1))\n+\t\t\t\tcontinue;\n+\t\t\tbest = p;\n+\t\t\tif (basename_same(one, two))\n+\t\t\t\tbreak;\n+\n+\t\t\t/* Too many identical alternatives? Pick one */\n+\t\t\tif (!--i)\n+\t\t\t\tbreak;\n \t\t}\n+\t\tif (best) {\n+\t\t\tbest->src_dst = 0;\n+\t\t\trecord_rename_pair(best->index, src->index, MAX_SCORE);\n+\t\t\trenames++;\n+\t\t}\n+\t} while ((src = src->next) != NULL);\n+\treturn renames;\n+}\n+\n+/*\n+ * Note: the rest of the rename logic depends on this\n+ * phase also populating all the filespecs for any\n+ * entry that isn't matched up with an exact rename.\n+ */\n+static void free_similarity_list(struct file_similarity *p)\n+{\n+\twhile (p) {\n+\t\tstruct file_similarity *entry = p;\n+\t\tp = p->next;\n+\n+\t\t/* Stupid special case, see note above! */\n+\t\tdiff_populate_filespec(entry->filespec, 0);\n+\t\tfree(entry);\n+\t}\n+}\n+\n+static int find_same_files(void *ptr)\n+{\n+\tint ret;\n+\tstruct file_similarity *p = ptr;\n+\tstruct file_similarity *src = NULL, *dst = NULL;\n+\n+\t/* Split the hash list up into sources and destinations */\n+\tdo {\n+\t\tstruct file_similarity *entry = p;\n+\t\tp = p->next;\n+\t\tif (entry->src_dst < 0) {\n+\t\t\tentry->next = src;\n+\t\t\tsrc = entry;\n+\t\t} else {\n+\t\t\tentry->next = dst;\n+\t\t\tdst = entry;\n+\t\t}\n+\t} while (p);\n+\n+\t/*\n+\t * If we have both sources *and* destinations, see if\n+\t * we can match them up\n+\t */\n+\tret = (src && dst) ? find_identical_files(src, dst) : 0;\n+\n+\t/* Free the hashes and return the number of renames found */\n+\tfree_similarity_list(src);\n+\tfree_similarity_list(dst);\n+\treturn ret;\n+}\n+\n+static unsigned int hash_filespec(struct diff_filespec *filespec)\n+{\n+\tunsigned int hash;\n+\tif (!filespec->sha1_valid) {\n+\t\tif (diff_populate_filespec(filespec, 0))\n+\t\t\treturn 0;\n+\t\thash_sha1_file(filespec->data, filespec->size, \"blob\", filespec->sha1);\n+\t}\n+\tmemcpy(&hash, filespec->sha1, sizeof(hash));\n+\treturn hash;\n+}\n+\n+static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec)\n+{\n+\tvoid **pos;\n+\tunsigned int hash;\n+\tstruct file_similarity *entry = xmalloc(sizeof(*entry));\n+\n+\tentry->src_dst = src_dst;\n+\tentry->index = index;\n+\tentry->filespec = filespec;\n+\tentry->next = NULL;\n+\n+\thash = hash_filespec(filespec);\n+\tpos = insert_hash(hash, entry, table);\n+\n+\t/* We already had an entry there? */\n+\tif (pos) {\n+\t\tentry->next = *pos;\n+\t\t*pos = entry;\n \t}\n-\treturn 1;\n }\n \n /*\n@@ -268,50 +351,26 @@ static int compute_stays(struct diff_queue_struct *q,\n  * The first round matches up the up-to-date entries,\n  * and then during the second round we try to match\n  * cache-dirty entries as well.\n- *\n- * Note: the rest of the rename logic depends on this\n- * phase also populating all the filespecs for any\n- * entry that isn't matched up with an exact rename,\n- * see \"is_exact_match()\".\n  */\n static int find_exact_renames(void)\n {\n-\tint rename_count = 0;\n-\tint contents_too;\n-\n-\tfor (contents_too = 0; contents_too < 2; contents_too++) {\n-\t\tint i;\n-\n-\t\tfor (i = 0; i < rename_dst_nr; i++) {\n-\t\t\tstruct diff_filespec *two = rename_dst[i].two;\n-\t\t\tint j;\n-\n-\t\t\tif (rename_dst[i].pair)\n-\t\t\t\tcontinue; /* dealt with an earlier round */\n-\t\t\tfor (j = 0; j < rename_src_nr; j++) {\n-\t\t\t\tint k;\n-\t\t\t\tstruct diff_filespec *one = rename_src[j].one;\n-\t\t\t\tif (!is_exact_match(one, two, contents_too))\n-\t\t\t\t\tcontinue;\n-\n-\t\t\t\t/* see if there is a basename match, too */\n-\t\t\t\tfor (k = j; k < rename_src_nr; k++) {\n-\t\t\t\t\tone = rename_src[k].one;\n-\t\t\t\t\tif (basename_same(one, two) &&\n-\t\t\t\t\t\tis_exact_match(one, two,\n-\t\t\t\t\t\t\tcontents_too)) {\n-\t\t\t\t\t\tj = k;\n-\t\t\t\t\t\tbreak;\n-\t\t\t\t\t}\n-\t\t\t\t}\n-\n-\t\t\t\trecord_rename_pair(i, j, (int)MAX_SCORE);\n-\t\t\t\trename_count++;\n-\t\t\t\tbreak; /* we are done with this entry */\n-\t\t\t}\n-\t\t}\n-\t}\n-\treturn rename_count;\n+\tint i;\n+\tstruct hash_table file_table;\n+\n+\tinit_hash(&file_table);\n+\tfor (i = 0; i < rename_src_nr; i++)\n+\t\tinsert_file_table(&file_table, -1, i, rename_src[i].one);\n+\n+\tfor (i = 0; i < rename_dst_nr; i++)\n+\t\tinsert_file_table(&file_table, 1, i, rename_dst[i].two);\n+\n+\t/* Find the renames */\n+\ti = for_each_hash(&file_table, find_same_files);\n+\n+\t/* .. and free the hash data structure */\n+\tfree_hash(&file_table);\n+\n+\treturn i;\n }\n \n void diffcore_rename(struct diff_options *options)\n@@ -340,20 +399,36 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\tlocate_rename_dst(p->two, 1);\n \t\t}\n \t\telse if (!DIFF_FILE_VALID(p->two)) {\n-\t\t\t/* If the source is a broken \"delete\", and\n+\t\t\t/*\n+\t\t\t * If the source is a broken \"delete\", and\n \t\t\t * they did not really want to get broken,\n \t\t\t * that means the source actually stays.\n+\t\t\t * So we increment the \"rename_used\" score\n+\t\t\t * by one, to indicate ourselves as a user\n \t\t\t */\n-\t\t\tint stays = (p->broken_pair && !p->score);\n-\t\t\tregister_rename_src(p->one, stays, p->score);\n+\t\t\tif (p->broken_pair && !p->score)\n+\t\t\t\tp->one->rename_used++;\n+\t\t\tregister_rename_src(p->one, p->score);\n+\t\t}\n+\t\telse if (detect_rename == DIFF_DETECT_COPY) {\n+\t\t\t/*\n+\t\t\t * Increment the \"rename_used\" score by\n+\t\t\t * one, to indicate ourselves as a user.\n+\t\t\t */\n+\t\t\tp->one->rename_used++;\n+\t\t\tregister_rename_src(p->one, p->score);\n \t\t}\n-\t\telse if (detect_rename == DIFF_DETECT_COPY)\n-\t\t\tregister_rename_src(p->one, 1, p->score);\n \t}\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n \t\tgoto cleanup; /* nothing to do */\n \n \t/*\n+\t * We really want to cull the candidates list early\n+\t * with cheap tests in order to avoid doing deltas.\n+\t */\n+\trename_count = find_exact_renames();\n+\n+\t/*\n \t * This basically does a test for the rename matrix not\n \t * growing larger than a \"rename_limit\" square matrix, ie:\n \t *\n@@ -369,12 +444,6 @@ void diffcore_rename(struct diff_options *options)\n \tif (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)\n \t\tgoto cleanup;\n \n-\t/*\n-\t * We really want to cull the candidates list early\n-\t * with cheap tests in order to avoid doing deltas.\n-\t */\n-\trename_count = find_exact_renames();\n-\n \t/* Have we run out the created file pool?  If so we can avoid\n \t * doing the delta matrix altogether.\n \t */\n@@ -474,16 +543,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\n \t\t\telse {\n-\t\t\t\tfor (j = 0; j < rename_dst_nr; j++) {\n-\t\t\t\t\tif (!rename_dst[j].pair)\n-\t\t\t\t\t\tcontinue;\n-\t\t\t\t\tif (strcmp(rename_dst[j].pair->\n-\t\t\t\t\t\t   one->path,\n-\t\t\t\t\t\t   p->one->path))\n-\t\t\t\t\t\tcontinue;\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t\tif (j < rename_dst_nr)\n+\t\t\t\tif (p->one->rename_used)\n \t\t\t\t\t/* this path remains */\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\n@@ -509,23 +569,6 @@ void diffcore_rename(struct diff_options *options)\n \t*q = outq;\n \tdiff_debug_queue(\"done collapsing\", q);\n \n-\t/* We need to see which rename source really stays here;\n-\t * earlier we only checked if the path is left in the result,\n-\t * but even if a path remains in the result, if that is coming\n-\t * from copying something else on top of it, then the original\n-\t * source is lost and does not stay.\n-\t */\n-\tfor (i = 0; i < q->nr; i++) {\n-\t\tstruct diff_filepair *p = q->queue[i];\n-\t\tif (DIFF_PAIR_RENAME(p) && p->source_stays) {\n-\t\t\t/* If one appears as the target of a rename-copy,\n-\t\t\t * then mark p->source_stays = 0; otherwise\n-\t\t\t * leave it as is.\n-\t\t\t */\n-\t\t\tp->source_stays = compute_stays(q, p->one);\n-\t\t}\n-\t}\n-\n \tfor (i = 0; i < rename_dst_nr; i++) {\n \t\tdiff_free_filespec_data(rename_dst[i].two);\n \t\tfree(rename_dst[i].two);\ndiff --git a/diffcore.h b/diffcore.h\nindex eb618b1..ceda932 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -30,6 +30,7 @@ struct diff_filespec {\n \tconst char *funcname_pattern_ident;\n \tunsigned long size;\n \tint xfrm_flags;\t\t /* for use by the xfrm */\n+\tint rename_used;         /* Count of rename users */\n \tunsigned short mode;\t /* file mode */\n \tunsigned sha1_valid : 1; /* if true, use sha1 and trust mode;\n \t\t\t\t  * if false, use the name and read from\n@@ -56,7 +57,6 @@ struct diff_filepair {\n \tstruct diff_filespec *two;\n \tunsigned short int score;\n \tchar status; /* M C R N D U (see Documentation/diff-format.txt) */\n-\tunsigned source_stays : 1; /* all of R/C are copies */\n \tunsigned broken_pair : 1;\n \tunsigned renamed_pair : 1;\n \tunsigned is_unmerged : 1;\ndiff --git a/hash.c b/hash.c\nnew file mode 100644\nindex 0000000..7b492d4\n--- /dev/null\n+++ b/hash.c\n@@ -0,0 +1,110 @@\n+/*\n+ * Some generic hashing helpers.\n+ */\n+#include \"cache.h\"\n+#include \"hash.h\"\n+\n+/*\n+ * Look up a hash entry in the hash table. Return the pointer to\n+ * the existing entry, or the empty slot if none existed. The caller\n+ * can then look at the (*ptr) to see whether it existed or not.\n+ */\n+static struct hash_table_entry *lookup_hash_entry(unsigned int hash, struct hash_table *table)\n+{\n+\tunsigned int size = table->size, nr = hash % size;\n+\tstruct hash_table_entry *array = table->array;\n+\n+\twhile (array[nr].ptr) {\n+\t\tif (array[nr].hash == hash)\n+\t\t\tbreak;\n+\t\tnr++;\n+\t\tif (nr >= size)\n+\t\t\tnr = 0;\n+\t}\n+\treturn array + nr;\n+}\n+\n+\n+/*\n+ * Insert a new hash entry pointer into the table.\n+ *\n+ * If that hash entry already existed, return the pointer to\n+ * the existing entry (and the caller can create a list of the\n+ * pointers or do anything else). If it didn't exist, return\n+ * NULL (and the caller knows the pointer has been inserted).\n+ */\n+static void **insert_hash_entry(unsigned int hash, void *ptr, struct hash_table *table)\n+{\n+\tstruct hash_table_entry *entry = lookup_hash_entry(hash, table);\n+\n+\tif (!entry->ptr) {\n+\t\tentry->ptr = ptr;\n+\t\tentry->hash = hash;\n+\t\ttable->nr++;\n+\t\treturn NULL;\n+\t}\n+\treturn &entry->ptr;\n+}\n+\n+static void grow_hash_table(struct hash_table *table)\n+{\n+\tunsigned int i;\n+\tunsigned int old_size = table->size, new_size;\n+\tstruct hash_table_entry *old_array = table->array, *new_array;\n+\n+\tnew_size = alloc_nr(old_size);\n+\tnew_array = xcalloc(sizeof(struct hash_table_entry), new_size);\n+\ttable->size = new_size;\n+\ttable->array = new_array;\n+\ttable->nr = 0;\n+\tfor (i = 0; i < old_size; i++) {\n+\t\tunsigned int hash = old_array[i].hash;\n+\t\tvoid *ptr = old_array[i].ptr;\n+\t\tif (ptr)\n+\t\t\tinsert_hash_entry(hash, ptr, table);\n+\t}\n+\tfree(old_array);\n+}\n+\n+void *lookup_hash(unsigned int hash, struct hash_table *table)\n+{\n+\tif (!table->array)\n+\t\treturn NULL;\n+\treturn &lookup_hash_entry(hash, table)->ptr;\n+}\n+\n+void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)\n+{\n+\tunsigned int nr = table->nr;\n+\tif (nr >= table->size/2)\n+\t\tgrow_hash_table(table);\n+\treturn insert_hash_entry(hash, ptr, table);\n+}\n+\n+int for_each_hash(struct hash_table *table, int (*fn)(void *))\n+{\n+\tint sum = 0;\n+\tunsigned int i;\n+\tunsigned int size = table->size;\n+\tstruct hash_table_entry *array = table->array;\n+\n+\tfor (i = 0; i < size; i++) {\n+\t\tvoid *ptr = array->ptr;\n+\t\tarray++;\n+\t\tif (ptr) {\n+\t\t\tint val = fn(ptr);\n+\t\t\tif (val < 0)\n+\t\t\t\treturn val;\n+\t\t\tsum += val;\n+\t\t}\n+\t}\n+\treturn sum;\n+}\n+\n+void free_hash(struct hash_table *table)\n+{\n+\tfree(table->array);\n+\ttable->array = NULL;\n+\ttable->size = 0;\n+\ttable->nr = 0;\n+}\ndiff --git a/hash.h b/hash.h\nnew file mode 100644\nindex 0000000..5056c9a\n--- /dev/null\n+++ b/hash.h\n@@ -0,0 +1,43 @@\n+#ifndef HASH_H\n+#define HASH_H\n+\n+/*\n+ * These are some simple generic hash table helper functions.\n+ * Not necessarily suitable for all users, but good for things\n+ * where you want to just keep track of a list of things, and\n+ * have a good hash to use on them.\n+ *\n+ * It keeps the hash table at roughly 50-75% free, so the memory\n+ * cost of the hash table itself is roughly\n+ *\n+ *\t3 * 2*sizeof(void *) * nr_of_objects\n+ *\n+ * bytes. \n+ *\n+ * FIXME: on 64-bit architectures, we waste memory. It would be\n+ * good to have just 32-bit pointers, requiring a special allocator\n+ * for hashed entries or something.\n+ */\n+struct hash_table_entry {\n+\tunsigned int hash;\n+\tvoid *ptr;\n+};\n+\n+struct hash_table {\n+\tunsigned int size, nr;\n+\tstruct hash_table_entry *array;\n+};\n+\n+extern void *lookup_hash(unsigned int hash, struct hash_table *table);\n+extern void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table);\n+extern int for_each_hash(struct hash_table *table, int (*fn)(void *));\n+extern void free_hash(struct hash_table *table);\n+\n+static inline void init_hash(struct hash_table *table)\n+{\n+\ttable->size = 0;\n+\ttable->nr = 0;\n+\ttable->array = NULL;\n+}\n+\n+#endif\n"},{"id":"56907","messageId":"alpine.LFD.0.999.0710221207300.30120@woody.linux-foundation.org","threadId":"10407","inReplyTo":"alpine.LFD.0.999.0710221009580.10525@woody.linux-foundation.org","subject":"Re: [PATCH, take 2] Linear-time/space rename logic (exact renames only)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-22T19:31:11Z","receivedAt":"2007-10-22T19:31:11Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 22 Oct 2007, Linus Torvalds wrote:\n> \n> Ok, as some people notices, there were a few bugs in the previous patch. I \n> didn't free the hashes correctly (stupid) and the Makefile had \"hash.o\" \n> instead of \"hash.h\".\n\nOk, there were still more bugs, and before you get too involved with this \nlast patch (not that I've seen any comments yet), apply this appended \npatch to actually fix things a bit more first!\n\nYes, I'm a moron. I hadn't even bothered to run the test-suite on it, and \nthat showed several silly problems.\n\nOne of the problems was that since the rename detection copied the \ndiffspecs around, the \"rename_used\" count couldn't work right, because \nthings got copied around and the count stayed with one diffspec, but not \nthe other..\n\nIn the kernel, we have a rule that says that any data structure that isn't \nref-counted is basically a bug, and that was true here too. Instead of \ncopying and splitting the diffspecs, just refcount them and keep track of \nhow many users there are.\n\nWhile the above bug was a somewhat subtle issue from me trying to be \nclever in avoiding the O(n*m) file copy/rename reuse issue, there were a \nfew issues that were me just being totally braindead: the exact rename \ndetection had lost the code that took file modes into account, so it would \ngenerate \"renames\" from regular files to symlinks, that the generic diff \ncore layer would just split up again.\n\nAnd even more stupidly, I had matched up the src/dst things when finding \nthe rename, which just complicated things (added a totally unnecessary \nneed to keep track of a destination being used more than once) and also \nbroke the basename matching comparison. Duh.\n\nSo here's an incremental patch on top of the previous failed try. And if \nsomebody is confused (and that might be me) and cannot get things to \napply, just holler and I'll send the whole thing again. I might even try \nto clean up the series a bit and do it in stages.\n\nThis patch shouldn't change any performance behaviour (well, it might \nspeed things up a bit to not allocate those diffspec structures, but it's \nunlikely that is even measurable). It just fixes stuff.\n\nI'm sure there's more to come..\n\n\t\tLinus\n\n---\n diff.c            |   17 ++++++++++++-----\n diffcore-rename.c |   40 ++++++++++++++++++++++------------------\n diffcore.h        |    2 ++\n 3 files changed, 36 insertions(+), 23 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex e892030..2e74cb3 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -1440,9 +1440,18 @@ struct diff_filespec *alloc_filespec(const char *path)\n \tmemset(spec, 0, sizeof(*spec));\n \tspec->path = (char *)(spec + 1);\n \tmemcpy(spec->path, path, namelen+1);\n+\tspec->count = 1;\n \treturn spec;\n }\n \n+void free_filespec(struct diff_filespec *spec)\n+{\n+\tif (!--spec->count) {\n+\t\tdiff_free_filespec_data(spec);\n+\t\tfree(spec);\n+\t}\n+}\n+\n void fill_filespec(struct diff_filespec *spec, const unsigned char *sha1,\n \t\t   unsigned short mode)\n {\n@@ -2431,10 +2440,8 @@ struct diff_filepair *diff_queue(struct diff_queue_struct *queue,\n \n void diff_free_filepair(struct diff_filepair *p)\n {\n-\tdiff_free_filespec_data(p->one);\n-\tdiff_free_filespec_data(p->two);\n-\tfree(p->one);\n-\tfree(p->two);\n+\tfree_filespec(p->one);\n+\tfree_filespec(p->two);\n \tfree(p);\n }\n \n@@ -2588,7 +2595,7 @@ void diff_debug_filepair(const struct diff_filepair *p, int i)\n \tdiff_debug_filespec(p->two, i, \"two\");\n \tfprintf(stderr, \"score %d, status %c rename_used %d broken %d\\n\",\n \t\tp->score, p->status ? p->status : '?',\n-\t\tp->rename_used, p->broken_pair);\n+\t\tp->one->rename_used, p->broken_pair);\n }\n \n void diff_debug_queue(const char *msg, struct diff_queue_struct *q)\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex cc105db..3946932 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -184,7 +184,7 @@ static int estimate_similarity(struct diff_filespec *src,\n \n static void record_rename_pair(int dst_index, int src_index, int score)\n {\n-\tstruct diff_filespec *one, *two, *src, *dst;\n+\tstruct diff_filespec *src, *dst;\n \tstruct diff_filepair *dp;\n \n \tif (rename_dst[dst_index].pair)\n@@ -192,14 +192,12 @@ static void record_rename_pair(int dst_index, int src_index, int score)\n \n \tsrc = rename_src[src_index].one;\n \tsrc->rename_used++;\n-\tone = alloc_filespec(src->path);\n-\tfill_filespec(one, src->sha1, src->mode);\n+\tsrc->count++;\n \n \tdst = rename_dst[dst_index].two;\n-\ttwo = alloc_filespec(dst->path);\n-\tfill_filespec(two, dst->sha1, dst->mode);\n+\tdst->count++;\n \n-\tdp = diff_queue(NULL, one, two);\n+\tdp = diff_queue(NULL, src, dst);\n \tdp->renamed_pair = 1;\n \tif (!strcmp(src->path, dst->path))\n \t\tdp->score = rename_src[src_index].score;\n@@ -232,21 +230,30 @@ static int find_identical_files(struct file_similarity *src,\n \t\t\t\tstruct file_similarity *dst)\n {\n \tint renames = 0;\n+\n+\t/*\n+\t * Walk over all the destinations ...\n+\t */\n \tdo {\n-\t\tstruct diff_filespec *one = src->filespec;\n+\t\tstruct diff_filespec *one = dst->filespec;\n \t\tstruct file_similarity *p, *best;\n \t\tint i = 100;\n \n+\t\t/*\n+\t\t * .. to find the best source match\n+\t\t */\n \t\tbest = NULL;\n-\t\tfor (p = dst; p; p = p->next) {\n+\t\tfor (p = src; p; p = p->next) {\n \t\t\tstruct diff_filespec *two = p->filespec;\n \n-\t\t\t/* Already picked as a destination? */\n-\t\t\tif (!p->src_dst)\n-\t\t\t\tcontinue;\n \t\t\t/* False hash collission? */\n \t\t\tif (hashcmp(one->sha1, two->sha1))\n \t\t\t\tcontinue;\n+\t\t\t/* Non-regular files? If so, the modes must match! */\n+\t\t\tif (!S_ISREG(one->mode) || !S_ISREG(two->mode)) {\n+\t\t\t\tif (one->mode != two->mode)\n+\t\t\t\t\tcontinue;\n+\t\t\t}\n \t\t\tbest = p;\n \t\t\tif (basename_same(one, two))\n \t\t\t\tbreak;\n@@ -256,11 +263,10 @@ static int find_identical_files(struct file_similarity *src,\n \t\t\t\tbreak;\n \t\t}\n \t\tif (best) {\n-\t\t\tbest->src_dst = 0;\n-\t\t\trecord_rename_pair(best->index, src->index, MAX_SCORE);\n+\t\t\trecord_rename_pair(dst->index, best->index, MAX_SCORE);\n \t\t\trenames++;\n \t\t}\n-\t} while ((src = src->next) != NULL);\n+\t} while ((dst = dst->next) != NULL);\n \treturn renames;\n }\n \n@@ -569,10 +575,8 @@ void diffcore_rename(struct diff_options *options)\n \t*q = outq;\n \tdiff_debug_queue(\"done collapsing\", q);\n \n-\tfor (i = 0; i < rename_dst_nr; i++) {\n-\t\tdiff_free_filespec_data(rename_dst[i].two);\n-\t\tfree(rename_dst[i].two);\n-\t}\n+\tfor (i = 0; i < rename_dst_nr; i++)\n+\t\tfree_filespec(rename_dst[i].two);\n \n \tfree(rename_dst);\n \trename_dst = NULL;\ndiff --git a/diffcore.h b/diffcore.h\nindex ceda932..cc96c20 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -29,6 +29,7 @@ struct diff_filespec {\n \tvoid *cnt_data;\n \tconst char *funcname_pattern_ident;\n \tunsigned long size;\n+\tint count;               /* Reference count */\n \tint xfrm_flags;\t\t /* for use by the xfrm */\n \tint rename_used;         /* Count of rename users */\n \tunsigned short mode;\t /* file mode */\n@@ -44,6 +45,7 @@ struct diff_filespec {\n };\n \n extern struct diff_filespec *alloc_filespec(const char *);\n+extern void free_filespec(struct diff_filespec *);\n extern void fill_filespec(struct diff_filespec *, const unsigned char *,\n \t\t\t  unsigned short);\n \n"},{"id":"56909","messageId":"alpine.LFD.0.999.0710221241560.30120@woody.linux-foundation.org","threadId":"10407","inReplyTo":"alpine.LFD.0.999.0710221207300.30120@woody.linux-foundation.org","subject":"Re: [PATCH, take 2] Linear-time/space rename logic (exact renames only)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-22T19:44:48Z","receivedAt":"2007-10-22T19:44:48Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 22 Oct 2007, Linus Torvalds wrote:\n> \n> I'm sure there's more to come..\n\nOne more detail.. The updated comment explains the issue: if we broke a \nfile apart, and rename detection joined it back together, the result is \nneither a rename nor a copy, it's a regular modification (and all \nremaining renames will be copies of the original, so don't bother \ndecrementing the \"rename_used\" count).\n\n\t\tLinus\n\n---\n diff.c |   18 ++++++++++++------\n 1 files changed, 12 insertions(+), 6 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 2e74cb3..e839f59 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2636,13 +2636,19 @@ static void diff_resolve_rename_copy(void)\n \t\t * either in-place edit or rename/copy edit.\n \t\t */\n \t\telse if (DIFF_PAIR_RENAME(p)) {\n-\t\t\t/* See if there is some other filepair that\n-\t\t\t * copies from the same source as us.  If so\n-\t\t\t * we are a copy.  Otherwise we are either a\n-\t\t\t * copy if the path stays, or a rename if it\n-\t\t\t * does not, but we already handled \"stays\" case.\n+\t\t\t/*\n+\t\t\t * A rename might have re-connected a broken\n+\t\t\t * pair up, causing the pathnames to be the\n+\t\t\t * same again. If so, that's not a rename at\n+\t\t\t * all, just a modification..\n+\t\t\t *\n+\t\t\t * Otherwise, see if this source was used for\n+\t\t\t * multiple renames, in which case we decrement\n+\t\t\t * the count, and call it a copy.\n \t\t\t */\n-\t\t\tif (--p->one->rename_used > 0)\n+\t\t\tif (!strcmp(p->one->path, p->two->path))\n+\t\t\t\tp->status = DIFF_STATUS_MODIFIED;\n+\t\t\telse if (--p->one->rename_used > 0)\n \t\t\t\tp->status = DIFF_STATUS_COPIED;\n \t\t\telse\n \t\t\t\tp->status = DIFF_STATUS_RENAMED;\n"},{"id":"56916","messageId":"20071022211706.GD23714@steel.home","threadId":"10407","inReplyTo":"alpine.LFD.0.999.0710221241560.30120@woody.linux-foundation.org","subject":"Re: [PATCH, take 2] Linear-time/space rename logic (exact renames only)","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2007-10-22T21:17:06Z","receivedAt":"2007-10-22T21:17:06Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Linus Torvalds, Mon, Oct 22, 2007 21:44:48 +0200:\n> \n> \n> On Mon, 22 Oct 2007, Linus Torvalds wrote:\n> > \n> > I'm sure there's more to come..\n> \n> One more detail.. The updated comment explains the issue: if we broke a \n> file apart, and rename detection joined it back together, the result is \n> neither a rename nor a copy, it's a regular modification (and all \n> remaining renames will be copies of the original, so don't bother \n> decrementing the \"rename_used\" count).\n\nIt breaks t3402-rebase-merge.sh\n"},{"id":"56917","messageId":"alpine.LFD.0.999.0710221437030.30120@woody.linux-foundation.org","threadId":"10407","inReplyTo":"20071022211706.GD23714@steel.home","subject":"Re: [PATCH, take 2] Linear-time/space rename logic (exact renames only)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-22T21:37:55Z","receivedAt":"2007-10-22T21:37:55Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 22 Oct 2007, Alex Riesen wrote:\n> \n> It breaks t3402-rebase-merge.sh\n\nHmm. Works for me here. But I will check if there is some incomplete \ndependency in the makefile or something...\n\n\t\tLinus\n"},{"id":"56921","messageId":"20071022225455.GH23714@steel.home","threadId":"10407","inReplyTo":"alpine.LFD.0.999.0710221437030.30120@woody.linux-foundation.org","subject":"Re: [PATCH, take 2] Linear-time/space rename logic (exact renames only)","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2007-10-22T22:54:55Z","receivedAt":"2007-10-22T22:54:55Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Linus Torvalds, Mon, Oct 22, 2007 23:37:55 +0200:\n> On Mon, 22 Oct 2007, Alex Riesen wrote:\n> > \n> > It breaks t3402-rebase-merge.sh\n> \n> Hmm. Works for me here. But I will check if there is some incomplete \n> dependency in the makefile or something...\n> \n\nOk, resolved. Turns out I completely missed the last two patches\n"}]}