{"thread":{"id":"10521","subject":"[PATCH/RFC 0/3] faster inexact rename handling","startedAt":"2007-10-30T04:21:19Z","lastAt":"2007-10-31T00:27:10Z","messageCount":13,"participants":["Jeff King","Linus Torvalds","Junio C Hamano","Andy C"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"57519","messageId":"20071030042118.GA14729@sigill.intra.peff.net","threadId":"10521","inReplyTo":null,"subject":"[PATCH/RFC 0/3] faster inexact rename handling","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-30T04:21:19Z","receivedAt":"2007-10-30T04:21:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This is my first stab at faster rename handling based on Andy's code.\nThe patches are on top of next (to get Linus' recent work on exact\nrenames). Most of the interesting stuff is in 2/3.\n\n  1/3: extension of hash interface\n  2/3: similarity detection code\n  3/3: integrate similarity detection into diffcore-rename\n\nThe implementation is pretty basic, so I think there is room for\ncode optimization (50% of the time is spent in hash lookups, so we might\nbe able to micro-optimize that) as well as algorithmic improvements (like the\nsampling Andy mentioned).\n\nWith these patches, I can get my monster binary diff down from about 2\nminutes to 17 seconds. And comparing all of linux-2.4 to all of\nlinux-2.6 (similar to Andy's previous demo) takes about 10 seconds.\n\nThere are a few downsides:\n  - the current implementation tends to give lower similarity values\n    compared to the old code (see discussion in 2/3), but this should be\n    tweakable\n  - on large datasets, it's more memory hungry than the old code because\n    the hash grows very large. This can be helped by bumping up the\n    binary chunk size (actually, the 17 seconds quoted above is using\n    256-byte chunks rather than 64-byte -- with 64-byte chunks, it's\n    more like 24 seconds) as well as sampling.\n  - no improvement on smaller datasets. Running \"git-whatchanged -M\n    --raw -l0\" on the linux-2.6 repo takes about the same time with the\n    old and new code (presumably the algorithmic savings of the new code\n    are lost in a higher constant factor, so when n is small, it is a\n    wash).\n\n-Peff\n"},{"id":"57520","messageId":"20071030042328.GA14954@sigill.intra.peff.net","threadId":"10521","inReplyTo":"20071030042118.GA14729@sigill.intra.peff.net","subject":"[PATCH/RFC 1/3] change hash table calling conventions","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-30T04:23:28Z","receivedAt":"2007-10-30T04:23:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The recent hash table code has two limitations in its\ncalling conventions that are addressed here:\n\n  1. Insertion either inserts a value, returning NULL, or\n     returns a pointer to the previously inserted value.\n     This is fine if you are making a linked list of the\n     colliding values, but is awkward if your goal is to:\n       a. modify the value if it already exists\n       b. otherwise, allocate and insert the value\n     With the old convention, you must either allocate the\n     structure (and throw it away in case a), or perform two\n     lookups (one to see if the entry exists, then another\n     to perform the insertion).\n\n     Instead, insertion no longer inserts any value; it\n     simply returns a pointer to where you _can_ insert a\n     value (which will be non-NULL if a value already\n     existed).\n\n  2. for_each_hash now allows a void 'data' pointer to be\n     passed to the callback function along with each hash\n     entry.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n\nThe insertion feels kind of hack-ish. Suggestions are welcome.\n\n diffcore-rename.c |   14 +++++---------\n hash.c            |   18 +++++++++---------\n hash.h            |    5 +++--\n 3 files changed, 17 insertions(+), 20 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex f9ebea5..ba038af 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -288,7 +288,7 @@ static void free_similarity_list(struct file_similarity *p)\n \t}\n }\n \n-static int find_same_files(void *ptr)\n+static int find_same_files(void *ptr, void *data)\n {\n \tint ret;\n \tstruct file_similarity *p = ptr;\n@@ -343,13 +343,9 @@ static void insert_file_table(struct hash_table *table, int src_dst, int index,\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+\tpos = insert_hash(hash, table);\n+\tentry->next = *pos;\n+\t*pos = entry;\n }\n \n /*\n@@ -372,7 +368,7 @@ static int find_exact_renames(void)\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+\ti = for_each_hash(&file_table, find_same_files, NULL);\n \n \t/* .. and free the hash data structure */\n \tfree_hash(&file_table);\ndiff --git a/hash.c b/hash.c\nindex 7b492d4..dc5d20e 100644\n--- a/hash.c\n+++ b/hash.c\n@@ -33,15 +33,13 @@ static struct hash_table_entry *lookup_hash_entry(unsigned int hash, struct hash\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+static void **insert_hash_entry(unsigned int hash, 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@@ -60,8 +58,10 @@ static void grow_hash_table(struct hash_table *table)\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\tif (ptr) {\n+\t\t\tvoid **pos = insert_hash_entry(hash, table);\n+\t\t\t*pos = ptr;\n+\t\t}\n \t}\n \tfree(old_array);\n }\n@@ -73,15 +73,15 @@ void *lookup_hash(unsigned int hash, struct hash_table *table)\n \treturn &lookup_hash_entry(hash, table)->ptr;\n }\n \n-void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table)\n+void **insert_hash(unsigned int hash, 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+\treturn insert_hash_entry(hash, table);\n }\n \n-int for_each_hash(struct hash_table *table, int (*fn)(void *))\n+int for_each_hash(struct hash_table *table, int (*fn)(void *, void *), void *d)\n {\n \tint sum = 0;\n \tunsigned int i;\n@@ -92,7 +92,7 @@ int for_each_hash(struct hash_table *table, int (*fn)(void *))\n \t\tvoid *ptr = array->ptr;\n \t\tarray++;\n \t\tif (ptr) {\n-\t\t\tint val = fn(ptr);\n+\t\t\tint val = fn(ptr, d);\n \t\t\tif (val < 0)\n \t\t\t\treturn val;\n \t\t\tsum += val;\ndiff --git a/hash.h b/hash.h\nindex a8b0fbb..f9a50da 100644\n--- a/hash.h\n+++ b/hash.h\n@@ -29,8 +29,9 @@ struct hash_table {\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 **insert_hash(unsigned int hash, struct hash_table *table);\n+extern int for_each_hash(struct hash_table *table, int (*fn)(void *, void*),\n+\t\tvoid *data);\n extern void free_hash(struct hash_table *table);\n \n static inline void init_hash(struct hash_table *table)\n-- \n1.5.3.4\n"},{"id":"57521","messageId":"20071030042407.GB14954@sigill.intra.peff.net","threadId":"10521","inReplyTo":"20071030042118.GA14729@sigill.intra.peff.net","subject":"[PATCH/RFC 2/3] introduce generic similarity library","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-30T04:24:07Z","receivedAt":"2007-10-30T04:24:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This library attempts to find similarities among items\nefficiently. It treats items as opaque pointers; callers are\nresponsible for providing an item along with its contents.\n\nThe algorithm is roughly:\n\n  1. for each item, create a set of fingerprints for each\n     chunk of the item (where each chunk is either delimited\n     by a newline or is 64 characters, whichever is smaller\n     -- this is the same fingerprint code from\n     diffcore-delta.c). A hash stores a mapping of\n     fingerprints to items, with each fingerprint having at\n     most one 'source' item and one 'dest' item.\n\n  2. for each fingerprint with a source and dest item,\n     find the entry with key (source, dest) in a hash table\n     and increment its value by the value of the fingerprint\n\n  3. for each (source, dest) pair that had non-zero\n     similarity, report the pair to the caller\n\nThe program test-similarity is a simple demonstration of the\ncode. It takes two list of files on stdin, with each file\nseparated by newlines and the two lists separated by a blank\nline. It prints the similarity score of each non-zero pair\non stdout.\n\nThere are a few \"interesting\" design decisions, which should\nprobably be tweaked:\n\n  - we store only one source and dest for each fingerprint\n    item. We need to bound this list so that we don't get\n    O(n^2) behavior for common fingerprints. This means that\n    some files won't get \"credit\" for common fingerprints,\n    which is probably OK, since those fingerprints are\n    probably uninteresting. We could bound at some small\n    number greater than one; one was chosen for speed and\n    simplicity of implementation. We also don't store any\n    overflow bit, so commonly used fingerprints will get\n    assigned to whatever file is found with them last.\n\n  - the similarity engine hands back absolute,\n    non-normalized scores. That means that bigger items will\n    have bigger scores, and the caller is responsible for\n    normalizing. This also means that the engine cannot\n    adjust normalization to account for chunks which are\n    thrown out by the bounding mentioned above (i.e., if a\n    file is 80 bytes, 64 of which are ignored as \"common\",\n    then it can at most have 20% similarity (16/80) with\n    another file. This means our normalized rename values\n    (i.e., percentage similarity) will be lower than other\n    algorithms.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n .gitignore        |    1 +\n Makefile          |    4 +-\n similarity.c      |  152 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n similarity.h      |   24 ++++++++\n test-similarity.c |   54 +++++++++++++++++++\n 5 files changed, 233 insertions(+), 2 deletions(-)\n create mode 100644 similarity.c\n create mode 100644 similarity.h\n create mode 100644 test-similarity.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 62afef2..8ce6026 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -155,6 +155,7 @@ test-dump-cache-tree\n test-genrandom\n test-match-trees\n test-sha1\n+test-similarity\n common-cmds.h\n *.tar.gz\n *.dsc\ndiff --git a/Makefile b/Makefile\nindex 2e6fd8f..0568d0d 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -300,7 +300,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 hash.o \\\n+\tinterpolate.o hash.o similarity.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 \\\n@@ -975,7 +975,7 @@ endif\n \n ### Testing rules\n \n-TEST_PROGRAMS = test-chmtime$X test-genrandom$X test-date$X test-delta$X test-sha1$X test-match-trees$X test-absolute-path$X\n+TEST_PROGRAMS = test-chmtime$X test-genrandom$X test-date$X test-delta$X test-sha1$X test-match-trees$X test-absolute-path$X test-similarity$X\n \n all:: $(TEST_PROGRAMS)\n \ndiff --git a/similarity.c b/similarity.c\nnew file mode 100644\nindex 0000000..0bd135c\n--- /dev/null\n+++ b/similarity.c\n@@ -0,0 +1,152 @@\n+#include \"cache.h\"\n+#include \"similarity.h\"\n+\n+struct fingerprint_entry {\n+\tvoid *src;\n+\tvoid *dst;\n+\tunsigned weight;\n+};\n+\n+struct score_entry {\n+\tvoid *src;\n+\tvoid *dst;\n+\tunsigned score;\n+\tstruct score_entry *next;\n+};\n+\n+void similarity_init(struct similarity *s)\n+{\n+\tinit_hash(&s->fingerprints);\n+\tinit_hash(&s->scores);\n+}\n+\n+static int free_one_fingerprint(void *ve, void *data)\n+{\n+\tstruct fingerprint_entry *e = ve;\n+\tfree(e);\n+\treturn 0;\n+}\n+\n+static int free_one_score(void *ve, void *data)\n+{\n+\tstruct score_entry *e = ve;\n+\twhile (e) {\n+\t\tstruct score_entry *next = e->next;\n+\t\tfree(e);\n+\t\te = next;\n+\t}\n+\treturn 0;\n+}\n+\n+void similarity_free(struct similarity *s)\n+{\n+\tfor_each_hash(&s->fingerprints, free_one_fingerprint, NULL);\n+\tfree_hash(&s->fingerprints);\n+\tfor_each_hash(&s->scores, free_one_score, NULL);\n+\tfree_hash(&s->scores);\n+}\n+\n+static void add_fingerprint(struct hash_table *h, unsigned int fp,\n+\t\tint type, void *data, unsigned weight)\n+{\n+\tvoid **pos;\n+\tstruct fingerprint_entry *e;\n+\n+\tpos = insert_hash(fp, h);\n+\tif (!*pos) {\n+\t\te = xmalloc(sizeof(*e));\n+\t\te->weight = weight;\n+\t\te->src = e->dst = NULL;\n+\t\t*pos = e;\n+\t}\n+\telse\n+\t\te = *pos;\n+\n+\tif (type == SIMILARITY_SOURCE)\n+\t\te->src = data;\n+\telse\n+\t\te->dst = data;\n+}\n+\n+void similarity_add(struct similarity *sim, int type, void *data,\n+\t\tconst char *buf, unsigned long sz, int is_text)\n+{\n+\tint n;\n+\tunsigned int accum1, accum2, hashval;\n+\n+\tn = 0;\n+\taccum1 = accum2 = 0;\n+\twhile (sz) {\n+\t\tunsigned int c = *buf++;\n+\t\tunsigned int old_1 = accum1;\n+\t\tsz--;\n+\n+\t\t/* Ignore CR in CRLF sequence if text */\n+\t\tif (!is_text && c == '\\r' && sz && *buf == '\\n')\n+\t\t\tcontinue;\n+\n+\t\taccum1 = (accum1 << 7) ^ (accum2 >> 25);\n+\t\taccum2 = (accum2 << 7) ^ (old_1 >> 25);\n+\t\taccum1 += c;\n+\t\tif (++n < 64 && c != '\\n')\n+\t\t\tcontinue;\n+\t\thashval = accum1 + accum2 * 0x61;\n+\t\tadd_fingerprint(&sim->fingerprints, hashval, type, data, n);\n+\t\tn = 0;\n+\t\taccum1 = accum2 = 0;\n+\t}\n+}\n+\n+static unsigned hash_void_pair(void *a, void *b)\n+{\n+\treturn (unsigned)a + (unsigned)b;\n+}\n+\n+static int score_one_entry(void *vfp, void *vsim)\n+{\n+\tstruct fingerprint_entry *fp = vfp;\n+\tstruct similarity *sim = vsim;\n+\tstruct score_entry *score;\n+\tvoid **pos;\n+\n+\tif (!fp->src || !fp->dst)\n+\t\treturn 0;\n+\n+\tpos = insert_hash(hash_void_pair(fp->src, fp->dst), &sim->scores);\n+\tfor (score = *pos; score; score = score->next) {\n+\t\tif (score->src == fp->src && score->dst == fp->dst) {\n+\t\t\tscore->score += fp->weight;\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+\n+\tscore = xmalloc(sizeof(*score));\n+\tscore->src = fp->src;\n+\tscore->dst = fp->dst;\n+\tscore->score = fp->weight;\n+\tscore->next = *pos;\n+\t*pos = score;\n+\n+\treturn 0;\n+}\n+\n+void similarity_score(struct similarity *s)\n+{\n+\tfor_each_hash(&s->fingerprints, score_one_entry, s);\n+}\n+\n+static int report_one_score(void *ve, void *vdata)\n+{\n+\tstruct score_entry *e;\n+\tvoid (*fn)(void *, void *, unsigned) = vdata;\n+\n+\tfor (e = ve; e; e = e->next)\n+\t\tfn(e->src, e->dst, e->score);\n+\treturn 1;\n+}\n+\n+void similarity_report(struct similarity *s,\n+\t\tvoid (*fn)(void *, void *, unsigned))\n+{\n+\tfor_each_hash(&s->scores, report_one_score, fn);\n+}\ndiff --git a/similarity.h b/similarity.h\nnew file mode 100644\nindex 0000000..6409ab8\n--- /dev/null\n+++ b/similarity.h\n@@ -0,0 +1,24 @@\n+#ifndef SIMILARITY_H\n+#define SIMILARITY_H\n+\n+#include \"hash.h\"\n+\n+#define SIMILARITY_SOURCE 0\n+#define SIMILARITY_DEST   1\n+\n+struct similarity {\n+\tstruct hash_table fingerprints;\n+\tstruct hash_table scores;\n+};\n+\n+void similarity_init(struct similarity *s);\n+void similarity_free(struct similarity *s);\n+\n+void similarity_add(struct similarity *s, int type, void *data,\n+\t\tconst char *buf, unsigned long sz, int is_text);\n+\n+void similarity_score(struct similarity *s);\n+void similarity_report(struct similarity *s,\n+\t\tvoid (*fn)(void *, void *, unsigned));\n+\n+#endif /* SIMILARITY_H */\ndiff --git a/test-similarity.c b/test-similarity.c\nnew file mode 100644\nindex 0000000..5947420\n--- /dev/null\n+++ b/test-similarity.c\n@@ -0,0 +1,54 @@\n+#include <string.h>\n+#include <stdio.h>\n+#include <errno.h>\n+\n+#include \"git-compat-util.h\"\n+#include \"similarity.h\"\n+#include \"strbuf.h\"\n+#include \"xdiff-interface.h\"\n+\n+static void print_rename(void *vone, void *vtwo, unsigned score) {\n+\tconst char *one = vone, *two = vtwo;\n+\tprintf(\"%u %s -> %s\\n\", score, one, two);\n+}\n+\n+static void add_file(struct similarity *sim, int type, const char *fn)\n+{\n+\tstruct strbuf sb = STRBUF_INIT;\n+\tint len;\n+\n+\tlen = strbuf_read_file(&sb, fn, 0);\n+\tif (len < 0)\n+\t\tdie(\"unable to read %s: %s\\n\", fn, strerror(errno));\n+\n+\tsimilarity_add(sim, type, strdup(fn),\n+\t\t\tsb.buf, sb.len, buffer_is_binary(sb.buf, sb.len));\n+\n+\tstrbuf_release(&sb);\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tstruct similarity sim;\n+\tstruct strbuf line;\n+\n+\tsimilarity_init(&sim);\n+\tstrbuf_init(&line, 0);\n+\n+\twhile (strbuf_getline(&line, stdin, '\\n') != EOF) {\n+\t\tif (!line.len)\n+\t\t\tbreak;\n+\t\tadd_file(&sim, SIMILARITY_SOURCE, line.buf);\n+\t}\n+\twhile (strbuf_getline(&line, stdin, '\\n') != EOF)\n+\t\tadd_file(&sim, SIMILARITY_DEST, line.buf);\n+\n+\tstrbuf_release(&line);\n+\n+\tsimilarity_score(&sim);\n+\tsimilarity_report(&sim, print_rename);\n+\n+\tsimilarity_free(&sim);\n+\n+\treturn 0;\n+}\n-- \n1.5.3.4\n"},{"id":"57522","messageId":"20071030042442.GC14954@sigill.intra.peff.net","threadId":"10521","inReplyTo":"20071030042118.GA14729@sigill.intra.peff.net","subject":"[PATCH/RFC 3/3] handle renames using similarity engine","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-30T04:24:42Z","receivedAt":"2007-10-30T04:24:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This changes diffcore-rename to use the engine in\nsimilarity.c rather than doing an O(m*n) loop around\ndiffcore_count_changes.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n diffcore-rename.c |  215 +++++++++++++++++++----------------------------------\n 1 files changed, 76 insertions(+), 139 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex ba038af..6c0d2d0 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -5,12 +5,21 @@\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"hash.h\"\n+#include \"similarity.h\"\n \n-/* Table of rename/copy destinations */\n+/* Table of rename/copy src files */\n+static struct diff_rename_src {\n+\tstruct diff_filespec *one;\n+\tunsigned short score; /* to remember the break score */\n+} *rename_src;\n+static int rename_src_nr, rename_src_alloc;\n \n+/* Table of rename/copy destinations */\n static struct diff_rename_dst {\n \tstruct diff_filespec *two;\n \tstruct diff_filepair *pair;\n+\tstruct diff_rename_src *best_match;\n+\tunsigned score;\n } *rename_dst;\n static int rename_dst_nr, rename_dst_alloc;\n \n@@ -49,16 +58,11 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n \trename_dst[first].two = alloc_filespec(two->path);\n \tfill_filespec(rename_dst[first].two, two->sha1, two->mode);\n \trename_dst[first].pair = NULL;\n+\trename_dst[first].best_match = NULL;\n+\trename_dst[first].score = 0;\n \treturn &(rename_dst[first]);\n }\n \n-/* Table of rename/copy src files */\n-static struct diff_rename_src {\n-\tstruct diff_filespec *one;\n-\tunsigned short score; /* to remember the break score */\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   unsigned short score)\n {\n@@ -109,88 +113,6 @@ static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n \t\t(!dst_len || dst->path[dst_len - 1] == '/');\n }\n \n-struct diff_score {\n-\tint src; /* index in rename_src */\n-\tint dst; /* index in rename_dst */\n-\tint score;\n-\tint name_score;\n-};\n-\n-static int estimate_similarity(struct diff_filespec *src,\n-\t\t\t       struct diff_filespec *dst,\n-\t\t\t       int minimum_score)\n-{\n-\t/* src points at a file that existed in the original tree (or\n-\t * optionally a file in the destination tree) and dst points\n-\t * at a newly created file.  They may be quite similar, in which\n-\t * case we want to say src is renamed to dst or src is copied into\n-\t * dst, and then some edit has been applied to dst.\n-\t *\n-\t * Compare them and return how similar they are, representing\n-\t * the score as an integer between 0 and MAX_SCORE.\n-\t *\n-\t * When there is an exact match, it is considered a better\n-\t * match than anything else; the destination does not even\n-\t * call into this function in that case.\n-\t */\n-\tunsigned long max_size, delta_size, base_size, src_copied, literal_added;\n-\tunsigned long delta_limit;\n-\tint score;\n-\n-\t/* We deal only with regular files.  Symlink renames are handled\n-\t * only when they are exact matches --- in other words, no edits\n-\t * after renaming.\n-\t */\n-\tif (!S_ISREG(src->mode) || !S_ISREG(dst->mode))\n-\t\treturn 0;\n-\n-\t/*\n-\t * Need to check that source and destination sizes are\n-\t * filled in before comparing them.\n-\t *\n-\t * If we already have \"cnt_data\" filled in, we know it's\n-\t * all good (avoid checking the size for zero, as that\n-\t * is a possible size - we really should have a flag to\n-\t * say whether the size is valid or not!)\n-\t */\n-\tif (!src->cnt_data && diff_populate_filespec(src, 0))\n-\t\treturn 0;\n-\tif (!dst->cnt_data && diff_populate_filespec(dst, 0))\n-\t\treturn 0;\n-\n-\tmax_size = ((src->size > dst->size) ? src->size : dst->size);\n-\tbase_size = ((src->size < dst->size) ? src->size : dst->size);\n-\tdelta_size = max_size - base_size;\n-\n-\t/* We would not consider edits that change the file size so\n-\t * drastically.  delta_size must be smaller than\n-\t * (MAX_SCORE-minimum_score)/MAX_SCORE * min(src->size, dst->size).\n-\t *\n-\t * Note that base_size == 0 case is handled here already\n-\t * and the final score computation below would not have a\n-\t * divide-by-zero issue.\n-\t */\n-\tif (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n-\t\treturn 0;\n-\n-\tdelta_limit = (unsigned long)\n-\t\t(base_size * (MAX_SCORE-minimum_score) / MAX_SCORE);\n-\tif (diffcore_count_changes(src, dst,\n-\t\t\t\t   &src->cnt_data, &dst->cnt_data,\n-\t\t\t\t   delta_limit,\n-\t\t\t\t   &src_copied, &literal_added))\n-\t\treturn 0;\n-\n-\t/* How similar are they?\n-\t * what percentage of material in dst are from source?\n-\t */\n-\tif (!dst->size)\n-\t\tscore = 0; /* should not happen */\n-\telse\n-\t\tscore = (int)(src_copied * MAX_SCORE / max_size);\n-\treturn score;\n-}\n-\n static void record_rename_pair(int dst_index, int src_index, int score)\n {\n \tstruct diff_filespec *src, *dst;\n@@ -215,20 +137,6 @@ static void record_rename_pair(int dst_index, int src_index, int score)\n \trename_dst[dst_index].pair = dp;\n }\n \n-/*\n- * We sort the rename similarity matrix with the score, in descending\n- * order (the most similar first).\n- */\n-static int score_compare(const void *a_, const void *b_)\n-{\n-\tconst struct diff_score *a = a_, *b = b_;\n-\n-\tif (a->score == b->score)\n-\t\treturn b->name_score - a->name_score;\n-\n-\treturn b->score - a->score;\n-}\n-\n struct file_similarity {\n \tint src_dst, index;\n \tstruct diff_filespec *filespec;\n@@ -376,6 +284,67 @@ static int find_exact_renames(void)\n \treturn i;\n }\n \n+static void record_similarity(void *vsrc, void *vdst, unsigned score)\n+{\n+\tstruct diff_rename_src *src = vsrc;\n+\tstruct diff_rename_dst *dst = vdst;\n+\tunsigned max_size = (src->one->size > dst->two->size) ?\n+\t\t\t\tsrc->one->size : dst->two->size;\n+\n+\tscore = (dst->two->size != 0) ? (score * MAX_SCORE / max_size) : 0;\n+\n+\t/* Is there a match already that is better than we are? */\n+\tif (dst->best_match) {\n+\t\tif (score < dst->score)\n+\t\t\treturn;\n+\t\tif (score == dst->score && !basename_same(src->one, dst->two))\n+\t\t\treturn;\n+\t}\n+\n+\tdst->best_match = src;\n+\tdst->score = score;\n+}\n+\n+static void find_approximate_renames(int minimum_score)\n+{\n+\tstruct similarity sim;\n+\tint i;\n+\n+\tsimilarity_init(&sim);\n+\n+\tfor (i = 0; i < rename_src_nr; i++) {\n+\t\tstruct diff_rename_src *s = &rename_src[i];\n+\t\tdiff_populate_filespec(s->one, 0);\n+\t\tsimilarity_add(&sim, SIMILARITY_SOURCE, s,\n+\t\t\t\ts->one->data, s->one->size,\n+\t\t\t\tdiff_filespec_is_binary(s->one));\n+\t\tdiff_free_filespec_data(s->one);\n+\t}\n+\n+\tfor (i = 0; i < rename_dst_nr; i++) {\n+\t\tstruct diff_rename_dst *d = &rename_dst[i];\n+\t\tif (d->pair)\n+\t\t\tcontinue;\n+\t\tdiff_populate_filespec(d->two, 0);\n+\t\tsimilarity_add(&sim, SIMILARITY_DEST, d,\n+\t\t\t\td->two->data, d->two->size,\n+\t\t\t\tdiff_filespec_is_binary(d->two));\n+\t\tdiff_free_filespec_data(d->two);\n+\t}\n+\n+\tsimilarity_score(&sim);\n+\tsimilarity_report(&sim, record_similarity);\n+\n+\tfor (i = 0 ; i < rename_dst_nr; i++) {\n+\t\tstruct diff_rename_dst *d = &rename_dst[i];\n+\t\tif (d->pair)\n+\t\t\tcontinue;\n+\t\tif (d->score < minimum_score)\n+\t\t\tcontinue;\n+\t\trecord_rename_pair(i, d->best_match - rename_src, d->score);\n+\t}\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -383,9 +352,8 @@ void diffcore_rename(struct diff_options *options)\n \tint rename_limit = options->rename_limit;\n \tstruct diff_queue_struct *q = &diff_queued_diff;\n \tstruct diff_queue_struct outq;\n-\tstruct diff_score *mx;\n-\tint i, j, rename_count;\n-\tint num_create, num_src, dst_cnt;\n+\tint num_create, num_src;\n+\tint i, rename_count;\n \n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n@@ -462,38 +430,7 @@ void diffcore_rename(struct diff_options *options)\n \tif (num_create * num_src > rename_limit * rename_limit)\n \t\tgoto cleanup;\n \n-\tmx = xmalloc(sizeof(*mx) * num_create * num_src);\n-\tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n-\t\tint base = dst_cnt * num_src;\n-\t\tstruct diff_filespec *two = rename_dst[i].two;\n-\t\tif (rename_dst[i].pair)\n-\t\t\tcontinue; /* dealt with exact match already. */\n-\t\tfor (j = 0; j < rename_src_nr; j++) {\n-\t\t\tstruct diff_filespec *one = rename_src[j].one;\n-\t\t\tstruct diff_score *m = &mx[base+j];\n-\t\t\tm->src = j;\n-\t\t\tm->dst = i;\n-\t\t\tm->score = estimate_similarity(one, two,\n-\t\t\t\t\t\t       minimum_score);\n-\t\t\tm->name_score = basename_same(one, two);\n-\t\t\tdiff_free_filespec_blob(one);\n-\t\t}\n-\t\t/* We do not need the text anymore */\n-\t\tdiff_free_filespec_blob(two);\n-\t\tdst_cnt++;\n-\t}\n-\t/* cost matrix sorted by most to least similar pair */\n-\tqsort(mx, num_create * num_src, sizeof(*mx), score_compare);\n-\tfor (i = 0; i < num_create * num_src; i++) {\n-\t\tstruct diff_rename_dst *dst = &rename_dst[mx[i].dst];\n-\t\tif (dst->pair)\n-\t\t\tcontinue; /* already done, either exact or fuzzy. */\n-\t\tif (mx[i].score < minimum_score)\n-\t\t\tbreak; /* there is no more usable pair. */\n-\t\trecord_rename_pair(mx[i].dst, mx[i].src, mx[i].score);\n-\t\trename_count++;\n-\t}\n-\tfree(mx);\n+\tfind_approximate_renames(minimum_score);\n \n  cleanup:\n \t/* At this point, we have found some renames and copies and they\n-- \n1.5.3.4\n"},{"id":"57528","messageId":"alpine.LFD.0.999.0710292156580.30120@woody.linux-foundation.org","threadId":"10521","inReplyTo":"20071030042118.GA14729@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/3] faster inexact rename handling","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-30T05:06:11Z","receivedAt":"2007-10-30T05:06:11Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 30 Oct 2007, Jeff King wrote:\n>\n>   - no improvement on smaller datasets. Running \"git-whatchanged -M\n>     --raw -l0\" on the linux-2.6 repo takes about the same time with the\n>     old and new code (presumably the algorithmic savings of the new code\n>     are lost in a higher constant factor, so when n is small, it is a\n>     wash).\n\nHave you compared the results? IOW, does it find the *same* renames?\n\nI'm a bit worried about the fact that you just pick a single (arbitrary) \nsrc/dst per fingerprint. Yes, it should be limited, but that seems to be a \nbit too *extremely* limited. But if it gives the same results in practice, \nmaybe nobody cares?\n\n\t\tLinus\n"},{"id":"57546","messageId":"7vlk9lm2e5.fsf@gitster.siamese.dyndns.org","threadId":"10521","inReplyTo":"alpine.LFD.0.999.0710292156580.30120@woody.linux-foundation.org","subject":"Re: [PATCH/RFC 0/3] faster inexact rename handling","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-10-30T08:29:22Z","receivedAt":"2007-10-30T08:29:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Tue, 30 Oct 2007, Jeff King wrote:\n>>\n>>   - no improvement on smaller datasets. Running \"git-whatchanged -M\n>>     --raw -l0\" on the linux-2.6 repo takes about the same time with the\n>>     old and new code (presumably the algorithmic savings of the new code\n>>     are lost in a higher constant factor, so when n is small, it is a\n>>     wash).\n>\n> Have you compared the results? IOW, does it find the *same* renames?\n>\n> I'm a bit worried about the fact that you just pick a single (arbitrary) \n> src/dst per fingerprint. Yes, it should be limited, but that seems to be a \n> bit too *extremely* limited. But if it gives the same results in practice, \n> maybe nobody cares?\n\nIf it always gives the same results in practice, obviously\nnobody can even notice.\n\nHowever, merging this series to 'pu' breaks rebase-merge test\nt3402 among other things.\n"},{"id":"57573","messageId":"20071030134355.GA21342@coredump.intra.peff.net","threadId":"10521","inReplyTo":"alpine.LFD.0.999.0710292156580.30120@woody.linux-foundation.org","subject":"Re: [PATCH/RFC 0/3] faster inexact rename handling","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-30T13:43:55Z","receivedAt":"2007-10-30T13:43:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 29, 2007 at 10:06:11PM -0700, Linus Torvalds wrote:\n\n> Have you compared the results? IOW, does it find the *same* renames?\n\n>From my limited testing, it generally finds the same pairs. However,\nthere are a number of renames that it _doesn't_ find, because they are\ncomposed of \"uninteresting\" lines, dropping them below the minimum\nscore. Try (in git.git):\n\n  git-show --raw -M -l0 :/'Big tool rename'\n\nwith the old and new code. Pairs like Documentation/git-add-script.txt\n-> Documentation/git-add.txt are not found, because the file is composed\nalmost entirely of boilerplate.\n\nMoving the size normalization into the similarity engine should probably\nfix that, and will let us compare old and new results more accurately.\nI'll try to work on that.\n\n> I'm a bit worried about the fact that you just pick a single (arbitrary) \n> src/dst per fingerprint. Yes, it should be limited, but that seems to be a \n> bit too *extremely* limited. But if it gives the same results in practice, \n> maybe nobody cares?\n\nYes, I have not convinced myself yet that it's the right approach (but\nit seemed like a good place to try first, for simplicity and speed).  As\nI noted, this approach seems to be a bit memory hungry on large, so I am\na bit concerned about increasing the size of the fingerprint_entry\nstructure.  However, Andy's sampling approach might help fix that.\n\nThe current code also doesn't bother marking overflow, so common lines\nget attributes to some random file (actually, worse than random: if a\nbunch of files have the same common lines, _all_ of the lines will go to\nthe last file, which means we subtly favor renames from the end of the\ninput list). So probably it should be tested as-is, with an \"overflow,\nthis line is too common to be interesting\" bit, and with a small-ish\nlimit (I had at one point tried 5, but the implementation was naive and\ntoo memory-hungry).\n\n-Peff\n"},{"id":"57574","messageId":"20071030134627.GB21342@coredump.intra.peff.net","threadId":"10521","inReplyTo":"7vlk9lm2e5.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH/RFC 0/3] faster inexact rename handling","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-30T13:46:27Z","receivedAt":"2007-10-30T13:46:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 30, 2007 at 01:29:22AM -0700, Junio C Hamano wrote:\n\n> If it always gives the same results in practice, obviously\n> nobody can even notice.\n> \n> However, merging this series to 'pu' breaks rebase-merge test\n> t3402 among other things.\n\nYes, sorry, I meant to mention the test breakage in the cover letter\n(which I think is just related to the size/score normalization). This is\nnot really meant for applying, but more for \"this is taking me a lot\nlonger than I hoped, so here is what is happening and you might be\ninterested to comment.\" I'm not even sure it's pu material. :)\n\nI will continue to refine it as I mentioned in the mail to Linus, but I\nam open to suggestions.\n\n-Peff\n"},{"id":"57586","messageId":"alpine.LFD.0.999.0710300818390.30120@woody.linux-foundation.org","threadId":"10521","inReplyTo":"20071030134355.GA21342@coredump.intra.peff.net","subject":"Re: [PATCH/RFC 0/3] faster inexact rename handling","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-30T15:38:24Z","receivedAt":"2007-10-30T15:38:24Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 30 Oct 2007, Jeff King wrote:\n>\n> On Mon, Oct 29, 2007 at 10:06:11PM -0700, Linus Torvalds wrote:\n> \n> > Have you compared the results? IOW, does it find the *same* renames?\n> \n> From my limited testing, it generally finds the same pairs. However,\n> there are a number of renames that it _doesn't_ find, because they are\n> composed of \"uninteresting\" lines, dropping them below the minimum\n> score. Try (in git.git):\n> \n>   git-show --raw -M -l0 :/'Big tool rename'\n> \n> with the old and new code. Pairs like Documentation/git-add-script.txt\n> -> Documentation/git-add.txt are not found, because the file is composed\n> almost entirely of boilerplate.\n\nOk, that does imply to me that we cannot just drop boilerplate text, \nbecause the fact is, lots of files contain boilerplate, but people still \nthink they are \"similar\".\n\nWe do actually depend on the similarity analysis being \"good\" - because it \nmatters a lot for things like merging. The old code was actually very \ncareful indeed, and while it didn't care about things like the exact \n*ordering* of lines (ie moving functions around in the same file resulted \nin the *exact* same fingerprint for the file!) it cared about everything \nelse.\n\n> Moving the size normalization into the similarity engine should probably\n> fix that, and will let us compare old and new results more accurately.\n> I'll try to work on that.\n\nHmm. I hope that is sufficient. But I suspect it may well not be. \nEspecially since you ignore boiler-plate lines for *some* files but not \nothers (ie it depends on which file you happen to find it in first).\n\n\t\t\tLinus\n"},{"id":"57614","messageId":"20071030202014.GA22733@coredump.intra.peff.net","threadId":"10521","inReplyTo":"alpine.LFD.0.999.0710300818390.30120@woody.linux-foundation.org","subject":"Re: [PATCH/RFC 0/3] faster inexact rename handling","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-30T20:20:14Z","receivedAt":"2007-10-30T20:20:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 30, 2007 at 08:38:24AM -0700, Linus Torvalds wrote:\n\n> > with the old and new code. Pairs like Documentation/git-add-script.txt\n> > -> Documentation/git-add.txt are not found, because the file is composed\n> > almost entirely of boilerplate.\n> \n> Ok, that does imply to me that we cannot just drop boilerplate text, \n> because the fact is, lots of files contain boilerplate, but people still \n> think they are \"similar\".\n\nWell, the problem is that instead of just \"dropping\" boilerplate text,\nwe fail to count it as a similarity, but it still counts towards the\nfile size. It may be that just dropping it totally is the right thing\n(in which case those renames _will_ turn up, because they will be filled\nwith identical non-boilerplate goodness).\n\n> Hmm. I hope that is sufficient. But I suspect it may well not be. \n> Especially since you ignore boiler-plate lines for *some* files but not \n> others (ie it depends on which file you happen to find it in first).\n\nYes, that part bothers me a little, so I think a \"too common, ignore\"\noverflow flag would at least be better.\n\nBut I think the best thing to do now is for me to shut up and see what\nthe results look like with the tweaks I have mentioned.\n\n-Peff\n"},{"id":"57618","messageId":"alpine.LFD.0.999.0710301338260.30120@woody.linux-foundation.org","threadId":"10521","inReplyTo":"20071030202014.GA22733@coredump.intra.peff.net","subject":"Re: [PATCH/RFC 0/3] faster inexact rename handling","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-30T20:39:45Z","receivedAt":"2007-10-30T20:39:45Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 30 Oct 2007, Jeff King wrote:\n> \n> Well, the problem is that instead of just \"dropping\" boilerplate text,\n> we fail to count it as a similarity, but it still counts towards the\n> file size. It may be that just dropping it totally is the right thing\n> (in which case those renames _will_ turn up, because they will be filled\n> with identical non-boilerplate goodness).\n\nYeah, you may well be right, and the normalization of the scores will just \nsolve things.\n\n\t\t\tLinus\n"},{"id":"57630","messageId":"596909b30710301706u78a326a4y88afac92f1480cec@mail.gmail.com","threadId":"10521","inReplyTo":"20071030042118.GA14729@sigill.intra.peff.net","subject":"Re: [PATCH/RFC 0/3] faster inexact rename handling","fromName":"Andy C","fromEmail":"andychup@gmail.com","sentAt":"2007-10-31T00:06:02Z","receivedAt":"2007-10-31T00:06:02Z","isPatch":true,"sender":{"key":"andychup@gmail.com","avatar":null},"body":"Sorry I have been AWOL... I was going to try to work on this, but I\ngot abjectly sick (long story).  But it's great to see this out.\n\n\nOn 10/29/07, Jeff King <peff@peff.net> wrote:\n> This is my first stab at faster rename handling based on Andy's code.\n> The patches are on top of next (to get Linus' recent work on exact\n> renames). Most of the interesting stuff is in 2/3.\n>\n>   1/3: extension of hash interface\n>   2/3: similarity detection code\n>   3/3: integrate similarity detection into diffcore-rename\n>\n> The implementation is pretty basic, so I think there is room for\n> code optimization (50% of the time is spent in hash lookups, so we might\n> be able to micro-optimize that) as well as algorithmic improvements (like the\n> sampling Andy mentioned).\n\nFor microoptimization, I was thinking that the hash tables could be\nimplemented without pointers per value (or memory allocation per\nvalue), so everything is in a contiguous block of memory.   In C++ you\ncan do this trivially by declaring a small struct as the second\ntemplate parameter of the container; in C I guess you can simulate it\nwith a macro or something.\n\nFor the inverted indexing step, the values in the hash are going to be\nquite small, especially if line_threshold=1.  Then you only need 2\nintegers for the left side and right side == 4 integers.  The integers\ncould just be indexes into the lists (like the current code uses).\n\nFor the count matrix step, the values are just going to be integers,\nso storing it right in the hash table makes sense.\n\nThe sampling should be only necessary for binary files, I think.\n\n\n> With these patches, I can get my monster binary diff down from about 2\n> minutes to 17 seconds. And comparing all of linux-2.4 to all of\n> linux-2.6 (similar to Andy's previous demo) takes about 10 seconds.\n\nHopefully that should be close to just reading the files off disk.\nThe algorithm should take a fraction of the time that simply reading\nthe files does, which presumably a git diff has to do.\n\nI was timing that by comparing it to doing a \"| xargs wc -l\" on the\nlists of files.\n\n\n> There are a few downsides:\n>   - the current implementation tends to give lower similarity values\n>     compared to the old code (see discussion in 2/3), but this should be\n>     tweakable\n>   - on large datasets, it's more memory hungry than the old code because\n>     the hash grows very large. This can be helped by bumping up the\n>     binary chunk size (actually, the 17 seconds quoted above is using\n>     256-byte chunks rather than 64-byte -- with 64-byte chunks, it's\n>     more like 24 seconds) as well as sampling.\n>   - no improvement on smaller datasets. Running \"git-whatchanged -M\n>     --raw -l0\" on the linux-2.6 repo takes about the same time with the\n>     old and new code (presumably the algorithmic savings of the new code\n>     are lost in a higher constant factor, so when n is small, it is a\n>     wash).\n\nI think the old code tries to respect the cache as much as possible,\nfrom what I can tell.  The new code has to use hash tables which are\nunpredictable of course.  Though for smaller data sets I would expect\nthe hash table to fit in cache.  What's your definition of small here?\n Are you sure the old code isn't triggering one of the limits that was\nthere?\n\nthanks,\nAndy\n"},{"id":"57633","messageId":"596909b30710301727o72770d51jfa519d858203480f@mail.gmail.com","threadId":"10521","inReplyTo":"20071030202014.GA22733@coredump.intra.peff.net","subject":"Re: [PATCH/RFC 0/3] faster inexact rename handling","fromName":"Andy C","fromEmail":"andychup@gmail.com","sentAt":"2007-10-31T00:27:10Z","receivedAt":"2007-10-31T00:27:10Z","isPatch":true,"sender":{"key":"andychup@gmail.com","avatar":null},"body":"On 10/30/07, Jeff King <peff@peff.net> wrote:\n> On Tue, Oct 30, 2007 at 08:38:24AM -0700, Linus Torvalds wrote:\n>\n> > > with the old and new code. Pairs like Documentation/git-add-script.txt\n> > > -> Documentation/git-add.txt are not found, because the file is composed\n> > > almost entirely of boilerplate.\n> >\n> > Ok, that does imply to me that we cannot just drop boilerplate text,\n> > because the fact is, lots of files contain boilerplate, but people still\n> > think they are \"similar\".\n>\n> Well, the problem is that instead of just \"dropping\" boilerplate text,\n> we fail to count it as a similarity, but it still counts towards the\n> file size. It may be that just dropping it totally is the right thing\n> (in which case those renames _will_ turn up, because they will be filled\n> with identical non-boilerplate goodness).\n\nRight, in the demo I make an extra pass after the inverted indexing\nstep to prune the index -- which means eliminating the common lines\n*entirely* from the index (so they don't get attributed to a random\nfile) *and* decrementing all the file sizes by 1.  That way the\nsimilarity scores shouldn't get skewed.\n\nAnd as you mentioned we could bump the threshold from 1 to some other\nsmall integer.  Intuitively I guess you could say it is common to copy\na file to 2 places or 3 places, and you don't want all the lines to\nget thrown out because of that.  But usually you don't copy a file to\n10 or 50 places.\n\nAndy\n"}]}