[PATCH 1/8] diffcore-rename: take advantage of "majority rules" to skip more renames

From: Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>
Date: Mar 13, 2021, 22:22 UTC
Message-ID: <960dcf365b350ef7166bd4f92d48ed016502f101.1615674128.git.gitgitgadget@gmail.com>
In-Reply-To: <pull.853.git.1615674128.gitgitgadget@gmail.com>

From: Elijah Newren <newren@gmail.com>

In directory rename detection (when a directory is removed on one side of history and the other side adds new files to that directory), we work to find where the greatest number of files within that directory were renamed to so that the new files can be moved with the majority of the files.

Naively, we can just do this by detecting renames for *all* files within the removed/renamed directory, looking at all the destination directories where files within that directory were moved, and if there is more than one such directory then taking the one with the greatest number of files as the directory where the old directory was renamed to.

However, sometimes there are enough renames from exact rename detection or basename-guided rename detection that we have enough information to determine the majority winner already. Add a function meant to compute whether particular renames are still needed based on this majority rules check. The next several commits will then add the necessary infrastructure to get the information we need to compute which additional rename sources we can skip.

An important side note for future further optimization:

There is a possible improvement to this optimization that I have not yet attempted and will not be included in this series of patches: we could first check whether exact renames provide enough information for us to determine directory renames, and avoid doing basename-guided rename detection on some or all of the RELEVANT_LOCATION files within those directories. In effect, this variant would mean doing the handle_early_known_dir_renames() both after exact rename detection and again after basename-guided rename detection, though it would also mean decrementing the number of "unknown" renames for each rename we found from basename-guided rename detection. Adding this additional check for skippable renames right after exact rename detection might turn out to be valuable, especially for partial clones where it might allow us to download certain source files entirely. However, this particular optimization was actually the last one I did in original implementation order, and by the time I implemented this idea, every testcase I had was sufficiently fast that further optimization was unwarranted. If future testcases arise that tax rename detection more heavily (or perhaps partial clones can benefit from avoiding loading more objects), it may be worth implementing this more involved variant.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diffcore-rename.c | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index e8508541be14..a5d10afa221a 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -1073,6 +1073,24 @@ static void remove_unneeded_paths_from_src(int detecting_copies,
 	rename_src_nr = new_num_src;
 }
 
+static void handle_early_known_dir_renames(struct dir_rename_info *info,
+					   struct strset *relevant_sources,
+					   struct strset *dirs_removed)
+{
+	/*
+	 * Not yet implemented; directory renames are determined via an
+	 * aggregate of all renames under them and using a "majority wins"
+	 * rule.  The fact that "majority wins", though, means we don't need
+	 * all the renames under the given directory, we only need enough to
+	 * ensure we have a majority.
+	 *
+	 * For now, we don't have enough information to know if we have a
+	 * majority after exact renames and basename-guided rename detection,
+	 * so just return early without doing any extra filtering.
+	 */
+	return;
+}
+
 void diffcore_rename_extended(struct diff_options *options,
 			      struct strset *relevant_sources,
 			      struct strset *dirs_removed,
@@ -1208,9 +1226,16 @@ void diffcore_rename_extended(struct diff_options *options,
 		 * Cull sources, again:
 		 *   - remove ones involved in renames (found via basenames)
 		 *   - remove ones not found in relevant_sources
+		 * and
+		 *   - remove ones in relevant_sources which are needed only
+		 *     for directory renames IF no ancestory directory
+		 *     actually needs to know any more individual path
+		 *     renames under them
 		 */
 		trace2_region_enter("diff", "cull basename", options->repo);
 		remove_unneeded_paths_from_src(want_copies, relevant_sources);
+		handle_early_known_dir_renames(&info, relevant_sources,
+					       dirs_removed);
 		trace2_region_leave("diff", "cull basename", options->repo);
 	}

-- 
gitgitgadget