{"thread":{"id":"54772","subject":"[PATCH 4/7] diffcore-rename: change a few comments to use 'add' instead of 'create'","startedAt":"2020-12-06T04:05:19Z","lastAt":"2021-11-11T16:19:56Z","messageCount":55,"participants":["Elijah Newren via GitGitGadget","Elijah Newren","Taylor Blau","Junio C Hamano","Christian Couder","Ævar Arnfjörð Bjarmason","Başar Uğur"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"411545","messageId":"77ca4656ed442321b41e653505c85d0be31b8045.1607223276.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","subject":"[PATCH 4/7] diffcore-rename: change a few comments to use 'add' instead of 'create'","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-06T02:54:33Z","receivedAt":"2020-12-06T04:05:19Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAs with the last commit, it feels odd to talk about \"creation\" (which to\nme implies a brand new file, i.e. one not associated with an existing\nfile, and thus one that could not have been a rename) when we are using\nthe files to look for renames. Use the term \"addition\" instead.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 655a67759c8..7270eb6af48 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -173,7 +173,7 @@ static int estimate_similarity(struct repository *r,\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 * at a newly added 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@@ -652,9 +652,9 @@ void diffcore_rename(struct diff_options *options)\n \t\t}\n \t\telse if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {\n \t\t\t/*\n-\t\t\t * Creation\n+\t\t\t * Addition\n \t\t\t *\n-\t\t\t * We would output this create record if it has\n+\t\t\t * We would output this add record if it has\n \t\t\t * not been turned into a rename/copy already.\n \t\t\t */\n \t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->two);\n@@ -664,7 +664,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t}\n \t\t\telse\n \t\t\t\t/* no matching rename/copy source, so\n-\t\t\t\t * record this as a creation.\n+\t\t\t\t * record this as an addition.\n \t\t\t\t */\n \t\t\t\tdiff_q(&outq, p);\n \t\t}\n-- \ngitgitgadget\n\n"},{"id":"411546","messageId":"f96bb36930a6e5e42f0d3b9c5dfa3b2cc27c1f9d.1607223276.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","subject":"[PATCH 2/7] diffcore-rename: remove unnecessary if-clause","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-06T02:54:31Z","receivedAt":"2020-12-06T04:06:57Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ndiffcore-rename had two different checks of the form\n\n if ((a < limit || b < limit) &&\n a * b <= limit * limit)\n\nSince these are all non-negative integers, this can be simplified to\n\n if (a * b <= limit * limit)\n\nThe only advantage of the former would be in avoiding a couple\nmultiplications in the rare case that both a and b are BOTH very large.\nI see no reason for such an optimization given that this code is not in\nany kind of loop. Prefer code simplicity here and change to the latter\nform.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 10 ++++------\n 1 file changed, 4 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 68ddf51a2a1..0f8fce9293e 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -450,9 +450,8 @@ static int too_many_rename_candidates(int num_targets, int num_sources,\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n-\tif ((num_targets <= rename_limit || num_sources <= rename_limit) &&\n-\t ((uint64_t)num_targets * (uint64_t)num_sources\n-\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n+\tif ((uint64_t)num_targets * (uint64_t)num_sources\n+\t <= (uint64_t)rename_limit * (uint64_t)rename_limit)\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n@@ -468,9 +467,8 @@ static int too_many_rename_candidates(int num_targets, int num_sources,\n \t\t\tcontinue;\n \t\tlimited_sources++;\n \t}\n-\tif ((num_targets <= rename_limit || limited_sources <= rename_limit) &&\n-\t ((uint64_t)num_targets * (uint64_t)limited_sources\n-\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n+\tif ((uint64_t)num_targets * (uint64_t)limited_sources\n+\t <= (uint64_t)rename_limit * (uint64_t)rename_limit)\n \t\treturn 2;\n \treturn 1;\n }\n-- \ngitgitgadget\n\n"},{"id":"411547","messageId":"CABPp-BEEzW1U1p=+XGd7pz_jRpph5PjYShsqd5ZuFiKkryATNQ@mail.gmail.com","threadId":"54772","inReplyTo":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/7] diffcore-rename improvements","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-06T03:01:52Z","receivedAt":"2020-12-06T04:08:46Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi Christian, Kaartic, and Sangeeta,\n\nOn Sat, Dec 5, 2020 at 6:54 PM Elijah Newren via GitGitGadget\n wrote:\n>\n> This patch series include 4 small code cleanups, 1 small bug fix (or perhaps\n> just a UI improvement -- it's a very minor issue either way), and 2\n> performance improvements. The first 6 patches are relatively easy to review,\n> while the last one...is a bit more involved (but provided the biggest\n> performance boost).\n\nIf I've heard correctly, you three are now interested in rename\ndetection and thus diffcore-rename.c. You might find this patch\nseries interesting; even if you don't want to review the details, just\nlooking over some of the commit messages might help orient you to the\ncodebase that you'll be working with in the upcoming months.\n"},{"id":"411548","messageId":"3e83b51628b6f3aeb71c5e637eca03dd63f9e95f.1607223276.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","subject":"[PATCH 7/7] Accelerate rename_dst setup","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-06T02:54:36Z","receivedAt":"2020-12-06T04:09:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nregister_rename_src() simply references the passed pair inside\nrename_src. In contrast, add_rename_dst() did something entirely\ndifferent for rename_dst. Instead of copying the passed pair, it made a\ncopy of the second diff_filespec from the passed pair, referenced it,\nand then set the diff_rename_dst.pair field to NULL. Later, when a\npairing is found, record_rename_pair() allocated a full diff_filepair\nvia diff_queue() and pointed its src and dst fields at the appropriate\ndiff_filespecs. This contrast between register_rename_src() for the\nrename_src data structure and add_rename_dst() for the rename_dst data\nstructure is oddly inconsistent and requires more memory and work than\nnecessary. Let's just reference the original diff_filepair in\nrename_dst as-is, just as we do with rename_src. Add a new\nrename_dst.is_rename field, since the rename_dst.p field is never NULL\nunlike the old rename_dst.pair field.\n\nTaking advantage of this change and the fact that same-named paths will\nbe adjacent, we can get rid of the sorting of the array and most of the\nlookups on it, allowing us to instead just append as we go. However,\nthere is one remaining reason to still keep locate_rename_dst():\nhandling broken pairs (i.e. when break detection is on). Those are\nsomewhat rare, but we can set up a simple strintmap to get the map\nbetween the source and the index. Doing that allows us to still have a\nfast lookup without sorting the rename_dst array. Since the sorting had\nbeen done in a weakly quadratic manner, when many renames are involved\nthis time could add up.\n\nThere is still a strcmp() in add_rename_dst() that I feel is\nunnecessary, because I disagree with a regression test in t4058.\nHowever, I'm trying to increase performance without changing behavior,\nso I'll leave that fight for a different day (a TODO has been left in\nthe code about it).\n\nThis patch is being submitted in a different order than its original\ndevelopment, but in a large rebase of many commits with lots of renames\nand with several optimizations to inexact rename detection, both setup\ntime and write back to output queue time from diffcore_rename() were\nsizeable chunks of overall runtime. This patch accelerated the setup\ntime by about 65%, and final write back to the output queue time by\nabout 50%, resulting in an overall drop of 3.5% on the execution time of\nrebasing a few dozen patches.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 161 ++++++++++++++++++++++------------------------\n 1 file changed, 77 insertions(+), 84 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 816d2fbac44..fb3c2817c6b 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -5,67 +5,64 @@\n #include \"cache.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n-#include \"object-store.h\"\n #include \"hashmap.h\"\n+#include \"object-store.h\"\n #include \"progress.h\"\n #include \"promisor-remote.h\"\n+#include \"strmap.h\"\n \n /* Table of rename/copy destinations */\n \n static struct diff_rename_dst {\n-\tstruct diff_filespec *two;\n-\tstruct diff_filepair *pair;\n+\tstruct diff_filepair *p;\n+\tstruct diff_filespec *filespec_to_free;\n+\tint is_rename; /* false -> just a create; true -> rename or copy */\n } *rename_dst;\n static int rename_dst_nr, rename_dst_alloc;\n+/* Mapping from break source pathname to break destination index */\n+static struct strintmap *break_idx = NULL;\n \n-static int find_rename_dst(struct diff_filespec *two)\n-{\n-\tint first, last;\n-\n-\tfirst = 0;\n-\tlast = rename_dst_nr;\n-\twhile (last > first) {\n-\t\tint next = first + ((last - first) >> 1);\n-\t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n-\t\tint cmp = strcmp(two->path, dst->two->path);\n-\t\tif (!cmp)\n-\t\t\treturn next;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n-\treturn -first - 1;\n-}\n-\n-static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two)\n+static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)\n {\n-\tint ofs = find_rename_dst(two);\n-\treturn ofs < 0 ? NULL : &rename_dst[ofs];\n+\t/* Lookup by p->ONE->path */\n+\tint idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;\n+\treturn (idx == -1) ? NULL : &rename_dst[idx];\n }\n \n /*\n * Returns 0 on success, -1 if we found a duplicate.\n */\n-static int add_rename_dst(struct diff_filespec *two)\n+static int add_rename_dst(struct diff_filepair *p)\n {\n-\tint first = find_rename_dst(two);\n-\n-\tif (first >= 0)\n+\t/*\n+\t * See t4058; trees might have duplicate entries. I think\n+\t * trees with duplicate entries should be ignored and we\n+\t * should just leave rename detection on; while the results\n+\t * may be slightly harder to understand, that's merely a\n+\t * result of the underlying tree making no sense. But I\n+\t * believe everything still works fine, the results do still\n+\t * make sense, and the extra overhead of doing this checking\n+\t * for a few historical weird trees from long ago seems like\n+\t * the dog wagging the tail to me.\n+\t *\n+\t * However: I don't feel like fighting that battle right now.\n+\t * For now, to keep the regression test passing, we have to\n+\t * detect it. Since the diff machinery passes these to us in\n+\t * adjacent pairs, we just need to check to see if our name\n+\t * matches the previous one.\n+\t *\n+\t * TODO: Dispense with this test, rip out the test in t4058, and\n+\t * lobby folks for the change.\n+\t */\n+\tif (rename_dst_nr > 0 &&\n+\t !strcmp(rename_dst[rename_dst_nr-1].p->two->path, p->two->path))\n \t\treturn -1;\n-\tfirst = -first - 1;\n \n-\t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);\n+\trename_dst[rename_dst_nr].p = p;\n+\trename_dst[rename_dst_nr].filespec_to_free = NULL;\n+\trename_dst[rename_dst_nr].is_rename = 0;\n \trename_dst_nr++;\n-\tif (first < rename_dst_nr)\n-\t\tMOVE_ARRAY(rename_dst + first + 1, rename_dst + first,\n-\t\t\t rename_dst_nr - first - 1);\n-\trename_dst[first].two = alloc_filespec(two->path);\n-\tfill_filespec(rename_dst[first].two, &two->oid, two->oid_valid,\n-\t\t two->mode);\n-\trename_dst[first].pair = NULL;\n \treturn 0;\n }\n \n@@ -78,6 +75,14 @@ static int rename_src_nr, rename_src_alloc;\n \n static void register_rename_src(struct diff_filepair *p)\n {\n+\tif (p->broken_pair) {\n+\t\tif (!break_idx) {\n+\t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\n+\t\t\tstrintmap_init(break_idx, -1);\n+\t\t}\n+\t\tstrintmap_set(break_idx, p->one->path, rename_dst_nr);\n+\t}\n+\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n \trename_src[rename_src_nr].p = p;\n \trename_src[rename_src_nr].score = p->score;\n@@ -117,14 +122,14 @@ static void prefetch(void *prefetch_options)\n \tstruct oid_array to_fetch = OID_ARRAY_INIT;\n \n \tfor (i = 0; i < rename_dst_nr; i++) {\n-\t\tif (rename_dst[i].pair)\n+\t\tif (rename_dst[i].p->renamed_pair)\n \t\t\t/*\n \t\t\t * The loop in diffcore_rename() will not need these\n \t\t\t * blobs, so skip prefetching.\n \t\t\t */\n \t\t\tcontinue; /* already found exact match */\n \t\tdiff_add_if_missing(options->repo, &to_fetch,\n-\t\t\t\t rename_dst[i].two);\n+\t\t\t\t rename_dst[i].p->two);\n \t}\n \tfor (i = 0; i < rename_src_nr; i++) {\n \t\tif (options->skip_unmodified &&\n@@ -234,26 +239,24 @@ static int estimate_similarity(struct repository *r,\n \n static void record_rename_pair(int dst_index, int src_index, int score)\n {\n-\tstruct diff_filespec *src, *dst;\n-\tstruct diff_filepair *dp;\n+\tstruct diff_filepair *src = rename_src[src_index].p;\n+\tstruct diff_filepair *dst = rename_dst[dst_index].p;\n \n-\tif (rename_dst[dst_index].pair)\n+\tif (dst->renamed_pair)\n \t\tdie(\"internal error: dst already matched.\");\n \n-\tsrc = rename_src[src_index].p->one;\n-\tsrc->rename_used++;\n-\tsrc->count++;\n+\tsrc->one->rename_used++;\n+\tsrc->one->count++;\n \n-\tdst = rename_dst[dst_index].two;\n-\tdst->count++;\n+\trename_dst[dst_index].filespec_to_free = dst->one;\n+\trename_dst[dst_index].is_rename = 1;\n \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+\tdst->one = src->one;\n+\tdst->renamed_pair = 1;\n+\tif (!strcmp(dst->one->path, dst->two->path))\n+\t\tdst->score = rename_src[src_index].score;\n \telse\n-\t\tdp->score = score;\n-\trename_dst[dst_index].pair = dp;\n+\t\tdst->score = score;\n }\n \n /*\n@@ -299,7 +302,7 @@ static int find_identical_files(struct hashmap *srcs,\n \t\t\t\tstruct diff_options *options)\n {\n \tint renames = 0;\n-\tstruct diff_filespec *target = rename_dst[dst_index].two;\n+\tstruct diff_filespec *target = rename_dst[dst_index].p->two;\n \tstruct file_similarity *p, *best = NULL;\n \tint i = 100, best_score = -1;\n \tunsigned int hash = hash_filespec(options->repo, target);\n@@ -460,7 +463,7 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i\n \t\t (mx[i].score < minimum_score))\n \t\t\tbreak; /* there is no more usable pair. */\n \t\tdst = &rename_dst[mx[i].dst];\n-\t\tif (dst->pair)\n+\t\tif (dst->is_rename)\n \t\t\tcontinue; /* already done, either exact or fuzzy. */\n \t\tif (!copies && rename_src[mx[i].src].p->one->rename_used)\n \t\t\tcontinue;\n@@ -495,7 +498,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\telse if (!options->flags.rename_empty &&\n \t\t\t\t is_empty_blob_oid(&p->two->oid))\n \t\t\t\tcontinue;\n-\t\t\telse if (add_rename_dst(p->two) < 0) {\n+\t\t\telse if (add_rename_dst(p) < 0) {\n \t\t\t\twarning(\"skipping rename detection, detected\"\n \t\t\t\t\t\" duplicate destination '%s'\",\n \t\t\t\t\tp->two->path);\n@@ -568,10 +571,10 @@ void diffcore_rename(struct diff_options *options)\n \n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_targets), sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n-\t\tstruct diff_filespec *two = rename_dst[i].two;\n+\t\tstruct diff_filespec *two = rename_dst[i].p->two;\n \t\tstruct diff_score *m;\n \n-\t\tif (rename_dst[i].pair)\n+\t\tif (rename_dst[i].is_rename)\n \t\t\tcontinue; /* dealt with exact match already. */\n \n \t\tm = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];\n@@ -628,22 +631,8 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {\n-\t\t\t/*\n-\t\t\t * Addition\n-\t\t\t *\n-\t\t\t * We would output this add record if it has\n-\t\t\t * not been turned into a rename/copy already.\n-\t\t\t */\n-\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->two);\n-\t\t\tif (dst && dst->pair) {\n-\t\t\t\tdiff_q(&outq, dst->pair);\n-\t\t\t\tpair_to_free = p;\n-\t\t\t}\n-\t\t\telse\n-\t\t\t\t/* no matching rename/copy source, so\n-\t\t\t\t * record this as an addition.\n-\t\t\t\t */\n-\t\t\t\tdiff_q(&outq, p);\n+\t\t\t/* Addition */\n+\t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {\n \t\t\t/*\n@@ -664,8 +653,9 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t */\n \t\t\tif (DIFF_PAIR_BROKEN(p)) {\n \t\t\t\t/* broken delete */\n-\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->one);\n-\t\t\t\tif (dst && dst->pair)\n+\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p);\n+\t\t\t\tassert(dst);\n+\t\t\t\tif (dst->is_rename)\n \t\t\t\t\t/* counterpart is now rename/copy */\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\n@@ -675,16 +665,14 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\n \n-\t\t\tif (pair_to_free)\n-\t\t\t\t;\n-\t\t\telse\n+\t\t\tif (!pair_to_free)\n \t\t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (!diff_unmodified_pair(p))\n \t\t\t/* all the usual ones need to be kept */\n \t\t\tdiff_q(&outq, p);\n \t\telse\n-\t\t\t/* no need to keep unmodified pairs */\n+\t\t\t/* no need to keep unmodified pairs; FIXME: remove earlier? */\n \t\t\tpair_to_free = p;\n \n \t\tif (pair_to_free)\n@@ -697,11 +685,16 @@ void diffcore_rename(struct diff_options *options)\n \tdiff_debug_queue(\"done collapsing\", q);\n \n \tfor (i = 0; i < rename_dst_nr; i++)\n-\t\tfree_filespec(rename_dst[i].two);\n+\t\tif (rename_dst[i].filespec_to_free)\n+\t\t\tfree_filespec(rename_dst[i].filespec_to_free);\n \n \tFREE_AND_NULL(rename_dst);\n \trename_dst_nr = rename_dst_alloc = 0;\n \tFREE_AND_NULL(rename_src);\n \trename_src_nr = rename_src_alloc = 0;\n+\tif (break_idx) {\n+\t\tstrintmap_clear(break_idx);\n+\t\tFREE_AND_NULL(break_idx);\n+\t}\n \treturn;\n }\n-- \ngitgitgadget\n"},{"id":"411549","messageId":"306a48820dd3c338d2b9e2288e5a3e1c7c89f36e.1607223276.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","subject":"[PATCH 6/7] diffcore-rename: simplify and accelerate register_rename_src()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-06T02:54:35Z","receivedAt":"2020-12-06T04:09:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nreigster_rename_src() took pains to create an array in rename_src which\nwas sorted by pathname of the contained diff_filepair. However, the\nfact that this array was sorted was not needed anywhere, and thus\nrepresented wasted time. Simply append to the end of the array, which\nin a usecase of note saved 45% of diffcore_rename() setup time for me.\n\nTechnically, there is one difference in the end result for the code. IF\nthe caller of diffcore-rename provides a set of pairs with a duplicate\nfilename in the sources (an erroneous input condition), the old code\nwould simply ignore the duplicate (without warning or error). The new\ncode will simply swallow it and thus allow multiple pairings for the\n\"same\" source file. Checking for this error condition is expensive\n(basically undoing the optimization) and the only existing callers\nalready avoid passing such an invalid input. If someone really wants to\nadd some error checking here on this input condition, I believe they\nshould add a separate function which can be called before\ndiffcore_rename(), and then other callers that don't need additional\nchecks because of their design (such as merge-ort) can avoid the extra\noverhead.\n\nAlso, note that I dropped the return type on the function since it was\nunconditionally discarded anyway.\n\nThis patch is being submitted in a different order than its original\ndevelopment, but in a large rebase of many commits with lots of renames\nand with several optimizations to inexact rename detection,\ndiffcore_rename() setup time was a sizeable chunk of overall runtime.\nThis patch dropped execution time of rebasing 35 commits with lots of\nrenames by 2% overall.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 30 +++---------------------------\n 1 file changed, 3 insertions(+), 27 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3d637ba4645..816d2fbac44 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -76,36 +76,12 @@ static struct diff_rename_src {\n } *rename_src;\n static int rename_src_nr, rename_src_alloc;\n \n-static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n+static void register_rename_src(struct diff_filepair *p)\n {\n-\tint first, last;\n-\tstruct diff_filespec *one = p->one;\n-\tunsigned short score = p->score;\n-\n-\tfirst = 0;\n-\tlast = rename_src_nr;\n-\twhile (last > first) {\n-\t\tint next = first + ((last - first) >> 1);\n-\t\tstruct diff_rename_src *src = &(rename_src[next]);\n-\t\tint cmp = strcmp(one->path, src->p->one->path);\n-\t\tif (!cmp)\n-\t\t\treturn src;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n-\n-\t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n+\trename_src[rename_src_nr].p = p;\n+\trename_src[rename_src_nr].score = p->score;\n \trename_src_nr++;\n-\tif (first < rename_src_nr)\n-\t\tMOVE_ARRAY(rename_src + first + 1, rename_src + first,\n-\t\t\t rename_src_nr - first - 1);\n-\trename_src[first].p = p;\n-\trename_src[first].score = score;\n-\treturn &(rename_src[first]);\n }\n \n static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n-- \ngitgitgadget\n\n"},{"id":"411550","messageId":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":null,"subject":"[PATCH 0/7] diffcore-rename improvements","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-06T02:54:29Z","receivedAt":"2020-12-06T04:10:36Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This patch series include 4 small code cleanups, 1 small bug fix (or perhaps\njust a UI improvement -- it's a very minor issue either way), and 2\nperformance improvements. The first 6 patches are relatively easy to review,\nwhile the last one...is a bit more involved (but provided the biggest\nperformance boost).\n\nThese patches came out of the merge-ort work, and are related, but there is\nno dependency between any of the series.\n\nElijah Newren (7):\n diffcore-rename: avoid usage of global in too_many_rename_candidates()\n diffcore-rename: remove unnecessary if-clause\n diffcore-rename: rename num_create to num_targets\n diffcore-rename: change a few comments to use 'add' instead of\n 'create'\n diffcore-rename: reduce jumpiness in progress counters\n diffcore-rename: simplify and accelerate register_rename_src()\n Accelerate rename_dst setup\n\n diffcore-rename.c | 225 ++++++++++++++++++++--------------------------\n 1 file changed, 96 insertions(+), 129 deletions(-)\n\n\nbase-commit: 3a0b884caba2752da0af626fb2de7d597c844e8b\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-929%2Fnewren%2Fdiffcore-rename-improvements-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-929/newren/diffcore-rename-improvements-v1\nPull-Request: https://github.com/git/git/pull/929\n-- \ngitgitgadget\n"},{"id":"411551","messageId":"e8257516c1f983d590b8a81fb32ecd5cb91dc737.1607223276.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","subject":"[PATCH 5/7] diffcore-rename: reduce jumpiness in progress counters","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-06T02:54:34Z","receivedAt":"2020-12-06T04:11:24Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nInexact rename detection works by comparing all sources to all\ndestinations, computing similarities, and then finding the best matches\namong those that are sufficiently similar.\n\nHowever, it is preceded by exact rename detection that works by\nchecking if there are files with identical hashes. If exact renames are\nfound, we can exclude some files from inexact rename detection.\n\nThe inexact rename detection loops over the full set of files, but\nimmediately skips those for which rename_dst[i].is_rename is true and\nthus doesn't compare any sources to that destination. As such, these\npaths shouldn't be included in the progress counter.\n\nFor the eagle eyed, this change hints at an actual optimization -- the\nfirst one I presented at Git Merge 2020. I'll be submitting that\noptimization later, once the basic merge-ort algorithm has merged.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 7270eb6af48..3d637ba4645 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -587,7 +587,7 @@ void diffcore_rename(struct diff_options *options)\n \tif (options->show_rename_progress) {\n \t\tprogress = start_delayed_progress(\n \t\t\t\t_(\"Performing inexact rename detection\"),\n-\t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n+\t\t\t\t(uint64_t)num_targets * (uint64_t)rename_src_nr);\n \t}\n \n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_targets), sizeof(*mx));\n@@ -626,7 +626,8 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tdiff_free_filespec_blob(two);\n \t\t}\n \t\tdst_cnt++;\n-\t\tdisplay_progress(progress, (uint64_t)(i+1)*(uint64_t)rename_src_nr);\n+\t\tdisplay_progress(progress,\n+\t\t\t\t (uint64_t)dst_cnt * (uint64_t)rename_src_nr);\n \t}\n \tstop_progress(&progress);\n \n-- \ngitgitgadget\n\n"},{"id":"411552","messageId":"30381addc5ca9f2b5299835020716291c7fe8d68.1607223276.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","subject":"[PATCH 3/7] diffcore-rename: rename num_create to num_targets","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-06T02:54:32Z","receivedAt":"2020-12-06T04:14:44Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nFiles added since the base commit serve as targets for rename detection.\nWhile it is true that added files can be thought of as being \"created\"\nwhen they are added IF they have no pairing file that they were renamed\nfrom, and it is true we start out not knowing what the pairings are, it\nseems a little odd to think in terms of \"file creation\" when we are\nlooking for \"file renames\". Rename the variable to avoid this minor\npoint of confusion.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 10 +++++-----\n 1 file changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 0f8fce9293e..655a67759c8 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -502,7 +502,7 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_queue_struct outq;\n \tstruct diff_score *mx;\n \tint i, j, rename_count, skip_unmodified = 0;\n-\tint num_create, dst_cnt;\n+\tint num_targets, dst_cnt;\n \tstruct progress *progress = NULL;\n \n \tif (!minimum_score)\n@@ -567,13 +567,13 @@ void diffcore_rename(struct diff_options *options)\n \t * Calculate how many renames are left (but all the source\n \t * files still remain as options for rename/copies!)\n \t */\n-\tnum_create = (rename_dst_nr - rename_count);\n+\tnum_targets = (rename_dst_nr - rename_count);\n \n \t/* All done? */\n-\tif (!num_create)\n+\tif (!num_targets)\n \t\tgoto cleanup;\n \n-\tswitch (too_many_rename_candidates(num_create, rename_src_nr, options)) {\n+\tswitch (too_many_rename_candidates(num_targets, rename_src_nr, options)) {\n \tcase 1:\n \t\tgoto cleanup;\n \tcase 2:\n@@ -590,7 +590,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n \t}\n \n-\tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_create), sizeof(*mx));\n+\tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_targets), sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n \t\tstruct diff_filespec *two = rename_dst[i].two;\n \t\tstruct diff_score *m;\n-- \ngitgitgadget\n\n"},{"id":"411553","messageId":"95a3fcb8be08cce186144d175a6cda71ab42d445.1607223276.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","subject":"[PATCH 1/7] diffcore-rename: avoid usage of global in too_many_rename_candidates()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-06T02:54:30Z","receivedAt":"2020-12-06T04:14:44Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ntoo_many_rename_candidates() got the number of rename targets via an\nargument to the function, but the number of rename sources via a global\nvariable. That felt rather inconsistent. Pass in the number of rename\nsources as an argument as well.\n\nWhile we are at it... We had a local variable, num_src, that served two\npurposes. Initially it was set to this global value, but later was used\nfor counting a subset of the number of sources. Since we now have a\nfunction argument for the former usage, introduce a clearer variable\nname for the latter usage.\n\nThis patch has no behavioral changes; it's just renaming and passing an\nargument instead of grabbing it from the global namespace. (You may\nfind it easier to view the patch using git diff's --color-words option.)\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 23 +++++++++++------------\n 1 file changed, 11 insertions(+), 12 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex d367a6d2443..68ddf51a2a1 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -434,12 +434,11 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n * 1 if we need to disable inexact rename detection;\n * 2 if we would be under the limit if we were given -C instead of -C -C.\n */\n-static int too_many_rename_candidates(int num_create,\n+static int too_many_rename_candidates(int num_targets, int num_sources,\n \t\t\t\t struct diff_options *options)\n {\n \tint rename_limit = options->rename_limit;\n-\tint num_src = rename_src_nr;\n-\tint i;\n+\tint i, limited_sources;\n \n \toptions->needed_rename_limit = 0;\n \n@@ -447,30 +446,30 @@ static int too_many_rename_candidates(int num_create,\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-\t * num_create * num_src > rename_limit * rename_limit\n+\t * num_targets * num_sources > rename_limit * rename_limit\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n-\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_create * (uint64_t)num_src\n+\tif ((num_targets <= rename_limit || num_sources <= rename_limit) &&\n+\t ((uint64_t)num_targets * (uint64_t)num_sources\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n-\t\tnum_src > num_create ? num_src : num_create;\n+\t\tnum_sources > num_targets ? num_sources : num_targets;\n \n \t/* Are we running under -C -C? */\n \tif (!options->flags.find_copies_harder)\n \t\treturn 1;\n \n \t/* Would we bust the limit if we were running under -C? */\n-\tfor (num_src = i = 0; i < rename_src_nr; i++) {\n+\tfor (limited_sources = i = 0; i < num_sources; i++) {\n \t\tif (diff_unmodified_pair(rename_src[i].p))\n \t\t\tcontinue;\n-\t\tnum_src++;\n+\t\tlimited_sources++;\n \t}\n-\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_create * (uint64_t)num_src\n+\tif ((num_targets <= rename_limit || limited_sources <= rename_limit) &&\n+\t ((uint64_t)num_targets * (uint64_t)limited_sources\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 2;\n \treturn 1;\n@@ -576,7 +575,7 @@ void diffcore_rename(struct diff_options *options)\n \tif (!num_create)\n \t\tgoto cleanup;\n \n-\tswitch (too_many_rename_candidates(num_create, options)) {\n+\tswitch (too_many_rename_candidates(num_create, rename_src_nr, options)) {\n \tcase 1:\n \t\tgoto cleanup;\n \tcase 2:\n-- \ngitgitgadget\n\n"},{"id":"411938","messageId":"X9FKVUT+daRqS0cY@nand.local","threadId":"54772","inReplyTo":"95a3fcb8be08cce186144d175a6cda71ab42d445.1607223276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/7] diffcore-rename: avoid usage of global in too_many_rename_candidates()","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-09T22:06:13Z","receivedAt":"2020-12-09T22:07:16Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Dec 06, 2020 at 02:54:30AM +0000, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n>\n> too_many_rename_candidates() got the number of rename targets via an\n> argument to the function, but the number of rename sources via a global\n> variable. That felt rather inconsistent. Pass in the number of rename\n> sources as an argument as well.\n>\n> While we are at it... We had a local variable, num_src, that served two\n> purposes. Initially it was set to this global value, but later was used\n> for counting a subset of the number of sources. Since we now have a\n> function argument for the former usage, introduce a clearer variable\n> name for the latter usage.\n>\n> This patch has no behavioral changes; it's just renaming and passing an\n> argument instead of grabbing it from the global namespace. (You may\n> find it easier to view the patch using git diff's --color-words option.)\n>\n> Signed-off-by: Elijah Newren \n> ---\n> diffcore-rename.c | 23 +++++++++++------------\n> 1 file changed, 11 insertions(+), 12 deletions(-)\n>\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index d367a6d2443..68ddf51a2a1 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -434,12 +434,11 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n> * 1 if we need to disable inexact rename detection;\n> * 2 if we would be under the limit if we were given -C instead of -C -C.\n> */\n> -static int too_many_rename_candidates(int num_create,\n> +static int too_many_rename_candidates(int num_targets, int num_sources,\n\nOK, so num_create becomes num_targets, and the global num_src becomes a\nnew parameter named num_sources.\n\nMakes sense, but it took me a second to figure all of that out. I don't\nthink that you need to split this across two patches (e.g., one to\nrename num_targets, and another to introduce the num_sources parameter),\nbut including the new names for each of these variables in the patch\nmessage might make this clearer to follow.\n\n> \t\t\t\t struct diff_options *options)\n> {\n> \tint rename_limit = options->rename_limit;\n> -\tint num_src = rename_src_nr;\n> -\tint i;\n> +\tint i, limited_sources;\n> [...]\n\nEverything else from here looks fine, and indeed viewing this with\n--color-words made it much easier to verify.\n\nThanks,\nTaylor\n"},{"id":"411939","messageId":"X9FLaiuWpYely6es@nand.local","threadId":"54772","inReplyTo":"f96bb36930a6e5e42f0d3b9c5dfa3b2cc27c1f9d.1607223276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/7] diffcore-rename: remove unnecessary if-clause","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-09T22:10:50Z","receivedAt":"2020-12-09T22:11:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Dec 06, 2020 at 02:54:31AM +0000, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n>\n> diffcore-rename had two different checks of the form\n>\n> if ((a < limit || b < limit) &&\n> a * b <= limit * limit)\n>\n> Since these are all non-negative integers, this can be simplified to\n>\n> if (a * b <= limit * limit)\n\nMakes sense.\n\n> The only advantage of the former would be in avoiding a couple\n> multiplications in the rare case that both a and b are BOTH very large.\n> I see no reason for such an optimization given that this code is not in\n> any kind of loop. Prefer code simplicity here and change to the latter\n> form.\n\nIf you were really paranoid, you could perform these checks with\nunsigned_mult_overflows(), but I don't think that it's worth doing so\nhere.\n\n> Signed-off-by: Elijah Newren \n> ---\n> diffcore-rename.c | 10 ++++------\n> 1 file changed, 4 insertions(+), 6 deletions(-)\n>\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 68ddf51a2a1..0f8fce9293e 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -450,9 +450,8 @@ static int too_many_rename_candidates(int num_targets, int num_sources,\n> \t */\n> \tif (rename_limit <= 0)\n> \t\trename_limit = 32767;\n> -\tif ((num_targets <= rename_limit || num_sources <= rename_limit) &&\n> -\t ((uint64_t)num_targets * (uint64_t)num_sources\n> -\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n> +\tif ((uint64_t)num_targets * (uint64_t)num_sources\n> +\t <= (uint64_t)rename_limit * (uint64_t)rename_limit)\n\nOne small nit here (and below) is that not all of these need casting.\nOnly one operand of each multiplication needs to be widened for the\ncompiler to widen the other, too. So, I'd write this instead as:\n\n> +\tif ((num_targets * (uint64_t)num_sources) <=\n> + (rename_limit * (uint64_t)rename_limit))\n\nor something. (I tend to prefer the cast on the right-most operand,\nsince it makes clear that there's no need to cast the \"first\" operand,\nand that casting either will do the trick).\n\n> \t\treturn 0;\n>\n> \toptions->needed_rename_limit =\n> @@ -468,9 +467,8 @@ static int too_many_rename_candidates(int num_targets, int num_sources,\n> \t\t\tcontinue;\n> \t\tlimited_sources++;\n> \t}\n> -\tif ((num_targets <= rename_limit || limited_sources <= rename_limit) &&\n> -\t ((uint64_t)num_targets * (uint64_t)limited_sources\n> -\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n> +\tif ((uint64_t)num_targets * (uint64_t)limited_sources\n> +\t <= (uint64_t)rename_limit * (uint64_t)rename_limit)\n\nSame notes here, of course. I was hoping that we could only do this\nmultiplication once, but it looks like limited_sources grows between the\ntwo checks, so we have to repeat it here, I suppose.\n\nThanks,\nTaylor\n"},{"id":"411942","messageId":"X9FOtEiN7C7cp+KS@nand.local","threadId":"54772","inReplyTo":"e8257516c1f983d590b8a81fb32ecd5cb91dc737.1607223276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 5/7] diffcore-rename: reduce jumpiness in progress counters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-09T22:24:52Z","receivedAt":"2020-12-09T22:35:16Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Dec 06, 2020 at 02:54:34AM +0000, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n>\n> Inexact rename detection works by comparing all sources to all\n> destinations, computing similarities, and then finding the best matches\n> among those that are sufficiently similar.\n>\n> However, it is preceded by exact rename detection that works by\n> checking if there are files with identical hashes. If exact renames are\n> found, we can exclude some files from inexact rename detection.\n>\n> The inexact rename detection loops over the full set of files, but\n> immediately skips those for which rename_dst[i].is_rename is true and\n> thus doesn't compare any sources to that destination. As such, these\n> paths shouldn't be included in the progress counter.\n>\n> For the eagle eyed, this change hints at an actual optimization -- the\n> first one I presented at Git Merge 2020. I'll be submitting that\n> optimization later, once the basic merge-ort algorithm has merged.\n\n;-) I was hoping that that was the case.\n\n> Signed-off-by: Elijah Newren \n> ---\n> diffcore-rename.c | 5 +++--\n> 1 file changed, 3 insertions(+), 2 deletions(-)\n>\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 7270eb6af48..3d637ba4645 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -587,7 +587,7 @@ void diffcore_rename(struct diff_options *options)\n> \tif (options->show_rename_progress) {\n> \t\tprogress = start_delayed_progress(\n> \t\t\t\t_(\"Performing inexact rename detection\"),\n> -\t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n> +\t\t\t\t(uint64_t)num_targets * (uint64_t)rename_src_nr);\n> \t}\n>\n> \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_targets), sizeof(*mx));\n> @@ -626,7 +626,8 @@ void diffcore_rename(struct diff_options *options)\n> \t\t\tdiff_free_filespec_blob(two);\n> \t\t}\n> \t\tdst_cnt++;\n> -\t\tdisplay_progress(progress, (uint64_t)(i+1)*(uint64_t)rename_src_nr);\n> +\t\tdisplay_progress(progress,\n> +\t\t\t\t (uint64_t)dst_cnt * (uint64_t)rename_src_nr);\n\nBoth of these spots need only one cast, but the patch itself looks\ncorrect (with or without dropping a cast on one of the operands in each\nexpression).\n\nThanks,\nTaylor\n"},{"id":"411944","messageId":"X9FScb3pzY0EBLvS@nand.local","threadId":"54772","inReplyTo":"306a48820dd3c338d2b9e2288e5a3e1c7c89f36e.1607223276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 6/7] diffcore-rename: simplify and accelerate register_rename_src()","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-09T22:40:49Z","receivedAt":"2020-12-09T22:42:31Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Dec 06, 2020 at 02:54:35AM +0000, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n>\n> reigster_rename_src() took pains to create an array in rename_src which\n> was sorted by pathname of the contained diff_filepair. However, the\n> fact that this array was sorted was not needed anywhere, and thus\n> represented wasted time. Simply append to the end of the array, which\n> in a usecase of note saved 45% of diffcore_rename() setup time for me.\n>\n> Technically, there is one difference in the end result for the code. IF\n\ns/IF/If ?\n\n> the caller of diffcore-rename provides a set of pairs with a duplicate\n> filename in the sources (an erroneous input condition), the old code\n> would simply ignore the duplicate (without warning or error). The new\n> code will simply swallow it and thus allow multiple pairings for the\n> \"same\" source file. Checking for this error condition is expensive\n> (basically undoing the optimization) and the only existing callers\n> already avoid passing such an invalid input. If someone really wants to\n> add some error checking here on this input condition, I believe they\n> should add a separate function which can be called before\n> diffcore_rename(), and then other callers that don't need additional\n> checks because of their design (such as merge-ort) can avoid the extra\n> overhead.\n\nIt seems like this is currently impossible to trigger, making any extra\n(expensive) checking of it worthless, no?\n\n> Also, note that I dropped the return type on the function since it was\n> unconditionally discarded anyway.\n>\n> This patch is being submitted in a different order than its original\n> development, but in a large rebase of many commits with lots of renames\n> and with several optimizations to inexact rename detection,\n> diffcore_rename() setup time was a sizeable chunk of overall runtime.\n> This patch dropped execution time of rebasing 35 commits with lots of\n> renames by 2% overall.\n\nNeat!\n\n> Signed-off-by: Elijah Newren \n> ---\n> diffcore-rename.c | 30 +++---------------------------\n> 1 file changed, 3 insertions(+), 27 deletions(-)\n>\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 3d637ba4645..816d2fbac44 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -76,36 +76,12 @@ static struct diff_rename_src {\n> [...]\n\nThis looks obviously correct.\n\nThanks,\nTaylor\n"},{"id":"411945","messageId":"X9FXPHUZJAZKSset@nand.local","threadId":"54772","inReplyTo":"3e83b51628b6f3aeb71c5e637eca03dd63f9e95f.1607223276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 7/7] Accelerate rename_dst setup","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-09T23:01:16Z","receivedAt":"2020-12-09T23:02:10Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Dec 06, 2020 at 02:54:36AM +0000, Elijah Newren via GitGitGadget wrote:\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 816d2fbac44..fb3c2817c6b 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -5,67 +5,64 @@\n> #include \"cache.h\"\n> #include \"diff.h\"\n> #include \"diffcore.h\"\n> -#include \"object-store.h\"\n> #include \"hashmap.h\"\n> +#include \"object-store.h\"\n\nShuffling around this object-store.h include looks like noise to me, but\nmaybe there's a good reason for doing it.\n\n> #include \"progress.h\"\n> #include \"promisor-remote.h\"\n> +#include \"strmap.h\"\n>\n> /* Table of rename/copy destinations */\n>\n> static struct diff_rename_dst {\n> -\tstruct diff_filespec *two;\n> -\tstruct diff_filepair *pair;\n> +\tstruct diff_filepair *p;\n> +\tstruct diff_filespec *filespec_to_free;\n> +\tint is_rename; /* false -> just a create; true -> rename or copy */\n> } *rename_dst;\n> static int rename_dst_nr, rename_dst_alloc;\n> +/* Mapping from break source pathname to break destination index */\n> +static struct strintmap *break_idx = NULL;\n>\n> -static int find_rename_dst(struct diff_filespec *two)\n> -{\n> -\tint first, last;\n> -\n> -\tfirst = 0;\n> -\tlast = rename_dst_nr;\n> -\twhile (last > first) {\n> -\t\tint next = first + ((last - first) >> 1);\n> -\t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n> -\t\tint cmp = strcmp(two->path, dst->two->path);\n> -\t\tif (!cmp)\n> -\t\t\treturn next;\n> -\t\tif (cmp < 0) {\n> -\t\t\tlast = next;\n> -\t\t\tcontinue;\n> -\t\t}\n> -\t\tfirst = next+1;\n> -\t}\n> -\treturn -first - 1;\n> -}\n> -\n> -static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two)\n> +static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)\n> {\n> -\tint ofs = find_rename_dst(two);\n> -\treturn ofs < 0 ? NULL : &rename_dst[ofs];\n> +\t/* Lookup by p->ONE->path */\n> +\tint idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;\n\nI had to lookup the behavior of strintmap_get() to realize that it\nreturns the map's \"default value\" to figure out why this double\nternary was necessary, but I think that it is.\n\nIdeally, if break_idx is non-NULL, then we ought to be able to immediately\nreturn NULL, but it's possible that break_idx is non-NULL and simply\ndoesn't contain p->one->path, in which case we also want to return NULL.\n\nSo, I think this is as clear as it can be.\n\n> +\treturn (idx == -1) ? NULL : &rename_dst[idx];\n> }\n>\n> /*\n> * Returns 0 on success, -1 if we found a duplicate.\n> */\n> -static int add_rename_dst(struct diff_filespec *two)\n> +static int add_rename_dst(struct diff_filepair *p)\n> {\n> -\tint first = find_rename_dst(two);\n> -\n> -\tif (first >= 0)\n> +\t/*\n> +\t * See t4058; trees might have duplicate entries. I think\n> +\t * trees with duplicate entries should be ignored and we\n> +\t * should just leave rename detection on; while the results\n> +\t * may be slightly harder to understand, that's merely a\n> +\t * result of the underlying tree making no sense. But I\n> +\t * believe everything still works fine, the results do still\n> +\t * make sense, and the extra overhead of doing this checking\n> +\t * for a few historical weird trees from long ago seems like\n> +\t * the dog wagging the tail to me.\n> +\t *\n> +\t * However: I don't feel like fighting that battle right now.\n> +\t * For now, to keep the regression test passing, we have to\n> +\t * detect it. Since the diff machinery passes these to us in\n> +\t * adjacent pairs, we just need to check to see if our name\n> +\t * matches the previous one.\n> +\t *\n> +\t * TODO: Dispense with this test, rip out the test in t4058, and\n> +\t * lobby folks for the change.\n> +\t */\n> +\tif (rename_dst_nr > 0 &&\n> +\t !strcmp(rename_dst[rename_dst_nr-1].p->two->path, p->two->path))\n> \t\treturn -1;\n> -\tfirst = -first - 1;\n>\n> -\t/* insert to make it at \"first\" */\n> \tALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);\n> +\trename_dst[rename_dst_nr].p = p;\n> +\trename_dst[rename_dst_nr].filespec_to_free = NULL;\n> +\trename_dst[rename_dst_nr].is_rename = 0;\n> \trename_dst_nr++;\n> -\tif (first < rename_dst_nr)\n> -\t\tMOVE_ARRAY(rename_dst + first + 1, rename_dst + first,\n> -\t\t\t rename_dst_nr - first - 1);\n> -\trename_dst[first].two = alloc_filespec(two->path);\n> -\tfill_filespec(rename_dst[first].two, &two->oid, two->oid_valid,\n> -\t\t two->mode);\n> -\trename_dst[first].pair = NULL;\n> \treturn 0;\n\nVery nice, this is much simpler than what was here before.\n\n> @@ -78,6 +75,14 @@ static int rename_src_nr, rename_src_alloc;\n>\n> static void register_rename_src(struct diff_filepair *p)\n> {\n> +\tif (p->broken_pair) {\n> +\t\tif (!break_idx) {\n> +\t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\n> +\t\t\tstrintmap_init(break_idx, -1);\n> +\t\t}\n> +\t\tstrintmap_set(break_idx, p->one->path, rename_dst_nr);\n> +\t}\n> +\n\nMakes sense.\n\n> @@ -664,8 +653,9 @@ void diffcore_rename(struct diff_options *options)\n> \t\t\t */\n> \t\t\tif (DIFF_PAIR_BROKEN(p)) {\n> \t\t\t\t/* broken delete */\n> -\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->one);\n> -\t\t\t\tif (dst && dst->pair)\n> +\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p);\n> +\t\t\t\tassert(dst);\n\nYou're not hurting anything, but I'm not convinced that this assert() is\nbuying you anything that the line immediately below it isn't already\ndoing.\n\nThe rest of the patch looks good to me.\n\nThanks,\nTaylor\n"},{"id":"411950","messageId":"CABPp-BGPfdFj1q09XVa7UOVz-0K9yf9Lp-h2wh6+nVVbVu94yg@mail.gmail.com","threadId":"54772","inReplyTo":"X9FScb3pzY0EBLvS@nand.local","subject":"Re: [PATCH 6/7] diffcore-rename: simplify and accelerate register_rename_src()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-10T00:25:18Z","receivedAt":"2020-12-10T00:26:40Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 9, 2020 at 2:40 PM Taylor Blau wrote:\n>\n> On Sun, Dec 06, 2020 at 02:54:35AM +0000, Elijah Newren via GitGitGadget wrote:\n> > From: Elijah Newren \n> >\n> > reigster_rename_src() took pains to create an array in rename_src which\n> > was sorted by pathname of the contained diff_filepair. However, the\n> > fact that this array was sorted was not needed anywhere, and thus\n> > represented wasted time. Simply append to the end of the array, which\n> > in a usecase of note saved 45% of diffcore_rename() setup time for me.\n> >\n> > Technically, there is one difference in the end result for the code. IF\n>\n> s/IF/If ?\n\nIndeed; will fix.\n\n> > the caller of diffcore-rename provides a set of pairs with a duplicate\n> > filename in the sources (an erroneous input condition), the old code\n> > would simply ignore the duplicate (without warning or error). The new\n> > code will simply swallow it and thus allow multiple pairings for the\n> > \"same\" source file. Checking for this error condition is expensive\n> > (basically undoing the optimization) and the only existing callers\n> > already avoid passing such an invalid input. If someone really wants to\n> > add some error checking here on this input condition, I believe they\n> > should add a separate function which can be called before\n> > diffcore_rename(), and then other callers that don't need additional\n> > checks because of their design (such as merge-ort) can avoid the extra\n> > overhead.\n>\n> It seems like this is currently impossible to trigger, making any extra\n> (expensive) checking of it worthless, no?\n\nI believe that's what it currently amounts to, and I debated just\nripping the paragraph out.\n\nHowever, a natural question that can easily arise for current\nreviewers or future readers of the patch is why was there ever sorting\nin the first place if the sorting isn't used? That question came up\nfor me, and I dug into it. Sorting is also used with rename_dst in\nnearby code in the file, and there are a few reasons for it there.\nThe quick indexing that rename_dst needs doesn't apply to rename_src,\nbut it's not as obvious whether the\nbroken-trees-with-duplicate-entries rationale applies or not. I spent\na while digging into it. (And it's possible that I didn't correctly\ncheck the callers or that in the seven months since I wrote this\nmessage someone added another caller of this code that does pass\nmultiple diff_filepair-s for the \"same\" source file.) Anyway, this\nparagraph exists because I had to go down a goose chase to answer this\nnatural question, and I wanted to provide an answer to anyone else\nasking the same question. Also, in the off chance that anyone did\nwant to add callers that passed multiple copies of any source file, I\nwanted to point out that this modified algorithm would result in a\nslight behavioral difference, but that otherwise the modified\nalgorithm gives identical results. (And if some future reader\nstumbled on the paragraph because they had made such a change, I\nwanted to provide a quick suggestion of how to get what they wanted\nwithout adversely affecting performance.)\n\nI hope that helps. I'm sorry if my worrying about these cases and\ndiscussing them made the patch harder to read or review, but I feel\nlike diffcore-rename is one of those low-level components you want to\nbe careful with. diffcore-rename is one of those parts of the code\nwhere a bug in it might not result in a directly observable breakage\nto users but in some secondary or tertiary side-effect showing weird\nresults (e.g. in a merge you won't necessarily see that A was renamed\nto B, instead you get a three-way content merge of original A, other\nA, and new B -- or don't get a three-way content merge you might\nexpect).\n\n> > Also, note that I dropped the return type on the function since it was\n> > unconditionally discarded anyway.\n> >\n> > This patch is being submitted in a different order than its original\n> > development, but in a large rebase of many commits with lots of renames\n> > and with several optimizations to inexact rename detection,\n> > diffcore_rename() setup time was a sizeable chunk of overall runtime.\n> > This patch dropped execution time of rebasing 35 commits with lots of\n> > renames by 2% overall.\n>\n> Neat!\n>\n> > Signed-off-by: Elijah Newren \n> > ---\n> > diffcore-rename.c | 30 +++---------------------------\n> > 1 file changed, 3 insertions(+), 27 deletions(-)\n> >\n> > diff --git a/diffcore-rename.c b/diffcore-rename.c\n> > index 3d637ba4645..816d2fbac44 100644\n> > --- a/diffcore-rename.c\n> > +++ b/diffcore-rename.c\n> > @@ -76,36 +76,12 @@ static struct diff_rename_src {\n> > [...]\n>\n> This looks obviously correct.\n\nThanks for taking a look!\n"},{"id":"411953","messageId":"CABPp-BHQNy3MQ9u=sZKd0h2vqOzhFZC35XqR-QbHgzeiJ7VbLQ@mail.gmail.com","threadId":"54772","inReplyTo":"X9FLaiuWpYely6es@nand.local","subject":"Re: [PATCH 2/7] diffcore-rename: remove unnecessary if-clause","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-10T00:32:40Z","receivedAt":"2020-12-10T00:34:10Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 9, 2020 at 2:10 PM Taylor Blau wrote:\n>\n> On Sun, Dec 06, 2020 at 02:54:31AM +0000, Elijah Newren via GitGitGadget wrote:\n> > From: Elijah Newren \n> >\n> > diffcore-rename had two different checks of the form\n> >\n> > if ((a < limit || b < limit) &&\n> > a * b <= limit * limit)\n> >\n> > Since these are all non-negative integers, this can be simplified to\n> >\n> > if (a * b <= limit * limit)\n>\n> Makes sense.\n>\n> > The only advantage of the former would be in avoiding a couple\n> > multiplications in the rare case that both a and b are BOTH very large.\n> > I see no reason for such an optimization given that this code is not in\n> > any kind of loop. Prefer code simplicity here and change to the latter\n> > form.\n>\n> If you were really paranoid, you could perform these checks with\n> unsigned_mult_overflows(), but I don't think that it's worth doing so\n> here.\n>\n> > Signed-off-by: Elijah Newren \n> > ---\n> > diffcore-rename.c | 10 ++++------\n> > 1 file changed, 4 insertions(+), 6 deletions(-)\n> >\n> > diff --git a/diffcore-rename.c b/diffcore-rename.c\n> > index 68ddf51a2a1..0f8fce9293e 100644\n> > --- a/diffcore-rename.c\n> > +++ b/diffcore-rename.c\n> > @@ -450,9 +450,8 @@ static int too_many_rename_candidates(int num_targets, int num_sources,\n> > */\n> > if (rename_limit <= 0)\n> > rename_limit = 32767;\n> > - if ((num_targets <= rename_limit || num_sources <= rename_limit) &&\n> > - ((uint64_t)num_targets * (uint64_t)num_sources\n> > - <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n> > + if ((uint64_t)num_targets * (uint64_t)num_sources\n> > + <= (uint64_t)rename_limit * (uint64_t)rename_limit)\n>\n> One small nit here (and below) is that not all of these need casting.\n> Only one operand of each multiplication needs to be widened for the\n> compiler to widen the other, too. So, I'd write this instead as:\n>\n> > + if ((num_targets * (uint64_t)num_sources) <=\n> > + (rename_limit * (uint64_t)rename_limit))\n>\n> or something. (I tend to prefer the cast on the right-most operand,\n> since it makes clear that there's no need to cast the \"first\" operand,\n> and that casting either will do the trick).\n\nYeah, I think that reads slightly better too, but on the other hand it\ndoes make the diff slightly harder to read. *shrug*.\n\n> > return 0;\n> >\n> > options->needed_rename_limit =\n> > @@ -468,9 +467,8 @@ static int too_many_rename_candidates(int num_targets, int num_sources,\n> > continue;\n> > limited_sources++;\n> > }\n> > - if ((num_targets <= rename_limit || limited_sources <= rename_limit) &&\n> > - ((uint64_t)num_targets * (uint64_t)limited_sources\n> > - <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n> > + if ((uint64_t)num_targets * (uint64_t)limited_sources\n> > + <= (uint64_t)rename_limit * (uint64_t)rename_limit)\n>\n> Same notes here, of course. I was hoping that we could only do this\n> multiplication once, but it looks like limited_sources grows between the\n> two checks, so we have to repeat it here, I suppose.\n\nThe right hand side of the expression is the same -- rename_limit *\nrename_limit -- so it could be stored off (though I don't think\nthere's much point in doing so unless it made the code clearer; this\nis not remotely close to a hot path). However, in the left hand side,\nit's not so much that one of the variables has changed since the last\ncheck, it's that it uses a different set of variables in the check.\nIn particular, it replaces 'num_sources' with 'limited_sources'.\n"},{"id":"411955","messageId":"X9FuycVtX7aK/wrU@nand.local","threadId":"54772","inReplyTo":"CABPp-BGPfdFj1q09XVa7UOVz-0K9yf9Lp-h2wh6+nVVbVu94yg@mail.gmail.com","subject":"Re: [PATCH 6/7] diffcore-rename: simplify and accelerate register_rename_src()","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-12-10T00:41:45Z","receivedAt":"2020-12-10T00:43:08Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, Dec 09, 2020 at 04:25:18PM -0800, Elijah Newren wrote:\n> On Wed, Dec 9, 2020 at 2:40 PM Taylor Blau wrote:\n> > > Technically, there is one difference in the end result for the code. IF\n> >\n> > s/IF/If ?\n>\n> Indeed; will fix.\n\n:-). In fairness, I did read it with _emphasis_, so it at least gave me\na laugh!\n\n> > > the caller of diffcore-rename provides a set of pairs with a duplicate\n> > > filename in the sources (an erroneous input condition), the old code\n> > > would simply ignore the duplicate (without warning or error). The new\n> > > code will simply swallow it and thus allow multiple pairings for the\n> > > \"same\" source file. Checking for this error condition is expensive\n> > > (basically undoing the optimization) and the only existing callers\n> > > already avoid passing such an invalid input. If someone really wants to\n> > > add some error checking here on this input condition, I believe they\n> > > should add a separate function which can be called before\n> > > diffcore_rename(), and then other callers that don't need additional\n> > > checks because of their design (such as merge-ort) can avoid the extra\n> > > overhead.\n> >\n> > It seems like this is currently impossible to trigger, making any extra\n> > (expensive) checking of it worthless, no?\n>\n> I believe that's what it currently amounts to, and I debated just\n> ripping the paragraph out.\n>\n> [ ... ]\n\nNo, no need to be sorry: this is exactly the sort of discussion I had\nhoped to provoke by sanity checking my understanding of what you had\nwritten. I think that the paragraph does belong in the patch message,\nand interested readers can find our discussion here.\n\nThanks,\nTaylor\n"},{"id":"411961","messageId":"CABPp-BEhVK9mMsqS-6Yg2ad5nG0=Pm5by80d9nrHKFp2hrMSBw@mail.gmail.com","threadId":"54772","inReplyTo":"X9FXPHUZJAZKSset@nand.local","subject":"Re: [PATCH 7/7] Accelerate rename_dst setup","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-10T00:57:02Z","receivedAt":"2020-12-10T00:59:04Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 9, 2020 at 3:01 PM Taylor Blau wrote:\n>\n> On Sun, Dec 06, 2020 at 02:54:36AM +0000, Elijah Newren via GitGitGadget wrote:\n> > diff --git a/diffcore-rename.c b/diffcore-rename.c\n> > index 816d2fbac44..fb3c2817c6b 100644\n> > --- a/diffcore-rename.c\n> > +++ b/diffcore-rename.c\n> > @@ -5,67 +5,64 @@\n> > #include \"cache.h\"\n> > #include \"diff.h\"\n> > #include \"diffcore.h\"\n> > -#include \"object-store.h\"\n> > #include \"hashmap.h\"\n> > +#include \"object-store.h\"\n>\n> Shuffling around this object-store.h include looks like noise to me, but\n> maybe there's a good reason for doing it.\n\nUm, well...I guess I couldn't help myself from alphabetizing the\n#include list (at least the portion after the initial \"cache.h\" or\n\"git-compat-util.h\" must come first). ;-)\n\nI probably should have done it in a separate patch.\n\n> > #include \"progress.h\"\n> > #include \"promisor-remote.h\"\n> > +#include \"strmap.h\"\n> >\n> > /* Table of rename/copy destinations */\n> >\n> > static struct diff_rename_dst {\n> > - struct diff_filespec *two;\n> > - struct diff_filepair *pair;\n> > + struct diff_filepair *p;\n> > + struct diff_filespec *filespec_to_free;\n> > + int is_rename; /* false -> just a create; true -> rename or copy */\n> > } *rename_dst;\n> > static int rename_dst_nr, rename_dst_alloc;\n> > +/* Mapping from break source pathname to break destination index */\n> > +static struct strintmap *break_idx = NULL;\n> >\n> > -static int find_rename_dst(struct diff_filespec *two)\n> > -{\n> > - int first, last;\n> > -\n> > - first = 0;\n> > - last = rename_dst_nr;\n> > - while (last > first) {\n> > - int next = first + ((last - first) >> 1);\n> > - struct diff_rename_dst *dst = &(rename_dst[next]);\n> > - int cmp = strcmp(two->path, dst->two->path);\n> > - if (!cmp)\n> > - return next;\n> > - if (cmp < 0) {\n> > - last = next;\n> > - continue;\n> > - }\n> > - first = next+1;\n> > - }\n> > - return -first - 1;\n> > -}\n> > -\n> > -static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two)\n> > +static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)\n> > {\n> > - int ofs = find_rename_dst(two);\n> > - return ofs < 0 ? NULL : &rename_dst[ofs];\n> > + /* Lookup by p->ONE->path */\n> > + int idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;\n>\n> I had to lookup the behavior of strintmap_get() to realize that it\n> returns the map's \"default value\" to figure out why this double\n> ternary was necessary, but I think that it is.\n>\n> Ideally, if break_idx is non-NULL, then we ought to be able to immediately\n> return NULL, but it's possible that break_idx is non-NULL and simply\n> doesn't contain p->one->path, in which case we also want to return NULL.\n>\n> So, I think this is as clear as it can be.\n>\n> > + return (idx == -1) ? NULL : &rename_dst[idx];\n> > }\n> >\n> > /*\n> > * Returns 0 on success, -1 if we found a duplicate.\n> > */\n> > -static int add_rename_dst(struct diff_filespec *two)\n> > +static int add_rename_dst(struct diff_filepair *p)\n> > {\n> > - int first = find_rename_dst(two);\n> > -\n> > - if (first >= 0)\n> > + /*\n> > + * See t4058; trees might have duplicate entries. I think\n> > + * trees with duplicate entries should be ignored and we\n> > + * should just leave rename detection on; while the results\n> > + * may be slightly harder to understand, that's merely a\n> > + * result of the underlying tree making no sense. But I\n> > + * believe everything still works fine, the results do still\n> > + * make sense, and the extra overhead of doing this checking\n> > + * for a few historical weird trees from long ago seems like\n> > + * the dog wagging the tail to me.\n> > + *\n> > + * However: I don't feel like fighting that battle right now.\n> > + * For now, to keep the regression test passing, we have to\n> > + * detect it. Since the diff machinery passes these to us in\n> > + * adjacent pairs, we just need to check to see if our name\n> > + * matches the previous one.\n> > + *\n> > + * TODO: Dispense with this test, rip out the test in t4058, and\n> > + * lobby folks for the change.\n> > + */\n> > + if (rename_dst_nr > 0 &&\n> > + !strcmp(rename_dst[rename_dst_nr-1].p->two->path, p->two->path))\n> > return -1;\n> > - first = -first - 1;\n> >\n> > - /* insert to make it at \"first\" */\n> > ALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);\n> > + rename_dst[rename_dst_nr].p = p;\n> > + rename_dst[rename_dst_nr].filespec_to_free = NULL;\n> > + rename_dst[rename_dst_nr].is_rename = 0;\n> > rename_dst_nr++;\n> > - if (first < rename_dst_nr)\n> > - MOVE_ARRAY(rename_dst + first + 1, rename_dst + first,\n> > - rename_dst_nr - first - 1);\n> > - rename_dst[first].two = alloc_filespec(two->path);\n> > - fill_filespec(rename_dst[first].two, &two->oid, two->oid_valid,\n> > - two->mode);\n> > - rename_dst[first].pair = NULL;\n> > return 0;\n>\n> Very nice, this is much simpler than what was here before.\n>\n> > @@ -78,6 +75,14 @@ static int rename_src_nr, rename_src_alloc;\n> >\n> > static void register_rename_src(struct diff_filepair *p)\n> > {\n> > + if (p->broken_pair) {\n> > + if (!break_idx) {\n> > + break_idx = xmalloc(sizeof(*break_idx));\n> > + strintmap_init(break_idx, -1);\n> > + }\n> > + strintmap_set(break_idx, p->one->path, rename_dst_nr);\n> > + }\n> > +\n>\n> Makes sense.\n>\n> > @@ -664,8 +653,9 @@ void diffcore_rename(struct diff_options *options)\n> > */\n> > if (DIFF_PAIR_BROKEN(p)) {\n> > /* broken delete */\n> > - struct diff_rename_dst *dst = locate_rename_dst(p->one);\n> > - if (dst && dst->pair)\n> > + struct diff_rename_dst *dst = locate_rename_dst(p);\n> > + assert(dst);\n>\n> You're not hurting anything, but I'm not convinced that this assert() is\n> buying you anything that the line immediately below it isn't already\n> doing.\n\nIt's identical for runtime correctness, yes. But the primary point\nisn't what happens at runtime, but what happens when future code\nreaders come along. If I only keep the \"if (dst->is_rename)\" line\nthat comes after without the assert, then someone in the future will\ncome along (maybe even myself) and think \"the original author wasn't\nbeing careful here; they should change this to a check on (dst &&\ndst->is_rename)\" (because honestly, it is the kind of mistake I'm\nprone to make). However, if they were to do so, and some bug gets\nintroduced so that locate_rename_dst() returns a NULL for a pair of\ninterest, then they've masked a bug in the algorithm and made it fail\nin harder-to-detect-and-track-down ways. I wanted it to be clear that\ndst == NULL is unacceptable. I guess I could have marked it with\nBUG(), but between an assertion and a NULL-pointer indirection, I\nfigured that code aborting under that condition was pretty well\ncovered. :-)\n\n> The rest of the patch looks good to me.\n>\n> Thanks,\n> Taylor\n"},{"id":"411964","messageId":"xmqq1rfyzb8r.fsf@gitster.c.googlers.com","threadId":"54772","inReplyTo":"CABPp-BEhVK9mMsqS-6Yg2ad5nG0=Pm5by80d9nrHKFp2hrMSBw@mail.gmail.com","subject":"Re: [PATCH 7/7] Accelerate rename_dst setup","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-10T01:43:48Z","receivedAt":"2020-12-10T01:44:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> It's identical for runtime correctness, yes. But the primary point\n> isn't what happens at runtime, but what happens when future code\n> readers come along. If I only keep the \"if (dst->is_rename)\" line\n> that comes after without the assert, then someone in the future will\n> come along (maybe even myself) and think \"the original author wasn't\n> being careful here; they should change this to a check on (dst &&\n> dst->is_rename)\" (because honestly, it is the kind of mistake I'm\n> prone to make). However, if they were to do so, and some bug gets\n> introduced so that locate_rename_dst() returns a NULL for a pair of\n> interest, then they've masked a bug in the algorithm and made it fail\n> in harder-to-detect-and-track-down ways. I wanted it to be clear that\n> dst == NULL is unacceptable. I guess I could have marked it with\n> BUG(), but between an assertion and a NULL-pointer indirection, I\n> figured that code aborting under that condition was pretty well\n> covered. :-)\n\nassert() often gets turned into no-op, so it is more like leaving a\ncomment in the code. A comment or BUG(\"text\") can describe not just\nthe fact that reaching this point with dst==NULL is a bug in the\ncaller but also why it is a bug (e.g. how NULL-dst would screw up\nthe computation downstream from this point), but an assert() cannot.\n\n"},{"id":"411968","messageId":"xmqqtusuxvr8.fsf@gitster.c.googlers.com","threadId":"54772","inReplyTo":"X9FLaiuWpYely6es@nand.local","subject":"Re: [PATCH 2/7] diffcore-rename: remove unnecessary if-clause","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-10T02:03:39Z","receivedAt":"2020-12-10T02:04:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> On Sun, Dec 06, 2020 at 02:54:31AM +0000, Elijah Newren via GitGitGadget wrote:\n>> From: Elijah Newren \n>>\n>> diffcore-rename had two different checks of the form\n>>\n>> if ((a < limit || b < limit) &&\n>> a * b <= limit * limit)\n>>\n>> Since these are all non-negative integers, this can be simplified to\n>>\n>> if (a * b <= limit * limit)\n>\n> Makes sense.\n\nI've always assumed that the original was for correctness (if a and\nb are both larger than limit, a*b could end up being smaller than\nlimit*limit when the result of multiplication of the former wraps\naround but not the latter) ...\n\n>> The only advantage of the former would be in avoiding a couple\n>> multiplications in the rare case that both a and b are BOTH very large.\n>> I see no reason for such an optimization given that this code is not in\n>> any kind of loop. Prefer code simplicity here and change to the latter\n>> form.\n>\n> If you were really paranoid, you could perform these checks with\n> unsigned_mult_overflows(), but I don't think that it's worth doing so\n> here.\n\n... and in no way as an optimization.\n\nSo, I dunno.\n"},{"id":"411969","messageId":"CABPp-BFcSV_LPy-_AW+c-1OgzAyHfEM7D+YL+fFwxYKDheqxEg@mail.gmail.com","threadId":"54772","inReplyTo":"xmqqtusuxvr8.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 2/7] diffcore-rename: remove unnecessary if-clause","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-10T02:17:27Z","receivedAt":"2020-12-10T02:18:38Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 9, 2020 at 6:03 PM Junio C Hamano wrote:\n>\n> Taylor Blau writes:\n>\n> > On Sun, Dec 06, 2020 at 02:54:31AM +0000, Elijah Newren via GitGitGadget wrote:\n> >> From: Elijah Newren \n> >>\n> >> diffcore-rename had two different checks of the form\n> >>\n> >> if ((a < limit || b < limit) &&\n> >> a * b <= limit * limit)\n> >>\n> >> Since these are all non-negative integers, this can be simplified to\n> >>\n> >> if (a * b <= limit * limit)\n> >\n> > Makes sense.\n>\n> I've always assumed that the original was for correctness (if a and\n> b are both larger than limit, a*b could end up being smaller than\n> limit*limit when the result of multiplication of the former wraps\n> around but not the latter) ...\n>\n> >> The only advantage of the former would be in avoiding a couple\n> >> multiplications in the rare case that both a and b are BOTH very large.\n> >> I see no reason for such an optimization given that this code is not in\n> >> any kind of loop. Prefer code simplicity here and change to the latter\n> >> form.\n> >\n> > If you were really paranoid, you could perform these checks with\n> > unsigned_mult_overflows(), but I don't think that it's worth doing so\n> > here.\n>\n> ... and in no way as an optimization.\n>\n> So, I dunno.\n\nAh, so would you be okay replacing these with\n\n if (st_mult(num_targets, limited_sources) <= st_mult(rename_limit,\nrename_limit))\n\n?\n\nThat'd make the correctness intent far clearer, and allow us to drop\nthe casting as well since st_mult converts to size_t. (If, on the off\nchance you're on a platform where size_t is 32-bits and the\nmultiplications don't fit in that size, then the requested matrices\nfor computing rename detection won't fit in memory for you.)\n"},{"id":"411970","messageId":"xmqqpn3ixuyj.fsf@gitster.c.googlers.com","threadId":"54772","inReplyTo":"30381addc5ca9f2b5299835020716291c7fe8d68.1607223276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/7] diffcore-rename: rename num_create to num_targets","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-10T02:20:52Z","receivedAt":"2020-12-10T02:21:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> From: Elijah Newren \n>\n> Files added since the base commit serve as targets for rename detection.\n> While it is true that added files can be thought of as being \"created\"\n> when they are added IF they have no pairing file that they were renamed\n> from, and it is true we start out not knowing what the pairings are, it\n> seems a little odd to think in terms of \"file creation\" when we are\n> looking for \"file renames\". Rename the variable to avoid this minor\n> point of confusion.\n\nThis is probably subjective. \n\nI've always viewed the rename detection as first collecting a set of\ndeleted paths and a set of created paths, and then trying to find a\ngood mapping from the former into the latter, so I find num_create a\nlot more intuitive than num_targets.\n\nBut the remaining elements in the latter set are counted in the\ncounter \"rename_dst_nr\", so we clearly are OK to call the elements\nof the latter set \"the destination\" (of a rename), which contrasts\nvery well with \"the source\" (of a rename), which is how the deleted\npaths are counted with rename_src_nr.\n\nWhen doing -C and -C -C, the \"source\" set has not just deleted but\nalso the preimage of the modified paths, so \"source\" is a more\nappropriate name than \"delete\". From that point of view,\n\"destination\" is a more appropriate name for \"create\" because it\ncontrasts well with \"source\".\n\nYou silently renamed num_create to num_targets in 1/7 without\njustification while adding num_sources. Perhaps we should go back\nto that step and use num_destinations to match? The result would be\nusing words that pair with each other much better than\nintroducing \"target\" to an existing mix of to\nmake it .\n\n"},{"id":"411971","messageId":"CABPp-BFypNXFKVav4hyG2+DvaU1U8UgcAwVqCMmWtZQWhzBnvw@mail.gmail.com","threadId":"54772","inReplyTo":"xmqqpn3ixuyj.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 3/7] diffcore-rename: rename num_create to num_targets","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-10T02:25:36Z","receivedAt":"2020-12-10T02:26:35Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 9, 2020 at 6:20 PM Junio C Hamano wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > From: Elijah Newren \n> >\n> > Files added since the base commit serve as targets for rename detection.\n> > While it is true that added files can be thought of as being \"created\"\n> > when they are added IF they have no pairing file that they were renamed\n> > from, and it is true we start out not knowing what the pairings are, it\n> > seems a little odd to think in terms of \"file creation\" when we are\n> > looking for \"file renames\". Rename the variable to avoid this minor\n> > point of confusion.\n>\n> This is probably subjective.\n>\n> I've always viewed the rename detection as first collecting a set of\n> deleted paths and a set of created paths, and then trying to find a\n> good mapping from the former into the latter, so I find num_create a\n> lot more intuitive than num_targets.\n>\n> But the remaining elements in the latter set are counted in the\n> counter \"rename_dst_nr\", so we clearly are OK to call the elements\n> of the latter set \"the destination\" (of a rename), which contrasts\n> very well with \"the source\" (of a rename), which is how the deleted\n> paths are counted with rename_src_nr.\n>\n> When doing -C and -C -C, the \"source\" set has not just deleted but\n> also the preimage of the modified paths, so \"source\" is a more\n> appropriate name than \"delete\". From that point of view,\n> \"destination\" is a more appropriate name for \"create\" because it\n> contrasts well with \"source\".\n>\n> You silently renamed num_create to num_targets in 1/7 without\n> justification while adding num_sources. Perhaps we should go back\n> to that step and use num_destinations to match? The result would be\n> using words that pair with each other much better than\n> introducing \"target\" to an existing mix of to\n> make it .\n\nOoh, I like it. num_destinations it is.\n"},{"id":"411972","messageId":"xmqqlfe6xukk.fsf@gitster.c.googlers.com","threadId":"54772","inReplyTo":"77ca4656ed442321b41e653505c85d0be31b8045.1607223276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 4/7] diffcore-rename: change a few comments to use 'add' instead of 'create'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-10T02:29:15Z","receivedAt":"2020-12-10T02:30:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> From: Elijah Newren \n>\n> As with the last commit, it feels odd to talk about \"creation\" (which to\n> me implies a brand new file, i.e. one not associated with an existing\n> file, and thus one that could not have been a rename) when we are using\n> the files to look for renames. Use the term \"addition\" instead.\n\nHmph, to me \"create\" and \"add\" mean the same thing in all the\nsentences this patch updates.\n\nWe first notice the differences in two trees, some paths have\ncontents in both trees so they cannot be creation or deletion. Some\npaths only exist in one of the trees and they are initially labelled\nas \"created\" or \"deleted\". If there were no request by the caller\nto detect renames, then that's the end of the story.\n\nOnly after we match up a path in the new tree that did not exist in\nthe old tree with another path in the old tree that no longer exists\nin the new tree, what initially got labelled as creation of one and\ndeletion of another may become a rename.\n\nAnd in the above two paragraphs, if I replace \"to create\" with \"to\nadd\" and \"to delete\" with \"to remove\", I do not see how the story\nbecomes more natural or logical or intuitive. Perhaps I am not\ngetting the subtle difference you find in these two words? This\nlooks like a totally meaningless churn to me.\n\n> Signed-off-by: Elijah Newren \n> ---\n> diffcore-rename.c | 8 ++++----\n> 1 file changed, 4 insertions(+), 4 deletions(-)\n>\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 655a67759c8..7270eb6af48 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -173,7 +173,7 @@ static int estimate_similarity(struct repository *r,\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 * at a newly added 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> @@ -652,9 +652,9 @@ void diffcore_rename(struct diff_options *options)\n> \t\t}\n> \t\telse if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {\n> \t\t\t/*\n> -\t\t\t * Creation\n> +\t\t\t * Addition\n> \t\t\t *\n> -\t\t\t * We would output this create record if it has\n> +\t\t\t * We would output this add record if it has\n> \t\t\t * not been turned into a rename/copy already.\n> \t\t\t */\n> \t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->two);\n> @@ -664,7 +664,7 @@ void diffcore_rename(struct diff_options *options)\n> \t\t\t}\n> \t\t\telse\n> \t\t\t\t/* no matching rename/copy source, so\n> -\t\t\t\t * record this as a creation.\n> +\t\t\t\t * record this as an addition.\n> \t\t\t\t */\n> \t\t\t\tdiff_q(&outq, p);\n> \t\t}\n"},{"id":"411973","messageId":"xmqqh7ouxu8l.fsf@gitster.c.googlers.com","threadId":"54772","inReplyTo":"e8257516c1f983d590b8a81fb32ecd5cb91dc737.1607223276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 5/7] diffcore-rename: reduce jumpiness in progress counters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-10T02:36:26Z","receivedAt":"2020-12-10T02:37:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> From: Elijah Newren \n>\n> Inexact rename detection works by comparing all sources to all\n> destinations, computing similarities, and then finding the best matches\n> among those that are sufficiently similar.\n\nHere, you are using as contrasting pair of\nwords, which supports my comment on 1/7 and 3/7 ;-)\n\n> However, it is preceded by exact rename detection that works by\n> checking if there are files with identical hashes. If exact renames are\n> found, we can exclude some files from inexact rename detection.\n>\n> The inexact rename detection loops over the full set of files, but\n> immediately skips those for which rename_dst[i].is_rename is true and\n> thus doesn't compare any sources to that destination. As such, these\n> paths shouldn't be included in the progress counter.\n> ...\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 7270eb6af48..3d637ba4645 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -587,7 +587,7 @@ void diffcore_rename(struct diff_options *options)\n> \tif (options->show_rename_progress) {\n> \t\tprogress = start_delayed_progress(\n> \t\t\t\t_(\"Performing inexact rename detection\"),\n> -\t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n> +\t\t\t\t(uint64_t)num_targets * (uint64_t)rename_src_nr);\n> \t}\n\nThe num_targets (number of destinations) holds the \"remaining\"\ncandidates after exact renames are taken care of, so this reduces\nthe size of the matrix used to count the progress meter. OK.\n\n> \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_targets), sizeof(*mx));\n> @@ -626,7 +626,8 @@ void diffcore_rename(struct diff_options *options)\n> \t\t\tdiff_free_filespec_blob(two);\n> \t\t}\n> \t\tdst_cnt++;\n> -\t\tdisplay_progress(progress, (uint64_t)(i+1)*(uint64_t)rename_src_nr);\n> +\t\tdisplay_progress(progress,\n> +\t\t\t\t (uint64_t)dst_cnt * (uint64_t)rename_src_nr);\n\nAnd this fills the progress meter by using the number of\ndestinations that are actually considered. Between the two hunks,\nthere is a \"if the source of this destination is already known, move\nto next 'i'\" continue, that does not update the progress meter.\nChanging (i+1) to dst_cnt here compensates for the reduction of the\nmatrix size we see above.\n\nMakes sense. This looks good.\n\n> \t}\n> \tstop_progress(&progress);\n"},{"id":"411975","messageId":"xmqqczzixtiy.fsf@gitster.c.googlers.com","threadId":"54772","inReplyTo":"306a48820dd3c338d2b9e2288e5a3e1c7c89f36e.1607223276.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 6/7] diffcore-rename: simplify and accelerate register_rename_src()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-10T02:51:49Z","receivedAt":"2020-12-10T02:53:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> From: Elijah Newren \n>\n> reigster_rename_src() took pains to create an array in rename_src which\n\nregister?\n\n> was sorted by pathname of the contained diff_filepair. However, the\n> fact that this array was sorted was not needed anywhere, and thus\n> represented wasted time. Simply append to the end of the array, which\n> in a usecase of note saved 45% of diffcore_rename() setup time for me.\n\nI originally started writing \"I do not recall when the sortedness\nstopped mattering\", until I realized you wrote \"anywhere\" not\n\"anymore\".\n\nI do not think of any other reason than we wanted to notice and deal\nwith the duplicated input. We do not look up the list of rename\nsources by pathname. So if we were sorting it, it is to prevent\nsuch a bug from breaking the rename machinery. What you call\n\"technically the behaviour is different\" is \"removing the safety\".\n\nI do not offhand know which caller might give us such an input in\nthe current code, so it may be entirely a safe thing to do.\nBesides, we use a hashmap of rename sources when computing exact\nrenames, so even if we need to notice and/or avoid duplicates, we do\nnot have to have register_rename_src() build the table with an\ninsertion sort as a way to do so.\n\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 3d637ba4645..816d2fbac44 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -76,36 +76,12 @@ static struct diff_rename_src {\n> } *rename_src;\n> static int rename_src_nr, rename_src_alloc;\n> \n> -static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n> +static void register_rename_src(struct diff_filepair *p)\n> {\n> -\tint first, last;\n> -\tstruct diff_filespec *one = p->one;\n> -\tunsigned short score = p->score;\n> -\n> -\tfirst = 0;\n> -\tlast = rename_src_nr;\n> -\twhile (last > first) {\n> -\t\tint next = first + ((last - first) >> 1);\n> -\t\tstruct diff_rename_src *src = &(rename_src[next]);\n> -\t\tint cmp = strcmp(one->path, src->p->one->path);\n> -\t\tif (!cmp)\n> -\t\t\treturn src;\n> -\t\tif (cmp < 0) {\n> -\t\t\tlast = next;\n> -\t\t\tcontinue;\n> -\t\t}\n> -\t\tfirst = next+1;\n> -\t}\n> -\n> -\t/* insert to make it at \"first\" */\n> \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n> +\trename_src[rename_src_nr].p = p;\n> +\trename_src[rename_src_nr].score = p->score;\n> \trename_src_nr++;\n> -\tif (first < rename_src_nr)\n> -\t\tMOVE_ARRAY(rename_src + first + 1, rename_src + first,\n> -\t\t\t rename_src_nr - first - 1);\n> -\trename_src[first].p = p;\n> -\trename_src[first].score = score;\n> -\treturn &(rename_src[first]);\n> }\n> \n> static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n"},{"id":"411983","messageId":"xmqqpn3iw3n0.fsf@gitster.c.googlers.com","threadId":"54772","inReplyTo":"CABPp-BFcSV_LPy-_AW+c-1OgzAyHfEM7D+YL+fFwxYKDheqxEg@mail.gmail.com","subject":"Re: [PATCH 2/7] diffcore-rename: remove unnecessary if-clause","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-10T06:56:19Z","receivedAt":"2020-12-10T06:57:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> Ah, so would you be okay replacing these with\n>\n> if (st_mult(num_targets, limited_sources) <= st_mult(rename_limit,\n> rename_limit))\n\nIt's subtle that the use of size_t is a sensible thing to do, and\ndefinitely deserves an in-line comment, but I think that is a good\nway to go.\n\n"},{"id":"412052","messageId":"428d8204894f668e925c640b2f72dc597164e706.1607677728.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v2 1/9] diffcore-rename: rename num_create to num_destinations","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:40Z","receivedAt":"2020-12-11T09:10:48Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nOur main data structures are rename_src and rename_dst. For counters of\nthese data structures, num_sources and num_destinations seem natural;\ndefinitely more so than using num_create for the latter.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 25 +++++++++++++------------\n 1 file changed, 13 insertions(+), 12 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex d367a6d2443..15a98f566e4 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -434,7 +434,7 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n * 1 if we need to disable inexact rename detection;\n * 2 if we would be under the limit if we were given -C instead of -C -C.\n */\n-static int too_many_rename_candidates(int num_create,\n+static int too_many_rename_candidates(int num_destinations,\n \t\t\t\t struct diff_options *options)\n {\n \tint rename_limit = options->rename_limit;\n@@ -447,17 +447,17 @@ static int too_many_rename_candidates(int num_create,\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-\t * num_create * num_src > rename_limit * rename_limit\n+\t * num_destinations * num_src > rename_limit * rename_limit\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n-\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_create * (uint64_t)num_src\n+\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n+\t ((uint64_t)num_destinations * (uint64_t)num_src\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n-\t\tnum_src > num_create ? num_src : num_create;\n+\t\tnum_src > num_destinations ? num_src : num_destinations;\n \n \t/* Are we running under -C -C? */\n \tif (!options->flags.find_copies_harder)\n@@ -469,8 +469,8 @@ static int too_many_rename_candidates(int num_create,\n \t\t\tcontinue;\n \t\tnum_src++;\n \t}\n-\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_create * (uint64_t)num_src\n+\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n+\t ((uint64_t)num_destinations * (uint64_t)num_src\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 2;\n \treturn 1;\n@@ -505,7 +505,7 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_queue_struct outq;\n \tstruct diff_score *mx;\n \tint i, j, rename_count, skip_unmodified = 0;\n-\tint num_create, dst_cnt;\n+\tint num_destinations, dst_cnt;\n \tstruct progress *progress = NULL;\n \n \tif (!minimum_score)\n@@ -570,13 +570,13 @@ void diffcore_rename(struct diff_options *options)\n \t * Calculate how many renames are left (but all the source\n \t * files still remain as options for rename/copies!)\n \t */\n-\tnum_create = (rename_dst_nr - rename_count);\n+\tnum_destinations = (rename_dst_nr - rename_count);\n \n \t/* All done? */\n-\tif (!num_create)\n+\tif (!num_destinations)\n \t\tgoto cleanup;\n \n-\tswitch (too_many_rename_candidates(num_create, options)) {\n+\tswitch (too_many_rename_candidates(num_destinations, options)) {\n \tcase 1:\n \t\tgoto cleanup;\n \tcase 2:\n@@ -593,7 +593,8 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n \t}\n \n-\tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_create), sizeof(*mx));\n+\tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n+\t\t sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n \t\tstruct diff_filespec *two = rename_dst[i].two;\n \t\tstruct diff_score *m;\n-- \ngitgitgadget\n\n"},{"id":"412053","messageId":"fc62f4c4f895a216bb2d39f654e48d390a9d1781.1607677728.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v2 2/9] diffcore-rename: avoid usage of global in too_many_rename_candidates()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:41Z","receivedAt":"2020-12-11T09:10:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ntoo_many_rename_candidates() got the number of rename destinations via\nan argument to the function, but the number of rename sources via a\nglobal variable. That felt rather inconsistent. Pass in the number of\nrename sources as an argument as well.\n\nWhile we are at it... We had a local variable, num_src, that served two\npurposes. Initially it was set to the global value, but later was used\nfor counting a subset of the number of sources. Since we now have a\nfunction argument for the former usage, introduce a clearer variable\nname for the latter usage.\n\nThis patch has no behavioral changes; it's just renaming and passing an\nargument instead of grabbing it from the global namespace. (You may\nfind it easier to view the patch using git diff's --color-words option.)\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 24 ++++++++++++------------\n 1 file changed, 12 insertions(+), 12 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 15a98f566e4..1d6675c040d 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -434,12 +434,11 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n * 1 if we need to disable inexact rename detection;\n * 2 if we would be under the limit if we were given -C instead of -C -C.\n */\n-static int too_many_rename_candidates(int num_destinations,\n+static int too_many_rename_candidates(int num_destinations, int num_sources,\n \t\t\t\t struct diff_options *options)\n {\n \tint rename_limit = options->rename_limit;\n-\tint num_src = rename_src_nr;\n-\tint i;\n+\tint i, limited_sources;\n \n \toptions->needed_rename_limit = 0;\n \n@@ -447,30 +446,30 @@ static int too_many_rename_candidates(int num_destinations,\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-\t * num_destinations * num_src > rename_limit * rename_limit\n+\t * num_destinations * num_sources > rename_limit * rename_limit\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n-\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_destinations * (uint64_t)num_src\n+\tif ((num_destinations <= rename_limit || num_sources <= rename_limit) &&\n+\t ((uint64_t)num_destinations * (uint64_t)num_sources\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n-\t\tnum_src > num_destinations ? num_src : num_destinations;\n+\t\tnum_sources > num_destinations ? num_sources : num_destinations;\n \n \t/* Are we running under -C -C? */\n \tif (!options->flags.find_copies_harder)\n \t\treturn 1;\n \n \t/* Would we bust the limit if we were running under -C? */\n-\tfor (num_src = i = 0; i < rename_src_nr; i++) {\n+\tfor (limited_sources = i = 0; i < num_sources; i++) {\n \t\tif (diff_unmodified_pair(rename_src[i].p))\n \t\t\tcontinue;\n-\t\tnum_src++;\n+\t\tlimited_sources++;\n \t}\n-\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_destinations * (uint64_t)num_src\n+\tif ((num_destinations <= rename_limit || limited_sources <= rename_limit) &&\n+\t ((uint64_t)num_destinations * (uint64_t)limited_sources\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 2;\n \treturn 1;\n@@ -576,7 +575,8 @@ void diffcore_rename(struct diff_options *options)\n \tif (!num_destinations)\n \t\tgoto cleanup;\n \n-\tswitch (too_many_rename_candidates(num_destinations, options)) {\n+\tswitch (too_many_rename_candidates(num_destinations, rename_src_nr,\n+\t\t\t\t\t options)) {\n \tcase 1:\n \t\tgoto cleanup;\n \tcase 2:\n-- \ngitgitgadget\n\n"},{"id":"412054","messageId":"7214fa73fdd13418744903f6c769fdb77c9512ce.1607677728.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v2 3/9] diffcore-rename: simplify limit check","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:42Z","receivedAt":"2020-12-11T09:10:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ndiffcore-rename had two different checks of the form\n\n if ((a < limit || b < limit) &&\n a * b <= limit * limit)\n\nThis can be simplified to\n\n if (st_mult(a, b) <= st_mult(limit, limit))\n\nwhich makes it clearer how we are checking for overflow, and makes it\nmuch easier to parse given the drop from 8 to 4 variable appearances.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 15 +++++++++------\n 1 file changed, 9 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1d6675c040d..16553ab259f 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -447,12 +447,16 @@ static int too_many_rename_candidates(int num_destinations, int num_sources,\n \t * growing larger than a \"rename_limit\" square matrix, ie:\n \t *\n \t * num_destinations * num_sources > rename_limit * rename_limit\n+\t *\n+\t * We use st_mult() to check overflow conditions; in the\n+\t * exceptional circumstance that size_t isn't large enough to hold\n+\t * the multiplication, the system won't be able to allocate enough\n+\t * memory for the matrix anyway.\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n-\tif ((num_destinations <= rename_limit || num_sources <= rename_limit) &&\n-\t ((uint64_t)num_destinations * (uint64_t)num_sources\n-\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n+\tif (st_mult(num_destinations, num_sources)\n+\t <= st_mult(rename_limit, rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n@@ -468,9 +472,8 @@ static int too_many_rename_candidates(int num_destinations, int num_sources,\n \t\t\tcontinue;\n \t\tlimited_sources++;\n \t}\n-\tif ((num_destinations <= rename_limit || limited_sources <= rename_limit) &&\n-\t ((uint64_t)num_destinations * (uint64_t)limited_sources\n-\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n+\tif (st_mult(num_destinations, limited_sources)\n+\t <= st_mult(rename_limit, rename_limit))\n \t\treturn 2;\n \treturn 1;\n }\n-- \ngitgitgadget\n\n"},{"id":"412055","messageId":"85714e1583d8c47858e6efd2d5c63bdcca748a25.1607677728.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v2 8/9] diffcore-rename: accelerate rename_dst setup","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:47Z","receivedAt":"2020-12-11T09:10:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nregister_rename_src() simply references the passed pair inside\nrename_src. In contrast, add_rename_dst() did something entirely\ndifferent for rename_dst. Instead of copying the passed pair, it made a\ncopy of the second diff_filespec from the passed pair, referenced it,\nand then set the diff_rename_dst.pair field to NULL. Later, when a\npairing is found, record_rename_pair() allocated a full diff_filepair\nvia diff_queue() and pointed its src and dst fields at the appropriate\ndiff_filespecs. This contrast between register_rename_src() for the\nrename_src data structure and add_rename_dst() for the rename_dst data\nstructure is oddly inconsistent and requires more memory and work than\nnecessary. Let's just reference the original diff_filepair in\nrename_dst as-is, just as we do with rename_src. Add a new\nrename_dst.is_rename field, since the rename_dst.p field is never NULL\nunlike the old rename_dst.pair field.\n\nTaking advantage of this change and the fact that same-named paths will\nbe adjacent, we can get rid of the sorting of the array and most of the\nlookups on it, allowing us to instead just append as we go. However,\nthere is one remaining reason to still keep locate_rename_dst():\nhandling broken pairs (i.e. when break detection is on). Those are\nsomewhat rare, but we can set up a simple strintmap to get the map\nbetween the source and the index. Doing that allows us to still have a\nfast lookup without sorting the rename_dst array. Since the sorting had\nbeen done in a weakly quadratic manner, when many renames are involved\nthis time could add up.\n\nThere is still a strcmp() in add_rename_dst() that I have left in place\nto make it easier to verify that the algorithm has the same results.\nThis strcmp() is there to check for duplicate destination entries (which\nwas the easiest way at the time to avoid segfaults in the\ndiffcore-rename code when trees had multiple entries at a given path).\nThe underlying double free()s are no longer an issue with the new\nalgorithm, but that can be addressed in a subsequent commit.\n\nThis patch is being submitted in a different order than its original\ndevelopment, but in a large rebase of many commits with lots of renames\nand with several optimizations to inexact rename detection, both setup\ntime and write back to output queue time from diffcore_rename() were\nsizeable chunks of overall runtime. This patch accelerated the setup\ntime by about 65%, and final write back to the output queue time by\nabout 50%, resulting in an overall drop of 3.5% on the execution time of\nrebasing a few dozen patches.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 148 ++++++++++++++++++++--------------------------\n 1 file changed, 65 insertions(+), 83 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex a215421a9cb..2a8fcd52928 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -9,63 +9,48 @@\n #include \"hashmap.h\"\n #include \"progress.h\"\n #include \"promisor-remote.h\"\n+#include \"strmap.h\"\n \n /* Table of rename/copy destinations */\n \n static struct diff_rename_dst {\n-\tstruct diff_filespec *two;\n-\tstruct diff_filepair *pair;\n+\tstruct diff_filepair *p;\n+\tstruct diff_filespec *filespec_to_free;\n+\tint is_rename; /* false -> just a create; true -> rename or copy */\n } *rename_dst;\n static int rename_dst_nr, rename_dst_alloc;\n+/* Mapping from break source pathname to break destination index */\n+static struct strintmap *break_idx = NULL;\n \n-static int find_rename_dst(struct diff_filespec *two)\n-{\n-\tint first, last;\n-\n-\tfirst = 0;\n-\tlast = rename_dst_nr;\n-\twhile (last > first) {\n-\t\tint next = first + ((last - first) >> 1);\n-\t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n-\t\tint cmp = strcmp(two->path, dst->two->path);\n-\t\tif (!cmp)\n-\t\t\treturn next;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n-\treturn -first - 1;\n-}\n-\n-static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two)\n+static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)\n {\n-\tint ofs = find_rename_dst(two);\n-\treturn ofs < 0 ? NULL : &rename_dst[ofs];\n+\t/* Lookup by p->ONE->path */\n+\tint idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;\n+\treturn (idx == -1) ? NULL : &rename_dst[idx];\n }\n \n /*\n * Returns 0 on success, -1 if we found a duplicate.\n */\n-static int add_rename_dst(struct diff_filespec *two)\n+static int add_rename_dst(struct diff_filepair *p)\n {\n-\tint first = find_rename_dst(two);\n-\n-\tif (first >= 0)\n+\t/*\n+\t * If we have multiple entries at the same path in the destination\n+\t * tree (an invalid tree, to be sure), turn off rename detection\n+\t * entirely. Once upon a time, diffcore-rename had double free()\n+\t * issues due to such duplicate paths, resulting in segfaults. See\n+\t * commit 4d6be03b95 (\"diffcore-rename: avoid processing duplicate\n+\t * destinations\", 2015-02-26).\n+\t */\n+\tif (rename_dst_nr > 0 &&\n+\t !strcmp(rename_dst[rename_dst_nr-1].p->two->path, p->two->path))\n \t\treturn -1;\n-\tfirst = -first - 1;\n \n-\t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);\n+\trename_dst[rename_dst_nr].p = p;\n+\trename_dst[rename_dst_nr].filespec_to_free = NULL;\n+\trename_dst[rename_dst_nr].is_rename = 0;\n \trename_dst_nr++;\n-\tif (first < rename_dst_nr)\n-\t\tMOVE_ARRAY(rename_dst + first + 1, rename_dst + first,\n-\t\t\t rename_dst_nr - first - 1);\n-\trename_dst[first].two = alloc_filespec(two->path);\n-\tfill_filespec(rename_dst[first].two, &two->oid, two->oid_valid,\n-\t\t two->mode);\n-\trename_dst[first].pair = NULL;\n \treturn 0;\n }\n \n@@ -89,6 +74,14 @@ static void register_rename_src(struct diff_filepair *p)\n \t !strcmp(rename_src[rename_src_nr-1].p->one->path, p->one->path))\n \t\treturn;\n \n+\tif (p->broken_pair) {\n+\t\tif (!break_idx) {\n+\t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\n+\t\t\tstrintmap_init(break_idx, -1);\n+\t\t}\n+\t\tstrintmap_set(break_idx, p->one->path, rename_dst_nr);\n+\t}\n+\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n \trename_src[rename_src_nr].p = p;\n \trename_src[rename_src_nr].score = p->score;\n@@ -128,14 +121,14 @@ static void prefetch(void *prefetch_options)\n \tstruct oid_array to_fetch = OID_ARRAY_INIT;\n \n \tfor (i = 0; i < rename_dst_nr; i++) {\n-\t\tif (rename_dst[i].pair)\n+\t\tif (rename_dst[i].p->renamed_pair)\n \t\t\t/*\n \t\t\t * The loop in diffcore_rename() will not need these\n \t\t\t * blobs, so skip prefetching.\n \t\t\t */\n \t\t\tcontinue; /* already found exact match */\n \t\tdiff_add_if_missing(options->repo, &to_fetch,\n-\t\t\t\t rename_dst[i].two);\n+\t\t\t\t rename_dst[i].p->two);\n \t}\n \tfor (i = 0; i < rename_src_nr; i++) {\n \t\tif (options->skip_unmodified &&\n@@ -245,26 +238,24 @@ static int estimate_similarity(struct repository *r,\n \n static void record_rename_pair(int dst_index, int src_index, int score)\n {\n-\tstruct diff_filespec *src, *dst;\n-\tstruct diff_filepair *dp;\n+\tstruct diff_filepair *src = rename_src[src_index].p;\n+\tstruct diff_filepair *dst = rename_dst[dst_index].p;\n \n-\tif (rename_dst[dst_index].pair)\n+\tif (dst->renamed_pair)\n \t\tdie(\"internal error: dst already matched.\");\n \n-\tsrc = rename_src[src_index].p->one;\n-\tsrc->rename_used++;\n-\tsrc->count++;\n+\tsrc->one->rename_used++;\n+\tsrc->one->count++;\n \n-\tdst = rename_dst[dst_index].two;\n-\tdst->count++;\n+\trename_dst[dst_index].filespec_to_free = dst->one;\n+\trename_dst[dst_index].is_rename = 1;\n \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+\tdst->one = src->one;\n+\tdst->renamed_pair = 1;\n+\tif (!strcmp(dst->one->path, dst->two->path))\n+\t\tdst->score = rename_src[src_index].score;\n \telse\n-\t\tdp->score = score;\n-\trename_dst[dst_index].pair = dp;\n+\t\tdst->score = score;\n }\n \n /*\n@@ -310,7 +301,7 @@ static int find_identical_files(struct hashmap *srcs,\n \t\t\t\tstruct diff_options *options)\n {\n \tint renames = 0;\n-\tstruct diff_filespec *target = rename_dst[dst_index].two;\n+\tstruct diff_filespec *target = rename_dst[dst_index].p->two;\n \tstruct file_similarity *p, *best = NULL;\n \tint i = 100, best_score = -1;\n \tunsigned int hash = hash_filespec(options->repo, target);\n@@ -476,7 +467,7 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i\n \t\t (mx[i].score < minimum_score))\n \t\t\tbreak; /* there is no more usable pair. */\n \t\tdst = &rename_dst[mx[i].dst];\n-\t\tif (dst->pair)\n+\t\tif (dst->is_rename)\n \t\t\tcontinue; /* already done, either exact or fuzzy. */\n \t\tif (!copies && rename_src[mx[i].src].p->one->rename_used)\n \t\t\tcontinue;\n@@ -511,7 +502,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\telse if (!options->flags.rename_empty &&\n \t\t\t\t is_empty_blob_oid(&p->two->oid))\n \t\t\t\tcontinue;\n-\t\t\telse if (add_rename_dst(p->two) < 0) {\n+\t\t\telse if (add_rename_dst(p) < 0) {\n \t\t\t\twarning(\"skipping rename detection, detected\"\n \t\t\t\t\t\" duplicate destination '%s'\",\n \t\t\t\t\tp->two->path);\n@@ -586,10 +577,10 @@ void diffcore_rename(struct diff_options *options)\n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n \t\t sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n-\t\tstruct diff_filespec *two = rename_dst[i].two;\n+\t\tstruct diff_filespec *two = rename_dst[i].p->two;\n \t\tstruct diff_score *m;\n \n-\t\tif (rename_dst[i].pair)\n+\t\tif (rename_dst[i].is_rename)\n \t\t\tcontinue; /* dealt with exact match already. */\n \n \t\tm = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];\n@@ -646,22 +637,8 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {\n-\t\t\t/*\n-\t\t\t * Creation\n-\t\t\t *\n-\t\t\t * We would output this create record if it has\n-\t\t\t * not been turned into a rename/copy already.\n-\t\t\t */\n-\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->two);\n-\t\t\tif (dst && dst->pair) {\n-\t\t\t\tdiff_q(&outq, dst->pair);\n-\t\t\t\tpair_to_free = p;\n-\t\t\t}\n-\t\t\telse\n-\t\t\t\t/* no matching rename/copy source, so\n-\t\t\t\t * record this as a creation.\n-\t\t\t\t */\n-\t\t\t\tdiff_q(&outq, p);\n+\t\t\t/* Creation */\n+\t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {\n \t\t\t/*\n@@ -682,8 +659,10 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t */\n \t\t\tif (DIFF_PAIR_BROKEN(p)) {\n \t\t\t\t/* broken delete */\n-\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->one);\n-\t\t\t\tif (dst && dst->pair)\n+\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p);\n+\t\t\t\tif (!dst)\n+\t\t\t\t\tBUG(\"tracking failed somehow; failed to find associated dst for broken pair\");\n+\t\t\t\tif (dst->is_rename)\n \t\t\t\t\t/* counterpart is now rename/copy */\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\n@@ -693,16 +672,14 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\n \n-\t\t\tif (pair_to_free)\n-\t\t\t\t;\n-\t\t\telse\n+\t\t\tif (!pair_to_free)\n \t\t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (!diff_unmodified_pair(p))\n \t\t\t/* all the usual ones need to be kept */\n \t\t\tdiff_q(&outq, p);\n \t\telse\n-\t\t\t/* no need to keep unmodified pairs */\n+\t\t\t/* no need to keep unmodified pairs; FIXME: remove earlier? */\n \t\t\tpair_to_free = p;\n \n \t\tif (pair_to_free)\n@@ -715,11 +692,16 @@ void diffcore_rename(struct diff_options *options)\n \tdiff_debug_queue(\"done collapsing\", q);\n \n \tfor (i = 0; i < rename_dst_nr; i++)\n-\t\tfree_filespec(rename_dst[i].two);\n+\t\tif (rename_dst[i].filespec_to_free)\n+\t\t\tfree_filespec(rename_dst[i].filespec_to_free);\n \n \tFREE_AND_NULL(rename_dst);\n \trename_dst_nr = rename_dst_alloc = 0;\n \tFREE_AND_NULL(rename_src);\n \trename_src_nr = rename_src_alloc = 0;\n+\tif (break_idx) {\n+\t\tstrintmap_clear(break_idx);\n+\t\tFREE_AND_NULL(break_idx);\n+\t}\n \treturn;\n }\n-- \ngitgitgadget\n\n"},{"id":"412056","messageId":"a58639b2927fc9b51351d2d1da134a757c657723.1607677728.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v2 7/9] diffcore-rename: simplify and accelerate register_rename_src()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:46Z","receivedAt":"2020-12-11T09:10:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nregister_rename_src() took pains to create an array in rename_src which\nwas sorted by pathname of the contained diff_filepair. The sorting was\nentirely unnecessary since callers pass filepairs to us in sorted\norder. We can simply append to the end of the rename_src array,\nspeeding up diffcore_rename() setup time.\n\nAlso, note that I dropped the return type on the function since it was\nunconditionally discarded anyway.\n\nThis patch is being submitted in a different order than its original\ndevelopment, but in a large rebase of many commits with lots of renames\nand with several optimizations to inexact rename detection,\ndiffcore_rename() setup time was a sizeable chunk of overall runtime.\nThis patch dropped execution time of rebasing 35 commits with lots of\nrenames by 2% overall.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 39 +++++++++++++--------------------------\n 1 file changed, 13 insertions(+), 26 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 55a188abcc3..a215421a9cb 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -76,36 +76,23 @@ static struct diff_rename_src {\n } *rename_src;\n static int rename_src_nr, rename_src_alloc;\n \n-static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n+static void register_rename_src(struct diff_filepair *p)\n {\n-\tint first, last;\n-\tstruct diff_filespec *one = p->one;\n-\tunsigned short score = p->score;\n-\n-\tfirst = 0;\n-\tlast = rename_src_nr;\n-\twhile (last > first) {\n-\t\tint next = first + ((last - first) >> 1);\n-\t\tstruct diff_rename_src *src = &(rename_src[next]);\n-\t\tint cmp = strcmp(one->path, src->p->one->path);\n-\t\tif (!cmp)\n-\t\t\treturn src;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n+\t/*\n+\t * If we have multiple entries at the same path in the source tree\n+\t * (an invalid tree, to be sure), avoid using more more than one\n+\t * such entry in rename detection. Once upon a time, doing so\n+\t * caused segfaults; see commit 25d5ea410f (\"[PATCH] Redo\n+\t * rename/copy detection logic.\", 2005-05-24).\n+\t */\n+\tif (rename_src_nr > 0 &&\n+\t !strcmp(rename_src[rename_src_nr-1].p->one->path, p->one->path))\n+\t\treturn;\n \n-\t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n+\trename_src[rename_src_nr].p = p;\n+\trename_src[rename_src_nr].score = p->score;\n \trename_src_nr++;\n-\tif (first < rename_src_nr)\n-\t\tMOVE_ARRAY(rename_src + first + 1, rename_src + first,\n-\t\t\t rename_src_nr - first - 1);\n-\trename_src[first].p = p;\n-\trename_src[first].score = score;\n-\treturn &(rename_src[first]);\n }\n \n static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n-- \ngitgitgadget\n\n"},{"id":"412057","messageId":"bf3581b1ac12bd616518f8093365d38eee4f01b7.1607677728.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v2 4/9] diffcore-rename: reduce jumpiness in progress counters","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:43Z","receivedAt":"2020-12-11T09:10:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nInexact rename detection works by comparing all sources to all\ndestinations, computing similarities, and then finding the best matches\namong those that are sufficiently similar.\n\nHowever, it is preceded by exact rename detection that works by\nchecking if there are files with identical hashes. If exact renames are\nfound, we can exclude some files from inexact rename detection.\n\nThe inexact rename detection loops over the full set of files, but\nimmediately skips those for which rename_dst[i].is_rename is true and\nthus doesn't compare any sources to that destination. As such, these\npaths shouldn't be included in the progress counter.\n\nFor the eagle eyed, this change hints at an actual optimization -- the\nfirst one I presented at Git Merge 2020. I'll be submitting that\noptimization later, once the basic merge-ort algorithm has merged.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 16553ab259f..55a188abcc3 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -593,7 +593,7 @@ void diffcore_rename(struct diff_options *options)\n \tif (options->show_rename_progress) {\n \t\tprogress = start_delayed_progress(\n \t\t\t\t_(\"Performing inexact rename detection\"),\n-\t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n+\t\t\t\t(uint64_t)num_destinations * (uint64_t)rename_src_nr);\n \t}\n \n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n@@ -633,7 +633,8 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tdiff_free_filespec_blob(two);\n \t\t}\n \t\tdst_cnt++;\n-\t\tdisplay_progress(progress, (uint64_t)(i+1)*(uint64_t)rename_src_nr);\n+\t\tdisplay_progress(progress,\n+\t\t\t\t (uint64_t)dst_cnt * (uint64_t)rename_src_nr);\n \t}\n \tstop_progress(&progress);\n \n-- \ngitgitgadget\n\n"},{"id":"412058","messageId":"af256b1c534e3fe103bb01bd673ac3a2ec467de4.1607677728.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v2 9/9] diffcore-rename: remove unneccessary duplicate entry checks","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:48Z","receivedAt":"2020-12-11T09:10:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nCommit 25d5ea410f (\"[PATCH] Redo rename/copy detection logic.\",\n2005-05-24) added a duplicate entry check on rename_src in order to\navoid segfaults; the code at the time was prone to double free()s and an\neasy way to avoid it was just to turn off rename detection for any\nduplicate entries. Note that the form of the check was modified two\ncommits ago in this series.\n\nSimilarly, commit 4d6be03b95 (\"diffcore-rename: avoid processing\nduplicate destinations\", 2015-02-26) added a duplicate entry check\non rename_dst for the exact same reason -- the code was prone to double\nfree()s, and an easy way to avoid it was just to turn off rename\ndetection entirely. Note that the form of the check was modified in the\ncommit just before this one.\n\nIn the original code in both places, the code was dealing with\nindividual diff_filespecs and trying to match things up, instead of just\nkeeping the original diff_filepairs around as we do now. The\nintervening change in structure has fixed the accounting problems and\nthe associated double free()s that used to occur, and thus we already\nhave a better fix. As such, we can remove the band-aid checks for\nduplicate entries.\n\nDue to the last two patches, the diffcore_rename() setup is no longer a\nsizeable chunk of overall runtime. Thus, in a large rebase of many\ncommits with lots of renames and several optimizations to inexact rename\ndetection, this patch only speeds up the overall code by about half a\npercent or so and is pretty close to the run-to-run variability making\nit hard to get an exact measurement. However, with some trace2 regions\naround the setup code in diffcore_rename() so that I can focus on just\nit, I measure that this patch consistently saves almost a third of the\nremaining time spent in diffcore_rename() setup.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 23 -----------------------\n t/t4058-diff-duplicates.sh | 2 +-\n 2 files changed, 1 insertion(+), 24 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 2a8fcd52928..90db9ebd6d0 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -34,18 +34,6 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)\n */\n static int add_rename_dst(struct diff_filepair *p)\n {\n-\t/*\n-\t * If we have multiple entries at the same path in the destination\n-\t * tree (an invalid tree, to be sure), turn off rename detection\n-\t * entirely. Once upon a time, diffcore-rename had double free()\n-\t * issues due to such duplicate paths, resulting in segfaults. See\n-\t * commit 4d6be03b95 (\"diffcore-rename: avoid processing duplicate\n-\t * destinations\", 2015-02-26).\n-\t */\n-\tif (rename_dst_nr > 0 &&\n-\t !strcmp(rename_dst[rename_dst_nr-1].p->two->path, p->two->path))\n-\t\treturn -1;\n-\n \tALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);\n \trename_dst[rename_dst_nr].p = p;\n \trename_dst[rename_dst_nr].filespec_to_free = NULL;\n@@ -63,17 +51,6 @@ static int rename_src_nr, rename_src_alloc;\n \n static void register_rename_src(struct diff_filepair *p)\n {\n-\t/*\n-\t * If we have multiple entries at the same path in the source tree\n-\t * (an invalid tree, to be sure), avoid using more more than one\n-\t * such entry in rename detection. Once upon a time, doing so\n-\t * caused segfaults; see commit 25d5ea410f (\"[PATCH] Redo\n-\t * rename/copy detection logic.\", 2005-05-24).\n-\t */\n-\tif (rename_src_nr > 0 &&\n-\t !strcmp(rename_src[rename_src_nr-1].p->one->path, p->one->path))\n-\t\treturn;\n-\n \tif (p->broken_pair) {\n \t\tif (!break_idx) {\n \t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\ndiff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\nindex ad3f37d388d..54614b814db 100755\n--- a/t/t4058-diff-duplicates.sh\n+++ b/t/t4058-diff-duplicates.sh\n@@ -91,7 +91,7 @@ test_expect_success 'diff-tree between duplicate trees' '\n test_expect_success 'diff-tree with renames' '\n \t# See NOTICE at top of file.\n \tgit diff-tree -M -r --no-abbrev one two >actual &&\n-\ttest_cmp expect actual\n+\ttest_must_be_empty actual\n '\n \n test_expect_success 'diff-tree FROM duplicate tree' '\n-- \ngitgitgadget\n"},{"id":"412059","messageId":"9a4a3159acf6144bfbfc773195a141afaa95dad3.1607677728.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v2 5/9] t4058: add more tests and documentation for duplicate tree entry handling","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:44Z","receivedAt":"2020-12-11T09:10:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nCommit 4d6be03b95 (\"diffcore-rename: avoid processing duplicate\ndestinations\", 2015-02-26) added t4058 to demonstrate that a workaround\nit added to avoid double frees (namely to just turn off rename detection\nwhen trees had duplicate entries) would indeed avoid segfaults. The\ntests, though, give the impression that the expected diffs are \"correct\"\nwhen in reality they are just \"don't segfault, and do something\nsemi-reasonable under the circumstances\". Add some notes to make this\nclearer.\n\nAlso, commit 25d5ea410f (\"[PATCH] Redo rename/copy detection logic.\",\n2005-05-24) added a similar workaround to avoid segfaults, but for\nrename_src rather than rename_dst. I do not see any tests in the\ntestsuite to cover the collision detection of entries limited to the\nsource side, so add a couple.\n\nSigned-off-by: Elijah Newren \n---\n t/t4058-diff-duplicates.sh | 47 ++++++++++++++++++++++++++++++++++++--\n 1 file changed, 45 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\nindex c24ee175ef0..bd685089561 100755\n--- a/t/t4058-diff-duplicates.sh\n+++ b/t/t4058-diff-duplicates.sh\n@@ -1,5 +1,14 @@\n #!/bin/sh\n \n+# NOTICE:\n+# This testsuite does a number of diffs and checks that the output match.\n+# However, it is a \"garbage in, garbage out\" situation; the trees have\n+# duplicate entries for individual paths, and it results in diffs that do\n+# not make much sense. As such, it is not clear that the diffs are\n+# \"correct\". The primary purpose of these tests was to verify that\n+# diff-tree does not segfault, but there is perhaps some value in ensuring\n+# that the diff output isn't wildly unreasonable.\n+\n test_description='test tree diff when trees have duplicate entries'\n . ./test-lib.sh\n \n@@ -57,7 +66,16 @@ test_expect_success 'create trees with duplicate entries' '\n \tgit tag two $outer_two\n '\n \n-test_expect_success 'diff-tree between trees' '\n+test_expect_success 'create tree without duplicate entries' '\n+\tblob_one=$(echo one | git hash-object -w --stdin) &&\n+\touter_three=$(make_tree \\\n+\t\t100644 renamed $blob_one\n+\t) &&\n+\tgit tag three $outer_three\n+'\n+\n+test_expect_success 'diff-tree between duplicate trees' '\n+\t# See NOTICE at top of file\n \t{\n \t\tprintf \":000000 100644 $ZERO_OID $blob_two A\\touter/inner\\n\" &&\n \t\tprintf \":000000 100644 $ZERO_OID $blob_two A\\touter/inner\\n\" &&\n@@ -71,9 +89,34 @@ test_expect_success 'diff-tree between trees' '\n '\n \n test_expect_success 'diff-tree with renames' '\n-\t# same expectation as above, since we disable rename detection\n+\t# See NOTICE at top of file.\n \tgit diff-tree -M -r --no-abbrev one two >actual &&\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'diff-tree FROM duplicate tree' '\n+\t# See NOTICE at top of file.\n+\t{\n+\t\tprintf \":100644 000000 $blob_one $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":000000 100644 $ZERO_OID $blob_one A\\trenamed\\n\"\n+\t} >expect &&\n+\tgit diff-tree -r --no-abbrev one three >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'diff-tree FROM duplicate tree, with renames' '\n+\t# See NOTICE at top of file.\n+\t{\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 100644 $blob_one $blob_one R100\\touter/inner\\trenamed\\n\"\n+\t} >expect &&\n+\tgit diff-tree -M -r --no-abbrev one three >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"412060","messageId":"8db27892c598a3976c0742e23563f1d360b8dee1.1607677728.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v2 6/9] t4058: explore duplicate tree entry handling in a bit more detail","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:45Z","receivedAt":"2020-12-11T09:10:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nWhile creating the last commit, I found a number of other cases where\ngit would segfault when faced with trees that have duplicate entries.\nNone of these segfaults are in the diffcore-rename code (they all occur\nin cache-tree and unpack-trees). Further, to my knowledge, no one has\never been adversely affected by these bugs, and given that it has been\n15 years and folks have fixed a few other issues with historical\nduplicate entries (as noted in the last commit), I am not sure we will\never run into anyone having problems with these. So I am not sure these\nare worth fixing, but it doesn't hurt to at least document these\nfailures in the same test file that is concerned with duplicate tree\nentries.\n\nSigned-off-by: Elijah Newren \n---\n t/t4058-diff-duplicates.sh | 67 ++++++++++++++++++++++++++++++++++++++\n 1 file changed, 67 insertions(+)\n\ndiff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\nindex bd685089561..ad3f37d388d 100755\n--- a/t/t4058-diff-duplicates.sh\n+++ b/t/t4058-diff-duplicates.sh\n@@ -119,4 +119,71 @@ test_expect_success 'diff-tree FROM duplicate tree, with renames' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'create a few commits' '\n+\tgit commit-tree -m \"Duplicate Entries\" two^{tree} >commit_id &&\n+\tgit branch base $(cat commit_id) &&\n+\n+\tgit commit-tree -p $(cat commit_id) -m \"Just one\" three^{tree} >up &&\n+\tgit branch update $(cat up) &&\n+\n+\tgit commit-tree -p $(cat up) -m \"Back to weird\" two^{tree} >final &&\n+\tgit branch final $(cat final) &&\n+\n+\trm commit_id up final\n+'\n+\n+test_expect_failure 'git read-tree does not segfault' '\n+\ttest_when_finished rm .git/index.lock &&\n+\ttest_might_fail git read-tree --reset base\n+'\n+\n+test_expect_failure 'reset --hard does not segfault' '\n+\ttest_when_finished rm .git/index.lock &&\n+\tgit checkout base &&\n+\ttest_might_fail git reset --hard\n+'\n+\n+test_expect_failure 'git diff HEAD does not segfault' '\n+\tgit checkout base &&\n+\tGIT_TEST_CHECK_CACHE_TREE=false &&\n+\tgit reset --hard &&\n+\ttest_might_fail git diff HEAD\n+'\n+\n+test_expect_failure 'can switch to another branch when status is empty' '\n+\tgit clean -ffdqx &&\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual &&\n+\tgit checkout update\n+'\n+\n+test_expect_success 'forcibly switch to another branch, verify status empty' '\n+\tgit checkout -f update &&\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual\n+'\n+\n+test_expect_success 'fast-forward from non-duplicate entries to duplicate' '\n+\tgit merge final\n+'\n+\n+test_expect_failure 'clean status, switch branches, status still clean' '\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual &&\n+\tgit checkout base &&\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual\n+'\n+\n+test_expect_success 'switch to base branch and force status to be clean' '\n+\tgit checkout base &&\n+\tGIT_TEST_CHECK_CACHE_TREE=false git reset --hard &&\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual\n+'\n+\n+test_expect_failure 'fast-forward from duplicate entries to non-duplicate' '\n+\tgit merge update\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"412061","messageId":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.git.git.1607223276.gitgitgadget@gmail.com","subject":"[PATCH v2 0/9] diffcore-rename improvements","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-11T09:08:39Z","receivedAt":"2020-12-11T09:10:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This patch series includes 3 small code cleanups, 1 small bug fix (or\nperhaps just a UI improvement -- it's a very minor issue either way), more\ntestcases, and 3 performance improvements. The first 7 patches are\nrelatively easy to review, while the second to last one...is a bit more\ninvolved (but provided the biggest performance boost).\n\nChanges since v1:\n\n * Inserted a patch at the beginning to rename num_create to\n num_destinations, as suggested by Junio. Also simplifies patch 2.\n * Used st_mult() to simplify the limit check\n * Dropped a patch Junio didn't care for\n * Inserted two new patches, 5 & 6, to add new testcases motivated by\n Junio's comments about register_rename_src() and correctness in the face\n of duplicate tree entries.\n * Modified patch 7 so that register_rename_src() behaves identically to\n current code, even when trees have duplicate entries\n * Added a new patch 9 which rips out the unnecessary duplicate entry checks\n for BOTH rename_src and rename_dst, and documents why they are safe to\n remove. This is also supported by the new testcases in patches 5 and 6. I\n also ran t4058 (which patches 5 and 6 add to) under valgrind afterwards\n and verified that no errors from diffcore-rename were reported (valgrind\n did report problems from cache-tree and unpack-trees, as documented in\n patch 6, but that was true before this patch series and probably has been\n that way for years or decades).\n * Miscellaneous small cleanups highlighted by Taylor and Junio\n\nElijah Newren (9):\n diffcore-rename: rename num_create to num_destinations\n diffcore-rename: avoid usage of global in too_many_rename_candidates()\n diffcore-rename: simplify limit check\n diffcore-rename: reduce jumpiness in progress counters\n t4058: add more tests and documentation for duplicate tree entry\n handling\n t4058: explore duplicate tree entry handling in a bit more detail\n diffcore-rename: simplify and accelerate register_rename_src()\n diffcore-rename: accelerate rename_dst setup\n diffcore-rename: remove unneccessary duplicate entry checks\n\n diffcore-rename.c | 209 ++++++++++++++-----------------------\n t/t4058-diff-duplicates.sh | 114 +++++++++++++++++++-\n 2 files changed, 192 insertions(+), 131 deletions(-)\n\n\nbase-commit: 3a0b884caba2752da0af626fb2de7d597c844e8b\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-929%2Fnewren%2Fdiffcore-rename-improvements-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-929/newren/diffcore-rename-improvements-v2\nPull-Request: https://github.com/git/git/pull/929\n\nRange-diff vs v1:\n\n 3: 30381addc5c ! 1: 428d8204894 diffcore-rename: rename num_create to num_targets\n @@ Metadata\n Author: Elijah Newren \n \n ## Commit message ##\n - diffcore-rename: rename num_create to num_targets\n + diffcore-rename: rename num_create to num_destinations\n \n - Files added since the base commit serve as targets for rename detection.\n - While it is true that added files can be thought of as being \"created\"\n - when they are added IF they have no pairing file that they were renamed\n - from, and it is true we start out not knowing what the pairings are, it\n - seems a little odd to think in terms of \"file creation\" when we are\n - looking for \"file renames\". Rename the variable to avoid this minor\n - point of confusion.\n + Our main data structures are rename_src and rename_dst. For counters of\n + these data structures, num_sources and num_destinations seem natural;\n + definitely more so than using num_create for the latter.\n \n Signed-off-by: Elijah Newren \n \n ## diffcore-rename.c ##\n +@@ diffcore-rename.c: static void record_if_better(struct diff_score m[], struct diff_score *o)\n + * 1 if we need to disable inexact rename detection;\n + * 2 if we would be under the limit if we were given -C instead of -C -C.\n + */\n +-static int too_many_rename_candidates(int num_create,\n ++static int too_many_rename_candidates(int num_destinations,\n + \t\t\t\t struct diff_options *options)\n + {\n + \tint rename_limit = options->rename_limit;\n +@@ diffcore-rename.c: static int too_many_rename_candidates(int num_create,\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 +-\t * num_create * num_src > rename_limit * rename_limit\n ++\t * num_destinations * num_src > rename_limit * rename_limit\n + \t */\n + \tif (rename_limit <= 0)\n + \t\trename_limit = 32767;\n +-\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n +-\t ((uint64_t)num_create * (uint64_t)num_src\n ++\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n ++\t ((uint64_t)num_destinations * (uint64_t)num_src\n + \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n + \t\treturn 0;\n + \n + \toptions->needed_rename_limit =\n +-\t\tnum_src > num_create ? num_src : num_create;\n ++\t\tnum_src > num_destinations ? num_src : num_destinations;\n + \n + \t/* Are we running under -C -C? */\n + \tif (!options->flags.find_copies_harder)\n +@@ diffcore-rename.c: static int too_many_rename_candidates(int num_create,\n + \t\t\tcontinue;\n + \t\tnum_src++;\n + \t}\n +-\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n +-\t ((uint64_t)num_create * (uint64_t)num_src\n ++\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n ++\t ((uint64_t)num_destinations * (uint64_t)num_src\n + \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n + \t\treturn 2;\n + \treturn 1;\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \tstruct diff_queue_struct outq;\n \tstruct diff_score *mx;\n \tint i, j, rename_count, skip_unmodified = 0;\n -\tint num_create, dst_cnt;\n -+\tint num_targets, dst_cnt;\n ++\tint num_destinations, dst_cnt;\n \tstruct progress *progress = NULL;\n \n \tif (!minimum_score)\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t * files still remain as options for rename/copies!)\n \t */\n -\tnum_create = (rename_dst_nr - rename_count);\n -+\tnum_targets = (rename_dst_nr - rename_count);\n ++\tnum_destinations = (rename_dst_nr - rename_count);\n \n \t/* All done? */\n -\tif (!num_create)\n -+\tif (!num_targets)\n ++\tif (!num_destinations)\n \t\tgoto cleanup;\n \n --\tswitch (too_many_rename_candidates(num_create, rename_src_nr, options)) {\n -+\tswitch (too_many_rename_candidates(num_targets, rename_src_nr, options)) {\n +-\tswitch (too_many_rename_candidates(num_create, options)) {\n ++\tswitch (too_many_rename_candidates(num_destinations, options)) {\n \tcase 1:\n \t\tgoto cleanup;\n \tcase 2:\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t}\n \n -\tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_create), sizeof(*mx));\n -+\tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_targets), sizeof(*mx));\n ++\tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n ++\t\t sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n \t\tstruct diff_filespec *two = rename_dst[i].two;\n \t\tstruct diff_score *m;\n 1: 95a3fcb8be0 ! 2: fc62f4c4f89 diffcore-rename: avoid usage of global in too_many_rename_candidates()\n @@ Metadata\n ## Commit message ##\n diffcore-rename: avoid usage of global in too_many_rename_candidates()\n \n - too_many_rename_candidates() got the number of rename targets via an\n - argument to the function, but the number of rename sources via a global\n - variable. That felt rather inconsistent. Pass in the number of rename\n - sources as an argument as well.\n + too_many_rename_candidates() got the number of rename destinations via\n + an argument to the function, but the number of rename sources via a\n + global variable. That felt rather inconsistent. Pass in the number of\n + rename sources as an argument as well.\n \n While we are at it... We had a local variable, num_src, that served two\n - purposes. Initially it was set to this global value, but later was used\n + purposes. Initially it was set to the global value, but later was used\n for counting a subset of the number of sources. Since we now have a\n function argument for the former usage, introduce a clearer variable\n name for the latter usage.\n @@ diffcore-rename.c: static void record_if_better(struct diff_score m[], struct di\n * 1 if we need to disable inexact rename detection;\n * 2 if we would be under the limit if we were given -C instead of -C -C.\n */\n --static int too_many_rename_candidates(int num_create,\n -+static int too_many_rename_candidates(int num_targets, int num_sources,\n +-static int too_many_rename_candidates(int num_destinations,\n ++static int too_many_rename_candidates(int num_destinations, int num_sources,\n \t\t\t\t struct diff_options *options)\n {\n \tint rename_limit = options->rename_limit;\n @@ diffcore-rename.c: static void record_if_better(struct diff_score m[], struct di\n \n \toptions->needed_rename_limit = 0;\n \n -@@ diffcore-rename.c: static int too_many_rename_candidates(int num_create,\n +@@ diffcore-rename.c: static int too_many_rename_candidates(int num_destinations,\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 --\t * num_create * num_src > rename_limit * rename_limit\n -+\t * num_targets * num_sources > rename_limit * rename_limit\n +-\t * num_destinations * num_src > rename_limit * rename_limit\n ++\t * num_destinations * num_sources > rename_limit * rename_limit\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n --\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n --\t ((uint64_t)num_create * (uint64_t)num_src\n -+\tif ((num_targets <= rename_limit || num_sources <= rename_limit) &&\n -+\t ((uint64_t)num_targets * (uint64_t)num_sources\n +-\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n +-\t ((uint64_t)num_destinations * (uint64_t)num_src\n ++\tif ((num_destinations <= rename_limit || num_sources <= rename_limit) &&\n ++\t ((uint64_t)num_destinations * (uint64_t)num_sources\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n --\t\tnum_src > num_create ? num_src : num_create;\n -+\t\tnum_sources > num_targets ? num_sources : num_targets;\n +-\t\tnum_src > num_destinations ? num_src : num_destinations;\n ++\t\tnum_sources > num_destinations ? num_sources : num_destinations;\n \n \t/* Are we running under -C -C? */\n \tif (!options->flags.find_copies_harder)\n @@ diffcore-rename.c: static int too_many_rename_candidates(int num_create,\n -\t\tnum_src++;\n +\t\tlimited_sources++;\n \t}\n --\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n --\t ((uint64_t)num_create * (uint64_t)num_src\n -+\tif ((num_targets <= rename_limit || limited_sources <= rename_limit) &&\n -+\t ((uint64_t)num_targets * (uint64_t)limited_sources\n +-\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n +-\t ((uint64_t)num_destinations * (uint64_t)num_src\n ++\tif ((num_destinations <= rename_limit || limited_sources <= rename_limit) &&\n ++\t ((uint64_t)num_destinations * (uint64_t)limited_sources\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 2;\n \treturn 1;\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n - \tif (!num_create)\n + \tif (!num_destinations)\n \t\tgoto cleanup;\n \n --\tswitch (too_many_rename_candidates(num_create, options)) {\n -+\tswitch (too_many_rename_candidates(num_create, rename_src_nr, options)) {\n +-\tswitch (too_many_rename_candidates(num_destinations, options)) {\n ++\tswitch (too_many_rename_candidates(num_destinations, rename_src_nr,\n ++\t\t\t\t\t options)) {\n \tcase 1:\n \t\tgoto cleanup;\n \tcase 2:\n 2: f96bb36930a ! 3: 7214fa73fdd diffcore-rename: remove unnecessary if-clause\n @@ Metadata\n Author: Elijah Newren \n \n ## Commit message ##\n - diffcore-rename: remove unnecessary if-clause\n + diffcore-rename: simplify limit check\n \n diffcore-rename had two different checks of the form\n \n if ((a < limit || b < limit) &&\n a * b <= limit * limit)\n \n - Since these are all non-negative integers, this can be simplified to\n + This can be simplified to\n \n - if (a * b <= limit * limit)\n + if (st_mult(a, b) <= st_mult(limit, limit))\n \n - The only advantage of the former would be in avoiding a couple\n - multiplications in the rare case that both a and b are BOTH very large.\n - I see no reason for such an optimization given that this code is not in\n - any kind of loop. Prefer code simplicity here and change to the latter\n - form.\n + which makes it clearer how we are checking for overflow, and makes it\n + much easier to parse given the drop from 8 to 4 variable appearances.\n \n Signed-off-by: Elijah Newren \n \n ## diffcore-rename.c ##\n -@@ diffcore-rename.c: static int too_many_rename_candidates(int num_targets, int num_sources,\n +@@ diffcore-rename.c: static int too_many_rename_candidates(int num_destinations, int num_sources,\n + \t * growing larger than a \"rename_limit\" square matrix, ie:\n + \t *\n + \t * num_destinations * num_sources > rename_limit * rename_limit\n ++\t *\n ++\t * We use st_mult() to check overflow conditions; in the\n ++\t * exceptional circumstance that size_t isn't large enough to hold\n ++\t * the multiplication, the system won't be able to allocate enough\n ++\t * memory for the matrix anyway.\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n --\tif ((num_targets <= rename_limit || num_sources <= rename_limit) &&\n --\t ((uint64_t)num_targets * (uint64_t)num_sources\n +-\tif ((num_destinations <= rename_limit || num_sources <= rename_limit) &&\n +-\t ((uint64_t)num_destinations * (uint64_t)num_sources\n -\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n -+\tif ((uint64_t)num_targets * (uint64_t)num_sources\n -+\t <= (uint64_t)rename_limit * (uint64_t)rename_limit)\n ++\tif (st_mult(num_destinations, num_sources)\n ++\t <= st_mult(rename_limit, rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n -@@ diffcore-rename.c: static int too_many_rename_candidates(int num_targets, int num_sources,\n +@@ diffcore-rename.c: static int too_many_rename_candidates(int num_destinations, int num_sources,\n \t\t\tcontinue;\n \t\tlimited_sources++;\n \t}\n --\tif ((num_targets <= rename_limit || limited_sources <= rename_limit) &&\n --\t ((uint64_t)num_targets * (uint64_t)limited_sources\n +-\tif ((num_destinations <= rename_limit || limited_sources <= rename_limit) &&\n +-\t ((uint64_t)num_destinations * (uint64_t)limited_sources\n -\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n -+\tif ((uint64_t)num_targets * (uint64_t)limited_sources\n -+\t <= (uint64_t)rename_limit * (uint64_t)rename_limit)\n ++\tif (st_mult(num_destinations, limited_sources)\n ++\t <= st_mult(rename_limit, rename_limit))\n \t\treturn 2;\n \treturn 1;\n }\n 4: 77ca4656ed4 < -: ----------- diffcore-rename: change a few comments to use 'add' instead of 'create'\n 5: e8257516c1f ! 4: bf3581b1ac1 diffcore-rename: reduce jumpiness in progress counters\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t\tprogress = start_delayed_progress(\n \t\t\t\t_(\"Performing inexact rename detection\"),\n -\t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n -+\t\t\t\t(uint64_t)num_targets * (uint64_t)rename_src_nr);\n ++\t\t\t\t(uint64_t)num_destinations * (uint64_t)rename_src_nr);\n \t}\n \n - \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_targets), sizeof(*mx));\n + \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t\t\tdiff_free_filespec_blob(two);\n \t\t}\n -: ----------- > 5: 9a4a3159acf t4058: add more tests and documentation for duplicate tree entry handling\n -: ----------- > 6: 8db27892c59 t4058: explore duplicate tree entry handling in a bit more detail\n 6: 306a48820dd ! 7: a58639b2927 diffcore-rename: simplify and accelerate register_rename_src()\n @@ Metadata\n ## Commit message ##\n diffcore-rename: simplify and accelerate register_rename_src()\n \n - reigster_rename_src() took pains to create an array in rename_src which\n - was sorted by pathname of the contained diff_filepair. However, the\n - fact that this array was sorted was not needed anywhere, and thus\n - represented wasted time. Simply append to the end of the array, which\n - in a usecase of note saved 45% of diffcore_rename() setup time for me.\n -\n - Technically, there is one difference in the end result for the code. IF\n - the caller of diffcore-rename provides a set of pairs with a duplicate\n - filename in the sources (an erroneous input condition), the old code\n - would simply ignore the duplicate (without warning or error). The new\n - code will simply swallow it and thus allow multiple pairings for the\n - \"same\" source file. Checking for this error condition is expensive\n - (basically undoing the optimization) and the only existing callers\n - already avoid passing such an invalid input. If someone really wants to\n - add some error checking here on this input condition, I believe they\n - should add a separate function which can be called before\n - diffcore_rename(), and then other callers that don't need additional\n - checks because of their design (such as merge-ort) can avoid the extra\n - overhead.\n + register_rename_src() took pains to create an array in rename_src which\n + was sorted by pathname of the contained diff_filepair. The sorting was\n + entirely unnecessary since callers pass filepairs to us in sorted\n + order. We can simply append to the end of the rename_src array,\n + speeding up diffcore_rename() setup time.\n \n Also, note that I dropped the return type on the function since it was\n unconditionally discarded anyway.\n @@ diffcore-rename.c: static struct diff_rename_src {\n -\t\t}\n -\t\tfirst = next+1;\n -\t}\n --\n ++\t/*\n ++\t * If we have multiple entries at the same path in the source tree\n ++\t * (an invalid tree, to be sure), avoid using more more than one\n ++\t * such entry in rename detection. Once upon a time, doing so\n ++\t * caused segfaults; see commit 25d5ea410f (\"[PATCH] Redo\n ++\t * rename/copy detection logic.\", 2005-05-24).\n ++\t */\n ++\tif (rename_src_nr > 0 &&\n ++\t !strcmp(rename_src[rename_src_nr-1].p->one->path, p->one->path))\n ++\t\treturn;\n + \n -\t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n +\trename_src[rename_src_nr].p = p;\n 7: 3e83b51628b ! 8: 85714e1583d Accelerate rename_dst setup\n @@ Metadata\n Author: Elijah Newren \n \n ## Commit message ##\n - Accelerate rename_dst setup\n + diffcore-rename: accelerate rename_dst setup\n \n register_rename_src() simply references the passed pair inside\n rename_src. In contrast, add_rename_dst() did something entirely\n @@ Commit message\n been done in a weakly quadratic manner, when many renames are involved\n this time could add up.\n \n - There is still a strcmp() in add_rename_dst() that I feel is\n - unnecessary, because I disagree with a regression test in t4058.\n - However, I'm trying to increase performance without changing behavior,\n - so I'll leave that fight for a different day (a TODO has been left in\n - the code about it).\n + There is still a strcmp() in add_rename_dst() that I have left in place\n + to make it easier to verify that the algorithm has the same results.\n + This strcmp() is there to check for duplicate destination entries (which\n + was the easiest way at the time to avoid segfaults in the\n + diffcore-rename code when trees had multiple entries at a given path).\n + The underlying double free()s are no longer an issue with the new\n + algorithm, but that can be addressed in a subsequent commit.\n \n This patch is being submitted in a different order than its original\n development, but in a large rebase of many commits with lots of renames\n @@ Commit message\n \n ## diffcore-rename.c ##\n @@\n - #include \"cache.h\"\n - #include \"diff.h\"\n - #include \"diffcore.h\"\n --#include \"object-store.h\"\n #include \"hashmap.h\"\n -+#include \"object-store.h\"\n #include \"progress.h\"\n #include \"promisor-remote.h\"\n +#include \"strmap.h\"\n @@ diffcore-rename.c\n -\n -\tif (first >= 0)\n +\t/*\n -+\t * See t4058; trees might have duplicate entries. I think\n -+\t * trees with duplicate entries should be ignored and we\n -+\t * should just leave rename detection on; while the results\n -+\t * may be slightly harder to understand, that's merely a\n -+\t * result of the underlying tree making no sense. But I\n -+\t * believe everything still works fine, the results do still\n -+\t * make sense, and the extra overhead of doing this checking\n -+\t * for a few historical weird trees from long ago seems like\n -+\t * the dog wagging the tail to me.\n -+\t *\n -+\t * However: I don't feel like fighting that battle right now.\n -+\t * For now, to keep the regression test passing, we have to\n -+\t * detect it. Since the diff machinery passes these to us in\n -+\t * adjacent pairs, we just need to check to see if our name\n -+\t * matches the previous one.\n -+\t *\n -+\t * TODO: Dispense with this test, rip out the test in t4058, and\n -+\t * lobby folks for the change.\n ++\t * If we have multiple entries at the same path in the destination\n ++\t * tree (an invalid tree, to be sure), turn off rename detection\n ++\t * entirely. Once upon a time, diffcore-rename had double free()\n ++\t * issues due to such duplicate paths, resulting in segfaults. See\n ++\t * commit 4d6be03b95 (\"diffcore-rename: avoid processing duplicate\n ++\t * destinations\", 2015-02-26).\n +\t */\n +\tif (rename_dst_nr > 0 &&\n +\t !strcmp(rename_dst[rename_dst_nr-1].p->two->path, p->two->path))\n @@ diffcore-rename.c\n \treturn 0;\n }\n \n -@@ diffcore-rename.c: static int rename_src_nr, rename_src_alloc;\n +@@ diffcore-rename.c: static void register_rename_src(struct diff_filepair *p)\n + \t !strcmp(rename_src[rename_src_nr-1].p->one->path, p->one->path))\n + \t\treturn;\n \n - static void register_rename_src(struct diff_filepair *p)\n - {\n +\tif (p->broken_pair) {\n +\t\tif (!break_idx) {\n +\t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t\t\t\t\t\" duplicate destination '%s'\",\n \t\t\t\t\tp->two->path);\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n - \n - \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_targets), sizeof(*mx));\n + \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n + \t\t sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n -\t\tstruct diff_filespec *two = rename_dst[i].two;\n +\t\tstruct diff_filespec *two = rename_dst[i].p->two;\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t\t}\n \t\telse if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {\n -\t\t\t/*\n --\t\t\t * Addition\n +-\t\t\t * Creation\n -\t\t\t *\n --\t\t\t * We would output this add record if it has\n +-\t\t\t * We would output this create record if it has\n -\t\t\t * not been turned into a rename/copy already.\n -\t\t\t */\n -\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->two);\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n -\t\t\t}\n -\t\t\telse\n -\t\t\t\t/* no matching rename/copy source, so\n --\t\t\t\t * record this as an addition.\n +-\t\t\t\t * record this as a creation.\n -\t\t\t\t */\n -\t\t\t\tdiff_q(&outq, p);\n -+\t\t\t/* Addition */\n ++\t\t\t/* Creation */\n +\t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n -\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->one);\n -\t\t\t\tif (dst && dst->pair)\n +\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p);\n -+\t\t\t\tassert(dst);\n ++\t\t\t\tif (!dst)\n ++\t\t\t\t\tBUG(\"tracking failed somehow; failed to find associated dst for broken pair\");\n +\t\t\t\tif (dst->is_rename)\n \t\t\t\t\t/* counterpart is now rename/copy */\n \t\t\t\t\tpair_to_free = p;\n -: ----------- > 9: af256b1c534 diffcore-rename: remove unneccessary duplicate entry checks\n\n-- \ngitgitgadget\n"},{"id":"413122","messageId":"CAP8UFD0r1RvbtOcHTbREcC4v33S-m_gS4e=fSq0OFEHr82K9nQ@mail.gmail.com","threadId":"54772","inReplyTo":"af256b1c534e3fe103bb01bd673ac3a2ec467de4.1607677728.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 9/9] diffcore-rename: remove unneccessary duplicate entry checks","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2020-12-29T08:31:29Z","receivedAt":"2020-12-29T08:32:40Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"About the subject:\n\ns/unneccessary/unnecessary/\n"},{"id":"413135","messageId":"CABPp-BH4cShLMa_dOShmZxbJt4Y57ZsG6+uvqPkGCa_toYOZ8g@mail.gmail.com","threadId":"54772","inReplyTo":"CAP8UFD0r1RvbtOcHTbREcC4v33S-m_gS4e=fSq0OFEHr82K9nQ@mail.gmail.com","subject":"Re: [PATCH v2 9/9] diffcore-rename: remove unneccessary duplicate entry checks","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-29T18:09:47Z","receivedAt":"2020-12-29T18:10:46Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Dec 29, 2020 at 12:31 AM Christian Couder\n wrote:\n>\n> About the subject:\n>\n> s/unneccessary/unnecessary/\n\nThanks, I'll remove the unnecessary double c.\n"},{"id":"413138","messageId":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v2.git.git.1607677728.gitgitgadget@gmail.com","subject":"[PATCH v3 0/9] diffcore-rename improvements","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:19Z","receivedAt":"2020-12-29T20:06:40Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This patch series includes 3 small code cleanups, 1 small bug fix (or\nperhaps just a UI improvement -- it's a very minor issue either way), more\ntestcases, and 3 performance improvements. The first 7 patches are\nrelatively easy to review, while the second to last one...is a bit more\ninvolved (but provided the biggest performance boost).\n\nChanges since v2:\n\n * Fixed spelling error: remove unnecessary double c in 'unneccessary'\n (thanks to Christian for spotting)\n\nElijah Newren (9):\n diffcore-rename: rename num_create to num_destinations\n diffcore-rename: avoid usage of global in too_many_rename_candidates()\n diffcore-rename: simplify limit check\n diffcore-rename: reduce jumpiness in progress counters\n t4058: add more tests and documentation for duplicate tree entry\n handling\n t4058: explore duplicate tree entry handling in a bit more detail\n diffcore-rename: simplify and accelerate register_rename_src()\n diffcore-rename: accelerate rename_dst setup\n diffcore-rename: remove unnecessary duplicate entry checks\n\n diffcore-rename.c | 209 ++++++++++++++-----------------------\n t/t4058-diff-duplicates.sh | 114 +++++++++++++++++++-\n 2 files changed, 192 insertions(+), 131 deletions(-)\n\n\nbase-commit: 3a0b884caba2752da0af626fb2de7d597c844e8b\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-929%2Fnewren%2Fdiffcore-rename-improvements-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-929/newren/diffcore-rename-improvements-v3\nPull-Request: https://github.com/git/git/pull/929\n\nRange-diff vs v2:\n\n 1: 428d8204894 = 1: 428d8204894 diffcore-rename: rename num_create to num_destinations\n 2: fc62f4c4f89 = 2: fc62f4c4f89 diffcore-rename: avoid usage of global in too_many_rename_candidates()\n 3: 7214fa73fdd = 3: 7214fa73fdd diffcore-rename: simplify limit check\n 4: bf3581b1ac1 = 4: bf3581b1ac1 diffcore-rename: reduce jumpiness in progress counters\n 5: 9a4a3159acf = 5: 9a4a3159acf t4058: add more tests and documentation for duplicate tree entry handling\n 6: 8db27892c59 = 6: 8db27892c59 t4058: explore duplicate tree entry handling in a bit more detail\n 7: a58639b2927 = 7: a58639b2927 diffcore-rename: simplify and accelerate register_rename_src()\n 8: 85714e1583d = 8: 85714e1583d diffcore-rename: accelerate rename_dst setup\n 9: af256b1c534 ! 9: 723b0e55e75 diffcore-rename: remove unneccessary duplicate entry checks\n @@ Metadata\n Author: Elijah Newren \n \n ## Commit message ##\n - diffcore-rename: remove unneccessary duplicate entry checks\n + diffcore-rename: remove unnecessary duplicate entry checks\n \n Commit 25d5ea410f (\"[PATCH] Redo rename/copy detection logic.\",\n 2005-05-24) added a duplicate entry check on rename_src in order to\n\n-- \ngitgitgadget\n"},{"id":"413139","messageId":"428d8204894f668e925c640b2f72dc597164e706.1609272328.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","subject":"[PATCH v3 1/9] diffcore-rename: rename num_create to num_destinations","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:20Z","receivedAt":"2020-12-29T20:06:40Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nOur main data structures are rename_src and rename_dst. For counters of\nthese data structures, num_sources and num_destinations seem natural;\ndefinitely more so than using num_create for the latter.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 25 +++++++++++++------------\n 1 file changed, 13 insertions(+), 12 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex d367a6d2443..15a98f566e4 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -434,7 +434,7 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n * 1 if we need to disable inexact rename detection;\n * 2 if we would be under the limit if we were given -C instead of -C -C.\n */\n-static int too_many_rename_candidates(int num_create,\n+static int too_many_rename_candidates(int num_destinations,\n \t\t\t\t struct diff_options *options)\n {\n \tint rename_limit = options->rename_limit;\n@@ -447,17 +447,17 @@ static int too_many_rename_candidates(int num_create,\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-\t * num_create * num_src > rename_limit * rename_limit\n+\t * num_destinations * num_src > rename_limit * rename_limit\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n-\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_create * (uint64_t)num_src\n+\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n+\t ((uint64_t)num_destinations * (uint64_t)num_src\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n-\t\tnum_src > num_create ? num_src : num_create;\n+\t\tnum_src > num_destinations ? num_src : num_destinations;\n \n \t/* Are we running under -C -C? */\n \tif (!options->flags.find_copies_harder)\n@@ -469,8 +469,8 @@ static int too_many_rename_candidates(int num_create,\n \t\t\tcontinue;\n \t\tnum_src++;\n \t}\n-\tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_create * (uint64_t)num_src\n+\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n+\t ((uint64_t)num_destinations * (uint64_t)num_src\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 2;\n \treturn 1;\n@@ -505,7 +505,7 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_queue_struct outq;\n \tstruct diff_score *mx;\n \tint i, j, rename_count, skip_unmodified = 0;\n-\tint num_create, dst_cnt;\n+\tint num_destinations, dst_cnt;\n \tstruct progress *progress = NULL;\n \n \tif (!minimum_score)\n@@ -570,13 +570,13 @@ void diffcore_rename(struct diff_options *options)\n \t * Calculate how many renames are left (but all the source\n \t * files still remain as options for rename/copies!)\n \t */\n-\tnum_create = (rename_dst_nr - rename_count);\n+\tnum_destinations = (rename_dst_nr - rename_count);\n \n \t/* All done? */\n-\tif (!num_create)\n+\tif (!num_destinations)\n \t\tgoto cleanup;\n \n-\tswitch (too_many_rename_candidates(num_create, options)) {\n+\tswitch (too_many_rename_candidates(num_destinations, options)) {\n \tcase 1:\n \t\tgoto cleanup;\n \tcase 2:\n@@ -593,7 +593,8 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n \t}\n \n-\tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_create), sizeof(*mx));\n+\tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n+\t\t sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n \t\tstruct diff_filespec *two = rename_dst[i].two;\n \t\tstruct diff_score *m;\n-- \ngitgitgadget\n\n"},{"id":"413144","messageId":"85714e1583d8c47858e6efd2d5c63bdcca748a25.1609272328.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","subject":"[PATCH v3 8/9] diffcore-rename: accelerate rename_dst setup","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:27Z","receivedAt":"2020-12-29T20:06:40Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nregister_rename_src() simply references the passed pair inside\nrename_src. In contrast, add_rename_dst() did something entirely\ndifferent for rename_dst. Instead of copying the passed pair, it made a\ncopy of the second diff_filespec from the passed pair, referenced it,\nand then set the diff_rename_dst.pair field to NULL. Later, when a\npairing is found, record_rename_pair() allocated a full diff_filepair\nvia diff_queue() and pointed its src and dst fields at the appropriate\ndiff_filespecs. This contrast between register_rename_src() for the\nrename_src data structure and add_rename_dst() for the rename_dst data\nstructure is oddly inconsistent and requires more memory and work than\nnecessary. Let's just reference the original diff_filepair in\nrename_dst as-is, just as we do with rename_src. Add a new\nrename_dst.is_rename field, since the rename_dst.p field is never NULL\nunlike the old rename_dst.pair field.\n\nTaking advantage of this change and the fact that same-named paths will\nbe adjacent, we can get rid of the sorting of the array and most of the\nlookups on it, allowing us to instead just append as we go. However,\nthere is one remaining reason to still keep locate_rename_dst():\nhandling broken pairs (i.e. when break detection is on). Those are\nsomewhat rare, but we can set up a simple strintmap to get the map\nbetween the source and the index. Doing that allows us to still have a\nfast lookup without sorting the rename_dst array. Since the sorting had\nbeen done in a weakly quadratic manner, when many renames are involved\nthis time could add up.\n\nThere is still a strcmp() in add_rename_dst() that I have left in place\nto make it easier to verify that the algorithm has the same results.\nThis strcmp() is there to check for duplicate destination entries (which\nwas the easiest way at the time to avoid segfaults in the\ndiffcore-rename code when trees had multiple entries at a given path).\nThe underlying double free()s are no longer an issue with the new\nalgorithm, but that can be addressed in a subsequent commit.\n\nThis patch is being submitted in a different order than its original\ndevelopment, but in a large rebase of many commits with lots of renames\nand with several optimizations to inexact rename detection, both setup\ntime and write back to output queue time from diffcore_rename() were\nsizeable chunks of overall runtime. This patch accelerated the setup\ntime by about 65%, and final write back to the output queue time by\nabout 50%, resulting in an overall drop of 3.5% on the execution time of\nrebasing a few dozen patches.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 148 ++++++++++++++++++++--------------------------\n 1 file changed, 65 insertions(+), 83 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex a215421a9cb..2a8fcd52928 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -9,63 +9,48 @@\n #include \"hashmap.h\"\n #include \"progress.h\"\n #include \"promisor-remote.h\"\n+#include \"strmap.h\"\n \n /* Table of rename/copy destinations */\n \n static struct diff_rename_dst {\n-\tstruct diff_filespec *two;\n-\tstruct diff_filepair *pair;\n+\tstruct diff_filepair *p;\n+\tstruct diff_filespec *filespec_to_free;\n+\tint is_rename; /* false -> just a create; true -> rename or copy */\n } *rename_dst;\n static int rename_dst_nr, rename_dst_alloc;\n+/* Mapping from break source pathname to break destination index */\n+static struct strintmap *break_idx = NULL;\n \n-static int find_rename_dst(struct diff_filespec *two)\n-{\n-\tint first, last;\n-\n-\tfirst = 0;\n-\tlast = rename_dst_nr;\n-\twhile (last > first) {\n-\t\tint next = first + ((last - first) >> 1);\n-\t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n-\t\tint cmp = strcmp(two->path, dst->two->path);\n-\t\tif (!cmp)\n-\t\t\treturn next;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n-\treturn -first - 1;\n-}\n-\n-static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two)\n+static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)\n {\n-\tint ofs = find_rename_dst(two);\n-\treturn ofs < 0 ? NULL : &rename_dst[ofs];\n+\t/* Lookup by p->ONE->path */\n+\tint idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;\n+\treturn (idx == -1) ? NULL : &rename_dst[idx];\n }\n \n /*\n * Returns 0 on success, -1 if we found a duplicate.\n */\n-static int add_rename_dst(struct diff_filespec *two)\n+static int add_rename_dst(struct diff_filepair *p)\n {\n-\tint first = find_rename_dst(two);\n-\n-\tif (first >= 0)\n+\t/*\n+\t * If we have multiple entries at the same path in the destination\n+\t * tree (an invalid tree, to be sure), turn off rename detection\n+\t * entirely. Once upon a time, diffcore-rename had double free()\n+\t * issues due to such duplicate paths, resulting in segfaults. See\n+\t * commit 4d6be03b95 (\"diffcore-rename: avoid processing duplicate\n+\t * destinations\", 2015-02-26).\n+\t */\n+\tif (rename_dst_nr > 0 &&\n+\t !strcmp(rename_dst[rename_dst_nr-1].p->two->path, p->two->path))\n \t\treturn -1;\n-\tfirst = -first - 1;\n \n-\t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);\n+\trename_dst[rename_dst_nr].p = p;\n+\trename_dst[rename_dst_nr].filespec_to_free = NULL;\n+\trename_dst[rename_dst_nr].is_rename = 0;\n \trename_dst_nr++;\n-\tif (first < rename_dst_nr)\n-\t\tMOVE_ARRAY(rename_dst + first + 1, rename_dst + first,\n-\t\t\t rename_dst_nr - first - 1);\n-\trename_dst[first].two = alloc_filespec(two->path);\n-\tfill_filespec(rename_dst[first].two, &two->oid, two->oid_valid,\n-\t\t two->mode);\n-\trename_dst[first].pair = NULL;\n \treturn 0;\n }\n \n@@ -89,6 +74,14 @@ static void register_rename_src(struct diff_filepair *p)\n \t !strcmp(rename_src[rename_src_nr-1].p->one->path, p->one->path))\n \t\treturn;\n \n+\tif (p->broken_pair) {\n+\t\tif (!break_idx) {\n+\t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\n+\t\t\tstrintmap_init(break_idx, -1);\n+\t\t}\n+\t\tstrintmap_set(break_idx, p->one->path, rename_dst_nr);\n+\t}\n+\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n \trename_src[rename_src_nr].p = p;\n \trename_src[rename_src_nr].score = p->score;\n@@ -128,14 +121,14 @@ static void prefetch(void *prefetch_options)\n \tstruct oid_array to_fetch = OID_ARRAY_INIT;\n \n \tfor (i = 0; i < rename_dst_nr; i++) {\n-\t\tif (rename_dst[i].pair)\n+\t\tif (rename_dst[i].p->renamed_pair)\n \t\t\t/*\n \t\t\t * The loop in diffcore_rename() will not need these\n \t\t\t * blobs, so skip prefetching.\n \t\t\t */\n \t\t\tcontinue; /* already found exact match */\n \t\tdiff_add_if_missing(options->repo, &to_fetch,\n-\t\t\t\t rename_dst[i].two);\n+\t\t\t\t rename_dst[i].p->two);\n \t}\n \tfor (i = 0; i < rename_src_nr; i++) {\n \t\tif (options->skip_unmodified &&\n@@ -245,26 +238,24 @@ static int estimate_similarity(struct repository *r,\n \n static void record_rename_pair(int dst_index, int src_index, int score)\n {\n-\tstruct diff_filespec *src, *dst;\n-\tstruct diff_filepair *dp;\n+\tstruct diff_filepair *src = rename_src[src_index].p;\n+\tstruct diff_filepair *dst = rename_dst[dst_index].p;\n \n-\tif (rename_dst[dst_index].pair)\n+\tif (dst->renamed_pair)\n \t\tdie(\"internal error: dst already matched.\");\n \n-\tsrc = rename_src[src_index].p->one;\n-\tsrc->rename_used++;\n-\tsrc->count++;\n+\tsrc->one->rename_used++;\n+\tsrc->one->count++;\n \n-\tdst = rename_dst[dst_index].two;\n-\tdst->count++;\n+\trename_dst[dst_index].filespec_to_free = dst->one;\n+\trename_dst[dst_index].is_rename = 1;\n \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+\tdst->one = src->one;\n+\tdst->renamed_pair = 1;\n+\tif (!strcmp(dst->one->path, dst->two->path))\n+\t\tdst->score = rename_src[src_index].score;\n \telse\n-\t\tdp->score = score;\n-\trename_dst[dst_index].pair = dp;\n+\t\tdst->score = score;\n }\n \n /*\n@@ -310,7 +301,7 @@ static int find_identical_files(struct hashmap *srcs,\n \t\t\t\tstruct diff_options *options)\n {\n \tint renames = 0;\n-\tstruct diff_filespec *target = rename_dst[dst_index].two;\n+\tstruct diff_filespec *target = rename_dst[dst_index].p->two;\n \tstruct file_similarity *p, *best = NULL;\n \tint i = 100, best_score = -1;\n \tunsigned int hash = hash_filespec(options->repo, target);\n@@ -476,7 +467,7 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i\n \t\t (mx[i].score < minimum_score))\n \t\t\tbreak; /* there is no more usable pair. */\n \t\tdst = &rename_dst[mx[i].dst];\n-\t\tif (dst->pair)\n+\t\tif (dst->is_rename)\n \t\t\tcontinue; /* already done, either exact or fuzzy. */\n \t\tif (!copies && rename_src[mx[i].src].p->one->rename_used)\n \t\t\tcontinue;\n@@ -511,7 +502,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\telse if (!options->flags.rename_empty &&\n \t\t\t\t is_empty_blob_oid(&p->two->oid))\n \t\t\t\tcontinue;\n-\t\t\telse if (add_rename_dst(p->two) < 0) {\n+\t\t\telse if (add_rename_dst(p) < 0) {\n \t\t\t\twarning(\"skipping rename detection, detected\"\n \t\t\t\t\t\" duplicate destination '%s'\",\n \t\t\t\t\tp->two->path);\n@@ -586,10 +577,10 @@ void diffcore_rename(struct diff_options *options)\n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n \t\t sizeof(*mx));\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n-\t\tstruct diff_filespec *two = rename_dst[i].two;\n+\t\tstruct diff_filespec *two = rename_dst[i].p->two;\n \t\tstruct diff_score *m;\n \n-\t\tif (rename_dst[i].pair)\n+\t\tif (rename_dst[i].is_rename)\n \t\t\tcontinue; /* dealt with exact match already. */\n \n \t\tm = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];\n@@ -646,22 +637,8 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (!DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two)) {\n-\t\t\t/*\n-\t\t\t * Creation\n-\t\t\t *\n-\t\t\t * We would output this create record if it has\n-\t\t\t * not been turned into a rename/copy already.\n-\t\t\t */\n-\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->two);\n-\t\t\tif (dst && dst->pair) {\n-\t\t\t\tdiff_q(&outq, dst->pair);\n-\t\t\t\tpair_to_free = p;\n-\t\t\t}\n-\t\t\telse\n-\t\t\t\t/* no matching rename/copy source, so\n-\t\t\t\t * record this as a creation.\n-\t\t\t\t */\n-\t\t\t\tdiff_q(&outq, p);\n+\t\t\t/* Creation */\n+\t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (DIFF_FILE_VALID(p->one) && !DIFF_FILE_VALID(p->two)) {\n \t\t\t/*\n@@ -682,8 +659,10 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t */\n \t\t\tif (DIFF_PAIR_BROKEN(p)) {\n \t\t\t\t/* broken delete */\n-\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p->one);\n-\t\t\t\tif (dst && dst->pair)\n+\t\t\t\tstruct diff_rename_dst *dst = locate_rename_dst(p);\n+\t\t\t\tif (!dst)\n+\t\t\t\t\tBUG(\"tracking failed somehow; failed to find associated dst for broken pair\");\n+\t\t\t\tif (dst->is_rename)\n \t\t\t\t\t/* counterpart is now rename/copy */\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\n@@ -693,16 +672,14 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t\tpair_to_free = p;\n \t\t\t}\n \n-\t\t\tif (pair_to_free)\n-\t\t\t\t;\n-\t\t\telse\n+\t\t\tif (!pair_to_free)\n \t\t\t\tdiff_q(&outq, p);\n \t\t}\n \t\telse if (!diff_unmodified_pair(p))\n \t\t\t/* all the usual ones need to be kept */\n \t\t\tdiff_q(&outq, p);\n \t\telse\n-\t\t\t/* no need to keep unmodified pairs */\n+\t\t\t/* no need to keep unmodified pairs; FIXME: remove earlier? */\n \t\t\tpair_to_free = p;\n \n \t\tif (pair_to_free)\n@@ -715,11 +692,16 @@ void diffcore_rename(struct diff_options *options)\n \tdiff_debug_queue(\"done collapsing\", q);\n \n \tfor (i = 0; i < rename_dst_nr; i++)\n-\t\tfree_filespec(rename_dst[i].two);\n+\t\tif (rename_dst[i].filespec_to_free)\n+\t\t\tfree_filespec(rename_dst[i].filespec_to_free);\n \n \tFREE_AND_NULL(rename_dst);\n \trename_dst_nr = rename_dst_alloc = 0;\n \tFREE_AND_NULL(rename_src);\n \trename_src_nr = rename_src_alloc = 0;\n+\tif (break_idx) {\n+\t\tstrintmap_clear(break_idx);\n+\t\tFREE_AND_NULL(break_idx);\n+\t}\n \treturn;\n }\n-- \ngitgitgadget\n\n"},{"id":"413140","messageId":"a58639b2927fc9b51351d2d1da134a757c657723.1609272328.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","subject":"[PATCH v3 7/9] diffcore-rename: simplify and accelerate register_rename_src()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:26Z","receivedAt":"2020-12-29T20:06:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nregister_rename_src() took pains to create an array in rename_src which\nwas sorted by pathname of the contained diff_filepair. The sorting was\nentirely unnecessary since callers pass filepairs to us in sorted\norder. We can simply append to the end of the rename_src array,\nspeeding up diffcore_rename() setup time.\n\nAlso, note that I dropped the return type on the function since it was\nunconditionally discarded anyway.\n\nThis patch is being submitted in a different order than its original\ndevelopment, but in a large rebase of many commits with lots of renames\nand with several optimizations to inexact rename detection,\ndiffcore_rename() setup time was a sizeable chunk of overall runtime.\nThis patch dropped execution time of rebasing 35 commits with lots of\nrenames by 2% overall.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 39 +++++++++++++--------------------------\n 1 file changed, 13 insertions(+), 26 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 55a188abcc3..a215421a9cb 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -76,36 +76,23 @@ static struct diff_rename_src {\n } *rename_src;\n static int rename_src_nr, rename_src_alloc;\n \n-static struct diff_rename_src *register_rename_src(struct diff_filepair *p)\n+static void register_rename_src(struct diff_filepair *p)\n {\n-\tint first, last;\n-\tstruct diff_filespec *one = p->one;\n-\tunsigned short score = p->score;\n-\n-\tfirst = 0;\n-\tlast = rename_src_nr;\n-\twhile (last > first) {\n-\t\tint next = first + ((last - first) >> 1);\n-\t\tstruct diff_rename_src *src = &(rename_src[next]);\n-\t\tint cmp = strcmp(one->path, src->p->one->path);\n-\t\tif (!cmp)\n-\t\t\treturn src;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n+\t/*\n+\t * If we have multiple entries at the same path in the source tree\n+\t * (an invalid tree, to be sure), avoid using more more than one\n+\t * such entry in rename detection. Once upon a time, doing so\n+\t * caused segfaults; see commit 25d5ea410f (\"[PATCH] Redo\n+\t * rename/copy detection logic.\", 2005-05-24).\n+\t */\n+\tif (rename_src_nr > 0 &&\n+\t !strcmp(rename_src[rename_src_nr-1].p->one->path, p->one->path))\n+\t\treturn;\n \n-\t/* insert to make it at \"first\" */\n \tALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);\n+\trename_src[rename_src_nr].p = p;\n+\trename_src[rename_src_nr].score = p->score;\n \trename_src_nr++;\n-\tif (first < rename_src_nr)\n-\t\tMOVE_ARRAY(rename_src + first + 1, rename_src + first,\n-\t\t\t rename_src_nr - first - 1);\n-\trename_src[first].p = p;\n-\trename_src[first].score = score;\n-\treturn &(rename_src[first]);\n }\n \n static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n-- \ngitgitgadget\n\n"},{"id":"413141","messageId":"fc62f4c4f895a216bb2d39f654e48d390a9d1781.1609272328.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","subject":"[PATCH v3 2/9] diffcore-rename: avoid usage of global in too_many_rename_candidates()","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:21Z","receivedAt":"2020-12-29T20:06:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ntoo_many_rename_candidates() got the number of rename destinations via\nan argument to the function, but the number of rename sources via a\nglobal variable. That felt rather inconsistent. Pass in the number of\nrename sources as an argument as well.\n\nWhile we are at it... We had a local variable, num_src, that served two\npurposes. Initially it was set to the global value, but later was used\nfor counting a subset of the number of sources. Since we now have a\nfunction argument for the former usage, introduce a clearer variable\nname for the latter usage.\n\nThis patch has no behavioral changes; it's just renaming and passing an\nargument instead of grabbing it from the global namespace. (You may\nfind it easier to view the patch using git diff's --color-words option.)\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 24 ++++++++++++------------\n 1 file changed, 12 insertions(+), 12 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 15a98f566e4..1d6675c040d 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -434,12 +434,11 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)\n * 1 if we need to disable inexact rename detection;\n * 2 if we would be under the limit if we were given -C instead of -C -C.\n */\n-static int too_many_rename_candidates(int num_destinations,\n+static int too_many_rename_candidates(int num_destinations, int num_sources,\n \t\t\t\t struct diff_options *options)\n {\n \tint rename_limit = options->rename_limit;\n-\tint num_src = rename_src_nr;\n-\tint i;\n+\tint i, limited_sources;\n \n \toptions->needed_rename_limit = 0;\n \n@@ -447,30 +446,30 @@ static int too_many_rename_candidates(int num_destinations,\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-\t * num_destinations * num_src > rename_limit * rename_limit\n+\t * num_destinations * num_sources > rename_limit * rename_limit\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n-\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_destinations * (uint64_t)num_src\n+\tif ((num_destinations <= rename_limit || num_sources <= rename_limit) &&\n+\t ((uint64_t)num_destinations * (uint64_t)num_sources\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n-\t\tnum_src > num_destinations ? num_src : num_destinations;\n+\t\tnum_sources > num_destinations ? num_sources : num_destinations;\n \n \t/* Are we running under -C -C? */\n \tif (!options->flags.find_copies_harder)\n \t\treturn 1;\n \n \t/* Would we bust the limit if we were running under -C? */\n-\tfor (num_src = i = 0; i < rename_src_nr; i++) {\n+\tfor (limited_sources = i = 0; i < num_sources; i++) {\n \t\tif (diff_unmodified_pair(rename_src[i].p))\n \t\t\tcontinue;\n-\t\tnum_src++;\n+\t\tlimited_sources++;\n \t}\n-\tif ((num_destinations <= rename_limit || num_src <= rename_limit) &&\n-\t ((uint64_t)num_destinations * (uint64_t)num_src\n+\tif ((num_destinations <= rename_limit || limited_sources <= rename_limit) &&\n+\t ((uint64_t)num_destinations * (uint64_t)limited_sources\n \t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 2;\n \treturn 1;\n@@ -576,7 +575,8 @@ void diffcore_rename(struct diff_options *options)\n \tif (!num_destinations)\n \t\tgoto cleanup;\n \n-\tswitch (too_many_rename_candidates(num_destinations, options)) {\n+\tswitch (too_many_rename_candidates(num_destinations, rename_src_nr,\n+\t\t\t\t\t options)) {\n \tcase 1:\n \t\tgoto cleanup;\n \tcase 2:\n-- \ngitgitgadget\n\n"},{"id":"413142","messageId":"7214fa73fdd13418744903f6c769fdb77c9512ce.1609272328.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","subject":"[PATCH v3 3/9] diffcore-rename: simplify limit check","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:22Z","receivedAt":"2020-12-29T20:06:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ndiffcore-rename had two different checks of the form\n\n if ((a < limit || b < limit) &&\n a * b <= limit * limit)\n\nThis can be simplified to\n\n if (st_mult(a, b) <= st_mult(limit, limit))\n\nwhich makes it clearer how we are checking for overflow, and makes it\nmuch easier to parse given the drop from 8 to 4 variable appearances.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 15 +++++++++------\n 1 file changed, 9 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1d6675c040d..16553ab259f 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -447,12 +447,16 @@ static int too_many_rename_candidates(int num_destinations, int num_sources,\n \t * growing larger than a \"rename_limit\" square matrix, ie:\n \t *\n \t * num_destinations * num_sources > rename_limit * rename_limit\n+\t *\n+\t * We use st_mult() to check overflow conditions; in the\n+\t * exceptional circumstance that size_t isn't large enough to hold\n+\t * the multiplication, the system won't be able to allocate enough\n+\t * memory for the matrix anyway.\n \t */\n \tif (rename_limit <= 0)\n \t\trename_limit = 32767;\n-\tif ((num_destinations <= rename_limit || num_sources <= rename_limit) &&\n-\t ((uint64_t)num_destinations * (uint64_t)num_sources\n-\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n+\tif (st_mult(num_destinations, num_sources)\n+\t <= st_mult(rename_limit, rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n@@ -468,9 +472,8 @@ static int too_many_rename_candidates(int num_destinations, int num_sources,\n \t\t\tcontinue;\n \t\tlimited_sources++;\n \t}\n-\tif ((num_destinations <= rename_limit || limited_sources <= rename_limit) &&\n-\t ((uint64_t)num_destinations * (uint64_t)limited_sources\n-\t <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n+\tif (st_mult(num_destinations, limited_sources)\n+\t <= st_mult(rename_limit, rename_limit))\n \t\treturn 2;\n \treturn 1;\n }\n-- \ngitgitgadget\n\n"},{"id":"413143","messageId":"bf3581b1ac12bd616518f8093365d38eee4f01b7.1609272328.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","subject":"[PATCH v3 4/9] diffcore-rename: reduce jumpiness in progress counters","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:23Z","receivedAt":"2020-12-29T20:06:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nInexact rename detection works by comparing all sources to all\ndestinations, computing similarities, and then finding the best matches\namong those that are sufficiently similar.\n\nHowever, it is preceded by exact rename detection that works by\nchecking if there are files with identical hashes. If exact renames are\nfound, we can exclude some files from inexact rename detection.\n\nThe inexact rename detection loops over the full set of files, but\nimmediately skips those for which rename_dst[i].is_rename is true and\nthus doesn't compare any sources to that destination. As such, these\npaths shouldn't be included in the progress counter.\n\nFor the eagle eyed, this change hints at an actual optimization -- the\nfirst one I presented at Git Merge 2020. I'll be submitting that\noptimization later, once the basic merge-ort algorithm has merged.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 16553ab259f..55a188abcc3 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -593,7 +593,7 @@ void diffcore_rename(struct diff_options *options)\n \tif (options->show_rename_progress) {\n \t\tprogress = start_delayed_progress(\n \t\t\t\t_(\"Performing inexact rename detection\"),\n-\t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n+\t\t\t\t(uint64_t)num_destinations * (uint64_t)rename_src_nr);\n \t}\n \n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n@@ -633,7 +633,8 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tdiff_free_filespec_blob(two);\n \t\t}\n \t\tdst_cnt++;\n-\t\tdisplay_progress(progress, (uint64_t)(i+1)*(uint64_t)rename_src_nr);\n+\t\tdisplay_progress(progress,\n+\t\t\t\t (uint64_t)dst_cnt * (uint64_t)rename_src_nr);\n \t}\n \tstop_progress(&progress);\n \n-- \ngitgitgadget\n\n"},{"id":"413145","messageId":"723b0e55e75d264f83407c3fb50f3ccc16d35062.1609272328.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","subject":"[PATCH v3 9/9] diffcore-rename: remove unnecessary duplicate entry checks","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:28Z","receivedAt":"2020-12-29T20:06:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nCommit 25d5ea410f (\"[PATCH] Redo rename/copy detection logic.\",\n2005-05-24) added a duplicate entry check on rename_src in order to\navoid segfaults; the code at the time was prone to double free()s and an\neasy way to avoid it was just to turn off rename detection for any\nduplicate entries. Note that the form of the check was modified two\ncommits ago in this series.\n\nSimilarly, commit 4d6be03b95 (\"diffcore-rename: avoid processing\nduplicate destinations\", 2015-02-26) added a duplicate entry check\non rename_dst for the exact same reason -- the code was prone to double\nfree()s, and an easy way to avoid it was just to turn off rename\ndetection entirely. Note that the form of the check was modified in the\ncommit just before this one.\n\nIn the original code in both places, the code was dealing with\nindividual diff_filespecs and trying to match things up, instead of just\nkeeping the original diff_filepairs around as we do now. The\nintervening change in structure has fixed the accounting problems and\nthe associated double free()s that used to occur, and thus we already\nhave a better fix. As such, we can remove the band-aid checks for\nduplicate entries.\n\nDue to the last two patches, the diffcore_rename() setup is no longer a\nsizeable chunk of overall runtime. Thus, in a large rebase of many\ncommits with lots of renames and several optimizations to inexact rename\ndetection, this patch only speeds up the overall code by about half a\npercent or so and is pretty close to the run-to-run variability making\nit hard to get an exact measurement. However, with some trace2 regions\naround the setup code in diffcore_rename() so that I can focus on just\nit, I measure that this patch consistently saves almost a third of the\nremaining time spent in diffcore_rename() setup.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 23 -----------------------\n t/t4058-diff-duplicates.sh | 2 +-\n 2 files changed, 1 insertion(+), 24 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 2a8fcd52928..90db9ebd6d0 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -34,18 +34,6 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)\n */\n static int add_rename_dst(struct diff_filepair *p)\n {\n-\t/*\n-\t * If we have multiple entries at the same path in the destination\n-\t * tree (an invalid tree, to be sure), turn off rename detection\n-\t * entirely. Once upon a time, diffcore-rename had double free()\n-\t * issues due to such duplicate paths, resulting in segfaults. See\n-\t * commit 4d6be03b95 (\"diffcore-rename: avoid processing duplicate\n-\t * destinations\", 2015-02-26).\n-\t */\n-\tif (rename_dst_nr > 0 &&\n-\t !strcmp(rename_dst[rename_dst_nr-1].p->two->path, p->two->path))\n-\t\treturn -1;\n-\n \tALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);\n \trename_dst[rename_dst_nr].p = p;\n \trename_dst[rename_dst_nr].filespec_to_free = NULL;\n@@ -63,17 +51,6 @@ static int rename_src_nr, rename_src_alloc;\n \n static void register_rename_src(struct diff_filepair *p)\n {\n-\t/*\n-\t * If we have multiple entries at the same path in the source tree\n-\t * (an invalid tree, to be sure), avoid using more more than one\n-\t * such entry in rename detection. Once upon a time, doing so\n-\t * caused segfaults; see commit 25d5ea410f (\"[PATCH] Redo\n-\t * rename/copy detection logic.\", 2005-05-24).\n-\t */\n-\tif (rename_src_nr > 0 &&\n-\t !strcmp(rename_src[rename_src_nr-1].p->one->path, p->one->path))\n-\t\treturn;\n-\n \tif (p->broken_pair) {\n \t\tif (!break_idx) {\n \t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\ndiff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\nindex ad3f37d388d..54614b814db 100755\n--- a/t/t4058-diff-duplicates.sh\n+++ b/t/t4058-diff-duplicates.sh\n@@ -91,7 +91,7 @@ test_expect_success 'diff-tree between duplicate trees' '\n test_expect_success 'diff-tree with renames' '\n \t# See NOTICE at top of file.\n \tgit diff-tree -M -r --no-abbrev one two >actual &&\n-\ttest_cmp expect actual\n+\ttest_must_be_empty actual\n '\n \n test_expect_success 'diff-tree FROM duplicate tree' '\n-- \ngitgitgadget\n"},{"id":"413146","messageId":"8db27892c598a3976c0742e23563f1d360b8dee1.1609272328.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","subject":"[PATCH v3 6/9] t4058: explore duplicate tree entry handling in a bit more detail","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:25Z","receivedAt":"2020-12-29T20:06:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nWhile creating the last commit, I found a number of other cases where\ngit would segfault when faced with trees that have duplicate entries.\nNone of these segfaults are in the diffcore-rename code (they all occur\nin cache-tree and unpack-trees). Further, to my knowledge, no one has\never been adversely affected by these bugs, and given that it has been\n15 years and folks have fixed a few other issues with historical\nduplicate entries (as noted in the last commit), I am not sure we will\never run into anyone having problems with these. So I am not sure these\nare worth fixing, but it doesn't hurt to at least document these\nfailures in the same test file that is concerned with duplicate tree\nentries.\n\nSigned-off-by: Elijah Newren \n---\n t/t4058-diff-duplicates.sh | 67 ++++++++++++++++++++++++++++++++++++++\n 1 file changed, 67 insertions(+)\n\ndiff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\nindex bd685089561..ad3f37d388d 100755\n--- a/t/t4058-diff-duplicates.sh\n+++ b/t/t4058-diff-duplicates.sh\n@@ -119,4 +119,71 @@ test_expect_success 'diff-tree FROM duplicate tree, with renames' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'create a few commits' '\n+\tgit commit-tree -m \"Duplicate Entries\" two^{tree} >commit_id &&\n+\tgit branch base $(cat commit_id) &&\n+\n+\tgit commit-tree -p $(cat commit_id) -m \"Just one\" three^{tree} >up &&\n+\tgit branch update $(cat up) &&\n+\n+\tgit commit-tree -p $(cat up) -m \"Back to weird\" two^{tree} >final &&\n+\tgit branch final $(cat final) &&\n+\n+\trm commit_id up final\n+'\n+\n+test_expect_failure 'git read-tree does not segfault' '\n+\ttest_when_finished rm .git/index.lock &&\n+\ttest_might_fail git read-tree --reset base\n+'\n+\n+test_expect_failure 'reset --hard does not segfault' '\n+\ttest_when_finished rm .git/index.lock &&\n+\tgit checkout base &&\n+\ttest_might_fail git reset --hard\n+'\n+\n+test_expect_failure 'git diff HEAD does not segfault' '\n+\tgit checkout base &&\n+\tGIT_TEST_CHECK_CACHE_TREE=false &&\n+\tgit reset --hard &&\n+\ttest_might_fail git diff HEAD\n+'\n+\n+test_expect_failure 'can switch to another branch when status is empty' '\n+\tgit clean -ffdqx &&\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual &&\n+\tgit checkout update\n+'\n+\n+test_expect_success 'forcibly switch to another branch, verify status empty' '\n+\tgit checkout -f update &&\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual\n+'\n+\n+test_expect_success 'fast-forward from non-duplicate entries to duplicate' '\n+\tgit merge final\n+'\n+\n+test_expect_failure 'clean status, switch branches, status still clean' '\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual &&\n+\tgit checkout base &&\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual\n+'\n+\n+test_expect_success 'switch to base branch and force status to be clean' '\n+\tgit checkout base &&\n+\tGIT_TEST_CHECK_CACHE_TREE=false git reset --hard &&\n+\tgit status --porcelain -uno >actual &&\n+\ttest_must_be_empty actual\n+'\n+\n+test_expect_failure 'fast-forward from duplicate entries to non-duplicate' '\n+\tgit merge update\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"413147","messageId":"9a4a3159acf6144bfbfc773195a141afaa95dad3.1609272328.git.gitgitgadget@gmail.com","threadId":"54772","inReplyTo":"pull.929.v3.git.git.1609272328.gitgitgadget@gmail.com","subject":"[PATCH v3 5/9] t4058: add more tests and documentation for duplicate tree entry handling","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-29T20:05:24Z","receivedAt":"2020-12-29T20:06:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nCommit 4d6be03b95 (\"diffcore-rename: avoid processing duplicate\ndestinations\", 2015-02-26) added t4058 to demonstrate that a workaround\nit added to avoid double frees (namely to just turn off rename detection\nwhen trees had duplicate entries) would indeed avoid segfaults. The\ntests, though, give the impression that the expected diffs are \"correct\"\nwhen in reality they are just \"don't segfault, and do something\nsemi-reasonable under the circumstances\". Add some notes to make this\nclearer.\n\nAlso, commit 25d5ea410f (\"[PATCH] Redo rename/copy detection logic.\",\n2005-05-24) added a similar workaround to avoid segfaults, but for\nrename_src rather than rename_dst. I do not see any tests in the\ntestsuite to cover the collision detection of entries limited to the\nsource side, so add a couple.\n\nSigned-off-by: Elijah Newren \n---\n t/t4058-diff-duplicates.sh | 47 ++++++++++++++++++++++++++++++++++++--\n 1 file changed, 45 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\nindex c24ee175ef0..bd685089561 100755\n--- a/t/t4058-diff-duplicates.sh\n+++ b/t/t4058-diff-duplicates.sh\n@@ -1,5 +1,14 @@\n #!/bin/sh\n \n+# NOTICE:\n+# This testsuite does a number of diffs and checks that the output match.\n+# However, it is a \"garbage in, garbage out\" situation; the trees have\n+# duplicate entries for individual paths, and it results in diffs that do\n+# not make much sense. As such, it is not clear that the diffs are\n+# \"correct\". The primary purpose of these tests was to verify that\n+# diff-tree does not segfault, but there is perhaps some value in ensuring\n+# that the diff output isn't wildly unreasonable.\n+\n test_description='test tree diff when trees have duplicate entries'\n . ./test-lib.sh\n \n@@ -57,7 +66,16 @@ test_expect_success 'create trees with duplicate entries' '\n \tgit tag two $outer_two\n '\n \n-test_expect_success 'diff-tree between trees' '\n+test_expect_success 'create tree without duplicate entries' '\n+\tblob_one=$(echo one | git hash-object -w --stdin) &&\n+\touter_three=$(make_tree \\\n+\t\t100644 renamed $blob_one\n+\t) &&\n+\tgit tag three $outer_three\n+'\n+\n+test_expect_success 'diff-tree between duplicate trees' '\n+\t# See NOTICE at top of file\n \t{\n \t\tprintf \":000000 100644 $ZERO_OID $blob_two A\\touter/inner\\n\" &&\n \t\tprintf \":000000 100644 $ZERO_OID $blob_two A\\touter/inner\\n\" &&\n@@ -71,9 +89,34 @@ test_expect_success 'diff-tree between trees' '\n '\n \n test_expect_success 'diff-tree with renames' '\n-\t# same expectation as above, since we disable rename detection\n+\t# See NOTICE at top of file.\n \tgit diff-tree -M -r --no-abbrev one two >actual &&\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'diff-tree FROM duplicate tree' '\n+\t# See NOTICE at top of file.\n+\t{\n+\t\tprintf \":100644 000000 $blob_one $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":000000 100644 $ZERO_OID $blob_one A\\trenamed\\n\"\n+\t} >expect &&\n+\tgit diff-tree -r --no-abbrev one three >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'diff-tree FROM duplicate tree, with renames' '\n+\t# See NOTICE at top of file.\n+\t{\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 000000 $blob_two $ZERO_OID D\\touter/inner\\n\" &&\n+\t\tprintf \":100644 100644 $blob_one $blob_one R100\\touter/inner\\trenamed\\n\"\n+\t} >expect &&\n+\tgit diff-tree -M -r --no-abbrev one three >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"422577","messageId":"87fszj3jni.fsf@evledraar.gmail.com","threadId":"54772","inReplyTo":"8db27892c598a3976c0742e23563f1d360b8dee1.1607677728.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 6/9] t4058: explore duplicate tree entry handling in a bit more detail","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-04-21T12:29:53Z","receivedAt":"2021-04-21T12:30:00Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Dec 11 2020, Elijah Newren via GitGitGadget wrote:\n\n> While creating the last commit, I found a number of other cases where\n> git would segfault when faced with trees that have duplicate entries.\n> None of these segfaults are in the diffcore-rename code (they all occur\n> in cache-tree and unpack-trees). Further, to my knowledge, no one has\n> ever been adversely affected by these bugs, and given that it has been\n> 15 years and folks have fixed a few other issues with historical\n> duplicate entries (as noted in the last commit), I am not sure we will\n> ever run into anyone having problems with these. So I am not sure these\n> are worth fixing, but it doesn't hurt to at least document these\n> failures in the same test file that is concerned with duplicate tree\n> entries.\n> [...]\n> +test_expect_failure 'fast-forward from duplicate entries to non-duplicate' '\n> +\tgit merge update\n> +'\n> +\n> test_done\n\nPer https://lore.kernel.org/git/87lf9b3mth.fsf@evledraar.gmail.com/\nisn't the noise of having a segfault from \"git\" worth fixing in itself\nthough? I.e. something like this, so we at least se why it fails:\n\ndiff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\nindex 54614b814db..ed91d9f7fe9 100755\n--- a/t/t4058-diff-duplicates.sh\n+++ b/t/t4058-diff-duplicates.sh\n@@ -182,8 +182,10 @@ test_expect_success 'switch to base branch and force status to be clean' '\n \ttest_must_be_empty actual\n '\n \n-test_expect_failure 'fast-forward from duplicate entries to non-duplicate' '\n-\tgit merge update\n+test_expect_success 'fast-forward from duplicate entries to non-duplicate' '\n+\t! git merge update 2>err &&\n+\tgrep \"^BUG: \" err &&\n+\tgrep -F \"should have entry at o->src_index->cache[1]\" err\n '\n \n test_done\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 8a1afbc1e49..230cb073fe1 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -789,8 +789,11 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,\n \t */\n \tfor (i = 0; i < nr_entries; i++) {\n \t\tint new_ce_len, len, rc;\n+\t\tint j = pos + i;\n \n-\t\tsrc[0] = o->src_index->cache[pos + i];\n+\t\tsrc[0] = o->src_index->cache[j];\n+\t\tif (!src[0])\n+\t\t\tBUG(\"should have entry at o->src_index->cache[%d]\", j);\n \n \t\tlen = ce_namelen(src[0]);\n \t\tnew_ce_len = cache_entry_size(len);\n\n"},{"id":"422609","messageId":"CABPp-BHoCron-aNvjwwDkoAcvi_5X5uoZdO639eGg9XnoJUqdQ@mail.gmail.com","threadId":"54772","inReplyTo":"87fszj3jni.fsf@evledraar.gmail.com","subject":"Re: [PATCH v2 6/9] t4058: explore duplicate tree entry handling in a bit more detail","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-04-21T17:38:03Z","receivedAt":"2021-04-21T17:38:16Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Apr 21, 2021 at 5:29 AM Ævar Arnfjörð Bjarmason\n wrote:\n>\n>\n> On Fri, Dec 11 2020, Elijah Newren via GitGitGadget wrote:\n>\n> > While creating the last commit, I found a number of other cases where\n> > git would segfault when faced with trees that have duplicate entries.\n> > None of these segfaults are in the diffcore-rename code (they all occur\n> > in cache-tree and unpack-trees). Further, to my knowledge, no one has\n> > ever been adversely affected by these bugs, and given that it has been\n> > 15 years and folks have fixed a few other issues with historical\n> > duplicate entries (as noted in the last commit), I am not sure we will\n> > ever run into anyone having problems with these. So I am not sure these\n> > are worth fixing, but it doesn't hurt to at least document these\n> > failures in the same test file that is concerned with duplicate tree\n> > entries.\n> > [...]\n> > +test_expect_failure 'fast-forward from duplicate entries to non-duplicate' '\n> > + git merge update\n> > +'\n> > +\n> > test_done\n>\n> Per https://lore.kernel.org/git/87lf9b3mth.fsf@evledraar.gmail.com/\n> isn't the noise of having a segfault from \"git\" worth fixing in itself\n> though? I.e. something like this, so we at least se why it fails:\n>\n> diff --git a/t/t4058-diff-duplicates.sh b/t/t4058-diff-duplicates.sh\n> index 54614b814db..ed91d9f7fe9 100755\n> --- a/t/t4058-diff-duplicates.sh\n> +++ b/t/t4058-diff-duplicates.sh\n> @@ -182,8 +182,10 @@ test_expect_success 'switch to base branch and force status to be clean' '\n> test_must_be_empty actual\n> '\n>\n> -test_expect_failure 'fast-forward from duplicate entries to non-duplicate' '\n> - git merge update\n> +test_expect_success 'fast-forward from duplicate entries to non-duplicate' '\n> + ! git merge update 2>err &&\n> + grep \"^BUG: \" err &&\n> + grep -F \"should have entry at o->src_index->cache[1]\" err\n> '\n>\n> test_done\n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index 8a1afbc1e49..230cb073fe1 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -789,8 +789,11 @@ static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,\n> */\n> for (i = 0; i < nr_entries; i++) {\n> int new_ce_len, len, rc;\n> + int j = pos + i;\n>\n> - src[0] = o->src_index->cache[pos + i];\n> + src[0] = o->src_index->cache[j];\n> + if (!src[0])\n> + BUG(\"should have entry at o->src_index->cache[%d]\", j);\n>\n> len = ce_namelen(src[0]);\n> new_ce_len = cache_entry_size(len);\n>\n\nSeems reasonable to me. Are you planning to add a commit message and\nturn it into a proper patch? If so, I'll give my Thumbs-up-by or\nwhatever we need. :-)\n"},{"id":"440767","messageId":"CAPNYHkm5Qp8HQGU5_6DXc7xpCrdGgEin0WYAxbRNOkKW0j2ERQ@mail.gmail.com","threadId":"54772","inReplyTo":"7214fa73fdd13418744903f6c769fdb77c9512ce.1609272328.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 3/9] diffcore-rename: simplify limit check","fromName":"Başar Uğur","fromEmail":"basarugur@gmail.com","sentAt":"2021-11-09T21:14:55Z","receivedAt":"2021-11-09T21:15:34Z","isPatch":true,"sender":{"key":"basarugur@gmail.com","avatar":null},"body":"Hi all,\n\nFirst post on Git mailing list, to provide a comment on a patch. Hope\nthis works.\n\nIn cases where the `rename_limit` is already greater than 65535, the\n`st_mult(rename_limit, rename_limit)` multiplication overflows and\nprocess halts. But I don't think an 'overflow error' is very helpful\nfor the users in understanding what is wrong with their configuration;\ni.e. `diff.renameLimit` documentation says nothing about a 'maximum\nallowed value'. I would either clamp it to a reasonable range, or\ninform the users about the limits, or maybe both.\n\nCheers,\n\n-- \nBasar\n"},{"id":"440868","messageId":"CABPp-BFqZj4qYXbPGLyX=4RM4OdLNL=VbYyhbLakU-RrvU+wfw@mail.gmail.com","threadId":"54772","inReplyTo":"CAPNYHkm5Qp8HQGU5_6DXc7xpCrdGgEin0WYAxbRNOkKW0j2ERQ@mail.gmail.com","subject":"Re: [PATCH v3 3/9] diffcore-rename: simplify limit check","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-11-10T20:06:05Z","receivedAt":"2021-11-10T20:06:21Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Nov 9, 2021 at 1:15 PM Başar Uğur wrote:\n>\n> Hi all,\n>\n> First post on Git mailing list, to provide a comment on a patch. Hope\n> this works.\n>\n> In cases where the `rename_limit` is already greater than 65535, the\n> `st_mult(rename_limit, rename_limit)` multiplication overflows and\n> process halts.\n\nOut of curiosity, what system are you on? And how many renames do you\nactually have?\n\nWe used to clamp to 32767, but one specific repository needed values\nlarger than that, in the range of ~50000. However, due to a number of\nrename detection related optimizations added since then, the git of\ntoday can handle that same particular repository and support full\nrename detection with a rename limit under 1000 for merge/cherry-pick\n(sorry, forgot the exact numbers), and probably less than 10000 for\ndiff (just guestimating; I don't want to go and check).\n\nAnyway, all that aside, I don't see any such overflow for rename_limit\nbeing 2**16; we can push it much farther:\n\n size_t a = 4294967295; /* 2**32 -1 */\n size_t b = a;\n size_t c = st_mult(a, b);\n printf(\"%\"PRIuMAX\" = %\"PRIuMAX\" * %\"PRIuMAX\"\\n\", c, a, b);\n\nOutput:\n\n 18446744065119617025 = 4294967295 * 4294967295\n\nAdding one to the value of a results in:\n\n fatal: size_t overflow: 4294967296 * 4294967296\n\n> But I don't think an 'overflow error' is very helpful\n> for the users in understanding what is wrong with their configuration;\n> i.e. `diff.renameLimit` documentation says nothing about a 'maximum\n> allowed value'. I would either clamp it to a reasonable range, or\n> inform the users about the limits, or maybe both.\n\nThat sounds reasonable, but I'm not sure it's worth the effort in\npractice. 2**32 - 1 is so impractically large for a rename_limit that\nI don't see why anyone would need a value even remotely close to that\nlevel (and I wouldn't at all be surprised if other things in git\nscaling broke before we even got to that point).\n\nPerhaps you're dealing with a 32-bit system? Even then, the\nrepository that hit this was about 6.5GB packed .git history; and you\nmight need to be a lot larger than that given the optimization since\nthen in order to hit this. Can 32-bit systems even handle that size\nof repository without dying in several other ways?\n"},{"id":"440902","messageId":"CAPNYHkn5aHW1e_G5BKcaHWnrTSR+=VKOnKPdDPLJ5bH9DedKTA@mail.gmail.com","threadId":"54772","inReplyTo":"CABPp-BFqZj4qYXbPGLyX=4RM4OdLNL=VbYyhbLakU-RrvU+wfw@mail.gmail.com","subject":"Re: [PATCH v3 3/9] diffcore-rename: simplify limit check","fromName":"Başar Uğur","fromEmail":"basarugur@gmail.com","sentAt":"2021-11-11T09:02:34Z","receivedAt":"2021-11-11T09:03:15Z","isPatch":true,"sender":{"key":"basarugur@gmail.com","avatar":null},"body":"On Wed, Nov 10, 2021 at 9:06 PM Elijah Newren wrote:\n>\n> On Tue, Nov 9, 2021 at 1:15 PM Başar Uğur wrote:\n> >\n> > Hi all,\n> >\n> > First post on Git mailing list, to provide a comment on a patch. Hope\n> > this works.\n> >\n> > In cases where the `rename_limit` is already greater than 65535, the\n> > `st_mult(rename_limit, rename_limit)` multiplication overflows and\n> > process halts.\n>\n> Out of curiosity, what system are you on? And how many renames do you\n> actually have?\n\nI am on a 64-bit Windows 10; but following up on your question, it\nbecame obvious that these limits have something to do with 'which git\nexecutable' I was dealing with. This problem surfaced when I was\nworking on Visual Studio 2019, and was trying to rename not more than\n10 files. My config had 999999 as the renameLimit, and VS2019 showed\nthe 'fatal error' in its git output. However, git bash was all fine\nwith listing the renamed files. And the difference between these\nscenarios turned out to be, yes, different git executables. VS2019 has\nits own copy of git which is 32-bit, and it hits this 999999 * 999999\noverflow; whereas *my* copy of git used in bash is 64-bit which does\nnot have that overflow problem.\n\n>\n> We used to clamp to 32767, but one specific repository needed values\n> larger than that, in the range of ~50000. However, due to a number of\n> rename detection related optimizations added since then, the git of\n> today can handle that same particular repository and support full\n> rename detection with a rename limit under 1000 for merge/cherry-pick\n> (sorry, forgot the exact numbers), and probably less than 10000 for\n> diff (just guestimating; I don't want to go and check).\n>\n> Anyway, all that aside, I don't see any such overflow for rename_limit\n> being 2**16; we can push it much farther:\n>\n> size_t a = 4294967295; /* 2**32 -1 */\n> size_t b = a;\n> size_t c = st_mult(a, b);\n> printf(\"%\"PRIuMAX\" = %\"PRIuMAX\" * %\"PRIuMAX\"\\n\", c, a, b);\n>\n> Output:\n>\n> 18446744065119617025 = 4294967295 * 4294967295\n>\n> Adding one to the value of a results in:\n>\n> fatal: size_t overflow: 4294967296 * 4294967296\n>\n> > But I don't think an 'overflow error' is very helpful\n> > for the users in understanding what is wrong with their configuration;\n> > i.e. `diff.renameLimit` documentation says nothing about a 'maximum\n> > allowed value'. I would either clamp it to a reasonable range, or\n> > inform the users about the limits, or maybe both.\n>\n> That sounds reasonable, but I'm not sure it's worth the effort in\n> practice. 2**32 - 1 is so impractically large for a rename_limit that\n> I don't see why anyone would need a value even remotely close to that\n> level (and I wouldn't at all be surprised if other things in git\n> scaling broke before we even got to that point).\n>\n> Perhaps you're dealing with a 32-bit system? Even then, the\n> repository that hit this was about 6.5GB packed .git history; and you\n> might need to be a lot larger than that given the optimization since\n> then in order to hit this. Can 32-bit systems even handle that size\n> of repository without dying in several other ways?\n\nGood point, but the system aside, 2**16 - 1 = 65535 would remain to be\nthe limit for the 32-bit git executables, wherever they are used.\nTherefore, maybe there is a point to curb it, or mention this\nsomewhere, as I have said before.\n\n-- \nBasar\n"},{"id":"440914","messageId":"CABPp-BEGH7reoVXx4TkJKkv7fr=BVOPCTuMBFbEGGDp5nS3bVg@mail.gmail.com","threadId":"54772","inReplyTo":"CAPNYHkn5aHW1e_G5BKcaHWnrTSR+=VKOnKPdDPLJ5bH9DedKTA@mail.gmail.com","subject":"Re: [PATCH v3 3/9] diffcore-rename: simplify limit check","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-11-11T16:19:40Z","receivedAt":"2021-11-11T16:19:56Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Nov 11, 2021 at 1:03 AM Başar Uğur wrote:\n>\n> On Wed, Nov 10, 2021 at 9:06 PM Elijah Newren wrote:\n> >\n> > On Tue, Nov 9, 2021 at 1:15 PM Başar Uğur wrote:\n> > >\n> > > Hi all,\n> > >\n> > > First post on Git mailing list, to provide a comment on a patch. Hope\n> > > this works.\n> > >\n> > > In cases where the `rename_limit` is already greater than 65535, the\n> > > `st_mult(rename_limit, rename_limit)` multiplication overflows and\n> > > process halts.\n> >\n> > Out of curiosity, what system are you on? And how many renames do you\n> > actually have?\n>\n> I am on a 64-bit Windows 10; but following up on your question, it\n> became obvious that these limits have something to do with 'which git\n> executable' I was dealing with. This problem surfaced when I was\n> working on Visual Studio 2019, and was trying to rename not more than\n> 10 files. My config had 999999 as the renameLimit, and VS2019 showed\n> the 'fatal error' in its git output. However, git bash was all fine\n> with listing the renamed files. And the difference between these\n> scenarios turned out to be, yes, different git executables. VS2019 has\n> its own copy of git which is 32-bit, and it hits this 999999 * 999999\n> overflow; whereas *my* copy of git used in bash is 64-bit which does\n> not have that overflow problem.\n\nAh, thanks for the extra info.\n\n> >\n> > We used to clamp to 32767, but one specific repository needed values\n> > larger than that, in the range of ~50000. However, due to a number of\n> > rename detection related optimizations added since then, the git of\n> > today can handle that same particular repository and support full\n> > rename detection with a rename limit under 1000 for merge/cherry-pick\n> > (sorry, forgot the exact numbers), and probably less than 10000 for\n> > diff (just guestimating; I don't want to go and check).\n> >\n> > Anyway, all that aside, I don't see any such overflow for rename_limit\n> > being 2**16; we can push it much farther:\n> >\n> > size_t a = 4294967295; /* 2**32 -1 */\n> > size_t b = a;\n> > size_t c = st_mult(a, b);\n> > printf(\"%\"PRIuMAX\" = %\"PRIuMAX\" * %\"PRIuMAX\"\\n\", c, a, b);\n> >\n> > Output:\n> >\n> > 18446744065119617025 = 4294967295 * 4294967295\n> >\n> > Adding one to the value of a results in:\n> >\n> > fatal: size_t overflow: 4294967296 * 4294967296\n> >\n> > > But I don't think an 'overflow error' is very helpful\n> > > for the users in understanding what is wrong with their configuration;\n> > > i.e. `diff.renameLimit` documentation says nothing about a 'maximum\n> > > allowed value'. I would either clamp it to a reasonable range, or\n> > > inform the users about the limits, or maybe both.\n> >\n> > That sounds reasonable, but I'm not sure it's worth the effort in\n> > practice. 2**32 - 1 is so impractically large for a rename_limit that\n> > I don't see why anyone would need a value even remotely close to that\n> > level (and I wouldn't at all be surprised if other things in git\n> > scaling broke before we even got to that point).\n> >\n> > Perhaps you're dealing with a 32-bit system? Even then, the\n> > repository that hit this was about 6.5GB packed .git history; and you\n> > might need to be a lot larger than that given the optimization since\n> > then in order to hit this. Can 32-bit systems even handle that size\n> > of repository without dying in several other ways?\n>\n> Good point, but the system aside, 2**16 - 1 = 65535 would remain to be\n> the limit for the 32-bit git executables, wherever they are used.\n> Therefore, maybe there is a point to curb it, or mention this\n> somewhere, as I have said before.\n\nFair enough. If someone wants to contribute a patch to either provide\na nicer error message if the value is set too high, or to clamp it\nwith a warning, and in either case to make sure the too-large check is\nspecific to 32-bit systems (or uses appropriately different limits on\n32-bit and 64-bit systems), then that would be a welcome contribution.\n"}]}