{"thread":{"id":"10463","subject":"[PATCH 2/6] Split out \"exact content match\" phase of rename detection","startedAt":"2007-10-25T18:15:16Z","lastAt":"2007-10-26T23:36:10Z","messageCount":18,"participants":["Linus Torvalds","Jeff King","Daniel Barkalow","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"57212","messageId":"alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":null,"subject":"[PATCH 0/6] Cleaned-up rename detection patch-series","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-25T18:15:16Z","receivedAt":"2007-10-25T18:15:16Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOk, here's the patch-series to do rename detection of exact renames in \nlinear time, except it's cleaned up into a nice series of 6 patches. The \nend result is identical to the previous patches (which got smushed down \ninto just two patches in Junio's tree), apart from a fixed dependency in \nthe Makefile that caused me grief and a broken test-suite due to some \nobject files simply not being correctly recompiled.\n\nThe end result should be more understandable this way.\n\n\t\tLinus\n"},{"id":"57216","messageId":"alpine.LFD.0.999.0710251115250.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org","subject":"[PATCH 1/6] Add 'diffcore.h' to LIB_H","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-25T18:16:50Z","receivedAt":"2007-10-25T18:16:50Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nSubject: [PATCH 1/6] Add 'diffcore.h' to LIB_H\n\nThe diffcore.h header file is included by more than just the internal\ndiff generation files, and needs to be part of the proper dependencies.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nThis caused me pain.\n\nI spent way too much time trying to debug something that wasn't buggy to \nbegin with (which made it really hard to see the bug ;).\n\nWe really should have a proper (automatic) dependency generation phase. \nThis patch does *not* do that, it just fixes up the crappy stuff we have \nnow.\n\n Makefile |    3 +--\n 1 files changed, 1 insertions(+), 2 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex b728920..8a0082d 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -290,7 +290,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 transport.h\n+\tmailmap.h remote.h transport.h diffcore.h\n \n DIFF_OBJS = \\\n \tdiff.o diff-lib.o diffcore-break.o diffcore-order.o \\\n@@ -917,7 +917,6 @@ git-http-push$X: revision.o http.o http-push.o $(GITLIBS)\n \n $(LIB_OBJS) $(BUILTIN_OBJS): $(LIB_H)\n $(patsubst git-%$X,%.o,$(PROGRAMS)): $(LIB_H) $(wildcard */*.h)\n-$(DIFF_OBJS): diffcore.h\n \n $(LIB_FILE): $(LIB_OBJS)\n \t$(QUIET_AR)$(RM) $@ && $(AR) rcs $@ $(LIB_OBJS)\n-- \n1.5.3.4.330.g1dec6\n"},{"id":"57209","messageId":"alpine.LFD.0.999.0710251116570.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org","subject":"[PATCH 2/6] Split out \"exact content match\" phase of rename detection","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-25T18:17:55Z","receivedAt":"2007-10-25T18:17:55Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nSubject: [PATCH 2/6] Split out \"exact content match\" phase of rename detection\n\nThis makes the exact content match a separate function of its own.\nPartly to cut down a bit on the size of the diffcore_rename() function\n(which is too complex as it is), and partly because there are smarter\nways to do this than an O(m*n) loop over it all, and that function\nshould be rewritten to take that into account.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nThis is, I think, identical to the patch you already have. Feel free to \nskip this, and base the rest of the patch-series on your existing one.\n\n diffcore-rename.c |   90 +++++++++++++++++++++++++++++++++--------------------\n 1 files changed, 56 insertions(+), 34 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 142e537..2077a9b 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -262,6 +262,58 @@ static int compute_stays(struct diff_queue_struct *q,\n \treturn 1;\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+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -270,12 +322,11 @@ void diffcore_rename(struct diff_options *options)\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, contents_too;\n+\tint i, j, rename_count;\n \tint num_create, num_src, dst_cnt;\n \n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n-\trename_count = 0;\n \n \tfor (i = 0; i < q->nr; i++) {\n \t\tstruct diff_filepair *p = q->queue[i];\n@@ -318,40 +369,11 @@ 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/* We really want to cull the candidates list early\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 * The first round matches up the up-to-date entries,\n-\t * and then during the second round we try to match\n-\t * cache-dirty entries as well.\n \t */\n-\tfor (contents_too = 0; contents_too < 2; contents_too++) {\n-\t\tfor (i = 0; i < rename_dst_nr; i++) {\n-\t\t\tstruct diff_filespec *two = rename_dst[i].two;\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+\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-- \n1.5.3.4.330.g1dec6\n"},{"id":"57211","messageId":"alpine.LFD.0.999.0710251117590.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org","subject":"[PATCH 3/6] Ref-count the filespecs used by diffcore","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-25T18:19:10Z","receivedAt":"2007-10-25T18:19:10Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nSubject: [PATCH 3/6] Ref-count the filespecs used by diffcore\n\nRather than copy the refcounts when introducing new versions of them\n(for rename or copy detection), use a refcount and increment the count\nwhen reusing the diff_filespec.\n\nThis avoids unnecessary allocations, but the real reason behind this is\na future enhancement: we will want to track shared data across the\ncopy/rename detection.  In order to efficiently notice when a filespec\nis used by a rename, the rename machinery wants to keep track of a\nrename usage count which is shared across all different users of the\nfilespec.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nThis was sent out in the original series as a fix on top of broken code. \nNow it sets up the infrastructure so that the next patch won't be broken.\n\n diff.c            |   15 +++++++++++----\n diffcore-rename.c |   16 ++++++----------\n diffcore.h        |    2 ++\n 3 files changed, 19 insertions(+), 14 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex dfb8595..0b320f6 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@@ -2435,10 +2444,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 \ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 2077a9b..3da06b7 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -209,21 +209,19 @@ 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 \t\tdie(\"internal error: dst already matched.\");\n \n \tsrc = rename_src[src_index].one;\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@@ -526,10 +524,8 @@ void diffcore_rename(struct diff_options *options)\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);\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 eb618b1..30055ac 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 \tunsigned short mode;\t /* file mode */\n \tunsigned sha1_valid : 1; /* if true, use sha1 and trust mode;\n@@ -43,6 +44,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-- \n1.5.3.4.330.g1dec6\n"},{"id":"57213","messageId":"alpine.LFD.0.999.0710251119120.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org","subject":"[PATCH 4/6] copy vs rename detection: avoid unnecessary O(n*m) loops","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-25T18:20:56Z","receivedAt":"2007-10-25T18:20:56Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nSubject: [PATCH 4/6] copy vs rename detection: avoid unnecessary O(n*m) loops\n\nThe core rename detection had some rather stupid code to check if a\npathname was used by a later modification or rename, which basically\nwalked the whole pathname space for all renames for each rename, in\norder to tell whether it was a pure rename (no remaining users) or\nshould be considered a copy (other users of the source file remaining).\n\nThat's really silly, since we can just keep a count of users around, and\nreplace all those complex and expensive loops with just testing that\nsimple counter (but this all depends on the previous commit that shared\nthe diff_filespec data structure by using a separate reference count).\n\nNote that the reference count is not the same as the rename count: they\nbehave otherwise rather similarly, but the reference count is tied to\nthe allocation (and decremented at de-allocation, so that when it turns\nzero we can get rid of the memory), while the rename count is tied to\nthe renames and is decremented when we find a rename (so that when it\nturns zero we know that it was a rename, not a copy).\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nThis fixes the generic diffcode infrastructure, but doesn't do the actual \n*detection* any faster. But as you can tell, it's a huge cleanup on its \nown, and basically removes the \"incidental\" and stupid support costs of \nrename detection.\n\n diff.c            |   40 +++++++++++++------------------\n diffcore-rename.c |   68 +++++++++++++---------------------------------------\n diffcore.h        |    2 +-\n 3 files changed, 35 insertions(+), 75 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 0b320f6..af85b94 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -2597,9 +2597,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->one->rename_used, p->broken_pair);\n }\n \n void diff_debug_queue(const char *msg, struct diff_queue_struct *q)\n@@ -2617,8 +2617,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@@ -2640,27 +2640,21 @@ 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\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\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 (!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\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 3da06b7..edb2424 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -55,12 +55,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,7 +90,6 @@ 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@@ -216,6 +213,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 \tsrc->count++;\n \n \tdst = rename_dst[dst_index].two;\n@@ -227,7 +225,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@@ -245,21 +242,6 @@ 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-{\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-\t\t}\n-\t}\n-\treturn 1;\n-}\n-\n /*\n  * Find exact renames first.\n  *\n@@ -338,15 +320,25 @@ 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\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\tint stays = (p->broken_pair && !p->score);\n-\t\t\tregister_rename_src(p->one, stays, p->score);\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@@ -472,16 +464,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@@ -507,23 +490,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\tfree_filespec(rename_dst[i].two);\n \ndiff --git a/diffcore.h b/diffcore.h\nindex 30055ac..cc96c20 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -31,6 +31,7 @@ struct diff_filespec {\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 \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@@ -58,7 +59,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;\n-- \n1.5.3.4.330.g1dec6\n"},{"id":"57217","messageId":"alpine.LFD.0.999.0710251120590.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org","subject":"[PATCH 5/6] Do linear-time/space rename logic for exact renames","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-25T18:23:26Z","receivedAt":"2007-10-25T18:23:26Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nSubject: [PATCH 5/6] Do linear-time/space rename logic for exact renames\n\nThis implements a smarter rename detector for exact renames, which\nrather than doing a pairwise comparison (time O(m*n)) will just hash the\nfiles into a hash-table (size O(n+m)), and only do pairwise comparisons\nto renames that have the same hash (time O(n+m) except for unrealistic\nhash collissions, which we just cull aggressively).\n\nAdmittedly the exact rename case is not nearly as interesting as the\ngeneric case, but it's an important case none-the-less.A similar general\napproach should work for the generic case too, but even then you do need\nto handle the exact renames/copies separately (to avoid the inevitable\nadded cost factor that comes from the _size_ of the file), so this is\nworth doing.\n\nIn the expectation that we will indeed do the same hashing trick for the\ngeneral rename case, this code uses a generic hash-table implementation\nthat can be used for other things too.  In fact, we might be able to\nconsolidate some of our existing hash tables with the new generic code\nin hash.[ch].\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nThis is obviously the actual meat of the new exact rename detection: \neverything else was just leading up to this.\n\nI could have split out \"hash.[ch]\" as a separate patch just to introduce \nthe infrastructure, but I hate patches that add code that isn't used at \nall. But hash.[ch] really is potentially independently useful, and has \nnothing that is specific to the rename detection per se in it.\n\n Makefile          |    4 +-\n diffcore-rename.c |  211 +++++++++++++++++++++++++++++++++++++----------------\n hash.c            |  110 +++++++++++++++++++++++++++\n hash.h            |   43 +++++++++++\n 4 files changed, 303 insertions(+), 65 deletions(-)\n create mode 100644 hash.c\n create mode 100644 hash.h\n\ndiff --git a/Makefile b/Makefile\nindex 8a0082d..845f811 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -290,7 +290,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 transport.h diffcore.h\n+\tmailmap.h remote.h transport.h diffcore.h hash.h\n \n DIFF_OBJS = \\\n \tdiff.o diff-lib.o diffcore-break.o diffcore-order.o \\\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 \\\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 edb2424..e7e370b 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@@ -93,29 +94,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@@ -242,56 +220,163 @@ static int score_compare(const void *a_, const void *b_)\n \treturn b->score - a->score;\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+\n+\t/*\n+\t * Walk over all the destinations ...\n+\t */\n+\tdo {\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 = src; p; p = p->next) {\n+\t\t\tstruct diff_filespec *two = p->filespec;\n+\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+\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\trecord_rename_pair(dst->index, best->index, MAX_SCORE);\n+\t\t\trenames++;\n+\t\t}\n+\t} while ((dst = dst->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+}\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+\tint i;\n+\tstruct hash_table file_table;\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+\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)\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..a8b0fbb\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-- \n1.5.3.4.330.g1dec6\n"},{"id":"57215","messageId":"alpine.LFD.0.999.0710251123280.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org","subject":"[PATCH 6/6] Do exact rename detection regardless of rename limits","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-25T18:24:47Z","receivedAt":"2007-10-25T18:24:47Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nSubject: [PATCH 6/6] Do exact rename detection regardless of rename limits\n\nNow that the exact rename detection is linear-time (with a very small\nconstant factor to boot), there is no longer any reason to limit it by\nthe number of files involved.\n\nIn some trivial testing, I created a repository with a directory that\nhad a hundred thousand files in it (all with different contents), and\nthen moved that directory to show the effects of renaming 100,000 files.\n\nWith the new code, that resulted in\n\n\t[torvalds@woody big-rename]$ time ~/git/git show -C | wc -l\n\t400006\n\n\treal    0m2.071s\n\tuser    0m1.520s\n\tsys     0m0.576s\n\nie the code can correctly detect the hundred thousand renames in about 2\nseconds (the number \"400006\" comes from four lines for each rename:\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\nMost of those two seconds weren't even really the rename detection, it's\nreally all the other stuff needed to get there.\n\nWith the old code, this wouldn't have been practically possible.  Doing\na pairwise check of the ten billion possible pairs would have been\nprohibitively expensive.  In fact, even with the rename limiter in\nplace, the old code would waste a lot of time just on the diff_filespec\nchecks, and despite not even trying to find renames, it used to look\nlike:\n\n\t[torvalds@woody big-rename]$ time git show -C | wc -l\n\t1400006\n\n\treal    0m12.337s\n\tuser    0m12.285s\n\tsys     0m0.192s\n\nie we used to take 12 seconds for this load and not even do any rename\ndetection! (The number 1400006 comes from fourteen lines per file moved:\nseven lines each for the delete and the create of a one-liner file, and\nthe same extra six lines of commit information).\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nThis obviously just moves the rename detection call. It made sense as a \nseparate patch largely because of the explanation that goes along with it, \nbut it conceptually is very different from actually improving the rename \ndetection logic itself. So it got a patch of its own.\n\n diffcore-rename.c |   12 ++++++------\n 1 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e7e370b..3946932 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -429,6 +429,12 @@ void diffcore_rename(struct diff_options *options)\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@@ -444,12 +450,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-- \n1.5.3.4.330.g1dec6\n"},{"id":"57220","messageId":"alpine.LFD.0.999.0710251126490.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org","subject":"Re: [PATCH 0/6] Cleaned-up rename detection patch-series","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-25T18:37:08Z","receivedAt":"2007-10-25T18:37:08Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nFinal notes:\n\n - all of these were done on top of the current 'master' branch.  Not that \n   it likely matters much, but I thought I'd mention it in case there are \n   conflicts with anything currently cooking in 'next'. I didn't even \n   check.\n\n - The commits depend on each other, but apart from the ordering, they all \n   stand on their own. They pass the test-suite at all stages.\n\n - In particular, the first four commits are cleanups and infrastructure \n   that really is totally independent of the last two. I'd argue that the \n   first one (the dependency fix) could/should be merged into stable, and \n   the next three can probably be merged more aggressively than the last \n   two.\n\n - I *think* this series is good to go. I've used the new rename detection \n   code in my own \"production\" environment (ie the kernel) since sending \n   it out, and the end result of all these patches is identical - apart \n   from the the dependency fix - to what I've been running for the last \n   week. But maybe it makes more sense to merge the first four into \n   'next', and leave the last two in 'pu', for example (or 'master' and \n   'next' respectively, depending on how comfy people are with the \n   patches).\n\nSplitting the thing up definitely makes the series more readable, and \nmaybe that means that somebody will actually comment on it. I don't think \nI got any comments on the original series once I fixed the stupid bugs. \nHopefully the cleaner series is more amenable to people reviewing it.\n\n\t\t\tLinus\n"},{"id":"57222","messageId":"20071025190840.GC27620@coredump.intra.peff.net","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org","subject":"Re: [PATCH 0/6] Cleaned-up rename detection patch-series","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-25T19:08:40Z","receivedAt":"2007-10-25T19:08:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 25, 2007 at 11:15:16AM -0700, Linus Torvalds wrote:\n\n> Ok, here's the patch-series to do rename detection of exact renames in \n> linear time, except it's cleaned up into a nice series of 6 patches. The \n> end result is identical to the previous patches (which got smushed down \n> into just two patches in Junio's tree), apart from a fixed dependency in \n> the Makefile that caused me grief and a broken test-suite due to some \n> object files simply not being correctly recompiled.\n\nThanks, I have been basing my inexact rename work off of your messy\npatches, so I will rebase onto this.\n\nSorry I am lagging behind on getting that work out, but I hope to have\nsomething to show soon.\n\n-Peff\n"},{"id":"57223","messageId":"Pine.LNX.4.64.0710251522190.7345@iabervon.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251120590.30120@woody.linux-foundation.org","subject":"Re: [PATCH 5/6] Do linear-time/space rename logic for exact renames","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2007-10-25T19:43:46Z","receivedAt":"2007-10-25T19:43:46Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"> +/*\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\nCreating a list of the pointers doesn't work correctly with the grow \nimplementation, because growing the hash may turn a collision into a \nnon-collision, at which point items other than the first cannot be found \n(since they're listed inside a bucket that's now wrong for them). AFAIK, \nresizing a hash table requires being able to figure out what happened with \ncollisions.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"57225","messageId":"20071025194859.GB27745@coredump.intra.peff.net","threadId":"10463","inReplyTo":"Pine.LNX.4.64.0710251522190.7345@iabervon.org","subject":"Re: [PATCH 5/6] Do linear-time/space rename logic for exact renames","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-10-25T19:48:59Z","receivedAt":"2007-10-25T19:48:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 25, 2007 at 03:43:46PM -0400, Daniel Barkalow wrote:\n\n> Creating a list of the pointers doesn't work correctly with the grow \n> implementation, because growing the hash may turn a collision into a \n> non-collision, at which point items other than the first cannot be found \n> (since they're listed inside a bucket that's now wrong for them). AFAIK, \n> resizing a hash table requires being able to figure out what happened with \n> collisions.\n\nI thought this at first, too, but there are two types of collisions in\nthis hash implementation: those that come from having the actual 32-bit\nhash collide, and those that come from not having enough buckets.\n\nThe client code gets a pointer kicked back to it when there is a\ncollision on the actual hash value (i.e., two things had the exact same\nhash value). The number of buckets grows when you simply have more\nbuckets filled than you like. Two different hashes that would be in the\nsame bucket don't actually occupy the same bucket -- the second one to\narrive gets shoved into the next available bucket.\n\n-Peff\n"},{"id":"57232","messageId":"Pine.LNX.4.64.0710251606280.7345@iabervon.org","threadId":"10463","inReplyTo":"20071025194859.GB27745@coredump.intra.peff.net","subject":"Re: [PATCH 5/6] Do linear-time/space rename logic for exact renames","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2007-10-25T20:23:37Z","receivedAt":"2007-10-25T20:23:37Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Thu, 25 Oct 2007, Jeff King wrote:\n\n> On Thu, Oct 25, 2007 at 03:43:46PM -0400, Daniel Barkalow wrote:\n> \n> > Creating a list of the pointers doesn't work correctly with the grow \n> > implementation, because growing the hash may turn a collision into a \n> > non-collision, at which point items other than the first cannot be found \n> > (since they're listed inside a bucket that's now wrong for them). AFAIK, \n> > resizing a hash table requires being able to figure out what happened with \n> > collisions.\n> \n> I thought this at first, too, but there are two types of collisions in\n> this hash implementation: those that come from having the actual 32-bit\n> hash collide, and those that come from not having enough buckets.\n> \n> The client code gets a pointer kicked back to it when there is a\n> collision on the actual hash value (i.e., two things had the exact same\n> hash value). The number of buckets grows when you simply have more\n> buckets filled than you like. Two different hashes that would be in the\n> same bucket don't actually occupy the same bucket -- the second one to\n> arrive gets shoved into the next available bucket.\n\nAh, right, nevermind. The comment might be a bit misleading in that case, \nif we both missed this at first.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"57234","messageId":"alpine.LFD.0.999.0710251317020.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"Pine.LNX.4.64.0710251522190.7345@iabervon.org","subject":"Re: [PATCH 5/6] Do linear-time/space rename logic for exact renames","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-25T20:25:34Z","receivedAt":"2007-10-25T20:25:34Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 25 Oct 2007, Daniel Barkalow wrote:\n> \n> Creating a list of the pointers doesn't work correctly with the grow \n> implementation, because growing the hash may turn a collision into a \n> non-collision, at which point items other than the first cannot be found \n> (since they're listed inside a bucket that's now wrong for them). AFAIK, \n> resizing a hash table requires being able to figure out what happened with \n> collisions.\n\nNope. \n\nThe hash algorithm is much smarter than that.\n\nI *always* uses a full 32-bit hash, and no amount of resizing is ever \ngoing to change that. The index into the hash-table is in fact entirely \nunused.\n\nThis has several good properties:\n\n - it means that hash-table resizing is a non-event\n\n - it means that you always have the full 32-bit hash, and a collision in \n   the hash size never causes unnecessary work apart from the fact that \n   the code walks the hash table a bit more.\n\n - because the hash is embedded in the table itself, it has relatively \n   good cache behaviour when compared to something that needs to actually \n   follow the pointer to validate the full data. So assuming that the full \n   32-bit hash is good enough to effectively never have any collisions \n   (or, assuming you don't even *care* about the collisions, which is the \n   case when you're just generating content fingerprints for lines when \n   comparing the data in two files), you never end up with unnecessarily \n   following pointers to cachelines that you are not interested in.\n\nThe last point at least somewhat mitigates the (inevitably) bad cache \nbehaviour that hash tables tend to have. It's not like it's going to be \nwonderful in the cache, but at least it's less horrid than the more common \nimplementation that needs to follow the pointer to validate each hash \nentry that may or may not be a collision.\n\nbut the important part is #1, which is what allows the code to be a \ngeneric hash algorithm that resizes the hash table without even \nunderstanding or caring what is behind the pointer.\n\n\t\tLinus\n"},{"id":"57242","messageId":"Pine.LNX.4.64.0710251722290.7345@iabervon.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251317020.30120@woody.linux-foundation.org","subject":"Re: [PATCH 5/6] Do linear-time/space rename logic for exact renames","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2007-10-25T21:37:07Z","receivedAt":"2007-10-25T21:37:07Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Thu, 25 Oct 2007, Linus Torvalds wrote:\n\n> On Thu, 25 Oct 2007, Daniel Barkalow wrote:\n> > \n> > Creating a list of the pointers doesn't work correctly with the grow \n> > implementation, because growing the hash may turn a collision into a \n> > non-collision, at which point items other than the first cannot be found \n> > (since they're listed inside a bucket that's now wrong for them). AFAIK, \n> > resizing a hash table requires being able to figure out what happened with \n> > collisions.\n> \n> Nope. \n> \n> The hash algorithm is much smarter than that.\n\nAh, yes. I was just confused by the comment suggesting the possibility of \na collision when the only way to have two calls get the same bucket is \nwhen the key that the library gets is actually identical.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"57312","messageId":"7vabq5wkri.fsf@gitster.siamese.dyndns.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710251119120.30120@woody.linux-foundation.org","subject":"Re: [PATCH 4/6] copy vs rename detection: avoid unnecessary O(n*m) loops","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-10-26T22:53:21Z","receivedAt":"2007-10-26T22:53:21Z","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> @@ -2640,27 +2640,21 @@ 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/*\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 (!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>  \t\t}\n>  \t\telse if (hashcmp(p->one->sha1, p->two->sha1) ||\n\nThe interaction between the above and ...\n\n> @@ -338,15 +320,25 @@ 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/*\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\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}\n>  \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n>  \t\tgoto cleanup; /* nothing to do */\n\n... this part feels a bit too subtle for a still-jet-lagged\nbrain to grok.  I wonder what happens if the preimage of a\nbroken pair is used as the rename source for more than two\npostimages.\n"},{"id":"57314","messageId":"alpine.LFD.0.999.0710261600510.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"7vabq5wkri.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 4/6] copy vs rename detection: avoid unnecessary O(n*m) loops","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-26T23:10:09Z","receivedAt":"2007-10-26T23:10:09Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 26 Oct 2007, Junio C Hamano wrote:\n\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n> \n> > @@ -2640,27 +2640,21 @@ 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/*\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 (!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> >  \t\t}\n> >  \t\telse if (hashcmp(p->one->sha1, p->two->sha1) ||\n> \n> The interaction between the above and ...\n\nHeh.\n\nI'm pretty sure it's right, because:\n\n> > @@ -338,15 +320,25 @@ 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/*\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\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}\n> >  \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n> >  \t\tgoto cleanup; /* nothing to do */\n> \n> ... this part feels a bit too subtle for a still-jet-lagged\n> brain to grok.  I wonder what happens if the preimage of a\n> broken pair is used as the rename source for more than two\n> postimages.\n\nThe nice thing about the whole counting thing is that we really don't even \ncare. What happens is:\n\n - *if* any rename at all happens, the rename detection will increment the \n   \"rename_used\" thing even more for the source (once for each rename)\n\n - so if the rename_used started out non-zero, it will never become zero \n   in diff_resolve_rename_copy(), and every single detected \"rename\" will \n   be considered a copy - exactly like we want.\n\n - in other words, a \"rename_used++\" before rename-detection guarantees \n   that you never see a rename, only a copy of the source.\n\nThe above is actually true *even*if* the \n\n\tif (!strcmp(p->one->path, p->two->path))\n\ncode in diff_resolve_rename_copy() actually triggers, so we could have \n(and at one point I did) done the \"--p->one->rename_used > 0\" test before \nthe strcmp() test, and it would all continue to work fine. However, the \nreason that I put the strcmp() first is that it needs to be done whether \nwe decide to consider it a \"copy\" or a \"rename\" (so we cannot avoid it \nanyway), and *if* it triggers, we actually want to avoid the rename_used \ngoing down to zero anyway (not that it would, because I think it's bound \nto be one of the cases where we pre-incremented the count), so not doing \nthe decrement there is equivalent to doing another pre-increment.\n\nSo I think it's all right, and more obviously right than it used to be. \nBut hey, it's possible that I missed something.\n\n\t\tLinus\n"},{"id":"57317","messageId":"7vy7dpv4ls.fsf@gitster.siamese.dyndns.org","threadId":"10463","inReplyTo":"alpine.LFD.0.999.0710261600510.30120@woody.linux-foundation.org","subject":"Re: [PATCH 4/6] copy vs rename detection: avoid unnecessary O(n*m) loops","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-10-26T23:27:43Z","receivedAt":"2007-10-26T23:27:43Z","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> The nice thing about the whole counting thing is that we really don't even \n> care. What happens is:\n>\n>  - *if* any rename at all happens, the rename detection will increment the \n>    \"rename_used\" thing even more for the source (once for each rename)\n>\n>  - so if the rename_used started out non-zero, it will never become zero \n>    in diff_resolve_rename_copy(), and every single detected \"rename\" will \n>    be considered a copy - exactly like we want.\n>\n>  - in other words, a \"rename_used++\" before rename-detection guarantees \n>    that you never see a rename, only a copy of the source.\n\nOk, and that is because we _know_ a broken pair means that the\npath itself remains in the postimage and any other postimage\nthat takes from its preimage can never \"rename the path away\".\nThey can only be copies.  Which makes sense.\n\n> The above is actually true *even*if* the \n>\n> \tif (!strcmp(p->one->path, p->two->path))\n>\n> code in diff_resolve_rename_copy() actually triggers,...\n> ..., so not doing \n> the decrement there is equivalent to doing another pre-increment.\n\nYes, this is what confused me.  So for a broken pair, the actual\nvalue of rename_used does not really matter.  We only care about\nit not going down to zero.\n"},{"id":"57319","messageId":"alpine.LFD.0.999.0710261633090.30120@woody.linux-foundation.org","threadId":"10463","inReplyTo":"7vy7dpv4ls.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 4/6] copy vs rename detection: avoid unnecessary O(n*m) loops","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-26T23:36:10Z","receivedAt":"2007-10-26T23:36:10Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 26 Oct 2007, Junio C Hamano wrote:\n> \n> So for a broken pair, the actual value of rename_used does not really \n> matter.  We only care about it not going down to zero.\n\nCorrect. The rename_used count really is immaterial *except* for the magic \ndistinction between zero (\"it's a rename, no original source file left\") \nand non-zero (\"it's a copy, original source file remains\").\n\nWhich is why the new counter is so fundamentally simple: by decrementing \nit for each rename we encounter, we automatically get that behaviour of \n\"only the last user turns into a 'rename' if the source file really went \naway\" that we want. \n\nThe old code did it all with some really expensive loops over the \nremaining renames.\n\n\t\tLinus\n"}]}