{"thread":{"id":"55231","subject":"[PATCH 1/8] diffcore-rename: enable filtering possible rename sources","startedAt":"2021-02-28T03:59:33Z","lastAt":"2021-03-15T17:12:07Z","messageCount":39,"participants":["Elijah Newren via GitGitGadget","Elijah Newren","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"417954","messageId":"064fa5de1e20ada3d9b2225d8561f4f6429bdf02.1614484707.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"[PATCH 1/8] diffcore-rename: enable filtering possible rename sources","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-28T03:58:19Z","receivedAt":"2021-02-28T03:59:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd the ability to diffcore_rename_extended() to allow external callers\nto declare that they only need renames detected for a subset of source\nfiles, and use that information to skip detecting renames for them.\n\nThere are two important pieces to this optimization that may not be\nobvious at first glance:\n\n * We do not require callers to just filter the filepairs out\n to remove the non-relevant sources, because exact rename detection\n is fast and when it finds a match it can remove both a source and a\n destination whereas the relevant_sources filter can only remove a\n source.\n\n * We need to filter out the source pairs in a preliminary pass instead\n of adding a\n strset_contains(relevant_sources, one->path)\n check within the nested matrix loop. The reason for that is if we\n have 30k renames, doing 30k * 30k = 900M strset_contains() calls\n becomes extraordinarily expensive and defeats the performance gains\n from this change; we only want to do 30k such calls instead.\n\nIf callers pass NULL for relevant_sources, that is special cases to\ntreat all sources as relevant. Since all callers currently pass NULL,\nthis optimization does not yet have any effect. Subsequent commits will\nhave merge-ort compute a set of relevant_sources to restrict which\nsources we detect renames for, and have merge-ort pass that set of\nrelevant_sources to diffcore_rename_extended().\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 26 +++++++++++++++++++-------\n diffcore.h | 1 +\n merge-ort.c | 1 +\n 3 files changed, 21 insertions(+), 7 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1fe902ed2af0..7f6115fd9018 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -991,11 +991,12 @@ static int find_renames(struct diff_score *mx,\n \treturn count;\n }\n \n-static void remove_unneeded_paths_from_src(int detecting_copies)\n+static void remove_unneeded_paths_from_src(int detecting_copies,\n+\t\t\t\t\t struct strset *interesting)\n {\n \tint i, new_num_src;\n \n-\tif (detecting_copies)\n+\tif (detecting_copies && !interesting)\n \t\treturn; /* nothing to remove */\n \tif (break_idx)\n \t\treturn; /* culling incompatible with break detection */\n@@ -1022,12 +1023,18 @@ static void remove_unneeded_paths_from_src(int detecting_copies)\n \t * from rename_src here.\n \t */\n \tfor (i = 0, new_num_src = 0; i < rename_src_nr; i++) {\n+\t\tstruct diff_filespec *one = rename_src[i].p->one;\n+\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\tif (!detecting_copies && one->rename_used)\n+\t\t\tcontinue;\n+\n+\t\t/* If we don't care about the source path, skip it */\n+\t\tif (interesting && !strset_contains(interesting, one->path))\n \t\t\tcontinue;\n \n \t\tif (new_num_src < i)\n@@ -1040,6 +1047,7 @@ static void remove_unneeded_paths_from_src(int detecting_copies)\n }\n \n void diffcore_rename_extended(struct diff_options *options,\n+\t\t\t struct strset *relevant_sources,\n \t\t\t struct strset *dirs_removed,\n \t\t\t struct strmap *dir_rename_count)\n {\n@@ -1060,6 +1068,8 @@ void diffcore_rename_extended(struct diff_options *options,\n \twant_copies = (detect_rename == DIFF_DETECT_COPY);\n \tif (dirs_removed && (break_idx || want_copies))\n \t\tBUG(\"dirs_removed incompatible with break/copy detection\");\n+\tif (break_idx && relevant_sources)\n+\t\tBUG(\"break detection incompatible with source specification\");\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -1127,9 +1137,10 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t/*\n \t\t * Cull sources:\n \t\t * - remove ones corresponding to exact renames\n+\t\t * - remove ones not found in relevant_sources\n \t\t */\n \t\ttrace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n-\t\tremove_unneeded_paths_from_src(want_copies);\n+\t\tremove_unneeded_paths_from_src(want_copies, relevant_sources);\n \t\ttrace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n \t} else {\n \t\t/* Determine minimum score to match basenames */\n@@ -1148,7 +1159,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t * - remove ones involved in renames (found via exact match)\n \t\t */\n \t\ttrace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n-\t\tremove_unneeded_paths_from_src(want_copies);\n+\t\tremove_unneeded_paths_from_src(want_copies, NULL);\n \t\ttrace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n \n \t\t/* Preparation for basename-driven matching. */\n@@ -1167,9 +1178,10 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t/*\n \t\t * Cull sources, again:\n \t\t * - remove ones involved in renames (found via basenames)\n+\t\t * - remove ones not found in relevant_sources\n \t\t */\n \t\ttrace2_region_enter(\"diff\", \"cull basename\", options->repo);\n-\t\tremove_unneeded_paths_from_src(want_copies);\n+\t\tremove_unneeded_paths_from_src(want_copies, relevant_sources);\n \t\ttrace2_region_leave(\"diff\", \"cull basename\", options->repo);\n \t}\n \n@@ -1342,5 +1354,5 @@ void diffcore_rename_extended(struct diff_options *options,\n \n void diffcore_rename(struct diff_options *options)\n {\n-\tdiffcore_rename_extended(options, NULL, NULL);\n+\tdiffcore_rename_extended(options, NULL, NULL, NULL);\n }\ndiff --git a/diffcore.h b/diffcore.h\nindex c6ba64abd198..737c93a6cc79 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -166,6 +166,7 @@ void partial_clear_dir_rename_count(struct strmap *dir_rename_count);\n void diffcore_break(struct repository *, int);\n void diffcore_rename(struct diff_options *);\n void diffcore_rename_extended(struct diff_options *options,\n+\t\t\t struct strset *relevant_sources,\n \t\t\t struct strset *dirs_removed,\n \t\t\t struct strmap *dir_rename_count);\n void diffcore_merge_broken(void);\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 467404cc0a35..aba0b9fa54c3 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2029,6 +2029,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_queued_diff = renames->pairs[side_index];\n \ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiffcore_rename_extended(&diff_opts,\n+\t\t\t\t NULL,\n \t\t\t\t &renames->dirs_removed[side_index],\n \t\t\t\t &renames->dir_rename_count[side_index]);\n \ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n-- \ngitgitgadget\n\n"},{"id":"417955","messageId":"pull.845.git.1614484707.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":null,"subject":"[PATCH 0/8] Optimization batch 9: avoid detecting irrelevant renames","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-28T03:58:18Z","receivedAt":"2021-02-28T03:59:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends textually on ort-perf-batch-8, but semantically it's\nalmost completely unrelated and can be reviewed without any familiarity with\nany of the previous patch series.\n\n=== Basic Optimization idea ===\n\nThis series determines paths which meet special cases where detection of\nrenames is irrelevant, where the irrelevance is due to the fact that the\nmerge machinery will arrive at the same result regardless of whether a\nrename is detected for any of those paths. This series represents\n\"Optimization #2\" from my Git Merge 2020 talk[1], though this series has\nsome improvements on the optimization relative to what I had at that time.\n\nThe basic idea here is that if side A of history:\n\n * only modifies/adds/deletes a few files\n * adds new files to few if any of the directories that side B deleted or\n renamed\n\nthen when we do rename detection on side B we can avoid even looking at most\n(and perhaps even all) paths that side B deleted. Since commits being\nrebased or cherry-picked tend to only modify a few files, this optimization\ntends to be particularly effective for rebases and cherry-picks.\n\nBasing rename detection on what the other side of history did to a file\nmeans that extra information needs to be fed from merge-ort to\ndiffcore-rename in order to take advantage of such an optimization.\n\n=== Comparison to previous series ===\n\nThis series differs from my two previous optimizations[2][3] (focusing on\nbasename-guided rename detection) in two important aspects:\n\n * there are no behavioral changes (there is no heuristic involved)\n\n * this optimization is merge specific (it does not help the diff/status/log\n family of commands, just merge/rebase/cherry-pick and such)\n\n=== Results ===\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28), the\nchanges in just this series improves the performance as follows:\n\n Before Series After Series\nno-renames: 12.596 s ± 0.061 s 5.680 s ± 0.096 s\nmega-renames: 130.465 s ± 0.259 s 13.812 s ± 0.162 s\njust-one-mega: 3.958 s ± 0.010 s 506.0 ms ± 3.9 ms\n\n\nHowever, interestingly, if we had ignored the basename-guided rename\ndetection optimizations[2][3], then this optimization series would have\nimproved the performance as follows:\n\n Before Basename Series After Just This Series\nno-renames: 13.815 s ± 0.062 s 5.728 s ± 0.104 s\nmega-renames: 1799.937 s ± 0.493 s 18.213 s ± 0.139 s\njust-one-mega 51.289 s ± 0.019 s 891.9 ms ± 7.0 ms\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=== Competition between optimizations ===\n\nWe now have three major rename-related optimizations:\n\n * exact rename detection\n * basename-guided rename detection[2][3]\n * skip-because-unnecessary (this series)\n\nIt is possible for all three to potentially apply for specific paths (they\ndo for the majority of renamed paths in our testcases), but we cannot use\nmore than one for any given path. It turns out that the priority we give\neach optimization is very important and can drastically affect performance.\nWe get best results by prioritizing them as follows:\n\n 1. exact rename detection\n 2. skip-because-unnecessary\n 3. basename-guided rename detection\n\nThe third-to-last patch of this series also discusses this ordering and\nanother minor variant of the skip-because-unnecessary optimization that was\ntried (and resulted in less effective performance gains than reported here),\nas well as some of the preparatory work over the past few years that this\nseries relies on in order to enable this optimization.\n\n=== Near optimal? ===\n\nYou may remember that there was a row labelled \"everything else\" from the\ncommit message of 557ac0350d that represented the maximum possible speed-up\nfrom accelerating rename detection alone; as stated in that commit, those\nrows represented how fast the code could be if we had somehow infinitely\nparallelized the inexact rename detection. However, if you compare those\n\"maximum speedup\" numbers to what we have above, you'll note that the\ninfinitely parallelized inexact rename detection would have been slightly\nslower than the results we have now achieved. (The reason this is possible,\ndespite the fact that we still spend time in rename detection after our\noptimizations, is because we implemented two optimizations outside of\ndiffcore_rename() along the way.) However, this good news does also come\nwith a downside -- it means that our remaining optimization potential is\nsomewhat limited, and subsequent optimization series will have to fight for\nmuch smaller gains.\n\n[1]\nhttps://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf\n[2]\nhttps://lore.kernel.org/git/pull.843.git.1612651937.gitgitgadget@gmail.com/\n[3]\nhttps://lore.kernel.org/git/pull.844.git.1613289544.gitgitgadget@gmail.com/\n\nElijah Newren (8):\n diffcore-rename: enable filtering possible rename sources\n merge-ort: precompute subset of sources for which we need rename\n detection\n merge-ort: add data structures for an alternate tree traversal\n merge-ort: introduce wrappers for alternate tree traversal\n merge-ort: precompute whether directory rename detection is needed\n merge-ort: use relevant_sources to filter possible rename sources\n merge-ort: skip rename detection entirely if possible\n diffcore-rename: avoid doing basename comparisons for irrelevant\n sources\n\n diffcore-rename.c | 63 ++++++++++---\n diffcore.h | 1 +\n merge-ort.c | 236 +++++++++++++++++++++++++++++++++++++++++++++-\n 3 files changed, 285 insertions(+), 15 deletions(-)\n\n\nbase-commit: 4be565c472088d4144063b736308bf2a57331f45\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-845%2Fnewren%2Fort-perf-batch-9-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-845/newren/ort-perf-batch-9-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/845\n-- \ngitgitgadget\n"},{"id":"417956","messageId":"042ce66011efabcf15be697816d9a97b76877fbf.1614484707.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"[PATCH 3/8] merge-ort: add data structures for an alternate tree traversal","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-28T03:58:21Z","receivedAt":"2021-02-28T03:59:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn order to determine whether directory rename detection is needed, we\nas a pre-requisite need a way to traverse through all the files in a\ngiven tree before visiting any directories within that tree.\ntraverse_trees() only iterates through the entries in the order they\nappear, so add some data structures that will store all the entries as\nwe iterate through them in traverse_trees(), which will allow us to\nre-traverse them in our desired order.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 26 ++++++++++++++++++++++++++\n 1 file changed, 26 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 83aa4c08121f..d49cfa8b030b 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -51,6 +51,12 @@ enum merge_side {\n \tMERGE_SIDE2 = 2\n };\n \n+struct traversal_callback_data {\n+\tunsigned long mask;\n+\tunsigned long dirmask;\n+\tstruct name_entry names[3];\n+};\n+\n struct rename_info {\n \t/*\n \t * All variables that are arrays of size 3 correspond to data tracked\n@@ -102,6 +108,22 @@ struct rename_info {\n \t */\n \tstruct strset relevant_sources[3];\n \n+\t/*\n+\t * callback_data_*: supporting data structures for alternate traversal\n+\t *\n+\t * We sometimes need to be able to traverse through all the files\n+\t * in a given tree before all immediate subdirectories within that\n+\t * tree. Since traverse_trees() doesn't do that naturally, we have\n+\t * a traverse_trees_wrapper() that stores any immediate\n+\t * subdirectories while traversing files, then traverses the\n+\t * immediate subdirectories later. These callback_data* variables\n+\t * store the information for the subdirectories so that we can do\n+\t * that traversal order.\n+\t */\n+\tstruct traversal_callback_data *callback_data;\n+\tint callback_data_nr, callback_data_alloc;\n+\tchar *callback_data_traverse_path;\n+\n \t/*\n \t * needed_limit: value needed for inexact rename detection to run\n \t *\n@@ -396,6 +418,10 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\t}\n \t\tstrmap_clear(&opti->output, 0);\n \t}\n+\n+\t/* Clean out callback_data as well. */\n+\tFREE_AND_NULL(renames->callback_data);\n+\trenames->callback_data_nr = renames->callback_data_alloc = 0;\n }\n \n static int err(struct merge_options *opt, const char *err, ...)\n-- \ngitgitgadget\n\n"},{"id":"417957","messageId":"69b42a41e83a006408b6f875dd17a0714be5b9ad.1614484707.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"[PATCH 2/8] merge-ort: precompute subset of sources for which we need rename detection","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-28T03:58:20Z","receivedAt":"2021-02-28T03:59:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nrename detection works by trying to pair all file deletions (or\n\"sources\") with all file additions (or \"destinations\"), checking\nsimilarity, and then marking the sufficiently similar ones as renames.\nThis can be expensive if there are many sources and destinations on a\ngiven side of history as it results in an N x M comparison matrix.\nHowever, there are many cases where we can compute in advance that\ndetecting renames for some of the sources provides no useful information\nand thus that we can exclude those sources from the matrix.\n\nTo see why, first note that the merge machinery uses detected renames in\ntwo ways:\n\n * directory rename detection: when one side of history renames a\n directory, and the other side of history adds new files to that\n directory, we want to be able to warn the user about the need to\n chose whether those new files stay in the old directory or move\n to the new one.\n\n * three-way content merging: in order to do three-way content merging\n of files, we need three different file versions. If one side of\n history renamed a file, then some of the content for the file is\n found under a different path than in the merge base or on the\n other side of history.\n\nThis commit concentrates just on the three-way content merging; it will\npunt and mark all sources as needed for directory rename detection, and\nleave it to future commits to narrow that down more.\n\nThe point of three-way content merging is to reconcile changes made on\n*both* sides of history. What if the file wasn't modified on both\nsides? There are two possibilities:\n\n * If it wasn't modified on the renamed side:\n -> then we get to do exact rename detection, which is cheap.\n\n * If it wasn't modified on the unrenamed side:\n -> then detection of a rename for that source file is irrelevant\n\nThat latter claim might be surprising at first, so let's walk through a\ncase to show why rename detection for that source file is irrelevant.\nLet's use two filenames, old.c & new.c, with the following abbreviated\nobject ids (and where the value '000000' is used to denote that the file\nis missing in that commit):\n\n old.c new.c\n MERGE_BASE: 01d01d 000000\n MERGE_SIDE1: 01d01d 000000\n MERGE_SIDE2: 000000 5e1ec7\n\nIf the rename *isn't* detected:\n then old.c looks like it was unmodified on one side and deleted on\n the other and should thus be removed. new.c looks like a new file we\n should keep as-is.\n\nIf the rename *is* detected:\n then a three-way content merge is done. Since the version of the\n file in MERGE_BASE and MERGE_SIDE1 are identical, the three-way merge\n will produce exactly the version of the file whose abbreviated\n object id is 5e1ec7. It will record that file at the path new.c,\n while removing old.c from the directory.\n\nNote that these two results are identical -- a single file named 'new.c'\nwith object id 5e1ec7. In other words, it doesn't matter if the rename\nis detected in the case where the file is unmodified on the unrenamed\nside.\n\nUse this information to compute whether we need rename detection for\neach source created in add_pair().\n\nIt's probably worth noting that there used to be a few other edge or\ncorner cases besides three-way content merges and directory rename\ndetection where lack of rename detection could have affected the result,\nbut those cases actually highlighted where conflict resolution methods\nwere not consistent with each other. Fixing those inconsistencies were\nthus critically important to enabling this optimization. That work\ninvolved the following:\n\n * bringing consistency to add/add, rename/add, and rename/rename\n conflict types, as done back in the topic merged at commit\n ac193e0e0a (\"Merge branch 'en/merge-path-collision'\", 2019-01-04),\n and further extended in commits 2a7c16c980 (\"t6422, t6426: be more\n flexible for add/add conflicts involving renames\", 2020-08-10) and\n e8eb99d4a6 (\"t642[23]: be more flexible for add/add conflicts\n involving pair renames\", 2020-08-10)\n\n * making rename/delete more consistent with modify/delete\n as done in commits 1f3c9ba707 (\"t6425: be more flexible with\n rename/delete conflict messages\", 2020-08-10) and 727c75b23f\n (\"t6404, t6423: expect improved rename/delete handling in ort\n backend\", 2020-10-26)\n\nSince the set of relevant_sources we compute has not yet been narrowed\ndown for directory rename detection, we do not pass it to\ndiffcore_rename_extended() yet. That will be done after subsequent\ncommits narrow down the list of relevant_sources needed for directory\nrename detection reasons.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 35 ++++++++++++++++++++++++++++++++---\n 1 file changed, 32 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex aba0b9fa54c3..83aa4c08121f 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -88,6 +88,20 @@ struct rename_info {\n \t */\n \tstruct strmap dir_renames[3];\n \n+\t/*\n+\t * relevant_sources: deleted paths for which we need rename detection\n+\t *\n+\t * relevant_sources is a set of deleted paths on each side of\n+\t * history for which we need rename detection. If a path is deleted\n+\t * on one side of history, we need to detect if it is part of a\n+\t * rename if either\n+\t * * we need to detect renames for an ancestor directory\n+\t * * the file is modified/deleted on the other side of history\n+\t * If neither of those are true, we can skip rename detection for\n+\t * that path.\n+\t */\n+\tstruct strset relevant_sources[3];\n+\n \t/*\n \t * needed_limit: value needed for inexact rename detection to run\n \t *\n@@ -358,6 +372,8 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\t\tstrmap_clear(&renames->dir_rename_count[i], 1);\n \n \t\tstrmap_func(&renames->dir_renames[i], 0);\n+\n+\t\tstrset_func(&renames->relevant_sources[i]);\n \t}\n \n \tif (!reinitialize) {\n@@ -533,12 +549,21 @@ static void add_pair(struct merge_options *opt,\n \t\t struct name_entry *names,\n \t\t const char *pathname,\n \t\t unsigned side,\n-\t\t unsigned is_add /* if false, is_delete */)\n+\t\t unsigned is_add /* if false, is_delete */,\n+\t\t unsigned match_mask)\n {\n \tstruct diff_filespec *one, *two;\n \tstruct rename_info *renames = &opt->priv->renames;\n \tint names_idx = is_add ? side : 0;\n \n+\tif (!is_add) {\n+\t\tunsigned content_relevant = (match_mask == 0);\n+\t\tunsigned location_relevant = 1; /* FIXME: compute this */\n+\n+\t\tif (content_relevant || location_relevant)\n+\t\t\tstrset_add(&renames->relevant_sources[side], pathname);\n+\t}\n+\n \tone = alloc_filespec(pathname);\n \ttwo = alloc_filespec(pathname);\n \tfill_filespec(is_add ? two : one,\n@@ -575,11 +600,13 @@ static void collect_rename_info(struct merge_options *opt,\n \n \t\t/* Check for deletion on side */\n \t\tif ((filemask & 1) && !(filemask & side_mask))\n-\t\t\tadd_pair(opt, names, fullname, side, 0 /* delete */);\n+\t\t\tadd_pair(opt, names, fullname, side, 0 /* delete */,\n+\t\t\t\t match_mask & filemask);\n \n \t\t/* Check for addition on side */\n \t\tif (!(filemask & 1) && (filemask & side_mask))\n-\t\t\tadd_pair(opt, names, fullname, side, 1 /* add */);\n+\t\t\tadd_pair(opt, names, fullname, side, 1 /* add */,\n+\t\t\t\t match_mask & filemask);\n \t}\n }\n \n@@ -3228,6 +3255,8 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t\t\t\t\t NULL, 1);\n \t\tstrmap_init_with_options(&renames->dir_renames[i],\n \t\t\t\t\t NULL, 0);\n+\t\tstrset_init_with_options(&renames->relevant_sources[i],\n+\t\t\t\t\t NULL, 0);\n \t}\n \n \t/*\n-- \ngitgitgadget\n\n"},{"id":"417958","messageId":"7673e4c23bbb4eb1ee625467a6515ff52145e79c.1614484707.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"[PATCH 4/8] merge-ort: introduce wrappers for alternate tree traversal","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-28T03:58:22Z","receivedAt":"2021-02-28T03:59:40Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd traverse_trees_wrapper() and traverse_trees_wrapper_callback()\nfunctions. The former runs traverse_trees() with info->fn set to\ntraverse_trees_wrapper_callback, in order to simply save all the entries\nwithout processing or recursing into any of them. This step allows\nextra computation to be done (e.g. checking some condition across all\nfiles) that can be used later. Then, after that is completed, it\niterates over all the saved entries and calls the original info->fn\ncallback with the saved data.\n\nCurrently, this does nothing more than marginally slowing down the tree\ntraversal since we do not take advantage of the opportunity to compute\nanything special in traverse_trees_wrapper_callback(), and thus the real\ncallback will be called identically as it would have been without this\nextra wrapper. However, a subsequent commit will add some special\ncomputation of some values that the real callback will be able to use.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 72 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 72 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex d49cfa8b030b..bd2b93a31141 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -512,6 +512,78 @@ static char *unique_path(struct strmap *existing_paths,\n \n /*** Function Grouping: functions related to collect_merge_info() ***/\n \n+static int traverse_trees_wrapper_callback(int n,\n+\t\t\t\t\t unsigned long mask,\n+\t\t\t\t\t unsigned long dirmask,\n+\t\t\t\t\t struct name_entry *names,\n+\t\t\t\t\t struct traverse_info *info)\n+{\n+\tstruct merge_options *opt = info->data;\n+\tstruct rename_info *renames = &opt->priv->renames;\n+\n+\tassert(n==3);\n+\n+\tif (!renames->callback_data_traverse_path)\n+\t\trenames->callback_data_traverse_path = xstrdup(info->traverse_path);\n+\n+\tALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,\n+\t\t renames->callback_data_alloc);\n+\trenames->callback_data[renames->callback_data_nr].mask = mask;\n+\trenames->callback_data[renames->callback_data_nr].dirmask = dirmask;\n+\tCOPY_ARRAY(renames->callback_data[renames->callback_data_nr].names,\n+\t\t names, 3);\n+\trenames->callback_data_nr++;\n+\n+\treturn mask;\n+}\n+\n+/*\n+ * Much like traverse_trees(), BUT:\n+ * - read all the tree entries FIRST, saving them\n+ * - note that the above step provides an opportunity to compute necessary\n+ * additional details before the \"real\" traversal\n+ * - loop through the saved entries and call the original callback on them\n+ */\n+MAYBE_UNUSED\n+static int traverse_trees_wrapper(struct index_state *istate,\n+\t\t\t\t int n,\n+\t\t\t\t struct tree_desc *t,\n+\t\t\t\t struct traverse_info *info)\n+{\n+\tint ret, i, old_offset;\n+\ttraverse_callback_t old_fn;\n+\tchar *old_callback_data_traverse_path;\n+\tstruct merge_options *opt = info->data;\n+\tstruct rename_info *renames = &opt->priv->renames;\n+\n+\told_callback_data_traverse_path = renames->callback_data_traverse_path;\n+\told_fn = info->fn;\n+\told_offset = renames->callback_data_nr;\n+\n+\trenames->callback_data_traverse_path = NULL;\n+\tinfo->fn = traverse_trees_wrapper_callback;\n+\tret = traverse_trees(istate, n, t, info);\n+\tif (ret < 0)\n+\t\treturn ret;\n+\n+\tinfo->traverse_path = renames->callback_data_traverse_path;\n+\tinfo->fn = old_fn;\n+\tfor (i = old_offset; i < renames->callback_data_nr; ++i) {\n+\t\tinfo->fn(n,\n+\t\t\t renames->callback_data[i].mask,\n+\t\t\t renames->callback_data[i].dirmask,\n+\t\t\t renames->callback_data[i].names,\n+\t\t\t info);\n+\n+\t}\n+\n+\trenames->callback_data_nr = old_offset;\n+\tfree(renames->callback_data_traverse_path);\n+\trenames->callback_data_traverse_path = old_callback_data_traverse_path;\n+\tinfo->traverse_path = NULL;\n+\treturn 0;\n+}\n+\n static void setup_path_info(struct merge_options *opt,\n \t\t\t struct string_list_item *result,\n \t\t\t const char *current_dir_name,\n-- \ngitgitgadget\n\n"},{"id":"417959","messageId":"8dbf0a4525453078cf87ee9149d89227d18c96f0.1614484707.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"[PATCH 5/8] merge-ort: precompute whether directory rename detection is needed","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-28T03:58:23Z","receivedAt":"2021-02-28T03:59:57Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe point of directory rename detection is that if one side of history\nrenames a directory, and the other side adds new files under the old\ndirectory, then the merge can move those new files into the new\ndirectory. This leads to the following important observation:\n\n * If the other side does not add any new files under the old\n directory, we do not need to detect any renames for that directory.\n\nSimilarly, directory rename detection had an important requirement:\n\n * If a directory still exists on one side of history, it has not been\n renamed on that side of history. (See section 4 of t6423 or\n Documentation/technical/directory-rename-detection.txt for more\n details).\n\nUsing these two bits of information, we note that directory rename\ndetection is only needed in cases where (1) directories exist in the\nmerge base and on one side of history (i.e. dirmask == 3 or dirmask ==\n5), and (2) where there is some new file added to that directory on the\nside where it still exists (thus where the file has filemask == 2 or\nfilemask == 4, respectively). This has to be done in two steps, because\nwe have the dirmask when we are first considering the directory, and\nwon't get the filemasks for the files within it until we recurse into\nthat directory. So, we save\n dir_rename_mask = dirmask - 1\nwhen we hit a directory that is missing on one side, and then later look\nfor cases of\n filemask == dir_rename_mask\n\nOne final note is that as soon as we hit a directory that needs\ndirectory rename detection, we will need to detect renames in all\nsubdirectories of that directory as well due to the \"majority rules\"\ndecision when files are renamed into different directory hierarchies.\nWe arbitrarily use the special value of 0x07 to record when we've hit\nsuch a directory.\n\nThe combination of all the above mean that we introduce a variable\nnamed dir_rename_mask (couldn't think of a better name) which has one\nof the following values as we traverse into a directory:\n * 0x00: directory rename detection not needed\n * 0x02 or 0x04: directory rename detection only needed if files added\n * 0x07: directory rename detection definitely needed\n\nWe then pass this value through to add_pairs() so that it can mark\nlocation_relevant as true only when dir_rename_mask is 0x07.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++-----\n 1 file changed, 61 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex bd2b93a31141..27acaa7380be 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -108,6 +108,14 @@ struct rename_info {\n \t */\n \tstruct strset relevant_sources[3];\n \n+\t/*\n+\t * dir_rename_mask:\n+\t * 0: optimization removing unmodified potential rename source okay\n+\t * 2 or 4: optimization okay, but must check for files added to dir\n+\t * 7: optimization forbidden; need rename source in case of dir rename\n+\t */\n+\tunsigned dir_rename_mask:3;\n+\n \t/*\n \t * callback_data_*: supporting data structures for alternate traversal\n \t *\n@@ -419,6 +427,8 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\tstrmap_clear(&opti->output, 0);\n \t}\n \n+\trenames->dir_rename_mask = 0;\n+\n \t/* Clean out callback_data as well. */\n \tFREE_AND_NULL(renames->callback_data);\n \trenames->callback_data_nr = renames->callback_data_alloc = 0;\n@@ -520,12 +530,16 @@ static int traverse_trees_wrapper_callback(int n,\n {\n \tstruct merge_options *opt = info->data;\n \tstruct rename_info *renames = &opt->priv->renames;\n+\tunsigned filemask = mask & ~dirmask;\n \n \tassert(n==3);\n \n \tif (!renames->callback_data_traverse_path)\n \t\trenames->callback_data_traverse_path = xstrdup(info->traverse_path);\n \n+\tif (filemask && filemask == renames->dir_rename_mask)\n+\t\trenames->dir_rename_mask = 0x07;\n+\n \tALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,\n \t\t renames->callback_data_alloc);\n \trenames->callback_data[renames->callback_data_nr].mask = mask;\n@@ -544,7 +558,6 @@ static int traverse_trees_wrapper_callback(int n,\n * additional details before the \"real\" traversal\n * - loop through the saved entries and call the original callback on them\n */\n-MAYBE_UNUSED\n static int traverse_trees_wrapper(struct index_state *istate,\n \t\t\t\t int n,\n \t\t\t\t struct tree_desc *t,\n@@ -556,6 +569,8 @@ static int traverse_trees_wrapper(struct index_state *istate,\n \tstruct merge_options *opt = info->data;\n \tstruct rename_info *renames = &opt->priv->renames;\n \n+\tassert(renames->dir_rename_mask == 2 || renames->dir_rename_mask == 4);\n+\n \told_callback_data_traverse_path = renames->callback_data_traverse_path;\n \told_fn = info->fn;\n \told_offset = renames->callback_data_nr;\n@@ -648,7 +663,8 @@ static void add_pair(struct merge_options *opt,\n \t\t const char *pathname,\n \t\t unsigned side,\n \t\t unsigned is_add /* if false, is_delete */,\n-\t\t unsigned match_mask)\n+\t\t unsigned match_mask,\n+\t\t unsigned dir_rename_mask)\n {\n \tstruct diff_filespec *one, *two;\n \tstruct rename_info *renames = &opt->priv->renames;\n@@ -656,7 +672,7 @@ static void add_pair(struct merge_options *opt,\n \n \tif (!is_add) {\n \t\tunsigned content_relevant = (match_mask == 0);\n-\t\tunsigned location_relevant = 1; /* FIXME: compute this */\n+\t\tunsigned location_relevant = (dir_rename_mask == 0x07);\n \n \t\tif (content_relevant || location_relevant)\n \t\t\tstrset_add(&renames->relevant_sources[side], pathname);\n@@ -680,6 +696,36 @@ static void collect_rename_info(struct merge_options *opt,\n \tstruct rename_info *renames = &opt->priv->renames;\n \tunsigned side;\n \n+\t/*\n+\t * Update dir_rename_mask (determines ignore-rename-source validity)\n+\t *\n+\t * dir_rename_mask helps us keep track of when directory rename\n+\t * detection may be relevant. Basically, whenver a directory is\n+\t * removed on one side of history, and a file is added to that\n+\t * directory on the other side of history, directory rename\n+\t * detection is relevant (meaning we have to detect renames for all\n+\t * files within that directory to deduce where the directory\n+\t * moved). Also, whenever a directory needs directory rename\n+\t * detection, due to the \"majority rules\" choice for where to move\n+\t * it (see t6423 testcase 1f), we also need to detect renames for\n+\t * all files within subdirectories of that directory as well.\n+\t *\n+\t * Here we haven't looked at files within the directory yet, we are\n+\t * just looking at the directory itself. So, if we aren't yet in\n+\t * a case where a parent directory needed directory rename detection\n+\t * (i.e. dir_rename_mask != 0x07), and if the directory was removed\n+\t * on one side of history, record the mask of the other side of\n+\t * history in dir_rename_mask.\n+\t */\n+\tif (renames->dir_rename_mask != 0x07 &&\n+\t (dirmask == 3 || dirmask == 5)) {\n+\t\t/* simple sanity check */\n+\t\tassert(renames->dir_rename_mask == 0 ||\n+\t\t renames->dir_rename_mask == (dirmask & ~1));\n+\t\t/* update dir_rename_mask; have it record mask of new side */\n+\t\trenames->dir_rename_mask = (dirmask & ~1);\n+\t}\n+\n \t/* Update dirs_removed, as needed */\n \tif (dirmask == 1 || dirmask == 3 || dirmask == 5) {\n \t\t/* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */\n@@ -699,12 +745,14 @@ static void collect_rename_info(struct merge_options *opt,\n \t\t/* Check for deletion on side */\n \t\tif ((filemask & 1) && !(filemask & side_mask))\n \t\t\tadd_pair(opt, names, fullname, side, 0 /* delete */,\n-\t\t\t\t match_mask & filemask);\n+\t\t\t\t match_mask & filemask,\n+\t\t\t\t renames->dir_rename_mask);\n \n \t\t/* Check for addition on side */\n \t\tif (!(filemask & 1) && (filemask & side_mask))\n \t\t\tadd_pair(opt, names, fullname, side, 1 /* add */,\n-\t\t\t\t match_mask & filemask);\n+\t\t\t\t match_mask & filemask,\n+\t\t\t\t renames->dir_rename_mask);\n \t}\n }\n \n@@ -722,12 +770,14 @@ static int collect_merge_info_callback(int n,\n \t */\n \tstruct merge_options *opt = info->data;\n \tstruct merge_options_internal *opti = opt->priv;\n+\tstruct rename_info *renames = &opt->priv->renames;\n \tstruct string_list_item pi; /* Path Info */\n \tstruct conflict_info *ci; /* typed alias to pi.util (which is void*) */\n \tstruct name_entry *p;\n \tsize_t len;\n \tchar *fullpath;\n \tconst char *dirname = opti->current_dir_name;\n+\tunsigned prev_dir_rename_mask = renames->dir_rename_mask;\n \tunsigned filemask = mask & ~dirmask;\n \tunsigned match_mask = 0; /* will be updated below */\n \tunsigned mbase_null = !(mask & 1);\n@@ -868,8 +918,13 @@ static int collect_merge_info_callback(int n,\n \n \t\toriginal_dir_name = opti->current_dir_name;\n \t\topti->current_dir_name = pi.string;\n-\t\tret = traverse_trees(NULL, 3, t, &newinfo);\n+\t\tif (renames->dir_rename_mask == 0 ||\n+\t\t renames->dir_rename_mask == 0x07)\n+\t\t\tret = traverse_trees(NULL, 3, t, &newinfo);\n+\t\telse\n+\t\t\tret = traverse_trees_wrapper(NULL, 3, t, &newinfo);\n \t\topti->current_dir_name = original_dir_name;\n+\t\trenames->dir_rename_mask = prev_dir_rename_mask;\n \n \t\tfor (i = MERGE_BASE; i <= MERGE_SIDE2; i++)\n \t\t\tfree(buf[i]);\n-- \ngitgitgadget\n\n"},{"id":"417960","messageId":"6b20977a5a811e3f3038aec58f615b621139f24b.1614484707.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"[PATCH 6/8] merge-ort: use relevant_sources to filter possible rename sources","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-28T03:58:24Z","receivedAt":"2021-02-28T04:00:08Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe past several commits determined conditions when rename sources might\nbe needed, and filled a relevant_sources strset with those paths. Pass\nthese along to diffcore_rename_extended() to use to limit the sources\nthat we need to detect renames for.\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: 12.596 s ± 0.061 s 6.003 s ± 0.048 s\n mega-renames: 130.465 s ± 0.259 s 114.009 s ± 0.236 s\n just-one-mega: 3.958 s ± 0.010 s 3.489 s ± 0.017 s\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 27acaa7380be..66892c63cee2 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2209,7 +2209,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_queued_diff = renames->pairs[side_index];\n \ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiffcore_rename_extended(&diff_opts,\n-\t\t\t\t NULL,\n+\t\t\t\t &renames->relevant_sources[side_index],\n \t\t\t\t &renames->dirs_removed[side_index],\n \t\t\t\t &renames->dir_rename_count[side_index]);\n \ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n-- \ngitgitgadget\n\n"},{"id":"417961","messageId":"d5486ab2846270486dd94bbfe81c5b27d18415d7.1614484707.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"[PATCH 7/8] merge-ort: skip rename detection entirely if possible","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-28T03:58:25Z","receivedAt":"2021-02-28T04:00:11Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ndiffcore_rename_extended() will do a bunch of setup, then check for\nexact renames, then abort before inexact rename detection if there are\nno more sources or destinations that need to be matched. It will\nsometimes be the case, however, that either\n * we start with neither any sources or destinations\n * we start with no *relevant* sources\nIn the first of these two cases, the setup and exact rename detection\nwill be very cheap since there are 0 files to operate on. In the second\ncase, it is quite possible to have thousands of files with none of the\nsource ones being relevant. Avoid calling diffcore_rename_extended() or\neven some of the setup before diffcore_rename_extended() when we can\ndetermine that rename detection is unnecessary.\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: 6.003 s ± 0.048 s 5.708 s ± 0.111 s\n mega-renames: 114.009 s ± 0.236 s 102.171 s ± 0.440 s\n just-one-mega: 3.489 s ± 0.017 s 3.471 s ± 0.015 s\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 45 +++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 45 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 66892c63cee2..8602c7b8936f 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2158,6 +2158,19 @@ static int process_renames(struct merge_options *opt,\n \treturn clean_merge;\n }\n \n+static inline int possible_side_renames(struct rename_info *renames,\n+\t\t\t\t\tunsigned side_index)\n+{\n+\treturn renames->pairs[side_index].nr > 0 &&\n+\t !strset_empty(&renames->relevant_sources[side_index]);\n+}\n+\n+static inline int possible_renames(struct rename_info *renames)\n+{\n+\treturn possible_side_renames(renames, 1) ||\n+\t possible_side_renames(renames, 2);\n+}\n+\n static void resolve_diffpair_statuses(struct diff_queue_struct *q)\n {\n \t/*\n@@ -2194,6 +2207,16 @@ static void detect_regular_renames(struct merge_options *opt,\n \tstruct diff_options diff_opts;\n \tstruct rename_info *renames = &opt->priv->renames;\n \n+\tif (!possible_side_renames(renames, side_index)) {\n+\t\t/*\n+\t\t * No rename detection needed for this side, but we still need\n+\t\t * to make sure 'adds' are marked correctly in case the other\n+\t\t * side had directory renames.\n+\t\t */\n+\t\tresolve_diffpair_statuses(&renames->pairs[side_index]);\n+\t\treturn;\n+\t}\n+\n \trepo_diff_setup(opt->repo, &diff_opts);\n \tdiff_opts.flags.recursive = 1;\n \tdiff_opts.flags.rename_empty = 0;\n@@ -2311,6 +2334,8 @@ static int detect_and_process_renames(struct merge_options *opt,\n \tint need_dir_renames, s, clean = 1;\n \n \tmemset(&combined, 0, sizeof(combined));\n+\tif (!possible_renames(renames))\n+\t\tgoto cleanup;\n \n \ttrace2_region_enter(\"merge\", \"regular renames\", opt->repo);\n \tdetect_regular_renames(opt, MERGE_SIDE1);\n@@ -2345,6 +2370,26 @@ static int detect_and_process_renames(struct merge_options *opt,\n \tclean &= process_renames(opt, &combined);\n \ttrace2_region_leave(\"merge\", \"process renames\", opt->repo);\n \n+\tgoto simple_cleanup; /* collect_renames() handles some of cleanup */\n+\n+cleanup:\n+\t/*\n+\t * Free now unneeded filepairs, which would have been handled\n+\t * in collect_renames() normally but we're about to skip that\n+\t * code...\n+\t */\n+\tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n+\t\tstruct diff_queue_struct *side_pairs;\n+\t\tint i;\n+\n+\t\tside_pairs = &renames->pairs[s];\n+\t\tfor (i = 0; i < side_pairs->nr; ++i) {\n+\t\t\tstruct diff_filepair *p = side_pairs->queue[i];\n+\t\t\tdiff_free_filepair(p);\n+\t\t}\n+\t}\n+\n+simple_cleanup:\n \t/* Free memory for renames->pairs[] and combined */\n \tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n \t\tfree(renames->pairs[s].queue);\n-- \ngitgitgadget\n\n"},{"id":"417962","messageId":"8fed92b62f375f97551a4e07bae5e43f9030d0d2.1614484707.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"[PATCH 8/8] diffcore-rename: avoid doing basename comparisons for irrelevant sources","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-02-28T03:58:26Z","receivedAt":"2021-02-28T04:00:16Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe basename comparison optimization implemented in\nfind_basename_matches() is very beneficial since it allows a source to\nsometimes only be compared with one other file instead of N other files.\nWhen a match is found, both a source and destination can be removed from\nthe matrix of inexact rename comparisons. In contrast, the irrelevant\nsource optimization only allows us to remove a source from the matrix of\ninexact rename comparisons...but it has the advantage of allowing a\nsource file to not even be loaded into memory at all and be compared to\n0 other files. Generally, not even comparing is a bigger performance\nwin, so when both optimizations could apply, prefer to use the\nirrelevant-source optimization.\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: 5.708 s ± 0.111 s 5.680 s ± 0.096 s\n mega-renames: 102.171 s ± 0.440 s 13.812 s ± 0.162 s\n just-one-mega: 3.471 s ± 0.015 s 506.0 ms ± 3.9 ms\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 37 +++++++++++++++++++++++++++++++++----\n 1 file changed, 33 insertions(+), 4 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 7f6115fd9018..e8508541be14 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -527,6 +527,7 @@ static void update_dir_rename_counts(struct dir_rename_info *info,\n }\n \n static void initialize_dir_rename_info(struct dir_rename_info *info,\n+\t\t\t\t struct strset *relevant_sources,\n \t\t\t\t struct strset *dirs_removed,\n \t\t\t\t struct strmap *dir_rename_count)\n {\n@@ -534,7 +535,7 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstruct strmap_entry *entry;\n \tint i;\n \n-\tif (!dirs_removed) {\n+\tif (!dirs_removed && !relevant_sources) {\n \t\tinfo->setup = 0;\n \t\treturn;\n \t}\n@@ -549,7 +550,20 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstrmap_init_with_options(&info->dir_rename_guess, NULL, 0);\n \n \t/* Setup info->relevant_source_dirs */\n-\tinfo->relevant_source_dirs = dirs_removed;\n+\tinfo->relevant_source_dirs = NULL;\n+\tif (dirs_removed || !relevant_sources) {\n+\t\tinfo->relevant_source_dirs = dirs_removed; /* might be NULL */\n+\t} else {\n+\t\tinfo->relevant_source_dirs = xmalloc(sizeof(struct strintmap));\n+\t\tstrset_init(info->relevant_source_dirs);\n+\t\tstrset_for_each_entry(relevant_sources, &iter, entry) {\n+\t\t\tchar *dirname = get_dirname(entry->key);\n+\t\t\tif (!dirs_removed ||\n+\t\t\t strset_contains(dirs_removed, dirname))\n+\t\t\t\tstrset_add(info->relevant_source_dirs, dirname);\n+\t\t\tfree(dirname);\n+\t\t}\n+\t}\n \n \t/*\n \t * Loop setting up both info->idx_map, and doing setup of\n@@ -627,6 +641,13 @@ static void cleanup_dir_rename_info(struct dir_rename_info *info,\n \t/* dir_rename_guess */\n \tstrmap_clear(&info->dir_rename_guess, 1);\n \n+\t/* relevant_source_dirs */\n+\tif (info->relevant_source_dirs &&\n+\t info->relevant_source_dirs != dirs_removed) {\n+\t\tstrset_clear(info->relevant_source_dirs);\n+\t\tFREE_AND_NULL(info->relevant_source_dirs);\n+\t}\n+\n \t/* dir_rename_count */\n \tif (!keep_dir_rename_count) {\n \t\tpartial_clear_dir_rename_count(info->dir_rename_count);\n@@ -749,6 +770,7 @@ static int idx_possible_rename(char *filename, struct dir_rename_info *info)\n static int find_basename_matches(struct diff_options *options,\n \t\t\t\t int minimum_score,\n \t\t\t\t struct dir_rename_info *info,\n+\t\t\t\t struct strset *relevant_sources,\n \t\t\t\t struct strset *dirs_removed)\n {\n \t/*\n@@ -839,6 +861,11 @@ static int find_basename_matches(struct diff_options *options,\n \t\tintptr_t src_index;\n \t\tintptr_t dst_index;\n \n+\t\t/* Skip irrelevant sources */\n+\t\tif (relevant_sources &&\n+\t\t !strset_contains(relevant_sources, filename))\n+\t\t\tcontinue;\n+\n \t\t/*\n \t\t * If the basename is unique among remaining sources, then\n \t\t * src_index will equal 'i' and we can attempt to match it\n@@ -1164,7 +1191,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \n \t\t/* Preparation for basename-driven matching. */\n \t\ttrace2_region_enter(\"diff\", \"dir rename setup\", options->repo);\n-\t\tinitialize_dir_rename_info(&info,\n+\t\tinitialize_dir_rename_info(&info, relevant_sources,\n \t\t\t\t\t dirs_removed, dir_rename_count);\n \t\ttrace2_region_leave(\"diff\", \"dir rename setup\", options->repo);\n \n@@ -1172,7 +1199,9 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\ttrace2_region_enter(\"diff\", \"basename matches\", options->repo);\n \t\trename_count += find_basename_matches(options,\n \t\t\t\t\t\t min_basename_score,\n-\t\t\t\t\t\t &info, dirs_removed);\n+\t\t\t\t\t\t &info,\n+\t\t\t\t\t\t relevant_sources,\n+\t\t\t\t\t\t dirs_removed);\n \t\ttrace2_region_leave(\"diff\", \"basename matches\", options->repo);\n \n \t\t/*\n-- \ngitgitgadget\n"},{"id":"418041","messageId":"CABPp-BEVvfMLGFthb5EQpYORSe9BifQRNb40+mgcg=bGCABc5Q@mail.gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/8] Optimization batch 9: avoid detecting irrelevant renames","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-03-01T16:39:07Z","receivedAt":"2021-03-01T16:44:28Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Sat, Feb 27, 2021 at 7:58 PM Elijah Newren via GitGitGadget\n wrote:\n>\n> This series depends textually on ort-perf-batch-8, but semantically it's\n> almost completely unrelated and can be reviewed without any familiarity with\n> any of the previous patch series.\n>\n> === Basic Optimization idea ===\n>\n> This series determines paths which meet special cases where detection of\n> renames is irrelevant, where the irrelevance is due to the fact that the\n> merge machinery will arrive at the same result regardless of whether a\n> rename is detected for any of those paths. This series represents\n> \"Optimization #2\" from my Git Merge 2020 talk[1], though this series has\n> some improvements on the optimization relative to what I had at that time.\n>\n> The basic idea here is that if side A of history:\n>\n> * only modifies/adds/deletes a few files\n> * adds new files to few if any of the directories that side B deleted or\n> renamed\n>\n> then when we do rename detection on side B we can avoid even looking at most\n> (and perhaps even all) paths that side B deleted. Since commits being\n> rebased or cherry-picked tend to only modify a few files, this optimization\n> tends to be particularly effective for rebases and cherry-picks.\n>\n> Basing rename detection on what the other side of history did to a file\n> means that extra information needs to be fed from merge-ort to\n> diffcore-rename in order to take advantage of such an optimization.\n>\n> === Comparison to previous series ===\n>\n> This series differs from my two previous optimizations[2][3] (focusing on\n> basename-guided rename detection) in two important aspects:\n>\n> * there are no behavioral changes (there is no heuristic involved)\n>\n> * this optimization is merge specific (it does not help the diff/status/log\n> family of commands, just merge/rebase/cherry-pick and such)\n>\n> === Results ===\n>\n> For the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\n> performance work; instrument with trace2_region_* calls\", 2020-10-28), the\n> changes in just this series improves the performance as follows:\n>\n> Before Series After Series\n> no-renames: 12.596 s ± 0.061 s 5.680 s ± 0.096 s\n> mega-renames: 130.465 s ± 0.259 s 13.812 s ± 0.162 s\n> just-one-mega: 3.958 s ± 0.010 s 506.0 ms ± 3.9 ms\n>\n>\n> However, interestingly, if we had ignored the basename-guided rename\n> detection optimizations[2][3], then this optimization series would have\n> improved the performance as follows:\n>\n> Before Basename Series After Just This Series\n> no-renames: 13.815 s ± 0.062 s 5.728 s ± 0.104 s\n> mega-renames: 1799.937 s ± 0.493 s 18.213 s ± 0.139 s\n> just-one-mega 51.289 s ± 0.019 s 891.9 ms ± 7.0 ms\n>\n>\n> As a reminder, before any merge-ort/diffcore-rename performance work, the\n> performance results we started with (as noted in the same commit message)\n> were:\n>\n> no-renames-am: 6.940 s ± 0.485 s\n> no-renames: 18.912 s ± 0.174 s\n> mega-renames: 5964.031 s ± 10.459 s\n> just-one-mega: 149.583 s ± 0.751 s\n>\n>\n> === Competition between optimizations ===\n>\n> We now have three major rename-related optimizations:\n>\n> * exact rename detection\n> * basename-guided rename detection[2][3]\n> * skip-because-unnecessary (this series)\n>\n> It is possible for all three to potentially apply for specific paths (they\n> do for the majority of renamed paths in our testcases), but we cannot use\n> more than one for any given path. It turns out that the priority we give\n> each optimization is very important and can drastically affect performance.\n> We get best results by prioritizing them as follows:\n>\n> 1. exact rename detection\n> 2. skip-because-unnecessary\n> 3. basename-guided rename detection\n>\n> The third-to-last patch of this series also discusses this ordering and\n> another minor variant of the skip-because-unnecessary optimization that was\n> tried (and resulted in less effective performance gains than reported here),\n> as well as some of the preparatory work over the past few years that this\n> series relies on in order to enable this optimization.\n\nOops. When I restructured the series I carefully re-read the commit\nmessages to make sure I didn't forget to update one...but I apparently\nforgot to update the cover letter. The discussion was actually split\nacross a few patches by the refactoring, and what is now the\nthird-to-last patch doesn't contain any of that discussion.\n\n> === Near optimal? ===\n>\n> You may remember that there was a row labelled \"everything else\" from the\n> commit message of 557ac0350d that represented the maximum possible speed-up\n> from accelerating rename detection alone; as stated in that commit, those\n> rows represented how fast the code could be if we had somehow infinitely\n> parallelized the inexact rename detection. However, if you compare those\n> \"maximum speedup\" numbers to what we have above, you'll note that the\n> infinitely parallelized inexact rename detection would have been slightly\n> slower than the results we have now achieved. (The reason this is possible,\n> despite the fact that we still spend time in rename detection after our\n> optimizations, is because we implemented two optimizations outside of\n> diffcore_rename() along the way.) However, this good news does also come\n> with a downside -- it means that our remaining optimization potential is\n> somewhat limited, and subsequent optimization series will have to fight for\n> much smaller gains.\n>\n> [1]\n> https://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf\n> [2]\n> https://lore.kernel.org/git/pull.843.git.1612651937.gitgitgadget@gmail.com/\n> [3]\n> https://lore.kernel.org/git/pull.844.git.1613289544.gitgitgadget@gmail.com/\n>\n> Elijah Newren (8):\n> diffcore-rename: enable filtering possible rename sources\n> merge-ort: precompute subset of sources for which we need rename\n> detection\n> merge-ort: add data structures for an alternate tree traversal\n> merge-ort: introduce wrappers for alternate tree traversal\n> merge-ort: precompute whether directory rename detection is needed\n> merge-ort: use relevant_sources to filter possible rename sources\n> merge-ort: skip rename detection entirely if possible\n> diffcore-rename: avoid doing basename comparisons for irrelevant\n> sources\n>\n> diffcore-rename.c | 63 ++++++++++---\n> diffcore.h | 1 +\n> merge-ort.c | 236 +++++++++++++++++++++++++++++++++++++++++++++-\n> 3 files changed, 285 insertions(+), 15 deletions(-)\n>\n>\n> base-commit: 4be565c472088d4144063b736308bf2a57331f45\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-845%2Fnewren%2Fort-perf-batch-9-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-845/newren/ort-perf-batch-9-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/845\n> --\n> gitgitgadget\n"},{"id":"418220","messageId":"CABPp-BEv1BN66A1jJ+P+HThyFSwM9mFevd-uj9FWbnWyMtsCNQ@mail.gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/8] Optimization batch 9: avoid detecting irrelevant renames","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-03-04T07:54:20Z","receivedAt":"2021-03-04T07:56:28Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi,\n\nOn Sat, Feb 27, 2021 at 7:58 PM Elijah Newren via GitGitGadget\n wrote:\n>\n> This series depends textually on ort-perf-batch-8, but semantically it's\n> almost completely unrelated and can be reviewed without any familiarity with\n> any of the previous patch series.\n>\n> === Basic Optimization idea ===\n>\n> The basic idea here is that if side A of history:\n>\n> * only modifies/adds/deletes a few files\n> * adds new files to few if any of the directories that side B deleted or\n> renamed\n>\n> then when we do rename detection on side B we can avoid even looking at most\n> (and perhaps even all) paths that side B deleted. Since commits being\n> rebased or cherry-picked tend to only modify a few files, this optimization\n> tends to be particularly effective for rebases and cherry-picks.\n\nAfter thinking it over a bit more, there's a much better way to put\nthis summary:\n\n We only need expensive rename detection on the subset of files\nchanged on *both* sides (for the most part).\n\nThis is because:\n\n1. The primary reason for rename detection in merges is enabling\nthree-way content merges\n2. The purpose of three-way content merges is reconciling changes when\n*both* sides of history modified some file\n3. If a file was only modified by the side that renamed the file, then\ndetecting the rename is irrelevant; we'll get the same answer without\nknowing about the rename.\n4. (Well...there are rare cases where we need the rename for reasons\nother than three-way content merges. Patch 5 explains those.)\n"},{"id":"418552","messageId":"33c231331744833e318cc652f5c7109861e010b3.1615248599.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"[PATCH v2 2/8] merge-ort: precompute subset of sources for which we need rename detection","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-09T00:09:53Z","receivedAt":"2021-03-09T00:10:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nrename detection works by trying to pair all file deletions (or\n\"sources\") with all file additions (or \"destinations\"), checking\nsimilarity, and then marking the sufficiently similar ones as renames.\nThis can be expensive if there are many sources and destinations on a\ngiven side of history as it results in an N x M comparison matrix.\nHowever, there are many cases where we can compute in advance that\ndetecting renames for some of the sources provides no useful information\nand thus that we can exclude those sources from the matrix.\n\nTo see why, first note that the merge machinery uses detected renames in\ntwo ways:\n\n * directory rename detection: when one side of history renames a\n directory, and the other side of history adds new files to that\n directory, we want to be able to warn the user about the need to\n chose whether those new files stay in the old directory or move\n to the new one.\n\n * three-way content merging: in order to do three-way content merging\n of files, we need three different file versions. If one side of\n history renamed a file, then some of the content for the file is\n found under a different path than in the merge base or on the\n other side of history.\n\nThis commit concentrates just on the three-way content merging; it will\npunt and mark all sources as needed for directory rename detection, and\nleave it to future commits to narrow that down more.\n\nThe point of three-way content merging is to reconcile changes made on\n*both* sides of history. What if the file wasn't modified on both\nsides? There are two possibilities:\n\n * If it wasn't modified on the renamed side:\n -> then we get to do exact rename detection, which is cheap.\n\n * If it wasn't modified on the unrenamed side:\n -> then detection of a rename for that source file is irrelevant\n\nThat latter claim might be surprising at first, so let's walk through a\ncase to show why rename detection for that source file is irrelevant.\nLet's use two filenames, old.c & new.c, with the following abbreviated\nobject ids (and where the value '000000' is used to denote that the file\nis missing in that commit):\n\n old.c new.c\n MERGE_BASE: 01d01d 000000\n MERGE_SIDE1: 01d01d 000000\n MERGE_SIDE2: 000000 5e1ec7\n\nIf the rename *isn't* detected:\n then old.c looks like it was unmodified on one side and deleted on\n the other and should thus be removed. new.c looks like a new file we\n should keep as-is.\n\nIf the rename *is* detected:\n then a three-way content merge is done. Since the version of the\n file in MERGE_BASE and MERGE_SIDE1 are identical, the three-way merge\n will produce exactly the version of the file whose abbreviated\n object id is 5e1ec7. It will record that file at the path new.c,\n while removing old.c from the directory.\n\nNote that these two results are identical -- a single file named 'new.c'\nwith object id 5e1ec7. In other words, it doesn't matter if the rename\nis detected in the case where the file is unmodified on the unrenamed\nside.\n\nUse this information to compute whether we need rename detection for\neach source created in add_pair().\n\nIt's probably worth noting that there used to be a few other edge or\ncorner cases besides three-way content merges and directory rename\ndetection where lack of rename detection could have affected the result,\nbut those cases actually highlighted where conflict resolution methods\nwere not consistent with each other. Fixing those inconsistencies were\nthus critically important to enabling this optimization. That work\ninvolved the following:\n\n * bringing consistency to add/add, rename/add, and rename/rename\n conflict types, as done back in the topic merged at commit\n ac193e0e0a (\"Merge branch 'en/merge-path-collision'\", 2019-01-04),\n and further extended in commits 2a7c16c980 (\"t6422, t6426: be more\n flexible for add/add conflicts involving renames\", 2020-08-10) and\n e8eb99d4a6 (\"t642[23]: be more flexible for add/add conflicts\n involving pair renames\", 2020-08-10)\n\n * making rename/delete more consistent with modify/delete\n as done in commits 1f3c9ba707 (\"t6425: be more flexible with\n rename/delete conflict messages\", 2020-08-10) and 727c75b23f\n (\"t6404, t6423: expect improved rename/delete handling in ort\n backend\", 2020-10-26)\n\nSince the set of relevant_sources we compute has not yet been narrowed\ndown for directory rename detection, we do not pass it to\ndiffcore_rename_extended() yet. That will be done after subsequent\ncommits narrow down the list of relevant_sources needed for directory\nrename detection reasons.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 35 ++++++++++++++++++++++++++++++++---\n 1 file changed, 32 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex aba0b9fa54c3..83aa4c08121f 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -88,6 +88,20 @@ struct rename_info {\n \t */\n \tstruct strmap dir_renames[3];\n \n+\t/*\n+\t * relevant_sources: deleted paths for which we need rename detection\n+\t *\n+\t * relevant_sources is a set of deleted paths on each side of\n+\t * history for which we need rename detection. If a path is deleted\n+\t * on one side of history, we need to detect if it is part of a\n+\t * rename if either\n+\t * * we need to detect renames for an ancestor directory\n+\t * * the file is modified/deleted on the other side of history\n+\t * If neither of those are true, we can skip rename detection for\n+\t * that path.\n+\t */\n+\tstruct strset relevant_sources[3];\n+\n \t/*\n \t * needed_limit: value needed for inexact rename detection to run\n \t *\n@@ -358,6 +372,8 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\t\tstrmap_clear(&renames->dir_rename_count[i], 1);\n \n \t\tstrmap_func(&renames->dir_renames[i], 0);\n+\n+\t\tstrset_func(&renames->relevant_sources[i]);\n \t}\n \n \tif (!reinitialize) {\n@@ -533,12 +549,21 @@ static void add_pair(struct merge_options *opt,\n \t\t struct name_entry *names,\n \t\t const char *pathname,\n \t\t unsigned side,\n-\t\t unsigned is_add /* if false, is_delete */)\n+\t\t unsigned is_add /* if false, is_delete */,\n+\t\t unsigned match_mask)\n {\n \tstruct diff_filespec *one, *two;\n \tstruct rename_info *renames = &opt->priv->renames;\n \tint names_idx = is_add ? side : 0;\n \n+\tif (!is_add) {\n+\t\tunsigned content_relevant = (match_mask == 0);\n+\t\tunsigned location_relevant = 1; /* FIXME: compute this */\n+\n+\t\tif (content_relevant || location_relevant)\n+\t\t\tstrset_add(&renames->relevant_sources[side], pathname);\n+\t}\n+\n \tone = alloc_filespec(pathname);\n \ttwo = alloc_filespec(pathname);\n \tfill_filespec(is_add ? two : one,\n@@ -575,11 +600,13 @@ static void collect_rename_info(struct merge_options *opt,\n \n \t\t/* Check for deletion on side */\n \t\tif ((filemask & 1) && !(filemask & side_mask))\n-\t\t\tadd_pair(opt, names, fullname, side, 0 /* delete */);\n+\t\t\tadd_pair(opt, names, fullname, side, 0 /* delete */,\n+\t\t\t\t match_mask & filemask);\n \n \t\t/* Check for addition on side */\n \t\tif (!(filemask & 1) && (filemask & side_mask))\n-\t\t\tadd_pair(opt, names, fullname, side, 1 /* add */);\n+\t\t\tadd_pair(opt, names, fullname, side, 1 /* add */,\n+\t\t\t\t match_mask & filemask);\n \t}\n }\n \n@@ -3228,6 +3255,8 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t\t\t\t\t NULL, 1);\n \t\tstrmap_init_with_options(&renames->dir_renames[i],\n \t\t\t\t\t NULL, 0);\n+\t\tstrset_init_with_options(&renames->relevant_sources[i],\n+\t\t\t\t\t NULL, 0);\n \t}\n \n \t/*\n-- \ngitgitgadget\n\n"},{"id":"418553","messageId":"dab8e3c6aee5a852ad46c569c0be729d64310ad9.1615248599.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"[PATCH v2 1/8] diffcore-rename: enable filtering possible rename sources","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-09T00:09:52Z","receivedAt":"2021-03-09T00:10:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd the ability to diffcore_rename_extended() to allow external callers\nto declare that they only need renames detected for a subset of source\nfiles, and use that information to skip detecting renames for them.\n\nThere are two important pieces to this optimization that may not be\nobvious at first glance:\n\n * We do not require callers to just filter the filepairs out\n to remove the non-relevant sources, because exact rename detection\n is fast and when it finds a match it can remove both a source and a\n destination whereas the relevant_sources filter can only remove a\n source.\n\n * We need to filter out the source pairs in a preliminary pass instead\n of adding a\n strset_contains(relevant_sources, one->path)\n check within the nested matrix loop. The reason for that is if we\n have 30k renames, doing 30k * 30k = 900M strset_contains() calls\n becomes extraordinarily expensive and defeats the performance gains\n from this change; we only want to do 30k such calls instead.\n\nIf callers pass NULL for relevant_sources, that is special cases to\ntreat all sources as relevant. Since all callers currently pass NULL,\nthis optimization does not yet have any effect. Subsequent commits will\nhave merge-ort compute a set of relevant_sources to restrict which\nsources we detect renames for, and have merge-ort pass that set of\nrelevant_sources to diffcore_rename_extended().\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 26 +++++++++++++++++++-------\n diffcore.h | 1 +\n merge-ort.c | 1 +\n 3 files changed, 21 insertions(+), 7 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1fe902ed2af0..7f6115fd9018 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -991,11 +991,12 @@ static int find_renames(struct diff_score *mx,\n \treturn count;\n }\n \n-static void remove_unneeded_paths_from_src(int detecting_copies)\n+static void remove_unneeded_paths_from_src(int detecting_copies,\n+\t\t\t\t\t struct strset *interesting)\n {\n \tint i, new_num_src;\n \n-\tif (detecting_copies)\n+\tif (detecting_copies && !interesting)\n \t\treturn; /* nothing to remove */\n \tif (break_idx)\n \t\treturn; /* culling incompatible with break detection */\n@@ -1022,12 +1023,18 @@ static void remove_unneeded_paths_from_src(int detecting_copies)\n \t * from rename_src here.\n \t */\n \tfor (i = 0, new_num_src = 0; i < rename_src_nr; i++) {\n+\t\tstruct diff_filespec *one = rename_src[i].p->one;\n+\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\tif (!detecting_copies && one->rename_used)\n+\t\t\tcontinue;\n+\n+\t\t/* If we don't care about the source path, skip it */\n+\t\tif (interesting && !strset_contains(interesting, one->path))\n \t\t\tcontinue;\n \n \t\tif (new_num_src < i)\n@@ -1040,6 +1047,7 @@ static void remove_unneeded_paths_from_src(int detecting_copies)\n }\n \n void diffcore_rename_extended(struct diff_options *options,\n+\t\t\t struct strset *relevant_sources,\n \t\t\t struct strset *dirs_removed,\n \t\t\t struct strmap *dir_rename_count)\n {\n@@ -1060,6 +1068,8 @@ void diffcore_rename_extended(struct diff_options *options,\n \twant_copies = (detect_rename == DIFF_DETECT_COPY);\n \tif (dirs_removed && (break_idx || want_copies))\n \t\tBUG(\"dirs_removed incompatible with break/copy detection\");\n+\tif (break_idx && relevant_sources)\n+\t\tBUG(\"break detection incompatible with source specification\");\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -1127,9 +1137,10 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t/*\n \t\t * Cull sources:\n \t\t * - remove ones corresponding to exact renames\n+\t\t * - remove ones not found in relevant_sources\n \t\t */\n \t\ttrace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n-\t\tremove_unneeded_paths_from_src(want_copies);\n+\t\tremove_unneeded_paths_from_src(want_copies, relevant_sources);\n \t\ttrace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n \t} else {\n \t\t/* Determine minimum score to match basenames */\n@@ -1148,7 +1159,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t * - remove ones involved in renames (found via exact match)\n \t\t */\n \t\ttrace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n-\t\tremove_unneeded_paths_from_src(want_copies);\n+\t\tremove_unneeded_paths_from_src(want_copies, NULL);\n \t\ttrace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n \n \t\t/* Preparation for basename-driven matching. */\n@@ -1167,9 +1178,10 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t/*\n \t\t * Cull sources, again:\n \t\t * - remove ones involved in renames (found via basenames)\n+\t\t * - remove ones not found in relevant_sources\n \t\t */\n \t\ttrace2_region_enter(\"diff\", \"cull basename\", options->repo);\n-\t\tremove_unneeded_paths_from_src(want_copies);\n+\t\tremove_unneeded_paths_from_src(want_copies, relevant_sources);\n \t\ttrace2_region_leave(\"diff\", \"cull basename\", options->repo);\n \t}\n \n@@ -1342,5 +1354,5 @@ void diffcore_rename_extended(struct diff_options *options,\n \n void diffcore_rename(struct diff_options *options)\n {\n-\tdiffcore_rename_extended(options, NULL, NULL);\n+\tdiffcore_rename_extended(options, NULL, NULL, NULL);\n }\ndiff --git a/diffcore.h b/diffcore.h\nindex c6ba64abd198..737c93a6cc79 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -166,6 +166,7 @@ void partial_clear_dir_rename_count(struct strmap *dir_rename_count);\n void diffcore_break(struct repository *, int);\n void diffcore_rename(struct diff_options *);\n void diffcore_rename_extended(struct diff_options *options,\n+\t\t\t struct strset *relevant_sources,\n \t\t\t struct strset *dirs_removed,\n \t\t\t struct strmap *dir_rename_count);\n void diffcore_merge_broken(void);\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 467404cc0a35..aba0b9fa54c3 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2029,6 +2029,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_queued_diff = renames->pairs[side_index];\n \ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiffcore_rename_extended(&diff_opts,\n+\t\t\t\t NULL,\n \t\t\t\t &renames->dirs_removed[side_index],\n \t\t\t\t &renames->dir_rename_count[side_index]);\n \ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n-- \ngitgitgadget\n\n"},{"id":"418554","messageId":"d62fdee45ad344a09062e2ab73702d1093c12efc.1615248599.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"[PATCH v2 6/8] merge-ort: use relevant_sources to filter possible rename sources","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-09T00:09:57Z","receivedAt":"2021-03-09T00:10:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe past several commits determined conditions when rename sources might\nbe needed, and filled a relevant_sources strset with those paths. Pass\nthese along to diffcore_rename_extended() to use to limit the sources\nthat we need to detect renames for.\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: 12.596 s ± 0.061 s 6.003 s ± 0.048 s\n mega-renames: 130.465 s ± 0.259 s 114.009 s ± 0.236 s\n just-one-mega: 3.958 s ± 0.010 s 3.489 s ± 0.017 s\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 27acaa7380be..66892c63cee2 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2209,7 +2209,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_queued_diff = renames->pairs[side_index];\n \ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiffcore_rename_extended(&diff_opts,\n-\t\t\t\t NULL,\n+\t\t\t\t &renames->relevant_sources[side_index],\n \t\t\t\t &renames->dirs_removed[side_index],\n \t\t\t\t &renames->dir_rename_count[side_index]);\n \ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n-- \ngitgitgadget\n\n"},{"id":"418555","messageId":"89b43c9f75a03ab8cc258db8e6a1137e6e6fbb3f.1615248599.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"[PATCH v2 3/8] merge-ort: add data structures for an alternate tree traversal","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-09T00:09:54Z","receivedAt":"2021-03-09T00:10:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn order to determine whether directory rename detection is needed, we\nas a pre-requisite need a way to traverse through all the files in a\ngiven tree before visiting any directories within that tree.\ntraverse_trees() only iterates through the entries in the order they\nappear, so add some data structures that will store all the entries as\nwe iterate through them in traverse_trees(), which will allow us to\nre-traverse them in our desired order.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 26 ++++++++++++++++++++++++++\n 1 file changed, 26 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 83aa4c08121f..d49cfa8b030b 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -51,6 +51,12 @@ enum merge_side {\n \tMERGE_SIDE2 = 2\n };\n \n+struct traversal_callback_data {\n+\tunsigned long mask;\n+\tunsigned long dirmask;\n+\tstruct name_entry names[3];\n+};\n+\n struct rename_info {\n \t/*\n \t * All variables that are arrays of size 3 correspond to data tracked\n@@ -102,6 +108,22 @@ struct rename_info {\n \t */\n \tstruct strset relevant_sources[3];\n \n+\t/*\n+\t * callback_data_*: supporting data structures for alternate traversal\n+\t *\n+\t * We sometimes need to be able to traverse through all the files\n+\t * in a given tree before all immediate subdirectories within that\n+\t * tree. Since traverse_trees() doesn't do that naturally, we have\n+\t * a traverse_trees_wrapper() that stores any immediate\n+\t * subdirectories while traversing files, then traverses the\n+\t * immediate subdirectories later. These callback_data* variables\n+\t * store the information for the subdirectories so that we can do\n+\t * that traversal order.\n+\t */\n+\tstruct traversal_callback_data *callback_data;\n+\tint callback_data_nr, callback_data_alloc;\n+\tchar *callback_data_traverse_path;\n+\n \t/*\n \t * needed_limit: value needed for inexact rename detection to run\n \t *\n@@ -396,6 +418,10 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\t}\n \t\tstrmap_clear(&opti->output, 0);\n \t}\n+\n+\t/* Clean out callback_data as well. */\n+\tFREE_AND_NULL(renames->callback_data);\n+\trenames->callback_data_nr = renames->callback_data_alloc = 0;\n }\n \n static int err(struct merge_options *opt, const char *err, ...)\n-- \ngitgitgadget\n\n"},{"id":"418556","messageId":"6497050c00126bdeff6880e5a2a52cd7b8457513.1615248599.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"[PATCH v2 4/8] merge-ort: introduce wrappers for alternate tree traversal","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-09T00:09:55Z","receivedAt":"2021-03-09T00:10:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd traverse_trees_wrapper() and traverse_trees_wrapper_callback()\nfunctions. The former runs traverse_trees() with info->fn set to\ntraverse_trees_wrapper_callback, in order to simply save all the entries\nwithout processing or recursing into any of them. This step allows\nextra computation to be done (e.g. checking some condition across all\nfiles) that can be used later. Then, after that is completed, it\niterates over all the saved entries and calls the original info->fn\ncallback with the saved data.\n\nCurrently, this does nothing more than marginally slowing down the tree\ntraversal since we do not take advantage of the opportunity to compute\nanything special in traverse_trees_wrapper_callback(), and thus the real\ncallback will be called identically as it would have been without this\nextra wrapper. However, a subsequent commit will add some special\ncomputation of some values that the real callback will be able to use.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 72 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 72 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex d49cfa8b030b..bd2b93a31141 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -512,6 +512,78 @@ static char *unique_path(struct strmap *existing_paths,\n \n /*** Function Grouping: functions related to collect_merge_info() ***/\n \n+static int traverse_trees_wrapper_callback(int n,\n+\t\t\t\t\t unsigned long mask,\n+\t\t\t\t\t unsigned long dirmask,\n+\t\t\t\t\t struct name_entry *names,\n+\t\t\t\t\t struct traverse_info *info)\n+{\n+\tstruct merge_options *opt = info->data;\n+\tstruct rename_info *renames = &opt->priv->renames;\n+\n+\tassert(n==3);\n+\n+\tif (!renames->callback_data_traverse_path)\n+\t\trenames->callback_data_traverse_path = xstrdup(info->traverse_path);\n+\n+\tALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,\n+\t\t renames->callback_data_alloc);\n+\trenames->callback_data[renames->callback_data_nr].mask = mask;\n+\trenames->callback_data[renames->callback_data_nr].dirmask = dirmask;\n+\tCOPY_ARRAY(renames->callback_data[renames->callback_data_nr].names,\n+\t\t names, 3);\n+\trenames->callback_data_nr++;\n+\n+\treturn mask;\n+}\n+\n+/*\n+ * Much like traverse_trees(), BUT:\n+ * - read all the tree entries FIRST, saving them\n+ * - note that the above step provides an opportunity to compute necessary\n+ * additional details before the \"real\" traversal\n+ * - loop through the saved entries and call the original callback on them\n+ */\n+MAYBE_UNUSED\n+static int traverse_trees_wrapper(struct index_state *istate,\n+\t\t\t\t int n,\n+\t\t\t\t struct tree_desc *t,\n+\t\t\t\t struct traverse_info *info)\n+{\n+\tint ret, i, old_offset;\n+\ttraverse_callback_t old_fn;\n+\tchar *old_callback_data_traverse_path;\n+\tstruct merge_options *opt = info->data;\n+\tstruct rename_info *renames = &opt->priv->renames;\n+\n+\told_callback_data_traverse_path = renames->callback_data_traverse_path;\n+\told_fn = info->fn;\n+\told_offset = renames->callback_data_nr;\n+\n+\trenames->callback_data_traverse_path = NULL;\n+\tinfo->fn = traverse_trees_wrapper_callback;\n+\tret = traverse_trees(istate, n, t, info);\n+\tif (ret < 0)\n+\t\treturn ret;\n+\n+\tinfo->traverse_path = renames->callback_data_traverse_path;\n+\tinfo->fn = old_fn;\n+\tfor (i = old_offset; i < renames->callback_data_nr; ++i) {\n+\t\tinfo->fn(n,\n+\t\t\t renames->callback_data[i].mask,\n+\t\t\t renames->callback_data[i].dirmask,\n+\t\t\t renames->callback_data[i].names,\n+\t\t\t info);\n+\n+\t}\n+\n+\trenames->callback_data_nr = old_offset;\n+\tfree(renames->callback_data_traverse_path);\n+\trenames->callback_data_traverse_path = old_callback_data_traverse_path;\n+\tinfo->traverse_path = NULL;\n+\treturn 0;\n+}\n+\n static void setup_path_info(struct merge_options *opt,\n \t\t\t struct string_list_item *result,\n \t\t\t const char *current_dir_name,\n-- \ngitgitgadget\n\n"},{"id":"418557","messageId":"608d5a4c6ad7e3fdccbb30985fd85da288279814.1615248599.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"[PATCH v2 5/8] merge-ort: precompute whether directory rename detection is needed","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-09T00:09:56Z","receivedAt":"2021-03-09T00:10:58Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe point of directory rename detection is that if one side of history\nrenames a directory, and the other side adds new files under the old\ndirectory, then the merge can move those new files into the new\ndirectory. This leads to the following important observation:\n\n * If the other side does not add any new files under the old\n directory, we do not need to detect any renames for that directory.\n\nSimilarly, directory rename detection had an important requirement:\n\n * If a directory still exists on one side of history, it has not been\n renamed on that side of history. (See section 4 of t6423 or\n Documentation/technical/directory-rename-detection.txt for more\n details).\n\nUsing these two bits of information, we note that directory rename\ndetection is only needed in cases where (1) directories exist in the\nmerge base and on one side of history (i.e. dirmask == 3 or dirmask ==\n5), and (2) where there is some new file added to that directory on the\nside where it still exists (thus where the file has filemask == 2 or\nfilemask == 4, respectively). This has to be done in two steps, because\nwe have the dirmask when we are first considering the directory, and\nwon't get the filemasks for the files within it until we recurse into\nthat directory. So, we save\n dir_rename_mask = dirmask - 1\nwhen we hit a directory that is missing on one side, and then later look\nfor cases of\n filemask == dir_rename_mask\n\nOne final note is that as soon as we hit a directory that needs\ndirectory rename detection, we will need to detect renames in all\nsubdirectories of that directory as well due to the \"majority rules\"\ndecision when files are renamed into different directory hierarchies.\nWe arbitrarily use the special value of 0x07 to record when we've hit\nsuch a directory.\n\nThe combination of all the above mean that we introduce a variable\nnamed dir_rename_mask (couldn't think of a better name) which has one\nof the following values as we traverse into a directory:\n * 0x00: directory rename detection not needed\n * 0x02 or 0x04: directory rename detection only needed if files added\n * 0x07: directory rename detection definitely needed\n\nWe then pass this value through to add_pairs() so that it can mark\nlocation_relevant as true only when dir_rename_mask is 0x07.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++-----\n 1 file changed, 61 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex bd2b93a31141..27acaa7380be 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -108,6 +108,14 @@ struct rename_info {\n \t */\n \tstruct strset relevant_sources[3];\n \n+\t/*\n+\t * dir_rename_mask:\n+\t * 0: optimization removing unmodified potential rename source okay\n+\t * 2 or 4: optimization okay, but must check for files added to dir\n+\t * 7: optimization forbidden; need rename source in case of dir rename\n+\t */\n+\tunsigned dir_rename_mask:3;\n+\n \t/*\n \t * callback_data_*: supporting data structures for alternate traversal\n \t *\n@@ -419,6 +427,8 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\tstrmap_clear(&opti->output, 0);\n \t}\n \n+\trenames->dir_rename_mask = 0;\n+\n \t/* Clean out callback_data as well. */\n \tFREE_AND_NULL(renames->callback_data);\n \trenames->callback_data_nr = renames->callback_data_alloc = 0;\n@@ -520,12 +530,16 @@ static int traverse_trees_wrapper_callback(int n,\n {\n \tstruct merge_options *opt = info->data;\n \tstruct rename_info *renames = &opt->priv->renames;\n+\tunsigned filemask = mask & ~dirmask;\n \n \tassert(n==3);\n \n \tif (!renames->callback_data_traverse_path)\n \t\trenames->callback_data_traverse_path = xstrdup(info->traverse_path);\n \n+\tif (filemask && filemask == renames->dir_rename_mask)\n+\t\trenames->dir_rename_mask = 0x07;\n+\n \tALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,\n \t\t renames->callback_data_alloc);\n \trenames->callback_data[renames->callback_data_nr].mask = mask;\n@@ -544,7 +558,6 @@ static int traverse_trees_wrapper_callback(int n,\n * additional details before the \"real\" traversal\n * - loop through the saved entries and call the original callback on them\n */\n-MAYBE_UNUSED\n static int traverse_trees_wrapper(struct index_state *istate,\n \t\t\t\t int n,\n \t\t\t\t struct tree_desc *t,\n@@ -556,6 +569,8 @@ static int traverse_trees_wrapper(struct index_state *istate,\n \tstruct merge_options *opt = info->data;\n \tstruct rename_info *renames = &opt->priv->renames;\n \n+\tassert(renames->dir_rename_mask == 2 || renames->dir_rename_mask == 4);\n+\n \told_callback_data_traverse_path = renames->callback_data_traverse_path;\n \told_fn = info->fn;\n \told_offset = renames->callback_data_nr;\n@@ -648,7 +663,8 @@ static void add_pair(struct merge_options *opt,\n \t\t const char *pathname,\n \t\t unsigned side,\n \t\t unsigned is_add /* if false, is_delete */,\n-\t\t unsigned match_mask)\n+\t\t unsigned match_mask,\n+\t\t unsigned dir_rename_mask)\n {\n \tstruct diff_filespec *one, *two;\n \tstruct rename_info *renames = &opt->priv->renames;\n@@ -656,7 +672,7 @@ static void add_pair(struct merge_options *opt,\n \n \tif (!is_add) {\n \t\tunsigned content_relevant = (match_mask == 0);\n-\t\tunsigned location_relevant = 1; /* FIXME: compute this */\n+\t\tunsigned location_relevant = (dir_rename_mask == 0x07);\n \n \t\tif (content_relevant || location_relevant)\n \t\t\tstrset_add(&renames->relevant_sources[side], pathname);\n@@ -680,6 +696,36 @@ static void collect_rename_info(struct merge_options *opt,\n \tstruct rename_info *renames = &opt->priv->renames;\n \tunsigned side;\n \n+\t/*\n+\t * Update dir_rename_mask (determines ignore-rename-source validity)\n+\t *\n+\t * dir_rename_mask helps us keep track of when directory rename\n+\t * detection may be relevant. Basically, whenver a directory is\n+\t * removed on one side of history, and a file is added to that\n+\t * directory on the other side of history, directory rename\n+\t * detection is relevant (meaning we have to detect renames for all\n+\t * files within that directory to deduce where the directory\n+\t * moved). Also, whenever a directory needs directory rename\n+\t * detection, due to the \"majority rules\" choice for where to move\n+\t * it (see t6423 testcase 1f), we also need to detect renames for\n+\t * all files within subdirectories of that directory as well.\n+\t *\n+\t * Here we haven't looked at files within the directory yet, we are\n+\t * just looking at the directory itself. So, if we aren't yet in\n+\t * a case where a parent directory needed directory rename detection\n+\t * (i.e. dir_rename_mask != 0x07), and if the directory was removed\n+\t * on one side of history, record the mask of the other side of\n+\t * history in dir_rename_mask.\n+\t */\n+\tif (renames->dir_rename_mask != 0x07 &&\n+\t (dirmask == 3 || dirmask == 5)) {\n+\t\t/* simple sanity check */\n+\t\tassert(renames->dir_rename_mask == 0 ||\n+\t\t renames->dir_rename_mask == (dirmask & ~1));\n+\t\t/* update dir_rename_mask; have it record mask of new side */\n+\t\trenames->dir_rename_mask = (dirmask & ~1);\n+\t}\n+\n \t/* Update dirs_removed, as needed */\n \tif (dirmask == 1 || dirmask == 3 || dirmask == 5) {\n \t\t/* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */\n@@ -699,12 +745,14 @@ static void collect_rename_info(struct merge_options *opt,\n \t\t/* Check for deletion on side */\n \t\tif ((filemask & 1) && !(filemask & side_mask))\n \t\t\tadd_pair(opt, names, fullname, side, 0 /* delete */,\n-\t\t\t\t match_mask & filemask);\n+\t\t\t\t match_mask & filemask,\n+\t\t\t\t renames->dir_rename_mask);\n \n \t\t/* Check for addition on side */\n \t\tif (!(filemask & 1) && (filemask & side_mask))\n \t\t\tadd_pair(opt, names, fullname, side, 1 /* add */,\n-\t\t\t\t match_mask & filemask);\n+\t\t\t\t match_mask & filemask,\n+\t\t\t\t renames->dir_rename_mask);\n \t}\n }\n \n@@ -722,12 +770,14 @@ static int collect_merge_info_callback(int n,\n \t */\n \tstruct merge_options *opt = info->data;\n \tstruct merge_options_internal *opti = opt->priv;\n+\tstruct rename_info *renames = &opt->priv->renames;\n \tstruct string_list_item pi; /* Path Info */\n \tstruct conflict_info *ci; /* typed alias to pi.util (which is void*) */\n \tstruct name_entry *p;\n \tsize_t len;\n \tchar *fullpath;\n \tconst char *dirname = opti->current_dir_name;\n+\tunsigned prev_dir_rename_mask = renames->dir_rename_mask;\n \tunsigned filemask = mask & ~dirmask;\n \tunsigned match_mask = 0; /* will be updated below */\n \tunsigned mbase_null = !(mask & 1);\n@@ -868,8 +918,13 @@ static int collect_merge_info_callback(int n,\n \n \t\toriginal_dir_name = opti->current_dir_name;\n \t\topti->current_dir_name = pi.string;\n-\t\tret = traverse_trees(NULL, 3, t, &newinfo);\n+\t\tif (renames->dir_rename_mask == 0 ||\n+\t\t renames->dir_rename_mask == 0x07)\n+\t\t\tret = traverse_trees(NULL, 3, t, &newinfo);\n+\t\telse\n+\t\t\tret = traverse_trees_wrapper(NULL, 3, t, &newinfo);\n \t\topti->current_dir_name = original_dir_name;\n+\t\trenames->dir_rename_mask = prev_dir_rename_mask;\n \n \t\tfor (i = MERGE_BASE; i <= MERGE_SIDE2; i++)\n \t\t\tfree(buf[i]);\n-- \ngitgitgadget\n\n"},{"id":"418558","messageId":"c443ba8abb89458cf2b883d8777fb3f703a90ff9.1615248599.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"[PATCH v2 8/8] diffcore-rename: avoid doing basename comparisons for irrelevant sources","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-09T00:09:59Z","receivedAt":"2021-03-09T00:10:59Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe basename comparison optimization implemented in\nfind_basename_matches() is very beneficial since it allows a source to\nsometimes only be compared with one other file instead of N other files.\nWhen a match is found, both a source and destination can be removed from\nthe matrix of inexact rename comparisons. In contrast, the irrelevant\nsource optimization only allows us to remove a source from the matrix of\ninexact rename comparisons...but it has the advantage of allowing a\nsource file to not even be loaded into memory at all and be compared to\n0 other files. Generally, not even comparing is a bigger performance\nwin, so when both optimizations could apply, prefer to use the\nirrelevant-source optimization.\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: 5.708 s ± 0.111 s 5.680 s ± 0.096 s\n mega-renames: 102.171 s ± 0.440 s 13.812 s ± 0.162 s\n just-one-mega: 3.471 s ± 0.015 s 506.0 ms ± 3.9 ms\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 37 +++++++++++++++++++++++++++++++++----\n 1 file changed, 33 insertions(+), 4 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 7f6115fd9018..e8508541be14 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -527,6 +527,7 @@ static void update_dir_rename_counts(struct dir_rename_info *info,\n }\n \n static void initialize_dir_rename_info(struct dir_rename_info *info,\n+\t\t\t\t struct strset *relevant_sources,\n \t\t\t\t struct strset *dirs_removed,\n \t\t\t\t struct strmap *dir_rename_count)\n {\n@@ -534,7 +535,7 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstruct strmap_entry *entry;\n \tint i;\n \n-\tif (!dirs_removed) {\n+\tif (!dirs_removed && !relevant_sources) {\n \t\tinfo->setup = 0;\n \t\treturn;\n \t}\n@@ -549,7 +550,20 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstrmap_init_with_options(&info->dir_rename_guess, NULL, 0);\n \n \t/* Setup info->relevant_source_dirs */\n-\tinfo->relevant_source_dirs = dirs_removed;\n+\tinfo->relevant_source_dirs = NULL;\n+\tif (dirs_removed || !relevant_sources) {\n+\t\tinfo->relevant_source_dirs = dirs_removed; /* might be NULL */\n+\t} else {\n+\t\tinfo->relevant_source_dirs = xmalloc(sizeof(struct strintmap));\n+\t\tstrset_init(info->relevant_source_dirs);\n+\t\tstrset_for_each_entry(relevant_sources, &iter, entry) {\n+\t\t\tchar *dirname = get_dirname(entry->key);\n+\t\t\tif (!dirs_removed ||\n+\t\t\t strset_contains(dirs_removed, dirname))\n+\t\t\t\tstrset_add(info->relevant_source_dirs, dirname);\n+\t\t\tfree(dirname);\n+\t\t}\n+\t}\n \n \t/*\n \t * Loop setting up both info->idx_map, and doing setup of\n@@ -627,6 +641,13 @@ static void cleanup_dir_rename_info(struct dir_rename_info *info,\n \t/* dir_rename_guess */\n \tstrmap_clear(&info->dir_rename_guess, 1);\n \n+\t/* relevant_source_dirs */\n+\tif (info->relevant_source_dirs &&\n+\t info->relevant_source_dirs != dirs_removed) {\n+\t\tstrset_clear(info->relevant_source_dirs);\n+\t\tFREE_AND_NULL(info->relevant_source_dirs);\n+\t}\n+\n \t/* dir_rename_count */\n \tif (!keep_dir_rename_count) {\n \t\tpartial_clear_dir_rename_count(info->dir_rename_count);\n@@ -749,6 +770,7 @@ static int idx_possible_rename(char *filename, struct dir_rename_info *info)\n static int find_basename_matches(struct diff_options *options,\n \t\t\t\t int minimum_score,\n \t\t\t\t struct dir_rename_info *info,\n+\t\t\t\t struct strset *relevant_sources,\n \t\t\t\t struct strset *dirs_removed)\n {\n \t/*\n@@ -839,6 +861,11 @@ static int find_basename_matches(struct diff_options *options,\n \t\tintptr_t src_index;\n \t\tintptr_t dst_index;\n \n+\t\t/* Skip irrelevant sources */\n+\t\tif (relevant_sources &&\n+\t\t !strset_contains(relevant_sources, filename))\n+\t\t\tcontinue;\n+\n \t\t/*\n \t\t * If the basename is unique among remaining sources, then\n \t\t * src_index will equal 'i' and we can attempt to match it\n@@ -1164,7 +1191,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \n \t\t/* Preparation for basename-driven matching. */\n \t\ttrace2_region_enter(\"diff\", \"dir rename setup\", options->repo);\n-\t\tinitialize_dir_rename_info(&info,\n+\t\tinitialize_dir_rename_info(&info, relevant_sources,\n \t\t\t\t\t dirs_removed, dir_rename_count);\n \t\ttrace2_region_leave(\"diff\", \"dir rename setup\", options->repo);\n \n@@ -1172,7 +1199,9 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\ttrace2_region_enter(\"diff\", \"basename matches\", options->repo);\n \t\trename_count += find_basename_matches(options,\n \t\t\t\t\t\t min_basename_score,\n-\t\t\t\t\t\t &info, dirs_removed);\n+\t\t\t\t\t\t &info,\n+\t\t\t\t\t\t relevant_sources,\n+\t\t\t\t\t\t dirs_removed);\n \t\ttrace2_region_leave(\"diff\", \"basename matches\", options->repo);\n \n \t\t/*\n-- \ngitgitgadget\n"},{"id":"418559","messageId":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.git.1614484707.gitgitgadget@gmail.com","subject":"[PATCH v2 0/8] Optimization batch 9: avoid detecting irrelevant renames","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-09T00:09:51Z","receivedAt":"2021-03-09T00:10:59Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends textually on ort-perf-batch-8, but semantically it's\nalmost completely unrelated and can be reviewed without any familiarity with\nany of the previous patch series.\n\nThere are no changes since v1; it's just a resend just over a week later to\nbump it so it isn't lost.\n\n=== Basic Optimization idea ===\n\nThis series determines paths which meet special cases where detection of\nrenames is irrelevant, where the irrelevance is due to the fact that the\nmerge machinery will arrive at the same result regardless of whether a\nrename is detected for any of those paths. This series represents\n\"Optimization #2\" from my Git Merge 2020 talk[1], though this series has\nsome improvements on the optimization relative to what I had at that time.\n\nThe basic idea here is:\n\nWe only need expensive rename detection on the subset of files changed on\nboth sides of history (for the most part).\n\nThis is because:\n\n 1. The primary reason for rename detection in merges is enabling three-way\n content merges\n 2. The purpose of three-way content merges is reconciling changes when\n\nboth sides of history modified some file 3. If a file was only modified by\nthe side that renamed the file, then detecting the rename is irrelevant;\nwe'll get the same answer without knowing about the rename. 4. (Well...there\nare rare cases where we need the rename for reasons other than three-way\ncontent merges. Patch 5 explains those.)\n\nSince commits being rebased or cherry-picked tend to only modify a few\nfiles, this optimization tends to be particularly effective for rebases and\ncherry-picks.\n\nBasing rename detection on what the other side of history did to a file\nmeans that extra information needs to be fed from merge-ort to\ndiffcore-rename in order to take advantage of such an optimization.\n\n=== Comparison to previous series ===\n\nThis series differs from my two previous optimizations[2][3] (focusing on\nbasename-guided rename detection) in two important aspects:\n\n * there are no behavioral changes (there is no heuristic involved)\n * this optimization is merge specific (it does not help the diff/status/log\n family of commands, just merge/rebase/cherry-pick and such)\n\n=== Results ===\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28), the\nchanges in just this series improves the performance as follows:\n\n Before Series After Series\nno-renames: 12.596 s ± 0.061 s 5.680 s ± 0.096 s\nmega-renames: 130.465 s ± 0.259 s 13.812 s ± 0.162 s\njust-one-mega: 3.958 s ± 0.010 s 506.0 ms ± 3.9 ms\n\n\nHowever, interestingly, if we had ignored the basename-guided rename\ndetection optimizations[2][3], then this optimization series would have\nimproved the performance as follows:\n\n Before Basename Series After Just This Series\nno-renames: 13.815 s ± 0.062 s 5.728 s ± 0.104 s\nmega-renames: 1799.937 s ± 0.493 s 18.213 s ± 0.139 s\njust-one-mega 51.289 s ± 0.019 s 891.9 ms ± 7.0 ms\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=== Competition between optimizations ===\n\nWe now have three major rename-related optimizations:\n\n * exact rename detection\n * basename-guided rename detection[2][3]\n * skip-because-unnecessary (this series)\n\nIt is possible for all three to potentially apply for specific paths (they\ndo for the majority of renamed paths in our testcases), but we cannot use\nmore than one for any given path. It turns out that the priority we give\neach optimization is very important and can drastically affect performance.\nWe get best results by prioritizing them as follows:\n\n 1. exact rename detection\n 2. skip-because-unnecessary\n 3. basename-guided rename detection\n\nSome of the commit messages discuss this ordering and another minor variant\nof the skip-because-unnecessary optimization that was tried (and resulted in\nless effective performance gains than reported here), as well as some of the\npreparatory work over the past few years that this series relies on in order\nto enable this optimization.\n\n=== Near optimal? ===\n\nYou may remember that there was a row labelled \"everything else\" from the\ncommit message of 557ac0350d that represented the maximum possible speed-up\nfrom accelerating rename detection alone; as stated in that commit, those\nrows represented how fast the code could be if we had somehow infinitely\nparallelized the inexact rename detection. However, if you compare those\n\"maximum speedup\" numbers to what we have above, you'll note that the\ninfinitely parallelized inexact rename detection would have been slightly\nslower than the results we have now achieved. (The reason this is possible,\ndespite the fact that we still spend time in rename detection after our\noptimizations, is because we implemented two optimizations outside of\ndiffcore_rename() along the way.) However, this good news does also come\nwith a downside -- it means that our remaining optimization potential is\nsomewhat limited, and subsequent optimization series will have to fight for\nmuch smaller gains.\n\n[1]\nhttps://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf\n[2]\nhttps://lore.kernel.org/git/pull.843.git.1612651937.gitgitgadget@gmail.com/\n[3]\nhttps://lore.kernel.org/git/pull.844.git.1613289544.gitgitgadget@gmail.com/\n\nElijah Newren (8):\n diffcore-rename: enable filtering possible rename sources\n merge-ort: precompute subset of sources for which we need rename\n detection\n merge-ort: add data structures for an alternate tree traversal\n merge-ort: introduce wrappers for alternate tree traversal\n merge-ort: precompute whether directory rename detection is needed\n merge-ort: use relevant_sources to filter possible rename sources\n merge-ort: skip rename detection entirely if possible\n diffcore-rename: avoid doing basename comparisons for irrelevant\n sources\n\n diffcore-rename.c | 63 ++++++++++---\n diffcore.h | 1 +\n merge-ort.c | 236 +++++++++++++++++++++++++++++++++++++++++++++-\n 3 files changed, 285 insertions(+), 15 deletions(-)\n\n\nbase-commit: 4be565c472088d4144063b736308bf2a57331f45\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-845%2Fnewren%2Fort-perf-batch-9-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-845/newren/ort-perf-batch-9-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/845\n\nRange-diff vs v1:\n\n 1: 064fa5de1e20 = 1: dab8e3c6aee5 diffcore-rename: enable filtering possible rename sources\n 2: 69b42a41e83a = 2: 33c231331744 merge-ort: precompute subset of sources for which we need rename detection\n 3: 042ce66011ef = 3: 89b43c9f75a0 merge-ort: add data structures for an alternate tree traversal\n 4: 7673e4c23bbb = 4: 6497050c0012 merge-ort: introduce wrappers for alternate tree traversal\n 5: 8dbf0a452545 = 5: 608d5a4c6ad7 merge-ort: precompute whether directory rename detection is needed\n 6: 6b20977a5a81 = 6: d62fdee45ad3 merge-ort: use relevant_sources to filter possible rename sources\n 7: d5486ab28462 = 7: cd931286f24d merge-ort: skip rename detection entirely if possible\n 8: 8fed92b62f37 = 8: c443ba8abb89 diffcore-rename: avoid doing basename comparisons for irrelevant sources\n\n-- \ngitgitgadget\n"},{"id":"418560","messageId":"cd931286f24d66efbf6b0f0a1f520b58ac468f88.1615248599.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"[PATCH v2 7/8] merge-ort: skip rename detection entirely if possible","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-09T00:09:58Z","receivedAt":"2021-03-09T00:10:59Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ndiffcore_rename_extended() will do a bunch of setup, then check for\nexact renames, then abort before inexact rename detection if there are\nno more sources or destinations that need to be matched. It will\nsometimes be the case, however, that either\n * we start with neither any sources or destinations\n * we start with no *relevant* sources\nIn the first of these two cases, the setup and exact rename detection\nwill be very cheap since there are 0 files to operate on. In the second\ncase, it is quite possible to have thousands of files with none of the\nsource ones being relevant. Avoid calling diffcore_rename_extended() or\neven some of the setup before diffcore_rename_extended() when we can\ndetermine that rename detection is unnecessary.\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: 6.003 s ± 0.048 s 5.708 s ± 0.111 s\n mega-renames: 114.009 s ± 0.236 s 102.171 s ± 0.440 s\n just-one-mega: 3.489 s ± 0.017 s 3.471 s ± 0.015 s\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 45 +++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 45 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 66892c63cee2..8602c7b8936f 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2158,6 +2158,19 @@ static int process_renames(struct merge_options *opt,\n \treturn clean_merge;\n }\n \n+static inline int possible_side_renames(struct rename_info *renames,\n+\t\t\t\t\tunsigned side_index)\n+{\n+\treturn renames->pairs[side_index].nr > 0 &&\n+\t !strset_empty(&renames->relevant_sources[side_index]);\n+}\n+\n+static inline int possible_renames(struct rename_info *renames)\n+{\n+\treturn possible_side_renames(renames, 1) ||\n+\t possible_side_renames(renames, 2);\n+}\n+\n static void resolve_diffpair_statuses(struct diff_queue_struct *q)\n {\n \t/*\n@@ -2194,6 +2207,16 @@ static void detect_regular_renames(struct merge_options *opt,\n \tstruct diff_options diff_opts;\n \tstruct rename_info *renames = &opt->priv->renames;\n \n+\tif (!possible_side_renames(renames, side_index)) {\n+\t\t/*\n+\t\t * No rename detection needed for this side, but we still need\n+\t\t * to make sure 'adds' are marked correctly in case the other\n+\t\t * side had directory renames.\n+\t\t */\n+\t\tresolve_diffpair_statuses(&renames->pairs[side_index]);\n+\t\treturn;\n+\t}\n+\n \trepo_diff_setup(opt->repo, &diff_opts);\n \tdiff_opts.flags.recursive = 1;\n \tdiff_opts.flags.rename_empty = 0;\n@@ -2311,6 +2334,8 @@ static int detect_and_process_renames(struct merge_options *opt,\n \tint need_dir_renames, s, clean = 1;\n \n \tmemset(&combined, 0, sizeof(combined));\n+\tif (!possible_renames(renames))\n+\t\tgoto cleanup;\n \n \ttrace2_region_enter(\"merge\", \"regular renames\", opt->repo);\n \tdetect_regular_renames(opt, MERGE_SIDE1);\n@@ -2345,6 +2370,26 @@ static int detect_and_process_renames(struct merge_options *opt,\n \tclean &= process_renames(opt, &combined);\n \ttrace2_region_leave(\"merge\", \"process renames\", opt->repo);\n \n+\tgoto simple_cleanup; /* collect_renames() handles some of cleanup */\n+\n+cleanup:\n+\t/*\n+\t * Free now unneeded filepairs, which would have been handled\n+\t * in collect_renames() normally but we're about to skip that\n+\t * code...\n+\t */\n+\tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n+\t\tstruct diff_queue_struct *side_pairs;\n+\t\tint i;\n+\n+\t\tside_pairs = &renames->pairs[s];\n+\t\tfor (i = 0; i < side_pairs->nr; ++i) {\n+\t\t\tstruct diff_filepair *p = side_pairs->queue[i];\n+\t\t\tdiff_free_filepair(p);\n+\t\t}\n+\t}\n+\n+simple_cleanup:\n \t/* Free memory for renames->pairs[] and combined */\n \tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n \t\tfree(renames->pairs[s].queue);\n-- \ngitgitgadget\n\n"},{"id":"418659","messageId":"9fce692f-86f9-59c1-07de-1eaabdbcb827@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/8] Optimization batch 9: avoid detecting irrelevant renames","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-03-09T22:08:37Z","receivedAt":"2021-03-09T22:09:32Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:> The basic idea here is:\n> \n> We only need expensive rename detection on the subset of files changed on\n> both sides of history (for the most part).\n> \n> This is because:\n> \n> 1. The primary reason for rename detection in merges is enabling three-way\n> content merges\n> 2. The purpose of three-way content merges is reconciling changes when\n> \n> both sides of history modified some file 3. If a file was only modified by\n> the side that renamed the file, then detecting the rename is irrelevant;\n> we'll get the same answer without knowing about the rename. 4. (Well...there\n> are rare cases where we need the rename for reasons other than three-way\n> content merges. Patch 5 explains those.)\n\nMakes sense. Don't compute information you won't need. I look forward to\ntrying to figure out the special cases here.\n \n> Before Series After Series\n> no-renames: 12.596 s ± 0.061 s 5.680 s ± 0.096 s\n> mega-renames: 130.465 s ± 0.259 s 13.812 s ± 0.162 s\n> just-one-mega: 3.958 s ± 0.010 s 506.0 ms ± 3.9 ms\n\nThese are _very_ impressive numbers for such a \"simple\" idea.\n \n> However, interestingly, if we had ignored the basename-guided rename\n> detection optimizations[2][3], then this optimization series would have\n> improved the performance as follows:\n> \n> Before Basename Series After Just This Series\n> no-renames: 13.815 s ± 0.062 s 5.728 s ± 0.104 s\n> mega-renames: 1799.937 s ± 0.493 s 18.213 s ± 0.139 s\n> just-one-mega 51.289 s ± 0.019 s 891.9 ms ± 7.0 ms\n\nAnd here it is even more impressive. I see that your optimizations are\nhaving combined effects but also are doing valuable things on their\nown.\n\n> We get best results by prioritizing them as follows:\n> \n> 1. exact rename detection\n> 2. skip-because-unnecessary\n> 3. basename-guided rename detection\n\nThis makes sense to me, since even the basename-guided rename is\ndoing some non-trivial work. It would be good to reduce that\neffort.\n\n> it means that our remaining optimization potential is\n> somewhat limited, and subsequent optimization series will have to fight for\n> much smaller gains.\n\nThis is a good place to end up. Let the code rest for a bit after\nwe are done here, and maybe we'll find new cases to care about\nlater. We could chase the long tail forever, but these steps are\na huge accomplishment!\n\nGetting to reading now.\n\n-Stolee\n"},{"id":"418660","messageId":"c646e320-566b-3b53-63d8-a97c6d17c5bd@gmail.com","threadId":"55231","inReplyTo":"dab8e3c6aee5a852ad46c569c0be729d64310ad9.1615248599.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/8] diffcore-rename: enable filtering possible rename sources","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-03-09T22:21:38Z","receivedAt":"2021-03-09T22:22:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:> @@ -1127,9 +1137,10 @@ void diffcore_rename_extended(struct diff_options *options,\n> \t\t/*\n> \t\t * Cull sources:\n> \t\t * - remove ones corresponding to exact renames\n> +\t\t * - remove ones not found in relevant_sources\n> \t\t */\n> \t\ttrace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n> -\t\tremove_unneeded_paths_from_src(want_copies);\n> +\t\tremove_unneeded_paths_from_src(want_copies, relevant_sources);\n> \t\ttrace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n\nIn this case, we are checking for copies. Perhaps there is a reason\nwhy we want to include relevant_sources in that case, so I'll look\nfor it later.\n\n> \t} else {\n> \t\t/* Determine minimum score to match basenames */\n> @@ -1148,7 +1159,7 @@ void diffcore_rename_extended(struct diff_options *options,\n> \t\t * - remove ones involved in renames (found via exact match)\n> \t\t */\n> \t\ttrace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n> -\t\tremove_unneeded_paths_from_src(want_copies);\n> +\t\tremove_unneeded_paths_from_src(want_copies, NULL);\n> \t\ttrace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n> \n> \t\t/* Preparation for basename-driven matching. */\n> @@ -1167,9 +1178,10 @@ void diffcore_rename_extended(struct diff_options *options,\n> \t\t/*\n> \t\t * Cull sources, again:\n> \t\t * - remove ones involved in renames (found via basenames)\n> +\t\t * - remove ones not found in relevant_sources\n> \t\t */\n> \t\ttrace2_region_enter(\"diff\", \"cull basename\", options->repo);\n> -\t\tremove_unneeded_paths_from_src(want_copies);\n> +\t\tremove_unneeded_paths_from_src(want_copies, relevant_sources);\n> \t\ttrace2_region_leave(\"diff\", \"cull basename\", options->repo);\n\nThis seems backwards from your cover letter. You are using the exact renames\n_and_ basename matches to remove the unneeded paths. Why are we not stripping\nout the relevant_sources in the call further up, before we call\nfind_basename_matches()?\n\nThanks,\n-Stolee\n"},{"id":"418661","messageId":"CABPp-BFnkHMd_1roiXL1njJXCP+T-Qm0H2eCTOQiM2qUM7gDBA@mail.gmail.com","threadId":"55231","inReplyTo":"c646e320-566b-3b53-63d8-a97c6d17c5bd@gmail.com","subject":"Re: [PATCH v2 1/8] diffcore-rename: enable filtering possible rename sources","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-03-09T22:40:00Z","receivedAt":"2021-03-09T22:41:20Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Mar 9, 2021 at 2:21 PM Derrick Stolee wrote:\n>\n> On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:> @@ -1127,9 +1137,10 @@ void diffcore_rename_extended(struct diff_options *options,\n> > /*\n> > * Cull sources:\n> > * - remove ones corresponding to exact renames\n> > + * - remove ones not found in relevant_sources\n> > */\n> > trace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n> > - remove_unneeded_paths_from_src(want_copies);\n> > + remove_unneeded_paths_from_src(want_copies, relevant_sources);\n> > trace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n>\n> In this case, we are checking for copies. Perhaps there is a reason\n> why we want to include relevant_sources in that case, so I'll look\n> for it later.\n\nThere is no current caller making use of this. I could have just\nmarked the two options as incompatible and passed NULL here for\nrelevant sources, but...I didn't see a compelling reason to. If some\ncaller wanted copy detection and were only interested in copies from a\nsubset of sources, they could take advantage of relevant_sources in\nthe same way to limit to those paths that are relevant. I guess it\ncomes down to whether you view this as designing the code for future\ntheoretical cases, or explicitly taking steps to limit future\npossibilities. I don't have a strong opinion here, but tried to\nenable other future uses since diffcore-rename.c is used by many other\ncallers too.\n\n> > } else {\n> > /* Determine minimum score to match basenames */\n> > @@ -1148,7 +1159,7 @@ void diffcore_rename_extended(struct diff_options *options,\n> > * - remove ones involved in renames (found via exact match)\n> > */\n> > trace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n> > - remove_unneeded_paths_from_src(want_copies);\n> > + remove_unneeded_paths_from_src(want_copies, NULL);\n> > trace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n> >\n> > /* Preparation for basename-driven matching. */\n> > @@ -1167,9 +1178,10 @@ void diffcore_rename_extended(struct diff_options *options,\n> > /*\n> > * Cull sources, again:\n> > * - remove ones involved in renames (found via basenames)\n> > + * - remove ones not found in relevant_sources\n> > */\n> > trace2_region_enter(\"diff\", \"cull basename\", options->repo);\n> > - remove_unneeded_paths_from_src(want_copies);\n> > + remove_unneeded_paths_from_src(want_copies, relevant_sources);\n> > trace2_region_leave(\"diff\", \"cull basename\", options->repo);\n>\n> This seems backwards from your cover letter. You are using the exact renames\n> _and_ basename matches to remove the unneeded paths. Why are we not stripping\n> out the relevant_sources in the call further up, before we call\n> find_basename_matches()?\n\nYeah, good flag. I should add a comment to the commit message about\nhow these are still needed in initialize_dir_rename_info() for\nbasename-guided directory rename detection...and will also play a role\nin some of the special cases where renames are needed for more than\nthree-way content merges. And add a comment about how by the end of\nthe series, relevant_sources will be passed to find_basename_matches()\nso that it can skip over those paths.\n"},{"id":"418662","messageId":"1898cd73-7ade-45fc-af41-e55cf38d1ab4@gmail.com","threadId":"55231","inReplyTo":"CABPp-BFnkHMd_1roiXL1njJXCP+T-Qm0H2eCTOQiM2qUM7gDBA@mail.gmail.com","subject":"Re: [PATCH v2 1/8] diffcore-rename: enable filtering possible rename sources","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-03-09T22:45:26Z","receivedAt":"2021-03-09T22:46:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/9/2021 5:40 PM, Elijah Newren wrote:\n> On Tue, Mar 9, 2021 at 2:21 PM Derrick Stolee wrote:\n>>\n>> On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:\n>>> @@ -1167,9 +1178,10 @@ void diffcore_rename_extended(struct diff_options *options,\n>>> /*\n>>> * Cull sources, again:\n>>> * - remove ones involved in renames (found via basenames)\n>>> + * - remove ones not found in relevant_sources\n>>> */\n>>> trace2_region_enter(\"diff\", \"cull basename\", options->repo);\n>>> - remove_unneeded_paths_from_src(want_copies);\n>>> + remove_unneeded_paths_from_src(want_copies, relevant_sources);\n>>> trace2_region_leave(\"diff\", \"cull basename\", options->repo);\n>>\n>> This seems backwards from your cover letter. You are using the exact renames\n>> _and_ basename matches to remove the unneeded paths. Why are we not stripping\n>> out the relevant_sources in the call further up, before we call\n>> find_basename_matches()?\n> \n> Yeah, good flag. I should add a comment to the commit message about\n> how these are still needed in initialize_dir_rename_info() for\n> basename-guided directory rename detection...and will also play a role\n> in some of the special cases where renames are needed for more than\n> three-way content merges. And add a comment about how by the end of\n> the series, relevant_sources will be passed to find_basename_matches()\n> so that it can skip over those paths.\n \nAh, so by the end, find_basename_matches() will be coupled to the\nrelevant_sources set directory instead of relying on the culling\nhappening earlier? Interesting. It seems to me like it would be\nbetter to have them be less coupled by relying on the culling\nbefore calling find_basename_matches(), but I'll keep reading to\nsee your good reason for not doing that.\n\nThanks,\n-Stolee\n"},{"id":"418663","messageId":"82be59b5-a930-ddca-c694-14f27a9fbae6@gmail.com","threadId":"55231","inReplyTo":"cd931286f24d66efbf6b0f0a1f520b58ac468f88.1615248599.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 7/8] merge-ort: skip rename detection entirely if possible","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-03-09T22:51:57Z","receivedAt":"2021-03-09T22:52:47Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:> +\tgoto simple_cleanup; /* collect_renames() handles some of cleanup */\n> +\n> +cleanup:\n> +\t/*\n> +\t * Free now unneeded filepairs, which would have been handled\n> +\t * in collect_renames() normally but we're about to skip that\n> +\t * code...\n> +\t */\n\n\"but we're about to skip that code\"\n\nHaven't you skipped it already, earlier in the above part? This should\ninstead say \"but we skipped that code\", right?\n\nThanks,\n-Stolee\n"},{"id":"418664","messageId":"CABPp-BFORhHL5L+zcY0qEFC-Qp4pnKVtWJaMFro-ExYNRyc8Wg@mail.gmail.com","threadId":"55231","inReplyTo":"82be59b5-a930-ddca-c694-14f27a9fbae6@gmail.com","subject":"Re: [PATCH v2 7/8] merge-ort: skip rename detection entirely if possible","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-03-09T22:57:34Z","receivedAt":"2021-03-09T22:58:42Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Mar 9, 2021 at 2:51 PM Derrick Stolee wrote:\n>\n> On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:> + goto simple_cleanup; /* collect_renames() handles some of cleanup */\n> > +\n> > +cleanup:\n> > + /*\n> > + * Free now unneeded filepairs, which would have been handled\n> > + * in collect_renames() normally but we're about to skip that\n> > + * code...\n> > + */\n>\n> \"but we're about to skip that code\"\n>\n> Haven't you skipped it already, earlier in the above part? This should\n> instead say \"but we skipped that code\", right?\n\nOh, indeed. I wonder if I moved that comment around and didn't update\nit. Anyway yes, I'll fix it.\n"},{"id":"418665","messageId":"6bc2af18-dd16-5e41-1f5b-31ab73d7b9d3@gmail.com","threadId":"55231","inReplyTo":"6497050c00126bdeff6880e5a2a52cd7b8457513.1615248599.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 4/8] merge-ort: introduce wrappers for alternate tree traversal","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-03-09T23:06:21Z","receivedAt":"2021-03-09T23:07:25Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n> \n> Add traverse_trees_wrapper() and traverse_trees_wrapper_callback()\n> functions. The former runs traverse_trees() with info->fn set to\n> traverse_trees_wrapper_callback, in order to simply save all the entries\n> without processing or recursing into any of them. This step allows\n> extra computation to be done (e.g. checking some condition across all\n> files) that can be used later. Then, after that is completed, it\n> iterates over all the saved entries and calls the original info->fn\n> callback with the saved data.\n> \n> Currently, this does nothing more than marginally slowing down the tree\n> traversal since we do not take advantage of the opportunity to compute\n> anything special in traverse_trees_wrapper_callback(), and thus the real\n> callback will be called identically as it would have been without this\n> extra wrapper. However, a subsequent commit will add some special\n> computation of some values that the real callback will be able to use.\n\nI'm glad that you use the normal callback in the appropriate case.\n\nIt took me a couple reads to understand this last sentence, but I think\nI'm with you now.\n\n> +\tinfo->traverse_path = renames->callback_data_traverse_path;\n> +\tinfo->fn = old_fn;\n> +\tfor (i = old_offset; i < renames->callback_data_nr; ++i) {\n> +\t\tinfo->fn(n,\n> +\t\t\t renames->callback_data[i].mask,\n> +\t\t\t renames->callback_data[i].dirmask,\n> +\t\t\t renames->callback_data[i].names,\n> +\t\t\t info);\n> +\n\nnit: extraneous newline.\n\nThanks,\n-Stolee\n"},{"id":"418687","messageId":"c4ce57f2-fc02-a70c-5ecb-0911a551192c@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/8] Optimization batch 9: avoid detecting irrelevant renames","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-03-10T15:08:58Z","receivedAt":"2021-03-10T15:09:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:\n> This series depends textually on ort-perf-batch-8, but semantically it's\n> almost completely unrelated and can be reviewed without any familiarity with\n> any of the previous patch series.\n> \n> There are no changes since v1; it's just a resend just over a week later to\n> bump it so it isn't lost.\n> \n> === Basic Optimization idea ===\n> \n> This series determines paths which meet special cases where detection of\n> renames is irrelevant, where the irrelevance is due to the fact that the\n> merge machinery will arrive at the same result regardless of whether a\n> rename is detected for any of those paths. This series represents\n> \"Optimization #2\" from my Git Merge 2020 talk[1], though this series has\n> some improvements on the optimization relative to what I had at that time.\n> \n> The basic idea here is:\n> \n> We only need expensive rename detection on the subset of files changed on\n> both sides of history (for the most part).\n\nI've taken time this morning to re-read some of the patches. I have a\ngrasp on the idea of the optimization and the code looks well presented\nand correct.\n\nThe only issue I have is that there are no additional tests to ensure that\nthese scenarios are being tested and are checked to return the correct\nresults. Naturally, it seems we are not testing the ORT strategy by default,\nand if I do enable it, that causes test failures still.\n\nI wonder how much we should be merging these optimizations before the full\ntest suite can pass with ORT as the default. Then, we can check to see if\nsmall mutations can be caught by the test suite. In particular, everything\nin this optimization seems to revolve around this condition in add_pair():\n\n\t\tif (content_relevant || location_relevant)\n\t\t\tstrset_add(&renames->relevant_sources[side], pathname);\n\nI'd prefer to have test cases that cover all four options for the two boolean\nvalues on this operator. Mostly, I'd like to know that if I delete either side\nof the || operator (or change it to &&) then we would have a test failure.\n\nThanks,\n-Stolee\n"},{"id":"418764","messageId":"3b253f5a63edfac5d4d2f4f60f5c824bcfafead0.1615423111.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","subject":"[PATCH v3 1/8] diffcore-rename: enable filtering possible rename sources","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-11T00:38:24Z","receivedAt":"2021-03-11T00:39:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd the ability to diffcore_rename_extended() to allow external callers\nto declare that they only need renames detected for a subset of source\nfiles, and use that information to skip detecting renames for them.\n\nThere are two important pieces to this optimization that may not be\nobvious at first glance:\n\n * We do not require callers to just filter the filepairs out\n to remove the non-relevant sources, because exact rename detection\n is fast and when it finds a match it can remove both a source and a\n destination whereas the relevant_sources filter can only remove a\n source.\n\n * We need to filter out the source pairs in a preliminary pass instead\n of adding a\n strset_contains(relevant_sources, one->path)\n check within the nested matrix loop. The reason for that is if we\n have 30k renames, doing 30k * 30k = 900M strset_contains() calls\n becomes extraordinarily expensive and defeats the performance gains\n from this change; we only want to do 30k such calls instead.\n\nIf callers pass NULL for relevant_sources, that is special cases to\ntreat all sources as relevant. Since all callers currently pass NULL,\nthis optimization does not yet have any effect. Subsequent commits will\nhave merge-ort compute a set of relevant_sources to restrict which\nsources we detect renames for, and have merge-ort pass that set of\nrelevant_sources to diffcore_rename_extended().\n\nA note about filtering order:\n\nSome may be curious why we don't filter out irrelevant sources at the\nsame time we filter out exact renames. While that technically could be\ndone at this point, there are two reasons to defer it:\n\nFirst, was to reinforce a lesson that was too easy to forget. As I\nmentioned above, in the past I filtered irrelevant sources out before\nexact rename checking, and then discovered that exact renames' ability\nto remove both sources and destinations was an important consideration\nand thus doing the filtering after exact rename checking would speed\nthings up. Then at some point I realized that basename matching could\nalso remove both sources and destinations, and decided to put irrelevant\nsource filtering after basename filtering. That slowed things down a\nlot. But, despite learning about this important ordering, in later\nrestructuring I forgot and made the same mistake of putting the\nfiltering after basename guided rename detection again. So, I have this\nseries of patches structured to do the irrelevant filtering last to\nstart to show how much extra it costs, and then add relevant filtering\nin to find_basename_matches() to show how much it speeds things up.\nBasically, it's a way to reinforce something that apparently was too\neasy to forget, and make sure the commit messages record this lesson.\n\nSecond, the items in the \"relevant_sources\" in this patch series will\ninclude all sources that *might be* relevant. It has to be conservative\nand catch anything that might need a rename, but in the patch series\nafter this one we'll find ways to weed out more of the *might be*\nrelevant ones. Unfortunately, merge-ort does not have sufficient\ninformation to weed those ones out, and there isn't enough information\nat the time of filtering exact renames out to remove the extra ones\neither. It has to be deferred. So the deferral is in part to simplify\nsome later additions.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 26 +++++++++++++++++++-------\n diffcore.h | 1 +\n merge-ort.c | 1 +\n 3 files changed, 21 insertions(+), 7 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1fe902ed2af0..7f6115fd9018 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -991,11 +991,12 @@ static int find_renames(struct diff_score *mx,\n \treturn count;\n }\n \n-static void remove_unneeded_paths_from_src(int detecting_copies)\n+static void remove_unneeded_paths_from_src(int detecting_copies,\n+\t\t\t\t\t struct strset *interesting)\n {\n \tint i, new_num_src;\n \n-\tif (detecting_copies)\n+\tif (detecting_copies && !interesting)\n \t\treturn; /* nothing to remove */\n \tif (break_idx)\n \t\treturn; /* culling incompatible with break detection */\n@@ -1022,12 +1023,18 @@ static void remove_unneeded_paths_from_src(int detecting_copies)\n \t * from rename_src here.\n \t */\n \tfor (i = 0, new_num_src = 0; i < rename_src_nr; i++) {\n+\t\tstruct diff_filespec *one = rename_src[i].p->one;\n+\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\tif (!detecting_copies && one->rename_used)\n+\t\t\tcontinue;\n+\n+\t\t/* If we don't care about the source path, skip it */\n+\t\tif (interesting && !strset_contains(interesting, one->path))\n \t\t\tcontinue;\n \n \t\tif (new_num_src < i)\n@@ -1040,6 +1047,7 @@ static void remove_unneeded_paths_from_src(int detecting_copies)\n }\n \n void diffcore_rename_extended(struct diff_options *options,\n+\t\t\t struct strset *relevant_sources,\n \t\t\t struct strset *dirs_removed,\n \t\t\t struct strmap *dir_rename_count)\n {\n@@ -1060,6 +1068,8 @@ void diffcore_rename_extended(struct diff_options *options,\n \twant_copies = (detect_rename == DIFF_DETECT_COPY);\n \tif (dirs_removed && (break_idx || want_copies))\n \t\tBUG(\"dirs_removed incompatible with break/copy detection\");\n+\tif (break_idx && relevant_sources)\n+\t\tBUG(\"break detection incompatible with source specification\");\n \tif (!minimum_score)\n \t\tminimum_score = DEFAULT_RENAME_SCORE;\n \n@@ -1127,9 +1137,10 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t/*\n \t\t * Cull sources:\n \t\t * - remove ones corresponding to exact renames\n+\t\t * - remove ones not found in relevant_sources\n \t\t */\n \t\ttrace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n-\t\tremove_unneeded_paths_from_src(want_copies);\n+\t\tremove_unneeded_paths_from_src(want_copies, relevant_sources);\n \t\ttrace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n \t} else {\n \t\t/* Determine minimum score to match basenames */\n@@ -1148,7 +1159,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t * - remove ones involved in renames (found via exact match)\n \t\t */\n \t\ttrace2_region_enter(\"diff\", \"cull after exact\", options->repo);\n-\t\tremove_unneeded_paths_from_src(want_copies);\n+\t\tremove_unneeded_paths_from_src(want_copies, NULL);\n \t\ttrace2_region_leave(\"diff\", \"cull after exact\", options->repo);\n \n \t\t/* Preparation for basename-driven matching. */\n@@ -1167,9 +1178,10 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t/*\n \t\t * Cull sources, again:\n \t\t * - remove ones involved in renames (found via basenames)\n+\t\t * - remove ones not found in relevant_sources\n \t\t */\n \t\ttrace2_region_enter(\"diff\", \"cull basename\", options->repo);\n-\t\tremove_unneeded_paths_from_src(want_copies);\n+\t\tremove_unneeded_paths_from_src(want_copies, relevant_sources);\n \t\ttrace2_region_leave(\"diff\", \"cull basename\", options->repo);\n \t}\n \n@@ -1342,5 +1354,5 @@ void diffcore_rename_extended(struct diff_options *options,\n \n void diffcore_rename(struct diff_options *options)\n {\n-\tdiffcore_rename_extended(options, NULL, NULL);\n+\tdiffcore_rename_extended(options, NULL, NULL, NULL);\n }\ndiff --git a/diffcore.h b/diffcore.h\nindex c6ba64abd198..737c93a6cc79 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -166,6 +166,7 @@ void partial_clear_dir_rename_count(struct strmap *dir_rename_count);\n void diffcore_break(struct repository *, int);\n void diffcore_rename(struct diff_options *);\n void diffcore_rename_extended(struct diff_options *options,\n+\t\t\t struct strset *relevant_sources,\n \t\t\t struct strset *dirs_removed,\n \t\t\t struct strmap *dir_rename_count);\n void diffcore_merge_broken(void);\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 467404cc0a35..aba0b9fa54c3 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2029,6 +2029,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_queued_diff = renames->pairs[side_index];\n \ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiffcore_rename_extended(&diff_opts,\n+\t\t\t\t NULL,\n \t\t\t\t &renames->dirs_removed[side_index],\n \t\t\t\t &renames->dir_rename_count[side_index]);\n \ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n-- \ngitgitgadget\n\n"},{"id":"418765","messageId":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"[PATCH v3 0/8] Optimization batch 9: avoid detecting irrelevant renames","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-11T00:38:23Z","receivedAt":"2021-03-11T00:39:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series determines paths which meet special cases where detection of\nrenames is irrelevant, where the irrelevance is due to the fact that the\nmerge machinery will arrive at the same result regardless of whether a\nrename is detected for any of those paths.\n\nChanges since v2:\n\n * Added an extended comment about filtering order to the first patch, to\n address Stolee's question\n * Added a new testcase that will fail if the critical \"if (content_relevant\n || location_relevant)\" check only checks for one of those two or the\n intersection of those two, as suggested by Stolee\n * Fixed the other minor problems Stolee pointed out in his review (stray\n newline, wording of comment)\n\nElijah Newren (8):\n diffcore-rename: enable filtering possible rename sources\n merge-ort: precompute subset of sources for which we need rename\n detection\n merge-ort: add data structures for an alternate tree traversal\n merge-ort: introduce wrappers for alternate tree traversal\n merge-ort: precompute whether directory rename detection is needed\n merge-ort: use relevant_sources to filter possible rename sources\n merge-ort: skip rename detection entirely if possible\n diffcore-rename: avoid doing basename comparisons for irrelevant\n sources\n\n diffcore-rename.c | 63 ++++++--\n diffcore.h | 1 +\n merge-ort.c | 234 +++++++++++++++++++++++++++-\n t/t6423-merge-rename-directories.sh | 71 +++++++++\n 4 files changed, 354 insertions(+), 15 deletions(-)\n\n\nbase-commit: 4be565c472088d4144063b736308bf2a57331f45\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-845%2Fnewren%2Fort-perf-batch-9-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-845/newren/ort-perf-batch-9-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/845\n\nRange-diff vs v2:\n\n 1: dab8e3c6aee5 ! 1: 3b253f5a63ed diffcore-rename: enable filtering possible rename sources\n @@ Commit message\n sources we detect renames for, and have merge-ort pass that set of\n relevant_sources to diffcore_rename_extended().\n \n + A note about filtering order:\n +\n + Some may be curious why we don't filter out irrelevant sources at the\n + same time we filter out exact renames. While that technically could be\n + done at this point, there are two reasons to defer it:\n +\n + First, was to reinforce a lesson that was too easy to forget. As I\n + mentioned above, in the past I filtered irrelevant sources out before\n + exact rename checking, and then discovered that exact renames' ability\n + to remove both sources and destinations was an important consideration\n + and thus doing the filtering after exact rename checking would speed\n + things up. Then at some point I realized that basename matching could\n + also remove both sources and destinations, and decided to put irrelevant\n + source filtering after basename filtering. That slowed things down a\n + lot. But, despite learning about this important ordering, in later\n + restructuring I forgot and made the same mistake of putting the\n + filtering after basename guided rename detection again. So, I have this\n + series of patches structured to do the irrelevant filtering last to\n + start to show how much extra it costs, and then add relevant filtering\n + in to find_basename_matches() to show how much it speeds things up.\n + Basically, it's a way to reinforce something that apparently was too\n + easy to forget, and make sure the commit messages record this lesson.\n +\n + Second, the items in the \"relevant_sources\" in this patch series will\n + include all sources that *might be* relevant. It has to be conservative\n + and catch anything that might need a rename, but in the patch series\n + after this one we'll find ways to weed out more of the *might be*\n + relevant ones. Unfortunately, merge-ort does not have sufficient\n + information to weed those ones out, and there isn't enough information\n + at the time of filtering exact renames out to remove the extra ones\n + either. It has to be deferred. So the deferral is in part to simplify\n + some later additions.\n +\n Signed-off-by: Elijah Newren \n \n ## diffcore-rename.c ##\n 2: 33c231331744 ! 2: d8378b3dde6c merge-ort: precompute subset of sources for which we need rename detection\n @@ Commit message\n found under a different path than in the merge base or on the\n other side of history.\n \n - This commit concentrates just on the three-way content merging; it will\n - punt and mark all sources as needed for directory rename detection, and\n - leave it to future commits to narrow that down more.\n + Add a simple testcase showing the two kinds of reasons renames are\n + relevant; it's a testcase that will only pass if we detect both kinds of\n + needed renames.\n +\n + Other than the testcase added above, this commit concentrates just on\n + the three-way content merging; it will punt and mark all sources as\n + needed for directory rename detection, and leave it to future commits to\n + narrow that down more.\n \n The point of three-way content merging is to reconcile changes made on\n *both* sides of history. What if the file wasn't modified on both\n @@ merge-ort.c: static void merge_start(struct merge_options *opt, struct merge_res\n \t}\n \n \t/*\n +\n + ## t/t6423-merge-rename-directories.sh ##\n +@@ t/t6423-merge-rename-directories.sh: test_expect_merge_algorithm failure success '12f: Trivial directory resolve, cac\n + \t)\n + '\n + \n ++# Testcase 12g, Testcase with two kinds of \"relevant\" renames\n ++# Commit O: somefile_O, subdir/{a_O,b_O}\n ++# Commit A: somefile_A, subdir/{a_O,b_O,c_A}\n ++# Commit B: newfile_B, newdir/{a_B,b_B}\n ++# Expected: newfile_{merged}, newdir/{a_B,b_B,c_A}\n ++\n ++test_setup_12g () {\n ++\ttest_create_repo 12g &&\n ++\t(\n ++\t\tcd 12g &&\n ++\n ++\t\tmkdir -p subdir &&\n ++\t\ttest_write_lines upon a time there was a >somefile &&\n ++\t\ttest_write_lines 1 2 3 4 5 6 7 8 9 10 >subdir/a &&\n ++\t\ttest_write_lines one two three four five six >subdir/b &&\n ++\t\tgit add . &&\n ++\t\ttest_tick &&\n ++\t\tgit commit -m \"O\" &&\n ++\n ++\t\tgit branch O &&\n ++\t\tgit branch A &&\n ++\t\tgit branch B &&\n ++\n ++\t\tgit switch A &&\n ++\t\ttest_write_lines once upon a time there was a >somefile &&\n ++\t\t> subdir/c &&\n ++\t\tgit add somefile subdir/c &&\n ++\t\ttest_tick &&\n ++\t\tgit commit -m \"A\" &&\n ++\n ++\t\tgit checkout B &&\n ++\t\tgit mv somefile newfile &&\n ++\t\tgit mv subdir newdir &&\n ++\t\techo repo >>newfile &&\n ++\t\ttest_write_lines 1 2 3 4 5 6 7 8 9 10 11 >newdir/a &&\n ++\t\ttest_write_lines one two three four five six seven >newdir/b &&\n ++\t\tgit add newfile newdir &&\n ++\t\ttest_tick &&\n ++\t\tgit commit -m \"B\"\n ++\t)\n ++}\n ++\n ++test_expect_success '12g: Testcase with two kinds of \"relevant\" renames' '\n ++\ttest_setup_12g &&\n ++\t(\n ++\t\tcd 12g &&\n ++\n ++\t\tgit checkout A^0 &&\n ++\n ++\t\tgit -c merge.directoryRenames=true merge -s recursive B^0 &&\n ++\n ++\t\ttest_write_lines once upon a time there was a repo >expect &&\n ++\t\ttest_cmp expect newfile &&\n ++\n ++\t\tgit ls-files -s >out &&\n ++\t\ttest_line_count = 4 out &&\n ++\n ++\t\tgit rev-parse >actual \\\n ++\t\t\tHEAD:newdir/a HEAD:newdir/b HEAD:newdir/c &&\n ++\t\tgit rev-parse >expect \\\n ++\t\t\tB:newdir/a B:newdir/b A:subdir/c &&\n ++\t\ttest_cmp expect actual &&\n ++\n ++\t\ttest_must_fail git rev-parse HEAD:subdir/a &&\n ++\t\ttest_must_fail git rev-parse HEAD:subdir/b &&\n ++\t\ttest_must_fail git rev-parse HEAD:subdir/c &&\n ++\t\ttest_path_is_missing subdir/ &&\n ++\t\ttest_path_is_file newdir/c\n ++\t)\n ++'\n ++\n + ###########################################################################\n + # SECTION 13: Checking informational and conflict messages\n + #\n 3: 89b43c9f75a0 = 3: a57cc981608c merge-ort: add data structures for an alternate tree traversal\n 4: 6497050c0012 ! 4: b595245fe902 merge-ort: introduce wrappers for alternate tree traversal\n @@ merge-ort.c: static char *unique_path(struct strmap *existing_paths,\n +\t\t\t renames->callback_data[i].dirmask,\n +\t\t\t renames->callback_data[i].names,\n +\t\t\t info);\n -+\n +\t}\n +\n +\trenames->callback_data_nr = old_offset;\n 5: 608d5a4c6ad7 = 5: dc146a867b16 merge-ort: precompute whether directory rename detection is needed\n 6: d62fdee45ad3 = 6: 375c9b36861b merge-ort: use relevant_sources to filter possible rename sources\n 7: cd931286f24d ! 7: 80a0c27a74ad merge-ort: skip rename detection entirely if possible\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n +cleanup:\n +\t/*\n +\t * Free now unneeded filepairs, which would have been handled\n -+\t * in collect_renames() normally but we're about to skip that\n -+\t * code...\n ++\t * in collect_renames() normally but we skipped that code.\n +\t */\n +\tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n +\t\tstruct diff_queue_struct *side_pairs;\n 8: c443ba8abb89 = 8: 98b0c7de5e70 diffcore-rename: avoid doing basename comparisons for irrelevant sources\n\n-- \ngitgitgadget\n"},{"id":"418766","messageId":"a57cc981608c67b068e1c32a68363c3180cab6e5.1615423112.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","subject":"[PATCH v3 3/8] merge-ort: add data structures for an alternate tree traversal","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-11T00:38:26Z","receivedAt":"2021-03-11T00:39:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn order to determine whether directory rename detection is needed, we\nas a pre-requisite need a way to traverse through all the files in a\ngiven tree before visiting any directories within that tree.\ntraverse_trees() only iterates through the entries in the order they\nappear, so add some data structures that will store all the entries as\nwe iterate through them in traverse_trees(), which will allow us to\nre-traverse them in our desired order.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 26 ++++++++++++++++++++++++++\n 1 file changed, 26 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 83aa4c08121f..d49cfa8b030b 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -51,6 +51,12 @@ enum merge_side {\n \tMERGE_SIDE2 = 2\n };\n \n+struct traversal_callback_data {\n+\tunsigned long mask;\n+\tunsigned long dirmask;\n+\tstruct name_entry names[3];\n+};\n+\n struct rename_info {\n \t/*\n \t * All variables that are arrays of size 3 correspond to data tracked\n@@ -102,6 +108,22 @@ struct rename_info {\n \t */\n \tstruct strset relevant_sources[3];\n \n+\t/*\n+\t * callback_data_*: supporting data structures for alternate traversal\n+\t *\n+\t * We sometimes need to be able to traverse through all the files\n+\t * in a given tree before all immediate subdirectories within that\n+\t * tree. Since traverse_trees() doesn't do that naturally, we have\n+\t * a traverse_trees_wrapper() that stores any immediate\n+\t * subdirectories while traversing files, then traverses the\n+\t * immediate subdirectories later. These callback_data* variables\n+\t * store the information for the subdirectories so that we can do\n+\t * that traversal order.\n+\t */\n+\tstruct traversal_callback_data *callback_data;\n+\tint callback_data_nr, callback_data_alloc;\n+\tchar *callback_data_traverse_path;\n+\n \t/*\n \t * needed_limit: value needed for inexact rename detection to run\n \t *\n@@ -396,6 +418,10 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\t}\n \t\tstrmap_clear(&opti->output, 0);\n \t}\n+\n+\t/* Clean out callback_data as well. */\n+\tFREE_AND_NULL(renames->callback_data);\n+\trenames->callback_data_nr = renames->callback_data_alloc = 0;\n }\n \n static int err(struct merge_options *opt, const char *err, ...)\n-- \ngitgitgadget\n\n"},{"id":"418767","messageId":"dc146a867b16cefeee71104f1967c5d325f5ffee.1615423112.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","subject":"[PATCH v3 5/8] merge-ort: precompute whether directory rename detection is needed","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-11T00:38:28Z","receivedAt":"2021-03-11T00:39:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe point of directory rename detection is that if one side of history\nrenames a directory, and the other side adds new files under the old\ndirectory, then the merge can move those new files into the new\ndirectory. This leads to the following important observation:\n\n * If the other side does not add any new files under the old\n directory, we do not need to detect any renames for that directory.\n\nSimilarly, directory rename detection had an important requirement:\n\n * If a directory still exists on one side of history, it has not been\n renamed on that side of history. (See section 4 of t6423 or\n Documentation/technical/directory-rename-detection.txt for more\n details).\n\nUsing these two bits of information, we note that directory rename\ndetection is only needed in cases where (1) directories exist in the\nmerge base and on one side of history (i.e. dirmask == 3 or dirmask ==\n5), and (2) where there is some new file added to that directory on the\nside where it still exists (thus where the file has filemask == 2 or\nfilemask == 4, respectively). This has to be done in two steps, because\nwe have the dirmask when we are first considering the directory, and\nwon't get the filemasks for the files within it until we recurse into\nthat directory. So, we save\n dir_rename_mask = dirmask - 1\nwhen we hit a directory that is missing on one side, and then later look\nfor cases of\n filemask == dir_rename_mask\n\nOne final note is that as soon as we hit a directory that needs\ndirectory rename detection, we will need to detect renames in all\nsubdirectories of that directory as well due to the \"majority rules\"\ndecision when files are renamed into different directory hierarchies.\nWe arbitrarily use the special value of 0x07 to record when we've hit\nsuch a directory.\n\nThe combination of all the above mean that we introduce a variable\nnamed dir_rename_mask (couldn't think of a better name) which has one\nof the following values as we traverse into a directory:\n * 0x00: directory rename detection not needed\n * 0x02 or 0x04: directory rename detection only needed if files added\n * 0x07: directory rename detection definitely needed\n\nWe then pass this value through to add_pairs() so that it can mark\nlocation_relevant as true only when dir_rename_mask is 0x07.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++-----\n 1 file changed, 61 insertions(+), 6 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex f8f7d06d481a..5840832cf3ed 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -108,6 +108,14 @@ struct rename_info {\n \t */\n \tstruct strset relevant_sources[3];\n \n+\t/*\n+\t * dir_rename_mask:\n+\t * 0: optimization removing unmodified potential rename source okay\n+\t * 2 or 4: optimization okay, but must check for files added to dir\n+\t * 7: optimization forbidden; need rename source in case of dir rename\n+\t */\n+\tunsigned dir_rename_mask:3;\n+\n \t/*\n \t * callback_data_*: supporting data structures for alternate traversal\n \t *\n@@ -419,6 +427,8 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\tstrmap_clear(&opti->output, 0);\n \t}\n \n+\trenames->dir_rename_mask = 0;\n+\n \t/* Clean out callback_data as well. */\n \tFREE_AND_NULL(renames->callback_data);\n \trenames->callback_data_nr = renames->callback_data_alloc = 0;\n@@ -520,12 +530,16 @@ static int traverse_trees_wrapper_callback(int n,\n {\n \tstruct merge_options *opt = info->data;\n \tstruct rename_info *renames = &opt->priv->renames;\n+\tunsigned filemask = mask & ~dirmask;\n \n \tassert(n==3);\n \n \tif (!renames->callback_data_traverse_path)\n \t\trenames->callback_data_traverse_path = xstrdup(info->traverse_path);\n \n+\tif (filemask && filemask == renames->dir_rename_mask)\n+\t\trenames->dir_rename_mask = 0x07;\n+\n \tALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,\n \t\t renames->callback_data_alloc);\n \trenames->callback_data[renames->callback_data_nr].mask = mask;\n@@ -544,7 +558,6 @@ static int traverse_trees_wrapper_callback(int n,\n * additional details before the \"real\" traversal\n * - loop through the saved entries and call the original callback on them\n */\n-MAYBE_UNUSED\n static int traverse_trees_wrapper(struct index_state *istate,\n \t\t\t\t int n,\n \t\t\t\t struct tree_desc *t,\n@@ -556,6 +569,8 @@ static int traverse_trees_wrapper(struct index_state *istate,\n \tstruct merge_options *opt = info->data;\n \tstruct rename_info *renames = &opt->priv->renames;\n \n+\tassert(renames->dir_rename_mask == 2 || renames->dir_rename_mask == 4);\n+\n \told_callback_data_traverse_path = renames->callback_data_traverse_path;\n \told_fn = info->fn;\n \told_offset = renames->callback_data_nr;\n@@ -647,7 +662,8 @@ static void add_pair(struct merge_options *opt,\n \t\t const char *pathname,\n \t\t unsigned side,\n \t\t unsigned is_add /* if false, is_delete */,\n-\t\t unsigned match_mask)\n+\t\t unsigned match_mask,\n+\t\t unsigned dir_rename_mask)\n {\n \tstruct diff_filespec *one, *two;\n \tstruct rename_info *renames = &opt->priv->renames;\n@@ -655,7 +671,7 @@ static void add_pair(struct merge_options *opt,\n \n \tif (!is_add) {\n \t\tunsigned content_relevant = (match_mask == 0);\n-\t\tunsigned location_relevant = 1; /* FIXME: compute this */\n+\t\tunsigned location_relevant = (dir_rename_mask == 0x07);\n \n \t\tif (content_relevant || location_relevant)\n \t\t\tstrset_add(&renames->relevant_sources[side], pathname);\n@@ -679,6 +695,36 @@ static void collect_rename_info(struct merge_options *opt,\n \tstruct rename_info *renames = &opt->priv->renames;\n \tunsigned side;\n \n+\t/*\n+\t * Update dir_rename_mask (determines ignore-rename-source validity)\n+\t *\n+\t * dir_rename_mask helps us keep track of when directory rename\n+\t * detection may be relevant. Basically, whenver a directory is\n+\t * removed on one side of history, and a file is added to that\n+\t * directory on the other side of history, directory rename\n+\t * detection is relevant (meaning we have to detect renames for all\n+\t * files within that directory to deduce where the directory\n+\t * moved). Also, whenever a directory needs directory rename\n+\t * detection, due to the \"majority rules\" choice for where to move\n+\t * it (see t6423 testcase 1f), we also need to detect renames for\n+\t * all files within subdirectories of that directory as well.\n+\t *\n+\t * Here we haven't looked at files within the directory yet, we are\n+\t * just looking at the directory itself. So, if we aren't yet in\n+\t * a case where a parent directory needed directory rename detection\n+\t * (i.e. dir_rename_mask != 0x07), and if the directory was removed\n+\t * on one side of history, record the mask of the other side of\n+\t * history in dir_rename_mask.\n+\t */\n+\tif (renames->dir_rename_mask != 0x07 &&\n+\t (dirmask == 3 || dirmask == 5)) {\n+\t\t/* simple sanity check */\n+\t\tassert(renames->dir_rename_mask == 0 ||\n+\t\t renames->dir_rename_mask == (dirmask & ~1));\n+\t\t/* update dir_rename_mask; have it record mask of new side */\n+\t\trenames->dir_rename_mask = (dirmask & ~1);\n+\t}\n+\n \t/* Update dirs_removed, as needed */\n \tif (dirmask == 1 || dirmask == 3 || dirmask == 5) {\n \t\t/* absent_mask = 0x07 - dirmask; sides = absent_mask/2 */\n@@ -698,12 +744,14 @@ static void collect_rename_info(struct merge_options *opt,\n \t\t/* Check for deletion on side */\n \t\tif ((filemask & 1) && !(filemask & side_mask))\n \t\t\tadd_pair(opt, names, fullname, side, 0 /* delete */,\n-\t\t\t\t match_mask & filemask);\n+\t\t\t\t match_mask & filemask,\n+\t\t\t\t renames->dir_rename_mask);\n \n \t\t/* Check for addition on side */\n \t\tif (!(filemask & 1) && (filemask & side_mask))\n \t\t\tadd_pair(opt, names, fullname, side, 1 /* add */,\n-\t\t\t\t match_mask & filemask);\n+\t\t\t\t match_mask & filemask,\n+\t\t\t\t renames->dir_rename_mask);\n \t}\n }\n \n@@ -721,12 +769,14 @@ static int collect_merge_info_callback(int n,\n \t */\n \tstruct merge_options *opt = info->data;\n \tstruct merge_options_internal *opti = opt->priv;\n+\tstruct rename_info *renames = &opt->priv->renames;\n \tstruct string_list_item pi; /* Path Info */\n \tstruct conflict_info *ci; /* typed alias to pi.util (which is void*) */\n \tstruct name_entry *p;\n \tsize_t len;\n \tchar *fullpath;\n \tconst char *dirname = opti->current_dir_name;\n+\tunsigned prev_dir_rename_mask = renames->dir_rename_mask;\n \tunsigned filemask = mask & ~dirmask;\n \tunsigned match_mask = 0; /* will be updated below */\n \tunsigned mbase_null = !(mask & 1);\n@@ -867,8 +917,13 @@ static int collect_merge_info_callback(int n,\n \n \t\toriginal_dir_name = opti->current_dir_name;\n \t\topti->current_dir_name = pi.string;\n-\t\tret = traverse_trees(NULL, 3, t, &newinfo);\n+\t\tif (renames->dir_rename_mask == 0 ||\n+\t\t renames->dir_rename_mask == 0x07)\n+\t\t\tret = traverse_trees(NULL, 3, t, &newinfo);\n+\t\telse\n+\t\t\tret = traverse_trees_wrapper(NULL, 3, t, &newinfo);\n \t\topti->current_dir_name = original_dir_name;\n+\t\trenames->dir_rename_mask = prev_dir_rename_mask;\n \n \t\tfor (i = MERGE_BASE; i <= MERGE_SIDE2; i++)\n \t\t\tfree(buf[i]);\n-- \ngitgitgadget\n\n"},{"id":"418768","messageId":"d8378b3dde6c28e70f24c689bbfac6abe731f9cf.1615423111.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","subject":"[PATCH v3 2/8] merge-ort: precompute subset of sources for which we need rename detection","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-11T00:38:25Z","receivedAt":"2021-03-11T00:39:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nrename detection works by trying to pair all file deletions (or\n\"sources\") with all file additions (or \"destinations\"), checking\nsimilarity, and then marking the sufficiently similar ones as renames.\nThis can be expensive if there are many sources and destinations on a\ngiven side of history as it results in an N x M comparison matrix.\nHowever, there are many cases where we can compute in advance that\ndetecting renames for some of the sources provides no useful information\nand thus that we can exclude those sources from the matrix.\n\nTo see why, first note that the merge machinery uses detected renames in\ntwo ways:\n\n * directory rename detection: when one side of history renames a\n directory, and the other side of history adds new files to that\n directory, we want to be able to warn the user about the need to\n chose whether those new files stay in the old directory or move\n to the new one.\n\n * three-way content merging: in order to do three-way content merging\n of files, we need three different file versions. If one side of\n history renamed a file, then some of the content for the file is\n found under a different path than in the merge base or on the\n other side of history.\n\nAdd a simple testcase showing the two kinds of reasons renames are\nrelevant; it's a testcase that will only pass if we detect both kinds of\nneeded renames.\n\nOther than the testcase added above, this commit concentrates just on\nthe three-way content merging; it will punt and mark all sources as\nneeded for directory rename detection, and leave it to future commits to\nnarrow that down more.\n\nThe point of three-way content merging is to reconcile changes made on\n*both* sides of history. What if the file wasn't modified on both\nsides? There are two possibilities:\n\n * If it wasn't modified on the renamed side:\n -> then we get to do exact rename detection, which is cheap.\n\n * If it wasn't modified on the unrenamed side:\n -> then detection of a rename for that source file is irrelevant\n\nThat latter claim might be surprising at first, so let's walk through a\ncase to show why rename detection for that source file is irrelevant.\nLet's use two filenames, old.c & new.c, with the following abbreviated\nobject ids (and where the value '000000' is used to denote that the file\nis missing in that commit):\n\n old.c new.c\n MERGE_BASE: 01d01d 000000\n MERGE_SIDE1: 01d01d 000000\n MERGE_SIDE2: 000000 5e1ec7\n\nIf the rename *isn't* detected:\n then old.c looks like it was unmodified on one side and deleted on\n the other and should thus be removed. new.c looks like a new file we\n should keep as-is.\n\nIf the rename *is* detected:\n then a three-way content merge is done. Since the version of the\n file in MERGE_BASE and MERGE_SIDE1 are identical, the three-way merge\n will produce exactly the version of the file whose abbreviated\n object id is 5e1ec7. It will record that file at the path new.c,\n while removing old.c from the directory.\n\nNote that these two results are identical -- a single file named 'new.c'\nwith object id 5e1ec7. In other words, it doesn't matter if the rename\nis detected in the case where the file is unmodified on the unrenamed\nside.\n\nUse this information to compute whether we need rename detection for\neach source created in add_pair().\n\nIt's probably worth noting that there used to be a few other edge or\ncorner cases besides three-way content merges and directory rename\ndetection where lack of rename detection could have affected the result,\nbut those cases actually highlighted where conflict resolution methods\nwere not consistent with each other. Fixing those inconsistencies were\nthus critically important to enabling this optimization. That work\ninvolved the following:\n\n * bringing consistency to add/add, rename/add, and rename/rename\n conflict types, as done back in the topic merged at commit\n ac193e0e0a (\"Merge branch 'en/merge-path-collision'\", 2019-01-04),\n and further extended in commits 2a7c16c980 (\"t6422, t6426: be more\n flexible for add/add conflicts involving renames\", 2020-08-10) and\n e8eb99d4a6 (\"t642[23]: be more flexible for add/add conflicts\n involving pair renames\", 2020-08-10)\n\n * making rename/delete more consistent with modify/delete\n as done in commits 1f3c9ba707 (\"t6425: be more flexible with\n rename/delete conflict messages\", 2020-08-10) and 727c75b23f\n (\"t6404, t6423: expect improved rename/delete handling in ort\n backend\", 2020-10-26)\n\nSince the set of relevant_sources we compute has not yet been narrowed\ndown for directory rename detection, we do not pass it to\ndiffcore_rename_extended() yet. That will be done after subsequent\ncommits narrow down the list of relevant_sources needed for directory\nrename detection reasons.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 35 ++++++++++++--\n t/t6423-merge-rename-directories.sh | 71 +++++++++++++++++++++++++++++\n 2 files changed, 103 insertions(+), 3 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex aba0b9fa54c3..83aa4c08121f 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -88,6 +88,20 @@ struct rename_info {\n \t */\n \tstruct strmap dir_renames[3];\n \n+\t/*\n+\t * relevant_sources: deleted paths for which we need rename detection\n+\t *\n+\t * relevant_sources is a set of deleted paths on each side of\n+\t * history for which we need rename detection. If a path is deleted\n+\t * on one side of history, we need to detect if it is part of a\n+\t * rename if either\n+\t * * we need to detect renames for an ancestor directory\n+\t * * the file is modified/deleted on the other side of history\n+\t * If neither of those are true, we can skip rename detection for\n+\t * that path.\n+\t */\n+\tstruct strset relevant_sources[3];\n+\n \t/*\n \t * needed_limit: value needed for inexact rename detection to run\n \t *\n@@ -358,6 +372,8 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,\n \t\t\tstrmap_clear(&renames->dir_rename_count[i], 1);\n \n \t\tstrmap_func(&renames->dir_renames[i], 0);\n+\n+\t\tstrset_func(&renames->relevant_sources[i]);\n \t}\n \n \tif (!reinitialize) {\n@@ -533,12 +549,21 @@ static void add_pair(struct merge_options *opt,\n \t\t struct name_entry *names,\n \t\t const char *pathname,\n \t\t unsigned side,\n-\t\t unsigned is_add /* if false, is_delete */)\n+\t\t unsigned is_add /* if false, is_delete */,\n+\t\t unsigned match_mask)\n {\n \tstruct diff_filespec *one, *two;\n \tstruct rename_info *renames = &opt->priv->renames;\n \tint names_idx = is_add ? side : 0;\n \n+\tif (!is_add) {\n+\t\tunsigned content_relevant = (match_mask == 0);\n+\t\tunsigned location_relevant = 1; /* FIXME: compute this */\n+\n+\t\tif (content_relevant || location_relevant)\n+\t\t\tstrset_add(&renames->relevant_sources[side], pathname);\n+\t}\n+\n \tone = alloc_filespec(pathname);\n \ttwo = alloc_filespec(pathname);\n \tfill_filespec(is_add ? two : one,\n@@ -575,11 +600,13 @@ static void collect_rename_info(struct merge_options *opt,\n \n \t\t/* Check for deletion on side */\n \t\tif ((filemask & 1) && !(filemask & side_mask))\n-\t\t\tadd_pair(opt, names, fullname, side, 0 /* delete */);\n+\t\t\tadd_pair(opt, names, fullname, side, 0 /* delete */,\n+\t\t\t\t match_mask & filemask);\n \n \t\t/* Check for addition on side */\n \t\tif (!(filemask & 1) && (filemask & side_mask))\n-\t\t\tadd_pair(opt, names, fullname, side, 1 /* add */);\n+\t\t\tadd_pair(opt, names, fullname, side, 1 /* add */,\n+\t\t\t\t match_mask & filemask);\n \t}\n }\n \n@@ -3228,6 +3255,8 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)\n \t\t\t\t\t NULL, 1);\n \t\tstrmap_init_with_options(&renames->dir_renames[i],\n \t\t\t\t\t NULL, 0);\n+\t\tstrset_init_with_options(&renames->relevant_sources[i],\n+\t\t\t\t\t NULL, 0);\n \t}\n \n \t/*\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex 4ab133f489ca..4c568050dd27 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -4895,6 +4895,77 @@ test_expect_merge_algorithm failure success '12f: Trivial directory resolve, cac\n \t)\n '\n \n+# Testcase 12g, Testcase with two kinds of \"relevant\" renames\n+# Commit O: somefile_O, subdir/{a_O,b_O}\n+# Commit A: somefile_A, subdir/{a_O,b_O,c_A}\n+# Commit B: newfile_B, newdir/{a_B,b_B}\n+# Expected: newfile_{merged}, newdir/{a_B,b_B,c_A}\n+\n+test_setup_12g () {\n+\ttest_create_repo 12g &&\n+\t(\n+\t\tcd 12g &&\n+\n+\t\tmkdir -p subdir &&\n+\t\ttest_write_lines upon a time there was a >somefile &&\n+\t\ttest_write_lines 1 2 3 4 5 6 7 8 9 10 >subdir/a &&\n+\t\ttest_write_lines one two three four five six >subdir/b &&\n+\t\tgit add . &&\n+\t\ttest_tick &&\n+\t\tgit commit -m \"O\" &&\n+\n+\t\tgit branch O &&\n+\t\tgit branch A &&\n+\t\tgit branch B &&\n+\n+\t\tgit switch A &&\n+\t\ttest_write_lines once upon a time there was a >somefile &&\n+\t\t> subdir/c &&\n+\t\tgit add somefile subdir/c &&\n+\t\ttest_tick &&\n+\t\tgit commit -m \"A\" &&\n+\n+\t\tgit checkout B &&\n+\t\tgit mv somefile newfile &&\n+\t\tgit mv subdir newdir &&\n+\t\techo repo >>newfile &&\n+\t\ttest_write_lines 1 2 3 4 5 6 7 8 9 10 11 >newdir/a &&\n+\t\ttest_write_lines one two three four five six seven >newdir/b &&\n+\t\tgit add newfile newdir &&\n+\t\ttest_tick &&\n+\t\tgit commit -m \"B\"\n+\t)\n+}\n+\n+test_expect_success '12g: Testcase with two kinds of \"relevant\" renames' '\n+\ttest_setup_12g &&\n+\t(\n+\t\tcd 12g &&\n+\n+\t\tgit checkout A^0 &&\n+\n+\t\tgit -c merge.directoryRenames=true merge -s recursive B^0 &&\n+\n+\t\ttest_write_lines once upon a time there was a repo >expect &&\n+\t\ttest_cmp expect newfile &&\n+\n+\t\tgit ls-files -s >out &&\n+\t\ttest_line_count = 4 out &&\n+\n+\t\tgit rev-parse >actual \\\n+\t\t\tHEAD:newdir/a HEAD:newdir/b HEAD:newdir/c &&\n+\t\tgit rev-parse >expect \\\n+\t\t\tB:newdir/a B:newdir/b A:subdir/c &&\n+\t\ttest_cmp expect actual &&\n+\n+\t\ttest_must_fail git rev-parse HEAD:subdir/a &&\n+\t\ttest_must_fail git rev-parse HEAD:subdir/b &&\n+\t\ttest_must_fail git rev-parse HEAD:subdir/c &&\n+\t\ttest_path_is_missing subdir/ &&\n+\t\ttest_path_is_file newdir/c\n+\t)\n+'\n+\n ###########################################################################\n # SECTION 13: Checking informational and conflict messages\n #\n-- \ngitgitgadget\n\n"},{"id":"418769","messageId":"b595245fe9020c06601c6a6c6c8d98b09af4a400.1615423112.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","subject":"[PATCH v3 4/8] merge-ort: introduce wrappers for alternate tree traversal","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-11T00:38:27Z","receivedAt":"2021-03-11T00:39:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd traverse_trees_wrapper() and traverse_trees_wrapper_callback()\nfunctions. The former runs traverse_trees() with info->fn set to\ntraverse_trees_wrapper_callback, in order to simply save all the entries\nwithout processing or recursing into any of them. This step allows\nextra computation to be done (e.g. checking some condition across all\nfiles) that can be used later. Then, after that is completed, it\niterates over all the saved entries and calls the original info->fn\ncallback with the saved data.\n\nCurrently, this does nothing more than marginally slowing down the tree\ntraversal since we do not take advantage of the opportunity to compute\nanything special in traverse_trees_wrapper_callback(), and thus the real\ncallback will be called identically as it would have been without this\nextra wrapper. However, a subsequent commit will add some special\ncomputation of some values that the real callback will be able to use.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 71 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 71 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex d49cfa8b030b..f8f7d06d481a 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -512,6 +512,77 @@ static char *unique_path(struct strmap *existing_paths,\n \n /*** Function Grouping: functions related to collect_merge_info() ***/\n \n+static int traverse_trees_wrapper_callback(int n,\n+\t\t\t\t\t unsigned long mask,\n+\t\t\t\t\t unsigned long dirmask,\n+\t\t\t\t\t struct name_entry *names,\n+\t\t\t\t\t struct traverse_info *info)\n+{\n+\tstruct merge_options *opt = info->data;\n+\tstruct rename_info *renames = &opt->priv->renames;\n+\n+\tassert(n==3);\n+\n+\tif (!renames->callback_data_traverse_path)\n+\t\trenames->callback_data_traverse_path = xstrdup(info->traverse_path);\n+\n+\tALLOC_GROW(renames->callback_data, renames->callback_data_nr + 1,\n+\t\t renames->callback_data_alloc);\n+\trenames->callback_data[renames->callback_data_nr].mask = mask;\n+\trenames->callback_data[renames->callback_data_nr].dirmask = dirmask;\n+\tCOPY_ARRAY(renames->callback_data[renames->callback_data_nr].names,\n+\t\t names, 3);\n+\trenames->callback_data_nr++;\n+\n+\treturn mask;\n+}\n+\n+/*\n+ * Much like traverse_trees(), BUT:\n+ * - read all the tree entries FIRST, saving them\n+ * - note that the above step provides an opportunity to compute necessary\n+ * additional details before the \"real\" traversal\n+ * - loop through the saved entries and call the original callback on them\n+ */\n+MAYBE_UNUSED\n+static int traverse_trees_wrapper(struct index_state *istate,\n+\t\t\t\t int n,\n+\t\t\t\t struct tree_desc *t,\n+\t\t\t\t struct traverse_info *info)\n+{\n+\tint ret, i, old_offset;\n+\ttraverse_callback_t old_fn;\n+\tchar *old_callback_data_traverse_path;\n+\tstruct merge_options *opt = info->data;\n+\tstruct rename_info *renames = &opt->priv->renames;\n+\n+\told_callback_data_traverse_path = renames->callback_data_traverse_path;\n+\told_fn = info->fn;\n+\told_offset = renames->callback_data_nr;\n+\n+\trenames->callback_data_traverse_path = NULL;\n+\tinfo->fn = traverse_trees_wrapper_callback;\n+\tret = traverse_trees(istate, n, t, info);\n+\tif (ret < 0)\n+\t\treturn ret;\n+\n+\tinfo->traverse_path = renames->callback_data_traverse_path;\n+\tinfo->fn = old_fn;\n+\tfor (i = old_offset; i < renames->callback_data_nr; ++i) {\n+\t\tinfo->fn(n,\n+\t\t\t renames->callback_data[i].mask,\n+\t\t\t renames->callback_data[i].dirmask,\n+\t\t\t renames->callback_data[i].names,\n+\t\t\t info);\n+\t}\n+\n+\trenames->callback_data_nr = old_offset;\n+\tfree(renames->callback_data_traverse_path);\n+\trenames->callback_data_traverse_path = old_callback_data_traverse_path;\n+\tinfo->traverse_path = NULL;\n+\treturn 0;\n+}\n+\n static void setup_path_info(struct merge_options *opt,\n \t\t\t struct string_list_item *result,\n \t\t\t const char *current_dir_name,\n-- \ngitgitgadget\n\n"},{"id":"418770","messageId":"98b0c7de5e70d62d47c3eeb3d290c6a234214f40.1615423112.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","subject":"[PATCH v3 8/8] diffcore-rename: avoid doing basename comparisons for irrelevant sources","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-11T00:38:31Z","receivedAt":"2021-03-11T00:39:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe basename comparison optimization implemented in\nfind_basename_matches() is very beneficial since it allows a source to\nsometimes only be compared with one other file instead of N other files.\nWhen a match is found, both a source and destination can be removed from\nthe matrix of inexact rename comparisons. In contrast, the irrelevant\nsource optimization only allows us to remove a source from the matrix of\ninexact rename comparisons...but it has the advantage of allowing a\nsource file to not even be loaded into memory at all and be compared to\n0 other files. Generally, not even comparing is a bigger performance\nwin, so when both optimizations could apply, prefer to use the\nirrelevant-source optimization.\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: 5.708 s ± 0.111 s 5.680 s ± 0.096 s\n mega-renames: 102.171 s ± 0.440 s 13.812 s ± 0.162 s\n just-one-mega: 3.471 s ± 0.015 s 506.0 ms ± 3.9 ms\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 37 +++++++++++++++++++++++++++++++++----\n 1 file changed, 33 insertions(+), 4 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 7f6115fd9018..e8508541be14 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -527,6 +527,7 @@ static void update_dir_rename_counts(struct dir_rename_info *info,\n }\n \n static void initialize_dir_rename_info(struct dir_rename_info *info,\n+\t\t\t\t struct strset *relevant_sources,\n \t\t\t\t struct strset *dirs_removed,\n \t\t\t\t struct strmap *dir_rename_count)\n {\n@@ -534,7 +535,7 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstruct strmap_entry *entry;\n \tint i;\n \n-\tif (!dirs_removed) {\n+\tif (!dirs_removed && !relevant_sources) {\n \t\tinfo->setup = 0;\n \t\treturn;\n \t}\n@@ -549,7 +550,20 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstrmap_init_with_options(&info->dir_rename_guess, NULL, 0);\n \n \t/* Setup info->relevant_source_dirs */\n-\tinfo->relevant_source_dirs = dirs_removed;\n+\tinfo->relevant_source_dirs = NULL;\n+\tif (dirs_removed || !relevant_sources) {\n+\t\tinfo->relevant_source_dirs = dirs_removed; /* might be NULL */\n+\t} else {\n+\t\tinfo->relevant_source_dirs = xmalloc(sizeof(struct strintmap));\n+\t\tstrset_init(info->relevant_source_dirs);\n+\t\tstrset_for_each_entry(relevant_sources, &iter, entry) {\n+\t\t\tchar *dirname = get_dirname(entry->key);\n+\t\t\tif (!dirs_removed ||\n+\t\t\t strset_contains(dirs_removed, dirname))\n+\t\t\t\tstrset_add(info->relevant_source_dirs, dirname);\n+\t\t\tfree(dirname);\n+\t\t}\n+\t}\n \n \t/*\n \t * Loop setting up both info->idx_map, and doing setup of\n@@ -627,6 +641,13 @@ static void cleanup_dir_rename_info(struct dir_rename_info *info,\n \t/* dir_rename_guess */\n \tstrmap_clear(&info->dir_rename_guess, 1);\n \n+\t/* relevant_source_dirs */\n+\tif (info->relevant_source_dirs &&\n+\t info->relevant_source_dirs != dirs_removed) {\n+\t\tstrset_clear(info->relevant_source_dirs);\n+\t\tFREE_AND_NULL(info->relevant_source_dirs);\n+\t}\n+\n \t/* dir_rename_count */\n \tif (!keep_dir_rename_count) {\n \t\tpartial_clear_dir_rename_count(info->dir_rename_count);\n@@ -749,6 +770,7 @@ static int idx_possible_rename(char *filename, struct dir_rename_info *info)\n static int find_basename_matches(struct diff_options *options,\n \t\t\t\t int minimum_score,\n \t\t\t\t struct dir_rename_info *info,\n+\t\t\t\t struct strset *relevant_sources,\n \t\t\t\t struct strset *dirs_removed)\n {\n \t/*\n@@ -839,6 +861,11 @@ static int find_basename_matches(struct diff_options *options,\n \t\tintptr_t src_index;\n \t\tintptr_t dst_index;\n \n+\t\t/* Skip irrelevant sources */\n+\t\tif (relevant_sources &&\n+\t\t !strset_contains(relevant_sources, filename))\n+\t\t\tcontinue;\n+\n \t\t/*\n \t\t * If the basename is unique among remaining sources, then\n \t\t * src_index will equal 'i' and we can attempt to match it\n@@ -1164,7 +1191,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \n \t\t/* Preparation for basename-driven matching. */\n \t\ttrace2_region_enter(\"diff\", \"dir rename setup\", options->repo);\n-\t\tinitialize_dir_rename_info(&info,\n+\t\tinitialize_dir_rename_info(&info, relevant_sources,\n \t\t\t\t\t dirs_removed, dir_rename_count);\n \t\ttrace2_region_leave(\"diff\", \"dir rename setup\", options->repo);\n \n@@ -1172,7 +1199,9 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\ttrace2_region_enter(\"diff\", \"basename matches\", options->repo);\n \t\trename_count += find_basename_matches(options,\n \t\t\t\t\t\t min_basename_score,\n-\t\t\t\t\t\t &info, dirs_removed);\n+\t\t\t\t\t\t &info,\n+\t\t\t\t\t\t relevant_sources,\n+\t\t\t\t\t\t dirs_removed);\n \t\ttrace2_region_leave(\"diff\", \"basename matches\", options->repo);\n \n \t\t/*\n-- \ngitgitgadget\n"},{"id":"418771","messageId":"375c9b36861b2068f34e3d6e5073ab768644a030.1615423112.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","subject":"[PATCH v3 6/8] merge-ort: use relevant_sources to filter possible rename sources","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-11T00:38:29Z","receivedAt":"2021-03-11T00:39:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe past several commits determined conditions when rename sources might\nbe needed, and filled a relevant_sources strset with those paths. Pass\nthese along to diffcore_rename_extended() to use to limit the sources\nthat we need to detect renames for.\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: 12.596 s ± 0.061 s 6.003 s ± 0.048 s\n mega-renames: 130.465 s ± 0.259 s 114.009 s ± 0.236 s\n just-one-mega: 3.958 s ± 0.010 s 3.489 s ± 0.017 s\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 5840832cf3ed..eea14024c657 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2208,7 +2208,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_queued_diff = renames->pairs[side_index];\n \ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiffcore_rename_extended(&diff_opts,\n-\t\t\t\t NULL,\n+\t\t\t\t &renames->relevant_sources[side_index],\n \t\t\t\t &renames->dirs_removed[side_index],\n \t\t\t\t &renames->dir_rename_count[side_index]);\n \ttrace2_region_leave(\"diff\", \"diffcore_rename\", opt->repo);\n-- \ngitgitgadget\n\n"},{"id":"418772","messageId":"80a0c27a74ad0314a84e956acf233f6de3b16252.1615423112.git.gitgitgadget@gmail.com","threadId":"55231","inReplyTo":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","subject":"[PATCH v3 7/8] merge-ort: skip rename detection entirely if possible","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-03-11T00:38:30Z","receivedAt":"2021-03-11T00:39:22Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\ndiffcore_rename_extended() will do a bunch of setup, then check for\nexact renames, then abort before inexact rename detection if there are\nno more sources or destinations that need to be matched. It will\nsometimes be the case, however, that either\n * we start with neither any sources or destinations\n * we start with no *relevant* sources\nIn the first of these two cases, the setup and exact rename detection\nwill be very cheap since there are 0 files to operate on. In the second\ncase, it is quite possible to have thousands of files with none of the\nsource ones being relevant. Avoid calling diffcore_rename_extended() or\neven some of the setup before diffcore_rename_extended() when we can\ndetermine that rename detection is unnecessary.\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: 6.003 s ± 0.048 s 5.708 s ± 0.111 s\n mega-renames: 114.009 s ± 0.236 s 102.171 s ± 0.440 s\n just-one-mega: 3.489 s ± 0.017 s 3.471 s ± 0.015 s\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 44 ++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 44 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex eea14024c657..bd089cb9a76f 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2157,6 +2157,19 @@ static int process_renames(struct merge_options *opt,\n \treturn clean_merge;\n }\n \n+static inline int possible_side_renames(struct rename_info *renames,\n+\t\t\t\t\tunsigned side_index)\n+{\n+\treturn renames->pairs[side_index].nr > 0 &&\n+\t !strset_empty(&renames->relevant_sources[side_index]);\n+}\n+\n+static inline int possible_renames(struct rename_info *renames)\n+{\n+\treturn possible_side_renames(renames, 1) ||\n+\t possible_side_renames(renames, 2);\n+}\n+\n static void resolve_diffpair_statuses(struct diff_queue_struct *q)\n {\n \t/*\n@@ -2193,6 +2206,16 @@ static void detect_regular_renames(struct merge_options *opt,\n \tstruct diff_options diff_opts;\n \tstruct rename_info *renames = &opt->priv->renames;\n \n+\tif (!possible_side_renames(renames, side_index)) {\n+\t\t/*\n+\t\t * No rename detection needed for this side, but we still need\n+\t\t * to make sure 'adds' are marked correctly in case the other\n+\t\t * side had directory renames.\n+\t\t */\n+\t\tresolve_diffpair_statuses(&renames->pairs[side_index]);\n+\t\treturn;\n+\t}\n+\n \trepo_diff_setup(opt->repo, &diff_opts);\n \tdiff_opts.flags.recursive = 1;\n \tdiff_opts.flags.rename_empty = 0;\n@@ -2310,6 +2333,8 @@ static int detect_and_process_renames(struct merge_options *opt,\n \tint need_dir_renames, s, clean = 1;\n \n \tmemset(&combined, 0, sizeof(combined));\n+\tif (!possible_renames(renames))\n+\t\tgoto cleanup;\n \n \ttrace2_region_enter(\"merge\", \"regular renames\", opt->repo);\n \tdetect_regular_renames(opt, MERGE_SIDE1);\n@@ -2344,6 +2369,25 @@ static int detect_and_process_renames(struct merge_options *opt,\n \tclean &= process_renames(opt, &combined);\n \ttrace2_region_leave(\"merge\", \"process renames\", opt->repo);\n \n+\tgoto simple_cleanup; /* collect_renames() handles some of cleanup */\n+\n+cleanup:\n+\t/*\n+\t * Free now unneeded filepairs, which would have been handled\n+\t * in collect_renames() normally but we skipped that code.\n+\t */\n+\tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n+\t\tstruct diff_queue_struct *side_pairs;\n+\t\tint i;\n+\n+\t\tside_pairs = &renames->pairs[s];\n+\t\tfor (i = 0; i < side_pairs->nr; ++i) {\n+\t\t\tstruct diff_filepair *p = side_pairs->queue[i];\n+\t\t\tdiff_free_filepair(p);\n+\t\t}\n+\t}\n+\n+simple_cleanup:\n \t/* Free memory for renames->pairs[] and combined */\n \tfor (s = MERGE_SIDE1; s <= MERGE_SIDE2; s++) {\n \t\tfree(renames->pairs[s].queue);\n-- \ngitgitgadget\n\n"},{"id":"419161","messageId":"4aed9cc6-b133-b398-353c-9618439c7b8b@gmail.com","threadId":"55231","inReplyTo":"pull.845.v3.git.1615423111.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/8] Optimization batch 9: avoid detecting irrelevant renames","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-03-15T13:57:11Z","receivedAt":"2021-03-15T13:58:05Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/10/2021 7:38 PM, Elijah Newren via GitGitGadget wrote:\n> This series determines paths which meet special cases where detection of\n> renames is irrelevant, where the irrelevance is due to the fact that the\n> merge machinery will arrive at the same result regardless of whether a\n> rename is detected for any of those paths.\n> \n> Changes since v2:\n> \n> * Added an extended comment about filtering order to the first patch, to\n> address Stolee's question\n> * Added a new testcase that will fail if the critical \"if (content_relevant\n> || location_relevant)\" check only checks for one of those two or the\n> intersection of those two, as suggested by Stolee\n> * Fixed the other minor problems Stolee pointed out in his review (stray\n> newline, wording of comment)\n\nThanks for these updates. This version works for me.\n\n-Stolee\n"},{"id":"419174","messageId":"CABPp-BGEJ+Qvb4C0bgnMEoxVZfYj1NMrtYF-opLG2gcwJ3-v_A@mail.gmail.com","threadId":"55231","inReplyTo":"pull.845.v2.git.1615248599.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/8] Optimization batch 9: avoid detecting irrelevant renames","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-03-15T17:10:50Z","receivedAt":"2021-03-15T17:12:07Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Mon, Mar 8, 2021 at 4:10 PM Elijah Newren via GitGitGadget\n wrote:\n>\n> This series depends textually on ort-perf-batch-8, but semantically it's\n> almost completely unrelated and can be reviewed without any familiarity with\n> any of the previous patch series.\n>\n> There are no changes since v1; it's just a resend just over a week later to\n> bump it so it isn't lost.\n>\n> === Basic Optimization idea ===\n>\n> This series determines paths which meet special cases where detection of\n> renames is irrelevant, where the irrelevance is due to the fact that the\n> merge machinery will arrive at the same result regardless of whether a\n> rename is detected for any of those paths. This series represents\n> \"Optimization #2\" from my Git Merge 2020 talk[1], though this series has\n> some improvements on the optimization relative to what I had at that time.\n>\n> The basic idea here is:\n>\n> We only need expensive rename detection on the subset of files changed on\n> both sides of history (for the most part).\n\nI know this series was already reviewed and even a subsequent series\nwas reviewed, but I thought I'd insert a bit of history trivia:\n\nI first submitted this optimization in late 2017 as an RFC at\nhttps://lore.kernel.org/git/20171110222156.23221-9-newren@gmail.com/.\nUnfortunately I had only handled the \"for the most part\" piece, not\nthe other special cases. I knew not handling those other cases caused\nbugs, but didn't readily find a solution for them at the time. I kept\nmulling it over periodically despite being switched onto other\nprojects; eventually I weaseled my way into being able to work on it\nagain and with some effort was able to work out the other necessary\nconditions and audit the code to verify I had all the cases covered.\nThose \"other cases\" were much more easily expressed in the context of\nmerge-ort's data structures than merge-recursive's, in part because\nmerge-ort's data structures were picked to help me solve this\noptimization problem and the various known failing testcases that I\nwanted to fix.\n"}]}