{"thread":{"id":"55094","subject":"[PATCH 0/2] Optimization batch 6: make full use of exact renames","startedAt":"2021-02-03T05:49:50Z","lastAt":"2021-02-14T07:36:05Z","messageCount":25,"participants":["Elijah Newren via GitGitGadget","Derrick Stolee","Elijah Newren","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"416031","messageId":"pull.842.git.1612331345.gitgitgadget@gmail.com","threadId":"55094","inReplyTo":null,"subject":"[PATCH 0/2] Optimization batch 6: make full use of exact renames","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-03T05:49:03Z","receivedAt":"2021-02-03T05:49:50Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/merge-ort-perf.\n\nFor the very curious who are wondering about the first five optimization\nbatches; see the end of this email.\n\nThis series makes full use of exact renames; see commit messages for\ndetails. It represents \"Optimization #1\" from my Git Merge 2020 talk[1]. For\nthe testcases mentioned in commit 557ac0350d (\"merge-ort: begin performance\nwork; instrument with trace2_region_* calls\", 2020-10-28), the changes in\njust this series improves the performance as follows:\n\n Before Series After Series\nno-renames: 14.263 s ± 0.053 s 13.815 s ± 0.062 s\nmega-renames: 5504.231 s ± 5.150 s 1799.937 s ± 0.493 s\njust-one-mega: 158.534 s ± 0.498 s 51.289 s ± 0.019 s\n\n\nAs a reminder, before any merge-ort/diffcore-rename performance work, the\nperformance results we started with (as noted in the same commit message)\nwere:\n\nno-renames-am: 6.940 s ± 0.485 s\nno-renames: 18.912 s ± 0.174 s\nmega-renames: 5964.031 s ± 10.459 s\njust-one-mega: 149.583 s ± 0.751 s\n\n\n[1]\nhttps://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf\n\n=== Previous optimization batches ===\n\nI'm labeling this as the \"6th\" batch, due to other optimizations submitted\npreviously, and a number of optimizations baked into the design of\nfast-rebase and merge-ort.\n\n 1. Previously submitted hashmap/strmap optimizations 1a) 33f20d8217\n (hashmap: introduce a new hashmap_partial_clear()) 1b) 6ccdfc2a20\n (strmap: enable faster clearing and reusing of strmaps) 1c) a208ec1f0b\n (strmap: enable allocations to come from a mem_pool) 1d) 23a276a9c4\n (strmap: take advantage of FLEXPTR_ALLOC_STR when relevant)\n\n 2. Previously submitted diffcore-rename optimizations 2a) b970b4ef62\n (diffcore-rename: simplify and accelerate register_rename_src()) 2b)\n 9db2ac5616 (diffcore-rename: accelerate rename_dst setup) 2c) 350410f6b1\n (diffcore-rename: remove unnecessary duplicate entry checks)\n\n 3. fast-rebase optimizations 3a) Avoid updating working-tree/index with\n every intermediate patch 3b) avoid reading/writing rebase metadata until\n conflict or completion\n\n 4. Small stuff baked into merge-ort design 4a) Using pahole to note I can\n reduce size of merged_info by 8 bytes 4b) Avoid recomparing hashes (due\n to use of match_masks) 4c) Avoid unconditional dropping and re-reading\n of the index 4d) avoid checking index matches HEAD with every patch; do\n it at start only\n\n 5. Big stuff baked into merge-ort design 5a) Avoid quadratic behavior with\n O(N) insertions/removals of index entries 5b) Avoid numerous expensive\n mini-tree traversals done by merge-recursive 5c) Avoid recursing into\n trees where both sides match merge base\n\nElijah Newren (2):\n diffcore-rename: no point trying to find a match better than exact\n diffcore-rename: filter rename_src list when possible\n\n diffcore-rename.c | 69 ++++++++++++++++++++++++++++++++++++++++++-----\n 1 file changed, 62 insertions(+), 7 deletions(-)\n\n\nbase-commit: 557ac0350d9efa1f59c708779ca3fb3aee121131\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-842%2Fnewren%2Fort-perf-batch-6-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-842/newren/ort-perf-batch-6-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/842\n-- \ngitgitgadget\n"},{"id":"416032","messageId":"3e69857f37e12540f7986245b99916b68702217a.1612331345.git.gitgitgadget@gmail.com","threadId":"55094","inReplyTo":"pull.842.git.1612331345.gitgitgadget@gmail.com","subject":"[PATCH 1/2] diffcore-rename: no point trying to find a match better than exact","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-03T05:49:04Z","receivedAt":"2021-02-03T05:49:51Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ndiffcore_rename() had some code to avoid having destination paths that\nalready had an exact rename detected from being re-checked for other\nrenames. Source paths, however, were re-checked because we wanted to\nallow the possibility of detecting copies. But if copy detection isn't\nturned on, then this merely amounts to attempting to find a\nbetter-than-exact match, which naturally ends up being an expensive\nno-op. In particular, copy detection is never turned on by the merge\nmachinery.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 14.263 s ± 0.053 s 14.119 s ± 0.101 s\n mega-renames: 5504.231 s ± 5.150 s 1802.044 s ± 0.828 s\n just-one-mega: 158.534 s ± 0.498 s 51.391 s ± 0.028 s\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 16 ++++++++++++----\n 1 file changed, 12 insertions(+), 4 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 8fe6c9384bc..e3047da3aaf 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -463,6 +463,7 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_score *mx;\n \tint i, j, rename_count, skip_unmodified = 0;\n \tint num_destinations, dst_cnt;\n+\tint num_sources;\n \tstruct progress *progress = NULL;\n \n \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n@@ -532,12 +533,15 @@ void diffcore_rename(struct diff_options *options)\n \t * files still remain as options for rename/copies!)\n \t */\n \tnum_destinations = (rename_dst_nr - rename_count);\n+\tnum_sources = rename_src_nr;\n+\tif (detect_rename != DIFF_DETECT_COPY)\n+\t\tnum_sources -= rename_count;\n \n \t/* All done? */\n-\tif (!num_destinations)\n+\tif (!num_destinations || !num_sources)\n \t\tgoto cleanup;\n \n-\tswitch (too_many_rename_candidates(num_destinations, rename_src_nr,\n+\tswitch (too_many_rename_candidates(num_destinations, num_sources,\n \t\t\t\t\t options)) {\n \tcase 1:\n \t\tgoto cleanup;\n@@ -553,7 +557,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)num_destinations * (uint64_t)rename_src_nr);\n+\t\t\t\t(uint64_t)num_destinations * (uint64_t)num_sources);\n \t}\n \n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n@@ -573,6 +577,10 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n \n+\t\t\tif (one->rename_used &&\n+\t\t\t detect_rename != DIFF_DETECT_COPY)\n+\t\t\t\tcontinue;\n+\n \t\t\tif (skip_unmodified &&\n \t\t\t diff_unmodified_pair(rename_src[j].p))\n \t\t\t\tcontinue;\n@@ -594,7 +602,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t}\n \t\tdst_cnt++;\n \t\tdisplay_progress(progress,\n-\t\t\t\t (uint64_t)dst_cnt * (uint64_t)rename_src_nr);\n+\t\t\t\t (uint64_t)dst_cnt * (uint64_t)num_sources);\n \t}\n \tstop_progress(&progress);\n \n-- \ngitgitgadget\n\n"},{"id":"416033","messageId":"580ba9a10f54c7a2e7f28d60395fc2edae25eec1.1612331345.git.gitgitgadget@gmail.com","threadId":"55094","inReplyTo":"pull.842.git.1612331345.gitgitgadget@gmail.com","subject":"[PATCH 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-03T05:49:05Z","receivedAt":"2021-02-03T05:49:59Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nWe have to look at each entry in rename_src a total of rename_dst_nr\ntimes. When we're not detecting copies, any exact renames or ignorable\nrename paths will just be skipped over. While checking that these can\nbe skipped over is a relatively cheap check, it's still a waste of time\nto do that check more than once, let alone rename_dst_nr times. When\nrename_src_nr is a few thousand times bigger than the number of relevant\nsources (such as when cherry-picking a commit that only touched a\nhandful of files, but from a side of history that has different names\nfor some high level directories), this time can add up.\n\nFirst make an initial pass over the rename_src array and move all the\nrelevant entries to the front, so that we can iterate over just those\nrelevant entries.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 14.119 s ± 0.101 s 13.815 s ± 0.062 s\n mega-renames: 1802.044 s ± 0.828 s 1799.937 s ± 0.493 s\n just-one-mega: 51.391 s ± 0.028 s 51.289 s ± 0.019 s\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 67 ++++++++++++++++++++++++++++++++++++++++-------\n 1 file changed, 57 insertions(+), 10 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e3047da3aaf..2a8e7b84b9c 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -454,6 +454,55 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i\n \treturn count;\n }\n \n+static int remove_unneeded_paths_from_src(int num_src,\n+\t\t\t\t\t int detecting_copies)\n+{\n+\tint i, new_num_src;\n+\n+\t/*\n+\t * Note on reasons why we cull unneeded sources but not destinations:\n+\t * 1) Pairings are stored in rename_dst (not rename_src), which we\n+\t * need to keep around. So, we just can't cull rename_dst even\n+\t * if we wanted to. But doing so wouldn't help because...\n+\t *\n+\t * 2) There is a matrix pairwise comparison that follows the\n+\t * \"Performing inexact rename detection\" progress message.\n+\t * Iterating over the destinations is done in the outer loop,\n+\t * hence we only iterate over each of those once and we can\n+\t * easily skip the outer loop early if the destination isn't\n+\t * relevant. That's only one check per destination path to\n+\t * skip.\n+\t *\n+\t * By contrast, the sources are iterated in the inner loop; if\n+\t * we check whether a source can be skipped, then we'll be\n+\t * checking it N separate times, once for each destination.\n+\t * We don't want to have to iterate over known-not-needed\n+\t * sources N times each, so avoid that by removing the sources\n+\t * from rename_src here.\n+\t */\n+\tif (detecting_copies)\n+\t\treturn num_src; /* nothing to remove */\n+\tif (break_idx)\n+\t\treturn num_src; /* culling incompatbile with break detection */\n+\n+\tfor (i = 0, new_num_src = 0; i < num_src; i++) {\n+\t\t/*\n+\t\t * renames are stored in rename_dst, so if a rename has\n+\t\t * already been detected using this source, we can just\n+\t\t * remove the source knowing rename_dst has its info.\n+\t\t */\n+\t\tif (rename_src[i].p->one->rename_used)\n+\t\t\tcontinue;\n+\n+\t\tif (new_num_src < i)\n+\t\t\tmemcpy(&rename_src[new_num_src], &rename_src[i],\n+\t\t\t sizeof(struct diff_rename_src));\n+\t\tnew_num_src++;\n+\t}\n+\n+\treturn new_num_src;\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -463,10 +512,11 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_score *mx;\n \tint i, j, rename_count, skip_unmodified = 0;\n \tint num_destinations, dst_cnt;\n-\tint num_sources;\n+\tint num_sources, want_copies;\n \tstruct progress *progress = NULL;\n \n \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n+\twant_copies = (detect_rename == DIFF_DETECT_COPY);\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -529,13 +579,10 @@ void diffcore_rename(struct diff_options *options)\n \t\tgoto cleanup;\n \n \t/*\n-\t * Calculate how many renames are left (but all the source\n-\t * files still remain as options for rename/copies!)\n+\t * Calculate how many renames are left\n \t */\n \tnum_destinations = (rename_dst_nr - rename_count);\n-\tnum_sources = rename_src_nr;\n-\tif (detect_rename != DIFF_DETECT_COPY)\n-\t\tnum_sources -= rename_count;\n+\tnum_sources = remove_unneeded_paths_from_src(rename_src_nr, want_copies);\n \n \t/* All done? */\n \tif (!num_destinations || !num_sources)\n@@ -573,13 +620,13 @@ void diffcore_rename(struct diff_options *options)\n \t\tfor (j = 0; j < NUM_CANDIDATE_PER_DST; j++)\n \t\t\tm[j].dst = -1;\n \n-\t\tfor (j = 0; j < rename_src_nr; j++) {\n+\t\tfor (j = 0; j < num_sources; j++) {\n \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n \n-\t\t\tif (one->rename_used &&\n-\t\t\t detect_rename != DIFF_DETECT_COPY)\n-\t\t\t\tcontinue;\n+\t\t\tassert(!one->rename_used ||\n+\t\t\t detect_rename == DIFF_DETECT_COPY ||\n+\t\t\t break_idx);\n \n \t\t\tif (skip_unmodified &&\n \t\t\t diff_unmodified_pair(rename_src[j].p))\n-- \ngitgitgadget\n"},{"id":"416036","messageId":"515f55bd-90e2-9a7f-0973-501c9351969e@gmail.com","threadId":"55094","inReplyTo":"3e69857f37e12540f7986245b99916b68702217a.1612331345.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/2] diffcore-rename: no point trying to find a match better than exact","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-02-03T11:44:50Z","receivedAt":"2021-02-03T11:45:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/3/2021 12:49 AM, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n> \n> diffcore_rename() had some code to avoid having destination paths that\n> already had an exact rename detected from being re-checked for other\n> renames. Source paths, however, were re-checked because we wanted to\n> allow the possibility of detecting copies. But if copy detection isn't\n> turned on, then this merely amounts to attempting to find a\n> better-than-exact match, which naturally ends up being an expensive\n> no-op. In particular, copy detection is never turned on by the merge\n> machinery.\n...\n> +\tnum_sources = rename_src_nr;\n> +\tif (detect_rename != DIFF_DETECT_COPY)\n> +\t\tnum_sources -= rename_count;\n\nOk, delete the renamed files from the sources. Using a new variable\nbecause rename_src_nr is actually a static global to diffcore-rename.c,\ndescribing the number of entries in the rename_src table. This is\nscary, but I think your new local is a good way to change the local\nlogic of this method without adjusting that global.\n\n> \n> \t/* All done? */\n> -\tif (!num_destinations)\n> +\tif (!num_destinations || !num_sources)\n> \t\tgoto cleanup;\n\nAnd add an extra quit condition which is very possible to hit.\nIs it only hit when every \"delete\" is actually a rename?\n\n> -\tswitch (too_many_rename_candidates(num_destinations, rename_src_nr,\n> +\tswitch (too_many_rename_candidates(num_destinations, num_sources,\n> \t\t\t\t\t options)) {\n\nThis is all about checking if we need to skip inexact renames. Makes\nsense to use the new number.\n \n> +\t\t\tif (one->rename_used &&\n> +\t\t\t detect_rename != DIFF_DETECT_COPY)\n> +\t\t\t\tcontinue;\n> +\n\nHave we \"consumed\" this input? Skip over it. Good. And this is inside\na double-loop:\n\n\tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n\t\t...\n\t\tfor (j = 0; j < rename_src_nr; j++) {\n\nKeeping rename_src_nr in the inner loop makes sense, but this new\n'continue;' gives most of the speedup, I imagine.\n\nThis is a nice speedup for such a simple optimization.\n\nThanks,\n-Stolee\n"},{"id":"416060","messageId":"CABPp-BEvu1ZQ5X35dDU-Skd71ZNLWQjj9Ow2HVvdc=faSBkGiw@mail.gmail.com","threadId":"55094","inReplyTo":"515f55bd-90e2-9a7f-0973-501c9351969e@gmail.com","subject":"Re: [PATCH 1/2] diffcore-rename: no point trying to find a match better than exact","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-02-03T16:31:45Z","receivedAt":"2021-02-03T16:32:48Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Feb 3, 2021 at 3:44 AM Derrick Stolee wrote:\n>\n> On 2/3/2021 12:49 AM, Elijah Newren via GitGitGadget wrote:\n> > From: Elijah Newren \n> >\n> > diffcore_rename() had some code to avoid having destination paths that\n> > already had an exact rename detected from being re-checked for other\n> > renames. Source paths, however, were re-checked because we wanted to\n> > allow the possibility of detecting copies. But if copy detection isn't\n> > turned on, then this merely amounts to attempting to find a\n> > better-than-exact match, which naturally ends up being an expensive\n> > no-op. In particular, copy detection is never turned on by the merge\n> > machinery.\n> ...\n> > + num_sources = rename_src_nr;\n> > + if (detect_rename != DIFF_DETECT_COPY)\n> > + num_sources -= rename_count;\n>\n> Ok, delete the renamed files from the sources. Using a new variable\n> because rename_src_nr is actually a static global to diffcore-rename.c,\n> describing the number of entries in the rename_src table. This is\n> scary, but I think your new local is a good way to change the local\n> logic of this method without adjusting that global.\n\nI thought about changing rename_src, rename_src_nr, rename_dst, and\nrename_dst_nr to all be in some struct and make one of those on the\nstack locally in diffcore_rename() and then pass that structure\naround. Would be nice to get rid of more global state. But I've got\nenough things in the queue that I never made the jump.\n\n> >\n> > /* All done? */\n> > - if (!num_destinations)\n> > + if (!num_destinations || !num_sources)\n> > goto cleanup;\n>\n> And add an extra quit condition which is very possible to hit.\n> Is it only hit when every \"delete\" is actually a rename?\n\nRight, when every \"delete\" gets paired by exact rename detection to\nsome \"add\" and is marked as a rename, meaning we have no more\n\"deletes\" to pair with anything. In later series, there will be\nadditional reasons for num_sources to decrease and possibly hit 0.\n\n> > - switch (too_many_rename_candidates(num_destinations, rename_src_nr,\n> > + switch (too_many_rename_candidates(num_destinations, num_sources,\n> > options)) {\n>\n> This is all about checking if we need to skip inexact renames. Makes\n> sense to use the new number.\n>\n> > + if (one->rename_used &&\n> > + detect_rename != DIFF_DETECT_COPY)\n> > + continue;\n> > +\n>\n> Have we \"consumed\" this input? Skip over it. Good. And this is inside\n> a double-loop:\n>\n> for (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n> ...\n> for (j = 0; j < rename_src_nr; j++) {\n>\n> Keeping rename_src_nr in the inner loop makes sense, but this new\n> 'continue;' gives most of the speedup, I imagine.\n>\n> This is a nice speedup for such a simple optimization.\n>\n> Thanks,\n> -Stolee\n"},{"id":"416066","messageId":"CABPp-BG8mu4qGQCz5sMWqJHSb9o1ipk9FgxUS34SbArhQcPutQ@mail.gmail.com","threadId":"55094","inReplyTo":"13feb106-c3a7-a26d-0e6e-013aa45c58d4@gmail.com","subject":"Re: [PATCH 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-02-03T17:12:47Z","receivedAt":"2021-02-03T17:13:56Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Feb 3, 2021 at 4:00 AM Derrick Stolee wrote:\n>\n> On 2/3/2021 12:49 AM, Elijah Newren via GitGitGadget wrote:\n> > From: Elijah Newren \n> >\n> > We have to look at each entry in rename_src a total of rename_dst_nr\n> > times. When we're not detecting copies, any exact renames or ignorable\n> > rename paths will just be skipped over. While checking that these can\n> > be skipped over is a relatively cheap check, it's still a waste of time\n> > to do that check more than once, let alone rename_dst_nr times. When\n> > rename_src_nr is a few thousand times bigger than the number of relevant\n> > sources (such as when cherry-picking a commit that only touched a\n> > handful of files, but from a side of history that has different names\n> > for some high level directories), this time can add up.\n> >\n> > First make an initial pass over the rename_src array and move all the\n> > relevant entries to the front, so that we can iterate over just those\n> > relevant entries.\n> >\n> > For the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\n> > performance work; instrument with trace2_region_* calls\", 2020-10-28),\n> > this change improves the performance as follows:\n> >\n> > Before After\n> > no-renames: 14.119 s ± 0.101 s 13.815 s ± 0.062 s\n> > mega-renames: 1802.044 s ± 0.828 s 1799.937 s ± 0.493 s\n> > just-one-mega: 51.391 s ± 0.028 s 51.289 s ± 0.019 s\n> >\n> > Signed-off-by: Elijah Newren \n> > ---\n> > diffcore-rename.c | 67 ++++++++++++++++++++++++++++++++++++++++-------\n> > 1 file changed, 57 insertions(+), 10 deletions(-)\n> >\n> > diff --git a/diffcore-rename.c b/diffcore-rename.c\n> > index e3047da3aaf..2a8e7b84b9c 100644\n> > --- a/diffcore-rename.c\n> > +++ b/diffcore-rename.c\n> > @@ -454,6 +454,55 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i\n> > return count;\n> > }\n> >\n> > +static int remove_unneeded_paths_from_src(int num_src,\n> > + int detecting_copies)\n> > +{\n> > + int i, new_num_src;\n> > +\n> > + /*\n> > + * Note on reasons why we cull unneeded sources but not destinations:\n> > + * 1) Pairings are stored in rename_dst (not rename_src), which we\n> > + * need to keep around. So, we just can't cull rename_dst even\n> > + * if we wanted to. But doing so wouldn't help because...\n> > + *\n> > + * 2) There is a matrix pairwise comparison that follows the\n> > + * \"Performing inexact rename detection\" progress message.\n> > + * Iterating over the destinations is done in the outer loop,\n> > + * hence we only iterate over each of those once and we can\n> > + * easily skip the outer loop early if the destination isn't\n> > + * relevant. That's only one check per destination path to\n> > + * skip.\n> > + *\n> > + * By contrast, the sources are iterated in the inner loop; if\n> > + * we check whether a source can be skipped, then we'll be\n> > + * checking it N separate times, once for each destination.\n> > + * We don't want to have to iterate over known-not-needed\n> > + * sources N times each, so avoid that by removing the sources\n> > + * from rename_src here.\n> > + */\n> > + if (detecting_copies)\n> > + return num_src; /* nothing to remove */\n> > + if (break_idx)\n> > + return num_src; /* culling incompatbile with break detection */\n>\n> While the comments here are certainly descriptive, they could probably\n> be sidelined to \"return when culling is incompatible\" with this before\n> the big comment:\n\nYeah, I guess at this stage a bigger explanation isn't needed. But I\nthink I'd end up just adding these comments back in later at an\nunrelated time if I were to take them out at this point. By the time\nmerge-ort is finished, I'll have over a dozen additional\noptimizations, many of them in diffcore-rename.c. There will be files\nfor which four different optimizations are all applicable, but they\nare mutually exclusive so we have to pick one of the four and exclude\nthe other three. Best results come from knowing which one provides\nthe best speedup and why (and which is second if the best doesn't\napply, etc.). So what I'll present as four optimizations originally\nfelt to me like 10 or so different ones, because I didn't start\nknowing the best, meaning I kept adding later additional optimizations\nthat fed the appropriate data in all the right places so that I could\ntweak which one(s) took priority and get the best speedups. You'll\nget the cleaner version to review that pretends I knew the right\nanswers all along. (Not to mention that I think I tried a lot more\noptimization ideas that failed than the number I tried that succeeded,\nand longer comments of mine sometimes highlight details that could\nhave prevented the need to attempt some of the failed ideas.) Anyway,\nlong story short: at some point along the way, the more detailed\ndescription felt very appropriate, but I don't have a clear breakpoint\nfor where that is and the longer description most logically goes along\nwith this early patch so I squashed it in here. *shrug*\n\n> if (detecting_copies || break_idx)\n> return num_src;\n>\n> This is a very minor nit pick, though.\n\nMoving these conditions above the comment makes sense, yes. I guess\ncombining the two if conditions here could also be done, though the\nreasoning is different as noted by the comments so I would have to\ntoss the comments. Since a later optimization will need to add an\nadditional condition that is only relevant for one of the two reasons,\nI would just need to split again later and I think I would want the\ncomments back at that time. So I think the split and keeping the\ncomments seems more natural to me.\n\n> > +\n> > + for (i = 0, new_num_src = 0; i < num_src; i++) {\n> > + /*\n> > + * renames are stored in rename_dst, so if a rename has\n> > + * already been detected using this source, we can just\n> > + * remove the source knowing rename_dst has its info.\n> > + */\n> > + if (rename_src[i].p->one->rename_used)\n> > + continue;\n> > +\n> > + if (new_num_src < i)\n> > + memcpy(&rename_src[new_num_src], &rename_src[i],\n> > + sizeof(struct diff_rename_src));\n>\n> 'struct diff_rename_src' is currently just a pointer and a short, so\n> this is a very small amount of data, but this conditional move doesn't\n> hurt.\n>\n> > + new_num_src++;\n> > + }\n> > +\n> > + return new_num_src;\n> > +}\n> > +\n>\n>\n> > void diffcore_rename(struct diff_options *options)\n> > {\n> > int detect_rename = options->detect_rename;\n> > @@ -463,10 +512,11 @@ void diffcore_rename(struct diff_options *options)\n> > struct diff_score *mx;\n> > int i, j, rename_count, skip_unmodified = 0;\n> > int num_destinations, dst_cnt;\n> > - int num_sources;\n> > + int num_sources, want_copies;\n> > struct progress *progress = NULL;\n> >\n> > trace2_region_enter(\"diff\", \"setup\", options->repo);\n> > + want_copies = (detect_rename == DIFF_DETECT_COPY);\n>\n> I was looking at this and thinking \"why wasn't this in the previous\n> patch?\" I see that you delete the \"if (detect_rename != DIFF_DETECT_COPY)\"\n> below in favor of the call to the helper.\n>\n> _If_ you were re-rolling, then maybe it would be slightly cleaner\n> to add 'want_copies' to the previous patch?\n\nOh, yeah, I think that does make sense. And you highlight some good\nreasons to re-roll below, so I'll do that.\n\n> > /*\n> > - * Calculate how many renames are left (but all the source\n> > - * files still remain as options for rename/copies!)\n> > + * Calculate how many renames are left\n> > */\n> > num_destinations = (rename_dst_nr - rename_count);\n> > - num_sources = rename_src_nr;\n> > - if (detect_rename != DIFF_DETECT_COPY)\n> > - num_sources -= rename_count;\n> > + num_sources = remove_unneeded_paths_from_src(rename_src_nr, want_copies);\n>\n> So here we update the local variable...\n>\n> >\n> > /* All done? */\n> > if (!num_destinations || !num_sources)\n> > @@ -573,13 +620,13 @@ void diffcore_rename(struct diff_options *options)\n> > for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)\n> > m[j].dst = -1;\n> >\n> > - for (j = 0; j < rename_src_nr; j++) {\n> > + for (j = 0; j < num_sources; j++) {\n>\n> ...and drop the use of the static global. However, don't we need to\n> update the global itself? There are other loops limited by\n> rename_src_nr that should only work on this smaller list, right?\n>\n> In particular, it seems that the prefetch() method would benefit\n> from looking at this smaller list. It fetches the blob contents in\n> a partial clone inside of estimate_similarity(). When there are a\n> lot of exact renames but even one possible inexact rename, it seems\n> to currently download the content for all of the blobs including the\n> exactly-matched ones.\n\nAh, indeed. The prefetch() method didn't exist at the time I wrote\nthis patch, but there's always the possibility of other reasons. It\nturns out I did make rename_src_nr match num_sources, but that diff\nhunk got placed in a later series. I agree with you that it should go\nhere instead.\n\n> For interesting tests around this prefetch() call, I think the\n> 'diff with rename detection batches blobs' test in t4067 should help.\n>\n> > struct diff_filespec *one = rename_src[j].p->one;\n> > struct diff_score this_src;\n> >\n> > - if (one->rename_used &&\n> > - detect_rename != DIFF_DETECT_COPY)\n> > - continue;\n> > + assert(!one->rename_used ||\n> > + detect_rename == DIFF_DETECT_COPY ||\n> > + break_idx);\n>\n> Looks like you could use 'want_copies' here (and in the previous\n> patch).\n\nYep, good catch. I'll make the change.\n\n> Thanks,\n> -Stolee\n\nThanks for reviewing!\n"},{"id":"416075","messageId":"xmqqft2dc7lj.fsf@gitster.c.googlers.com","threadId":"55094","inReplyTo":"515f55bd-90e2-9a7f-0973-501c9351969e@gmail.com","subject":"Re: [PATCH 1/2] diffcore-rename: no point trying to find a match better than exact","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-03T18:46:32Z","receivedAt":"2021-02-03T18:47:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> \t/* All done? */\n>> -\tif (!num_destinations)\n>> +\tif (!num_destinations || !num_sources)\n>> \t\tgoto cleanup;\n>\n> And add an extra quit condition which is very possible to hit.\n> Is it only hit when every \"delete\" is actually a rename?\n\nWhen every delete is actually an unmodified exact rename, I think.\nIf this simple change gives us good performance gain, that is\nsuperb.\n\nNicely done.\n"},{"id":"416076","messageId":"CABPp-BH45RzNjo_Xj9uTpLj5f00dWwXun4m+mob25FJ0sPprWg@mail.gmail.com","threadId":"55094","inReplyTo":"xmqqft2dc7lj.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/2] diffcore-rename: no point trying to find a match better than exact","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-02-03T19:10:55Z","receivedAt":"2021-02-03T19:11:52Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Feb 3, 2021 at 10:46 AM Junio C Hamano wrote:\n>\n> Derrick Stolee writes:\n>\n> >> /* All done? */\n> >> - if (!num_destinations)\n> >> + if (!num_destinations || !num_sources)\n> >> goto cleanup;\n> >\n> > And add an extra quit condition which is very possible to hit.\n> > Is it only hit when every \"delete\" is actually a rename?\n>\n> When every delete is actually an unmodified exact rename, I think.\n\nYes, exactly.\n\n> If this simple change gives us good performance gain, that is\n> superb.\n>\n> Nicely done.\n\nThanks.\n\nI probably should have separated this from the speculative\nnot-quite-working changes that weren't ready yet and pushed just it\nsooner.[1] But I kinda wanted to get all the performance changes\ntogether, and...well, all the other performance changes took a while\nto complete (especially given multiple starts and stops).\n\n[1] https://lore.kernel.org/git/20171110222156.23221-2-newren@gmail.com/\n"},{"id":"416077","messageId":"xmqqbld1c6dz.fsf@gitster.c.googlers.com","threadId":"55094","inReplyTo":"580ba9a10f54c7a2e7f28d60395fc2edae25eec1.1612331345.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-03T19:12:40Z","receivedAt":"2021-02-03T19:13:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> +static int remove_unneeded_paths_from_src(int num_src,\n> +\t\t\t\t\t int detecting_copies)\n> +{\n> +\tint i, new_num_src;\n> +\n> +\t/*\n> +\t * Note on reasons why we cull unneeded sources but not destinations:\n> +\t * 1) Pairings are stored in rename_dst (not rename_src), which we\n> +\t * need to keep around. So, we just can't cull rename_dst even\n> +\t * if we wanted to. But doing so wouldn't help because...\n> +\t *\n> +\t * 2) There is a matrix pairwise comparison that follows the\n> +\t * \"Performing inexact rename detection\" progress message.\n> +\t * Iterating over the destinations is done in the outer loop,\n> +\t * hence we only iterate over each of those once and we can\n> +\t * easily skip the outer loop early if the destination isn't\n> +\t * relevant. That's only one check per destination path to\n> +\t * skip.\n> +\t *\n> +\t * By contrast, the sources are iterated in the inner loop; if\n> +\t * we check whether a source can be skipped, then we'll be\n> +\t * checking it N separate times, once for each destination.\n> +\t * We don't want to have to iterate over known-not-needed\n> +\t * sources N times each, so avoid that by removing the sources\n> +\t * from rename_src here.\n> +\t */\n> +\tif (detecting_copies)\n> +\t\treturn num_src; /* nothing to remove */\n> +\tif (break_idx)\n> +\t\treturn num_src; /* culling incompatbile with break detection */\n> +\n> +\tfor (i = 0, new_num_src = 0; i < num_src; i++) {\n> +\t\t/*\n> +\t\t * renames are stored in rename_dst, so if a rename has\n> +\t\t * already been detected using this source, we can just\n> +\t\t * remove the source knowing rename_dst has its info.\n> +\t\t */\n> +\t\tif (rename_src[i].p->one->rename_used)\n> +\t\t\tcontinue;\n> +\n> +\t\tif (new_num_src < i)\n> +\t\t\tmemcpy(&rename_src[new_num_src], &rename_src[i],\n> +\t\t\t sizeof(struct diff_rename_src));\n> +\t\tnew_num_src++;\n> +\t}\n> +\n> +\treturn new_num_src;\n> +}\n\nEssentially we are compacting rename_src[] array from num_src\nelements down to new_num_src elements; we are losing pointers, but I\npresume these are all borrowed pointers that we do not own and we\nare not responsible for freeing? If we were to free them, the\ncompaction would leave duplicates after the new tail (new_num_src)\nand we'd end up having to worry about double-freeing, so hopefully\nall we need to do is just to free the entire array of pointers, and\nnot the pointees.\n\nHaving to do this just once and being able to reduce the number of\nentries we need to iterate over does sound like a good simple\noptimization.\n\n> void diffcore_rename(struct diff_options *options)\n> {\n> \tint detect_rename = options->detect_rename;\n> @@ -463,10 +512,11 @@ void diffcore_rename(struct diff_options *options)\n> \tstruct diff_score *mx;\n> \tint i, j, rename_count, skip_unmodified = 0;\n> \tint num_destinations, dst_cnt;\n> -\tint num_sources;\n> +\tint num_sources, want_copies;\n> \tstruct progress *progress = NULL;\n> \n> \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n> +\twant_copies = (detect_rename == DIFF_DETECT_COPY);\n> \tif (!minimum_score)\n> \t\tminimum_score = DEFAULT_RENAME_SCORE;\n> \n> @@ -529,13 +579,10 @@ void diffcore_rename(struct diff_options *options)\n> \t\tgoto cleanup;\n> \n> \t/*\n> -\t * Calculate how many renames are left (but all the source\n> -\t * files still remain as options for rename/copies!)\n> +\t * Calculate how many renames are left\n> \t */\n> \tnum_destinations = (rename_dst_nr - rename_count);\n> -\tnum_sources = rename_src_nr;\n> -\tif (detect_rename != DIFF_DETECT_COPY)\n> -\t\tnum_sources -= rename_count;\n> +\tnum_sources = remove_unneeded_paths_from_src(rename_src_nr, want_copies);\n\nOK, this is in a sense an extended version of the previous step.\n\nI am not sure if rename_src_nr can be left out of sync with reality\nlike this patch does, though. The reference to that variable in\nregister_rename_src() and find_exact_renames() are OK as we are not\ngoing to call them after we futz with the rename_src[] array, but\nthe reference in prefetch(), which does not actually happen early\nbut only when we start running estimate_similarity(), which is after\nwe compacted the rename_src[] array, would be affected, no?\n\nThanks.\n"},{"id":"416078","messageId":"CABPp-BGm6A7vrkehQx0br4h-D8vDNJAB+oEOdkTrzvD3OM+BQA@mail.gmail.com","threadId":"55094","inReplyTo":"xmqqbld1c6dz.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-02-03T19:19:39Z","receivedAt":"2021-02-03T19:20:52Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Feb 3, 2021 at 11:12 AM Junio C Hamano wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > +static int remove_unneeded_paths_from_src(int num_src,\n> > + int detecting_copies)\n> > +{\n> > + int i, new_num_src;\n> > +\n> > + /*\n> > + * Note on reasons why we cull unneeded sources but not destinations:\n> > + * 1) Pairings are stored in rename_dst (not rename_src), which we\n> > + * need to keep around. So, we just can't cull rename_dst even\n> > + * if we wanted to. But doing so wouldn't help because...\n> > + *\n> > + * 2) There is a matrix pairwise comparison that follows the\n> > + * \"Performing inexact rename detection\" progress message.\n> > + * Iterating over the destinations is done in the outer loop,\n> > + * hence we only iterate over each of those once and we can\n> > + * easily skip the outer loop early if the destination isn't\n> > + * relevant. That's only one check per destination path to\n> > + * skip.\n> > + *\n> > + * By contrast, the sources are iterated in the inner loop; if\n> > + * we check whether a source can be skipped, then we'll be\n> > + * checking it N separate times, once for each destination.\n> > + * We don't want to have to iterate over known-not-needed\n> > + * sources N times each, so avoid that by removing the sources\n> > + * from rename_src here.\n> > + */\n> > + if (detecting_copies)\n> > + return num_src; /* nothing to remove */\n> > + if (break_idx)\n> > + return num_src; /* culling incompatbile with break detection */\n> > +\n> > + for (i = 0, new_num_src = 0; i < num_src; i++) {\n> > + /*\n> > + * renames are stored in rename_dst, so if a rename has\n> > + * already been detected using this source, we can just\n> > + * remove the source knowing rename_dst has its info.\n> > + */\n> > + if (rename_src[i].p->one->rename_used)\n> > + continue;\n> > +\n> > + if (new_num_src < i)\n> > + memcpy(&rename_src[new_num_src], &rename_src[i],\n> > + sizeof(struct diff_rename_src));\n> > + new_num_src++;\n> > + }\n> > +\n> > + return new_num_src;\n> > +}\n>\n> Essentially we are compacting rename_src[] array from num_src\n> elements down to new_num_src elements; we are losing pointers, but I\n> presume these are all borrowed pointers that we do not own and we\n> are not responsible for freeing? If we were to free them, the\n> compaction would leave duplicates after the new tail (new_num_src)\n> and we'd end up having to worry about double-freeing, so hopefully\n> all we need to do is just to free the entire array of pointers, and\n> not the pointees.\n>\n> Having to do this just once and being able to reduce the number of\n> entries we need to iterate over does sound like a good simple\n> optimization.\n\nCorrect, they are all just borrowed pointers and we only need to free\nthe array, not the pointers within the array.\n\n> > void diffcore_rename(struct diff_options *options)\n> > {\n> > int detect_rename = options->detect_rename;\n> > @@ -463,10 +512,11 @@ void diffcore_rename(struct diff_options *options)\n> > struct diff_score *mx;\n> > int i, j, rename_count, skip_unmodified = 0;\n> > int num_destinations, dst_cnt;\n> > - int num_sources;\n> > + int num_sources, want_copies;\n> > struct progress *progress = NULL;\n> >\n> > trace2_region_enter(\"diff\", \"setup\", options->repo);\n> > + want_copies = (detect_rename == DIFF_DETECT_COPY);\n> > if (!minimum_score)\n> > minimum_score = DEFAULT_RENAME_SCORE;\n> >\n> > @@ -529,13 +579,10 @@ void diffcore_rename(struct diff_options *options)\n> > goto cleanup;\n> >\n> > /*\n> > - * Calculate how many renames are left (but all the source\n> > - * files still remain as options for rename/copies!)\n> > + * Calculate how many renames are left\n> > */\n> > num_destinations = (rename_dst_nr - rename_count);\n> > - num_sources = rename_src_nr;\n> > - if (detect_rename != DIFF_DETECT_COPY)\n> > - num_sources -= rename_count;\n> > + num_sources = remove_unneeded_paths_from_src(rename_src_nr, want_copies);\n>\n> OK, this is in a sense an extended version of the previous step.\n>\n> I am not sure if rename_src_nr can be left out of sync with reality\n> like this patch does, though. The reference to that variable in\n> register_rename_src() and find_exact_renames() are OK as we are not\n> going to call them after we futz with the rename_src[] array, but\n> the reference in prefetch(), which does not actually happen early\n> but only when we start running estimate_similarity(), which is after\n> we compacted the rename_src[] array, would be affected, no?\n\nYes, good catch. This is the same issue Stolee caught. I did set\nrename_src_nr to the new num_sources in my \"ort\" branch, but when\nbreaking up the changes to upstream them, that line of code somehow\ngot separated into a later patch (that I haven't submitted yet) and I\njust didn't notice it when reviewing this early series. It belongs in\nthis patch as both of you pointed out.\n"},{"id":"416083","messageId":"pull.842.v2.git.1612382628.gitgitgadget@gmail.com","threadId":"55094","inReplyTo":"pull.842.git.1612331345.gitgitgadget@gmail.com","subject":"[PATCH v2 0/2] Optimization batch 6: make full use of exact renames","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-03T20:03:45Z","receivedAt":"2021-02-03T20:04:38Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/merge-ort-perf and makes full use of exact\nrenames; see commit messages for details.\n\nThanks to Stolee and Junio for reviewing v1.\n\nChanges since v1:\n\n * Update rename_src_nr when updating rename_src\n * Introduce want_copies in the first patch and use it in a few more places\n * Move a comment below a few exit-early if-checks.\n\nElijah Newren (2):\n diffcore-rename: no point trying to find a match better than exact\n diffcore-rename: filter rename_src list when possible\n\n diffcore-rename.c | 69 +++++++++++++++++++++++++++++++++++++++++------\n 1 file changed, 61 insertions(+), 8 deletions(-)\n\n\nbase-commit: 557ac0350d9efa1f59c708779ca3fb3aee121131\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-842%2Fnewren%2Fort-perf-batch-6-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-842/newren/ort-perf-batch-6-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/842\n\nRange-diff vs v1:\n\n 1: 3e69857f37e ! 1: 770e894b4ab diffcore-rename: no point trying to find a match better than exact\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \tstruct diff_score *mx;\n \tint i, j, rename_count, skip_unmodified = 0;\n \tint num_destinations, dst_cnt;\n -+\tint num_sources;\n ++\tint num_sources, want_copies;\n \tstruct progress *progress = NULL;\n \n \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n ++\twant_copies = (detect_rename == DIFF_DETECT_COPY);\n + \tif (!minimum_score)\n + \t\tminimum_score = DEFAULT_RENAME_SCORE;\n + \n +@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n + \t\t\t\tp->one->rename_used++;\n + \t\t\tregister_rename_src(p);\n + \t\t}\n +-\t\telse if (detect_rename == DIFF_DETECT_COPY) {\n ++\t\telse if (want_copies) {\n + \t\t\t/*\n + \t\t\t * Increment the \"rename_used\" score by\n + \t\t\t * one, to indicate ourselves as a user.\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t * files still remain as options for rename/copies!)\n \t */\n \tnum_destinations = (rename_dst_nr - rename_count);\n +\tnum_sources = rename_src_nr;\n -+\tif (detect_rename != DIFF_DETECT_COPY)\n ++\tif (!want_copies)\n +\t\tnum_sources -= rename_count;\n \n \t/* All done? */\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n \n -+\t\t\tif (one->rename_used &&\n -+\t\t\t detect_rename != DIFF_DETECT_COPY)\n ++\t\t\tif (one->rename_used && !want_copies)\n +\t\t\t\tcontinue;\n +\n \t\t\tif (skip_unmodified &&\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t}\n \tstop_progress(&progress);\n \n +@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n + \tSTABLE_QSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);\n + \n + \trename_count += find_renames(mx, dst_cnt, minimum_score, 0);\n +-\tif (detect_rename == DIFF_DETECT_COPY)\n ++\tif (want_copies)\n + \t\trename_count += find_renames(mx, dst_cnt, minimum_score, 1);\n + \tfree(mx);\n + \ttrace2_region_leave(\"diff\", \"inexact renames\", options->repo);\n 2: 580ba9a10f5 ! 2: 7ae9460d3db diffcore-rename: filter rename_src list when possible\n @@ diffcore-rename.c: static int find_renames(struct diff_score *mx, int dst_cnt, i\n \treturn count;\n }\n \n -+static int remove_unneeded_paths_from_src(int num_src,\n -+\t\t\t\t\t int detecting_copies)\n ++static void remove_unneeded_paths_from_src(int detecting_copies)\n +{\n +\tint i, new_num_src;\n +\n ++\tif (detecting_copies)\n ++\t\treturn; /* nothing to remove */\n ++\tif (break_idx)\n ++\t\treturn; /* culling incompatbile with break detection */\n ++\n +\t/*\n +\t * Note on reasons why we cull unneeded sources but not destinations:\n +\t * 1) Pairings are stored in rename_dst (not rename_src), which we\n @@ diffcore-rename.c: static int find_renames(struct diff_score *mx, int dst_cnt, i\n +\t * sources N times each, so avoid that by removing the sources\n +\t * from rename_src here.\n +\t */\n -+\tif (detecting_copies)\n -+\t\treturn num_src; /* nothing to remove */\n -+\tif (break_idx)\n -+\t\treturn num_src; /* culling incompatbile with break detection */\n -+\n -+\tfor (i = 0, new_num_src = 0; i < num_src; i++) {\n ++\tfor (i = 0, new_num_src = 0; i < rename_src_nr; i++) {\n +\t\t/*\n +\t\t * renames are stored in rename_dst, so if a rename has\n +\t\t * already been detected using this source, we can just\n @@ diffcore-rename.c: static int find_renames(struct diff_score *mx, int dst_cnt, i\n +\t\tnew_num_src++;\n +\t}\n +\n -+\treturn new_num_src;\n ++\trename_src_nr = new_num_src;\n +}\n +\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n -@@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n - \tstruct diff_score *mx;\n - \tint i, j, rename_count, skip_unmodified = 0;\n - \tint num_destinations, dst_cnt;\n --\tint num_sources;\n -+\tint num_sources, want_copies;\n - \tstruct progress *progress = NULL;\n - \n - \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n -+\twant_copies = (detect_rename == DIFF_DETECT_COPY);\n - \tif (!minimum_score)\n - \t\tminimum_score = DEFAULT_RENAME_SCORE;\n - \n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n \t\tgoto cleanup;\n \n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n +\t * Calculate how many renames are left\n \t */\n \tnum_destinations = (rename_dst_nr - rename_count);\n --\tnum_sources = rename_src_nr;\n --\tif (detect_rename != DIFF_DETECT_COPY)\n ++\tremove_unneeded_paths_from_src(want_copies);\n + \tnum_sources = rename_src_nr;\n +-\tif (!want_copies)\n -\t\tnum_sources -= rename_count;\n -+\tnum_sources = remove_unneeded_paths_from_src(rename_src_nr, want_copies);\n \n \t/* All done? */\n \tif (!num_destinations || !num_sources)\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n - \t\tfor (j = 0; j < NUM_CANDIDATE_PER_DST; j++)\n - \t\t\tm[j].dst = -1;\n - \n --\t\tfor (j = 0; j < rename_src_nr; j++) {\n -+\t\tfor (j = 0; j < num_sources; j++) {\n \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n \n --\t\t\tif (one->rename_used &&\n --\t\t\t detect_rename != DIFF_DETECT_COPY)\n +-\t\t\tif (one->rename_used && !want_copies)\n -\t\t\t\tcontinue;\n -+\t\t\tassert(!one->rename_used ||\n -+\t\t\t detect_rename == DIFF_DETECT_COPY ||\n -+\t\t\t break_idx);\n ++\t\t\tassert(!one->rename_used || want_copies || break_idx);\n \n \t\t\tif (skip_unmodified &&\n \t\t\t diff_unmodified_pair(rename_src[j].p))\n\n-- \ngitgitgadget\n"},{"id":"416084","messageId":"770e894b4abdf24112fa51f963b6fce15be942c1.1612382628.git.gitgitgadget@gmail.com","threadId":"55094","inReplyTo":"pull.842.v2.git.1612382628.gitgitgadget@gmail.com","subject":"[PATCH v2 1/2] diffcore-rename: no point trying to find a match better than exact","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-03T20:03:46Z","receivedAt":"2021-02-03T20:04:39Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ndiffcore_rename() had some code to avoid having destination paths that\nalready had an exact rename detected from being re-checked for other\nrenames. Source paths, however, were re-checked because we wanted to\nallow the possibility of detecting copies. But if copy detection isn't\nturned on, then this merely amounts to attempting to find a\nbetter-than-exact match, which naturally ends up being an expensive\nno-op. In particular, copy detection is never turned on by the merge\nmachinery.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 14.263 s ± 0.053 s 14.119 s ± 0.101 s\n mega-renames: 5504.231 s ± 5.150 s 1802.044 s ± 0.828 s\n just-one-mega: 158.534 s ± 0.498 s 51.391 s ± 0.028 s\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 20 ++++++++++++++------\n 1 file changed, 14 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 8fe6c9384bc..8b118628b4e 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -463,9 +463,11 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_score *mx;\n \tint i, j, rename_count, skip_unmodified = 0;\n \tint num_destinations, dst_cnt;\n+\tint num_sources, want_copies;\n \tstruct progress *progress = NULL;\n \n \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n+\twant_copies = (detect_rename == DIFF_DETECT_COPY);\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -502,7 +504,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\tp->one->rename_used++;\n \t\t\tregister_rename_src(p);\n \t\t}\n-\t\telse if (detect_rename == DIFF_DETECT_COPY) {\n+\t\telse if (want_copies) {\n \t\t\t/*\n \t\t\t * Increment the \"rename_used\" score by\n \t\t\t * one, to indicate ourselves as a user.\n@@ -532,12 +534,15 @@ void diffcore_rename(struct diff_options *options)\n \t * files still remain as options for rename/copies!)\n \t */\n \tnum_destinations = (rename_dst_nr - rename_count);\n+\tnum_sources = rename_src_nr;\n+\tif (!want_copies)\n+\t\tnum_sources -= rename_count;\n \n \t/* All done? */\n-\tif (!num_destinations)\n+\tif (!num_destinations || !num_sources)\n \t\tgoto cleanup;\n \n-\tswitch (too_many_rename_candidates(num_destinations, rename_src_nr,\n+\tswitch (too_many_rename_candidates(num_destinations, num_sources,\n \t\t\t\t\t options)) {\n \tcase 1:\n \t\tgoto cleanup;\n@@ -553,7 +558,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)num_destinations * (uint64_t)rename_src_nr);\n+\t\t\t\t(uint64_t)num_destinations * (uint64_t)num_sources);\n \t}\n \n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n@@ -573,6 +578,9 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n \n+\t\t\tif (one->rename_used && !want_copies)\n+\t\t\t\tcontinue;\n+\n \t\t\tif (skip_unmodified &&\n \t\t\t diff_unmodified_pair(rename_src[j].p))\n \t\t\t\tcontinue;\n@@ -594,7 +602,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t}\n \t\tdst_cnt++;\n \t\tdisplay_progress(progress,\n-\t\t\t\t (uint64_t)dst_cnt * (uint64_t)rename_src_nr);\n+\t\t\t\t (uint64_t)dst_cnt * (uint64_t)num_sources);\n \t}\n \tstop_progress(&progress);\n \n@@ -602,7 +610,7 @@ void diffcore_rename(struct diff_options *options)\n \tSTABLE_QSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);\n \n \trename_count += find_renames(mx, dst_cnt, minimum_score, 0);\n-\tif (detect_rename == DIFF_DETECT_COPY)\n+\tif (want_copies)\n \t\trename_count += find_renames(mx, dst_cnt, minimum_score, 1);\n \tfree(mx);\n \ttrace2_region_leave(\"diff\", \"inexact renames\", options->repo);\n-- \ngitgitgadget\n\n"},{"id":"416085","messageId":"7ae9460d3dba84122c2674b46e4339b9d42bdedd.1612382628.git.gitgitgadget@gmail.com","threadId":"55094","inReplyTo":"pull.842.v2.git.1612382628.gitgitgadget@gmail.com","subject":"[PATCH v2 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-03T20:03:47Z","receivedAt":"2021-02-03T20:04:52Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nWe have to look at each entry in rename_src a total of rename_dst_nr\ntimes. When we're not detecting copies, any exact renames or ignorable\nrename paths will just be skipped over. While checking that these can\nbe skipped over is a relatively cheap check, it's still a waste of time\nto do that check more than once, let alone rename_dst_nr times. When\nrename_src_nr is a few thousand times bigger than the number of relevant\nsources (such as when cherry-picking a commit that only touched a\nhandful of files, but from a side of history that has different names\nfor some high level directories), this time can add up.\n\nFirst make an initial pass over the rename_src array and move all the\nrelevant entries to the front, so that we can iterate over just those\nrelevant entries.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 14.119 s ± 0.101 s 13.815 s ± 0.062 s\n mega-renames: 1802.044 s ± 0.828 s 1799.937 s ± 0.493 s\n just-one-mega: 51.391 s ± 0.028 s 51.289 s ± 0.019 s\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 57 ++++++++++++++++++++++++++++++++++++++++++-----\n 1 file changed, 51 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 8b118628b4e..74930716e70 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -454,6 +454,54 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i\n \treturn count;\n }\n \n+static void remove_unneeded_paths_from_src(int detecting_copies)\n+{\n+\tint i, new_num_src;\n+\n+\tif (detecting_copies)\n+\t\treturn; /* nothing to remove */\n+\tif (break_idx)\n+\t\treturn; /* culling incompatbile with break detection */\n+\n+\t/*\n+\t * Note on reasons why we cull unneeded sources but not destinations:\n+\t * 1) Pairings are stored in rename_dst (not rename_src), which we\n+\t * need to keep around. So, we just can't cull rename_dst even\n+\t * if we wanted to. But doing so wouldn't help because...\n+\t *\n+\t * 2) There is a matrix pairwise comparison that follows the\n+\t * \"Performing inexact rename detection\" progress message.\n+\t * Iterating over the destinations is done in the outer loop,\n+\t * hence we only iterate over each of those once and we can\n+\t * easily skip the outer loop early if the destination isn't\n+\t * relevant. That's only one check per destination path to\n+\t * skip.\n+\t *\n+\t * By contrast, the sources are iterated in the inner loop; if\n+\t * we check whether a source can be skipped, then we'll be\n+\t * checking it N separate times, once for each destination.\n+\t * We don't want to have to iterate over known-not-needed\n+\t * sources N times each, so avoid that by removing the sources\n+\t * from rename_src here.\n+\t */\n+\tfor (i = 0, new_num_src = 0; i < rename_src_nr; i++) {\n+\t\t/*\n+\t\t * renames are stored in rename_dst, so if a rename has\n+\t\t * already been detected using this source, we can just\n+\t\t * remove the source knowing rename_dst has its info.\n+\t\t */\n+\t\tif (rename_src[i].p->one->rename_used)\n+\t\t\tcontinue;\n+\n+\t\tif (new_num_src < i)\n+\t\t\tmemcpy(&rename_src[new_num_src], &rename_src[i],\n+\t\t\t sizeof(struct diff_rename_src));\n+\t\tnew_num_src++;\n+\t}\n+\n+\trename_src_nr = new_num_src;\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -530,13 +578,11 @@ void diffcore_rename(struct diff_options *options)\n \t\tgoto cleanup;\n \n \t/*\n-\t * Calculate how many renames are left (but all the source\n-\t * files still remain as options for rename/copies!)\n+\t * Calculate how many renames are left\n \t */\n \tnum_destinations = (rename_dst_nr - rename_count);\n+\tremove_unneeded_paths_from_src(want_copies);\n \tnum_sources = rename_src_nr;\n-\tif (!want_copies)\n-\t\tnum_sources -= rename_count;\n \n \t/* All done? */\n \tif (!num_destinations || !num_sources)\n@@ -578,8 +624,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n \n-\t\t\tif (one->rename_used && !want_copies)\n-\t\t\t\tcontinue;\n+\t\t\tassert(!one->rename_used || want_copies || break_idx);\n \n \t\t\tif (skip_unmodified &&\n \t\t\t diff_unmodified_pair(rename_src[j].p))\n-- \ngitgitgadget\n"},{"id":"416108","messageId":"xmqqlfc4byt6.fsf@gitster.c.googlers.com","threadId":"55094","inReplyTo":"pull.842.v2.git.1612382628.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/2] Optimization batch 6: make full use of exact renames","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-03T21:56:21Z","receivedAt":"2021-02-03T21:57:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> This series depends on en/merge-ort-perf and makes full use of exact\n> renames; see commit messages for details.\n>\n> Thanks to Stolee and Junio for reviewing v1.\n>\n> Changes since v1:\n>\n> * Update rename_src_nr when updating rename_src\n> * Introduce want_copies in the first patch and use it in a few more places\n> * Move a comment below a few exit-early if-checks.\n>\n> Elijah Newren (2):\n> diffcore-rename: no point trying to find a match better than exact\n> diffcore-rename: filter rename_src list when possible\n>\n> diffcore-rename.c | 69 +++++++++++++++++++++++++++++++++++++++++------\n> 1 file changed, 61 insertions(+), 8 deletions(-)\n\nThanks, these look bettrer.\n\nWith these changes, I guess there are only two things I find myself\nsomewhat embarrassing in the rename machinery that is still there\nsince I invented it.\n\n - We still need to go full matrix while finding the \"best\"\n pairing. I cannot think of a way to avoid it (that is what makes\n it embarrassing) but wish there were some way to.\n\n In an early attempt, I tried to retire rename_src[j], once\n rename_dst[i] has been found to be a \"good enough\" match for it,\n from the pool of rename src candidates to find a good match for\n rename_dst[k] for i < k, but naive implementation of it would not\n work well for obvious reasons---rename_src[j] may match a lot\n better with rename_dst[k] than rename_dst[i] but we do not know\n that until we try to estimate similarity with rename_dst[k].\n\n\n - The .cnt_data member was designed to be a concise summary of the\n blob characteristics so that two .cnt_data can be \"compared\"\n fairly cheaply to see how \"similar\" two blobs are [*], but (1) it\n is rather big to be called a \"concise summary\", and (2) it was\n not chosen after real performance measurement, and we've been\n using it for the past 15 years without revisiting its design.\n\n Side note: In a very early prototype, the approach to assess\n similarity between two blobs was very different---there was no\n attempt to compute \"concise summary\" for each blob, but we just\n attempted to create delta (as in the pack data) between src and\n dst blobs and measured how small a delta we can use to transform\n from src to dst.\n\n"},{"id":"416112","messageId":"CABPp-BEgwfv70NRGgyAnHnQBPx4APSyYxNCbvH9F=7WGSj4DLQ@mail.gmail.com","threadId":"55094","inReplyTo":"xmqqlfc4byt6.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 0/2] Optimization batch 6: make full use of exact renames","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-02-03T23:06:26Z","receivedAt":"2021-02-03T23:08:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Feb 3, 2021 at 1:56 PM Junio C Hamano wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > This series depends on en/merge-ort-perf and makes full use of exact\n> > renames; see commit messages for details.\n> >\n> > Thanks to Stolee and Junio for reviewing v1.\n> >\n> > Changes since v1:\n> >\n> > * Update rename_src_nr when updating rename_src\n> > * Introduce want_copies in the first patch and use it in a few more places\n> > * Move a comment below a few exit-early if-checks.\n> >\n> > Elijah Newren (2):\n> > diffcore-rename: no point trying to find a match better than exact\n> > diffcore-rename: filter rename_src list when possible\n> >\n> > diffcore-rename.c | 69 +++++++++++++++++++++++++++++++++++++++++------\n> > 1 file changed, 61 insertions(+), 8 deletions(-)\n>\n> Thanks, these look bettrer.\n>\n> With these changes, I guess there are only two things I find myself\n> somewhat embarrassing in the rename machinery that is still there\n> since I invented it.\n>\n> - We still need to go full matrix while finding the \"best\"\n> pairing. I cannot think of a way to avoid it (that is what makes\n> it embarrassing) but wish there were some way to.\n\nIt turns out that exact renames aren't the only thing that can reduce\nthe size of the matrix. My next few series will add some more.\n\nThe matrix does remain, even at the end of all my performance work,\nbut multiple ways to shrink it certainly help a lot.\n\n> In an early attempt, I tried to retire rename_src[j], once\n> rename_dst[i] has been found to be a \"good enough\" match for it,\n> from the pool of rename src candidates to find a good match for\n> rename_dst[k] for i < k, but naive implementation of it would not\n> work well for obvious reasons---rename_src[j] may match a lot\n> better with rename_dst[k] than rename_dst[i] but we do not know\n> that until we try to estimate similarity with rename_dst[k].\n\nYou may really like the next two series I submit. I have a smarter\nway to find a \"good enough\" match (comparing to exactly one other file\nand often finding sufficient similarity), and one that'll make\nintuitive sense to users.\n\nThen I have other series after those that optimize in different ways.\n\n> - The .cnt_data member was designed to be a concise summary of the\n> blob characteristics so that two .cnt_data can be \"compared\"\n> fairly cheaply to see how \"similar\" two blobs are [*], but (1) it\n> is rather big to be called a \"concise summary\", and (2) it was\n> not chosen after real performance measurement, and we've been\n> using it for the past 15 years without revisiting its design.\n\n.cnt_data seemed kind of clever to me, though it did have a few things\nthat seemed surprising:\n\n1) Small \"lines\". The similarity works by mapping each \"line\" to an\ninteger using some simple hash, and keeps track of the list of hashed\nintegers for each file. Once you have a list of hashed integers for\neach file, similarity is determined by looking through the two lists\nfor two files and seeing what percentage of integers is found in both\n(but see item #3 for how percentage is defined). One special\nconsideration here was \"lines\".\n\nI think because of a desire to handle binary files, there was a\ndecision to split at 64-bytes or LF, whichever comes first, so each\nreal line of code might be broken into multiple \"lines\". The 64-bytes\nthing might make things a little weird, though. If you have a lot of\nlines that are just over 64-characters long, they'll be split into two\n\"lines\", with the second ones being very short. Really short lines\nare much more likely to look like other really short lines, which\nmight pad your similarity count. I'm not sure what to do differently,\nthough.\n\n2) Size-agnostic hashing. The integer that each \"line\" is mapped to\nis strictly between 0 and HASHBASE-1, where HASHBASE is #define'd to\n107927.\n\nBy the pigeon-hole principle, since this hash size is fixed, any two\nsufficiently large files will be marked by this algorithm as similar.\nI created some testcases and verified that this was indeed true. I\ncreated two files at random using disjoint \"alphabets\" (e.g. one file\nonly contained letters, the other file only contained digits), and\nfound that at a certain size the algorithm would always return >50%\nsimilarity. The size was somewhere between 1MB and 8MB; I can't find\nthe table where I recorded that anymore. So, basically, sufficiently\nlarge files that are sufficiently close in size (since the algorithm\nchecks for size similarity as an optimization) will always be marked\nas a rename or copy. I think we haven't gotten reports of this \"bug\"\nbecause files that large are for all intents and purposes binaries\nthat people likely won't modify. And if they do modify the files,\nthen they'll conflict, but people won't look at the files to resolve\nthe conflict; instead, they'll generate a new \"good\" binary externally\nand then stick it into place. I investigated this just a little bit,\nand even considered turning off rename detection for sufficiently\nlarge files, but sizes aren't available until the tight inner loop and\nadding any extra checking there actually costs enough to offset most\nany benefit. There might have been a way to avoid that, but\nultimately I just dropped the issue and did nothing.\n\n3) It uses a similarity measure that diverges from what researches\nused for MinHash and other fancy algorithms. In particular,\n\n size(A intersect B) / size(A union B) != size(A intersect B) /\nmax(size(A), size(B))\n\nThe formula on the right hand side would mean that if file A is a\nsubset of file B, say the first 10% of file B, then it will be treated\nas 100% similar when most humans would look at it and say it is only\n10% similar. The MinHash definition for similarity measure seems like\nit makes more sense...though if people have been passing numbers like\n\"60%\" to -M, then this change of definition will force them to\nrecalibrate what numbers they pass. I think it'd be really nice to\nuse the MinHash definition and that it might even fix bugs to do so,\nbut I was worried folks might perceive it as a backward incompatible\nchange if they need to recalibrate their numberings.\n\nSo, I ultimately didn't do anything here either...yet. But this is\nthe one that I'd most like to do something about. Are others\nconcerned about the possible need to recalibrate, or is that okay?\nMaybe the performance gains I'm adding elsewhere will offset possible\ngrumpy users?\n\n> Side note: In a very early prototype, the approach to assess\n> similarity between two blobs was very different---there was no\n> attempt to compute \"concise summary\" for each blob, but we just\n> attempted to create delta (as in the pack data) between src and\n> dst blobs and measured how small a delta we can use to transform\n> from src to dst.\n\nInteresting; I didn't know that.\n"},{"id":"416113","messageId":"xmqq5z38bune.fsf@gitster.c.googlers.com","threadId":"55094","inReplyTo":"CABPp-BEgwfv70NRGgyAnHnQBPx4APSyYxNCbvH9F=7WGSj4DLQ@mail.gmail.com","subject":"Re: [PATCH v2 0/2] Optimization batch 6: make full use of exact renames","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-03T23:26:13Z","receivedAt":"2021-02-03T23:27:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> 3) It uses a similarity measure that diverges from what researches\n> used for MinHash and other fancy algorithms. In particular,\n>\n> size(A intersect B) / size(A union B) != size(A intersect B) /\n> max(size(A), size(B))\n>\n> The formula on the right hand side would mean that if file A is a\n> subset of file B, say the first 10% of file B, then it will be treated\n> as 100% similar when most humans would look at it and say it is only\n> 10% similar.\n\nIf you are talking about \"you start from 100 lines file and appended\n900 lines of your own, then you still have 100% of the original\nmaterial remaining in the file\", it is quite deliberate that we used\nit as an indication that the original \"100 lines\" file is a good\ncandidate to have been renamed to the resulting \"1000 lines\" file.\nIt is \"what you have kept from the original\" measure.\n\nOf course, taken to the extreme, this means that rename does not\nhave to be symmetrical. \"diff A B\" may find that the original\n100-line file in A has grown into 1000-line file in B elsewhere, but\n\"diff B A\" or \"diff -R A B\" would not necessarily pair these two\nblobs as matching.\n\n> Maybe the performance gains I'm adding elsewhere will offset possible\n> grumpy users?\n\nUsers, as they are, it would never happen. When they have something\nto complain about, they will, regardless of what else you do.\n\n\n"},{"id":"416114","messageId":"YBszm/s9na3ixUsO@coredump.intra.peff.net","threadId":"55094","inReplyTo":"CABPp-BEgwfv70NRGgyAnHnQBPx4APSyYxNCbvH9F=7WGSj4DLQ@mail.gmail.com","subject":"Re: [PATCH v2 0/2] Optimization batch 6: make full use of exact renames","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-02-03T23:36:59Z","receivedAt":"2021-02-03T23:37:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Feb 03, 2021 at 03:06:26PM -0800, Elijah Newren wrote:\n\n> > In an early attempt, I tried to retire rename_src[j], once\n> > rename_dst[i] has been found to be a \"good enough\" match for it,\n> > from the pool of rename src candidates to find a good match for\n> > rename_dst[k] for i < k, but naive implementation of it would not\n> > work well for obvious reasons---rename_src[j] may match a lot\n> > better with rename_dst[k] than rename_dst[i] but we do not know\n> > that until we try to estimate similarity with rename_dst[k].\n> \n> You may really like the next two series I submit. I have a smarter\n> way to find a \"good enough\" match (comparing to exactly one other file\n> and often finding sufficient similarity), and one that'll make\n> intuitive sense to users.\n\nHere's a really old thread with an approach that may or may not be\nsimilar to what you're thinking of:\n\n https://lore.kernel.org/git/596909b30710220240g665054d8hc40bc5d2234ba9e1@mail.gmail.com/\n\nThough maybe start with this summary message:\n\n https://lore.kernel.org/git/596909b30710220309l1a28e646r9fd47f967dc32574@mail.gmail.com/\n\nI remember experimenting some with it at the time, but never making\nthings faster. It's entirely possible (likely, even) that I was simply\nnot doing it well enough.\n\nIt's also been long enough since I looked at the rename code that I'm\nnot sure how different it is in practice. It still has a quadratic\nmatrix in the end. We basically do a similar strategy of\nrolling-hash-fingerprint-and-see-where-things-collide, but I think we\nmay end up with more work during the quadratic part (again, it's been\na while, so I may just be totally off-base).\n\nI've also wondered if something similar might be helpful for delta\ncompression (which is now done with an O(m*n) sliding window).\n\n-Peff\n"},{"id":"416117","messageId":"CABPp-BHMDi2i=9etq-L=0H=OO7Mbo=RFwMWTNebNB3H9Vbm3+A@mail.gmail.com","threadId":"55094","inReplyTo":"YBszm/s9na3ixUsO@coredump.intra.peff.net","subject":"Re: [PATCH v2 0/2] Optimization batch 6: make full use of exact renames","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-02-04T00:05:32Z","receivedAt":"2021-02-04T00:07:04Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Feb 3, 2021 at 3:37 PM Jeff King wrote:\n>\n> On Wed, Feb 03, 2021 at 03:06:26PM -0800, Elijah Newren wrote:\n>\n> > > In an early attempt, I tried to retire rename_src[j], once\n> > > rename_dst[i] has been found to be a \"good enough\" match for it,\n> > > from the pool of rename src candidates to find a good match for\n> > > rename_dst[k] for i < k, but naive implementation of it would not\n> > > work well for obvious reasons---rename_src[j] may match a lot\n> > > better with rename_dst[k] than rename_dst[i] but we do not know\n> > > that until we try to estimate similarity with rename_dst[k].\n> >\n> > You may really like the next two series I submit. I have a smarter\n> > way to find a \"good enough\" match (comparing to exactly one other file\n> > and often finding sufficient similarity), and one that'll make\n> > intuitive sense to users.\n>\n> Here's a really old thread with an approach that may or may not be\n> similar to what you're thinking of:\n>\n> https://lore.kernel.org/git/596909b30710220240g665054d8hc40bc5d2234ba9e1@mail.gmail.com/\n>\n> Though maybe start with this summary message:\n>\n> https://lore.kernel.org/git/596909b30710220309l1a28e646r9fd47f967dc32574@mail.gmail.com/\n\nInteresting thread; thanks for the link. It's not remotely similar to\nwhat I have done, but a brief glance through it reminds me of the\nideas at https://github.com/gitgitgadget/git/issues/519.\n\n> I remember experimenting some with it at the time, but never making\n> things faster. It's entirely possible (likely, even) that I was simply\n> not doing it well enough.\n>\n> It's also been long enough since I looked at the rename code that I'm\n> not sure how different it is in practice. It still has a quadratic\n> matrix in the end. We basically do a similar strategy of\n> rolling-hash-fingerprint-and-see-where-things-collide, but I think we\n> may end up with more work during the quadratic part (again, it's been\n> a while, so I may just be totally off-base).\n\nI'm not sure if I should spoil the surprise for the patchsets I\nhaven't yet submitted but... when I get done, for the testcases I have\nlooked at, rename detection is no longer the slowest part of\nmerging/rebasing/cherry-picking -- not even when there are tens of\nthousands of renames on one side of history. And I didn't achieve\nthat by making other parts of the code slower.\n\nIf someone can come up with a real-world testcase where rename\ndetection is still really slow in a merge/rebase/cherry-pick with my\nimplemented optimizations, I've got at least one more optimization\nthat I hadn't bothered implementing because everything was fast enough\nfor me already. And the idea you linked above and the ideas in the\ngitgitgadget issue linked above all have more possibilities that are\ncomplementary to what I have done that might help further.\n\n> I've also wondered if something similar might be helpful for delta\n> compression (which is now done with an O(m*n) sliding window).\n"},{"id":"416820","messageId":"xmqqczx4vkus.fsf@gitster.c.googlers.com","threadId":"55094","inReplyTo":"7ae9460d3dba84122c2674b46e4339b9d42bdedd.1612382628.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-13T01:04:43Z","receivedAt":"2021-02-13T01:05:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> +\t\treturn; /* culling incompatbile with break detection */\n\nincompatible.\n\n> \t/*\n> -\t * Calculate how many renames are left (but all the source\n> -\t * files still remain as options for rename/copies!)\n> +\t * Calculate how many renames are left\n> \t */\n\nThis no longer needs to be a multi-line comment, does it?\n\n"},{"id":"416821","messageId":"xmqq8s7svkr9.fsf@gitster.c.googlers.com","threadId":"55094","inReplyTo":"7ae9460d3dba84122c2674b46e4339b9d42bdedd.1612382628.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-02-13T01:06:50Z","receivedAt":"2021-02-13T01:08:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> @@ -578,8 +624,7 @@ void diffcore_rename(struct diff_options *options)\n> \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n> \t\t\tstruct diff_score this_src;\n> \n> -\t\t\tif (one->rename_used && !want_copies)\n> -\t\t\t\tcontinue;\n> +\t\t\tassert(!one->rename_used || want_copies || break_idx);\n\nDoesn't assert becomes a no-op in production builds? Shouldn't this\nbe a BUG() instead?\n"},{"id":"416833","messageId":"CABPp-BEpvx-pHQs3_mK-Wr=ZmZRwLD4vA64LLryU4ehqiCz58w@mail.gmail.com","threadId":"55094","inReplyTo":"xmqqczx4vkus.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-02-13T04:24:31Z","receivedAt":"2021-02-13T04:25:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Feb 12, 2021 at 5:04 PM Junio C Hamano wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > + return; /* culling incompatbile with break detection */\n>\n> incompatible.\n\nThanks.\n\n> > /*\n> > - * Calculate how many renames are left (but all the source\n> > - * files still remain as options for rename/copies!)\n> > + * Calculate how many renames are left\n> > */\n>\n> This no longer needs to be a multi-line comment, does it?\n\nIndeed.\n\nWill fix both.\n"},{"id":"416834","messageId":"CABPp-BHj2k0dDwYB-F=G_aXTemSp5Hu-DK=mrX2pZf3WTH9fQg@mail.gmail.com","threadId":"55094","inReplyTo":"xmqq8s7svkr9.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-02-13T04:43:25Z","receivedAt":"2021-02-13T04:45:31Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Feb 12, 2021 at 5:06 PM Junio C Hamano wrote:\n>\n> \"Elijah Newren via GitGitGadget\" writes:\n>\n> > @@ -578,8 +624,7 @@ void diffcore_rename(struct diff_options *options)\n> > struct diff_filespec *one = rename_src[j].p->one;\n> > struct diff_score this_src;\n> >\n> > - if (one->rename_used && !want_copies)\n> > - continue;\n> > + assert(!one->rename_used || want_copies || break_idx);\n>\n> Doesn't assert becomes a no-op in production builds? Shouldn't this\n> be a BUG() instead?\n\nI guess it depends on the reason for the line. If we're just trying\nto help others understand the code by documenting conditions that are\ntrue (and perhaps help them when they are refactoring), then comments\nlike\n\n /* The following is true at this point: !one->rename_used ||\nwant_copies || break_idx */\n\ncould also be used, but it's kind of verbose. The form\n\n assert(!one->rename_used || want_copies || break_idx);\n\nis shorter, clearer, and is likely to be up-to-date because even if\nmost builds and users turn off assertions, some folks will build and\nrun with assertions on. If it's a refactoring-aid, then the latter\nform is also more likely to help the future developer (who may be\nfuture me).\n\n\nIf, however, the purpose is to check for bad input or worries about\nprogramming logic possibly have edge cases, and we're afraid that such\nconditions might cause severe and hard to debug problems later in the\ncode, then we absolutely would rather use a BUG().\n\nMost of my uses of assert() fall in the former category. I use BUG()\nwhen it's a line meant for the latter category. There are a few that\nperhaps fall in between, where I just have to make a judgement call.\nI'd like to say that I'm more likely to use BUG() for those, but the\nlack of a BUG_ON() does tend to make it pretty annoying to use and\ncertainly discourages it.\n\nGranted, that's the way I look at it. I'm curious if others have a\ndifferent view. It certainly seems like the project likes to use both\nforms nearly equally:\n$ git grep assert\\( origin/master | wc -l\n468\n$ git grep BUG\\( origin/master | wc -l\n506\n\nso I'm curious if there are other factors that make folks pick one or the other.\n"},{"id":"416855","messageId":"pull.842.v3.git.1613288101.gitgitgadget@gmail.com","threadId":"55094","inReplyTo":"pull.842.v2.git.1612382628.gitgitgadget@gmail.com","subject":"[PATCH v3 0/2] Optimization batch 6: make full use of exact renames","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-14T07:34:59Z","receivedAt":"2021-02-14T07:36:05Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series makes full use of exact renames; removing not only a destination\npair, but a source pair as well when an exact rename is found and copy\ndetection is not turned on.\n\nChanges since v2:\n\n * Fix a comment typo, and fix a multi-line comment that didn't need to be a\n multi-line comment\n\nElijah Newren (2):\n diffcore-rename: no point trying to find a match better than exact\n diffcore-rename: filter rename_src list when possible\n\n diffcore-rename.c | 71 ++++++++++++++++++++++++++++++++++++++++-------\n 1 file changed, 61 insertions(+), 10 deletions(-)\n\n\nbase-commit: f0117958910fbc734457a83a9f8ecc3c62463417\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-842%2Fnewren%2Fort-perf-batch-6-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-842/newren/ort-perf-batch-6-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/842\n\nRange-diff vs v2:\n\n 1: 770e894b4abd = 1: a59c1960f614 diffcore-rename: no point trying to find a match better than exact\n 2: 7ae9460d3dba ! 2: dd6595b45640 diffcore-rename: filter rename_src list when possible\n @@ diffcore-rename.c: static int find_renames(struct diff_score *mx, int dst_cnt, i\n +\tif (detecting_copies)\n +\t\treturn; /* nothing to remove */\n +\tif (break_idx)\n -+\t\treturn; /* culling incompatbile with break detection */\n ++\t\treturn; /* culling incompatible with break detection */\n +\n +\t/*\n +\t * Note on reasons why we cull unneeded sources but not destinations:\n @@ diffcore-rename.c: static int find_renames(struct diff_score *mx, int dst_cnt, i\n {\n \tint detect_rename = options->detect_rename;\n @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)\n + \tif (minimum_score == MAX_SCORE)\n \t\tgoto cleanup;\n \n - \t/*\n +-\t/*\n -\t * Calculate how many renames are left (but all the source\n -\t * files still remain as options for rename/copies!)\n -+\t * Calculate how many renames are left\n - \t */\n +-\t */\n ++\t/* Calculate how many renames are left */\n \tnum_destinations = (rename_dst_nr - rename_count);\n +\tremove_unneeded_paths_from_src(want_copies);\n \tnum_sources = rename_src_nr;\n\n-- \ngitgitgadget\n"},{"id":"416856","messageId":"a59c1960f6141e71bba3492e20111af458741c38.1613288101.git.gitgitgadget@gmail.com","threadId":"55094","inReplyTo":"pull.842.v3.git.1613288101.gitgitgadget@gmail.com","subject":"[PATCH v3 1/2] diffcore-rename: no point trying to find a match better than exact","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-14T07:35:00Z","receivedAt":"2021-02-14T07:36:05Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ndiffcore_rename() had some code to avoid having destination paths that\nalready had an exact rename detected from being re-checked for other\nrenames. Source paths, however, were re-checked because we wanted to\nallow the possibility of detecting copies. But if copy detection isn't\nturned on, then this merely amounts to attempting to find a\nbetter-than-exact match, which naturally ends up being an expensive\nno-op. In particular, copy detection is never turned on by the merge\nmachinery.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 14.263 s ± 0.053 s 14.119 s ± 0.101 s\n mega-renames: 5504.231 s ± 5.150 s 1802.044 s ± 0.828 s\n just-one-mega: 158.534 s ± 0.498 s 51.391 s ± 0.028 s\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 20 ++++++++++++++------\n 1 file changed, 14 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 8fe6c9384bcb..8b118628b4ef 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -463,9 +463,11 @@ void diffcore_rename(struct diff_options *options)\n \tstruct diff_score *mx;\n \tint i, j, rename_count, skip_unmodified = 0;\n \tint num_destinations, dst_cnt;\n+\tint num_sources, want_copies;\n \tstruct progress *progress = NULL;\n \n \ttrace2_region_enter(\"diff\", \"setup\", options->repo);\n+\twant_copies = (detect_rename == DIFF_DETECT_COPY);\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -502,7 +504,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\tp->one->rename_used++;\n \t\t\tregister_rename_src(p);\n \t\t}\n-\t\telse if (detect_rename == DIFF_DETECT_COPY) {\n+\t\telse if (want_copies) {\n \t\t\t/*\n \t\t\t * Increment the \"rename_used\" score by\n \t\t\t * one, to indicate ourselves as a user.\n@@ -532,12 +534,15 @@ void diffcore_rename(struct diff_options *options)\n \t * files still remain as options for rename/copies!)\n \t */\n \tnum_destinations = (rename_dst_nr - rename_count);\n+\tnum_sources = rename_src_nr;\n+\tif (!want_copies)\n+\t\tnum_sources -= rename_count;\n \n \t/* All done? */\n-\tif (!num_destinations)\n+\tif (!num_destinations || !num_sources)\n \t\tgoto cleanup;\n \n-\tswitch (too_many_rename_candidates(num_destinations, rename_src_nr,\n+\tswitch (too_many_rename_candidates(num_destinations, num_sources,\n \t\t\t\t\t options)) {\n \tcase 1:\n \t\tgoto cleanup;\n@@ -553,7 +558,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)num_destinations * (uint64_t)rename_src_nr);\n+\t\t\t\t(uint64_t)num_destinations * (uint64_t)num_sources);\n \t}\n \n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_destinations),\n@@ -573,6 +578,9 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n \n+\t\t\tif (one->rename_used && !want_copies)\n+\t\t\t\tcontinue;\n+\n \t\t\tif (skip_unmodified &&\n \t\t\t diff_unmodified_pair(rename_src[j].p))\n \t\t\t\tcontinue;\n@@ -594,7 +602,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t}\n \t\tdst_cnt++;\n \t\tdisplay_progress(progress,\n-\t\t\t\t (uint64_t)dst_cnt * (uint64_t)rename_src_nr);\n+\t\t\t\t (uint64_t)dst_cnt * (uint64_t)num_sources);\n \t}\n \tstop_progress(&progress);\n \n@@ -602,7 +610,7 @@ void diffcore_rename(struct diff_options *options)\n \tSTABLE_QSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);\n \n \trename_count += find_renames(mx, dst_cnt, minimum_score, 0);\n-\tif (detect_rename == DIFF_DETECT_COPY)\n+\tif (want_copies)\n \t\trename_count += find_renames(mx, dst_cnt, minimum_score, 1);\n \tfree(mx);\n \ttrace2_region_leave(\"diff\", \"inexact renames\", options->repo);\n-- \ngitgitgadget\n\n"},{"id":"416857","messageId":"dd6595b45640ee9894293e8b729ef9a254564a49.1613288101.git.gitgitgadget@gmail.com","threadId":"55094","inReplyTo":"pull.842.v3.git.1613288101.gitgitgadget@gmail.com","subject":"[PATCH v3 2/2] diffcore-rename: filter rename_src list when possible","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-14T07:35:01Z","receivedAt":"2021-02-14T07:36:05Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nWe have to look at each entry in rename_src a total of rename_dst_nr\ntimes. When we're not detecting copies, any exact renames or ignorable\nrename paths will just be skipped over. While checking that these can\nbe skipped over is a relatively cheap check, it's still a waste of time\nto do that check more than once, let alone rename_dst_nr times. When\nrename_src_nr is a few thousand times bigger than the number of relevant\nsources (such as when cherry-picking a commit that only touched a\nhandful of files, but from a side of history that has different names\nfor some high level directories), this time can add up.\n\nFirst make an initial pass over the rename_src array and move all the\nrelevant entries to the front, so that we can iterate over just those\nrelevant entries.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 14.119 s ± 0.101 s 13.815 s ± 0.062 s\n mega-renames: 1802.044 s ± 0.828 s 1799.937 s ± 0.493 s\n just-one-mega: 51.391 s ± 0.028 s 51.289 s ± 0.019 s\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 59 ++++++++++++++++++++++++++++++++++++++++-------\n 1 file changed, 51 insertions(+), 8 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 8b118628b4ef..6fd0c4a2f485 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -454,6 +454,54 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i\n \treturn count;\n }\n \n+static void remove_unneeded_paths_from_src(int detecting_copies)\n+{\n+\tint i, new_num_src;\n+\n+\tif (detecting_copies)\n+\t\treturn; /* nothing to remove */\n+\tif (break_idx)\n+\t\treturn; /* culling incompatible with break detection */\n+\n+\t/*\n+\t * Note on reasons why we cull unneeded sources but not destinations:\n+\t * 1) Pairings are stored in rename_dst (not rename_src), which we\n+\t * need to keep around. So, we just can't cull rename_dst even\n+\t * if we wanted to. But doing so wouldn't help because...\n+\t *\n+\t * 2) There is a matrix pairwise comparison that follows the\n+\t * \"Performing inexact rename detection\" progress message.\n+\t * Iterating over the destinations is done in the outer loop,\n+\t * hence we only iterate over each of those once and we can\n+\t * easily skip the outer loop early if the destination isn't\n+\t * relevant. That's only one check per destination path to\n+\t * skip.\n+\t *\n+\t * By contrast, the sources are iterated in the inner loop; if\n+\t * we check whether a source can be skipped, then we'll be\n+\t * checking it N separate times, once for each destination.\n+\t * We don't want to have to iterate over known-not-needed\n+\t * sources N times each, so avoid that by removing the sources\n+\t * from rename_src here.\n+\t */\n+\tfor (i = 0, new_num_src = 0; i < rename_src_nr; i++) {\n+\t\t/*\n+\t\t * renames are stored in rename_dst, so if a rename has\n+\t\t * already been detected using this source, we can just\n+\t\t * remove the source knowing rename_dst has its info.\n+\t\t */\n+\t\tif (rename_src[i].p->one->rename_used)\n+\t\t\tcontinue;\n+\n+\t\tif (new_num_src < i)\n+\t\t\tmemcpy(&rename_src[new_num_src], &rename_src[i],\n+\t\t\t sizeof(struct diff_rename_src));\n+\t\tnew_num_src++;\n+\t}\n+\n+\trename_src_nr = new_num_src;\n+}\n+\n void diffcore_rename(struct diff_options *options)\n {\n \tint detect_rename = options->detect_rename;\n@@ -529,14 +577,10 @@ void diffcore_rename(struct diff_options *options)\n \tif (minimum_score == MAX_SCORE)\n \t\tgoto cleanup;\n \n-\t/*\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+\t/* Calculate how many renames are left */\n \tnum_destinations = (rename_dst_nr - rename_count);\n+\tremove_unneeded_paths_from_src(want_copies);\n \tnum_sources = rename_src_nr;\n-\tif (!want_copies)\n-\t\tnum_sources -= rename_count;\n \n \t/* All done? */\n \tif (!num_destinations || !num_sources)\n@@ -578,8 +622,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tstruct diff_filespec *one = rename_src[j].p->one;\n \t\t\tstruct diff_score this_src;\n \n-\t\t\tif (one->rename_used && !want_copies)\n-\t\t\t\tcontinue;\n+\t\t\tassert(!one->rename_used || want_copies || break_idx);\n \n \t\t\tif (skip_unmodified &&\n \t\t\t diff_unmodified_pair(rename_src[j].p))\n-- \ngitgitgadget\n"}]}