[PATCH 1/8] diffcore-rename: enable filtering possible rename sources
From: Elijah Newren via GitGitGadget <hidden>
Date: 2021-02-28 03:59:33
Subsystem:
the rest · Maintainer:
Linus Torvalds
From: Elijah Newren <redacted>
Add the ability to diffcore_rename_extended() to allow external callers
to declare that they only need renames detected for a subset of source
files, and use that information to skip detecting renames for them.
There are two important pieces to this optimization that may not be
obvious at first glance:
* We do not require callers to just filter the filepairs out
to remove the non-relevant sources, because exact rename detection
is fast and when it finds a match it can remove both a source and a
destination whereas the relevant_sources filter can only remove a
source.
* We need to filter out the source pairs in a preliminary pass instead
of adding a
strset_contains(relevant_sources, one->path)
check within the nested matrix loop. The reason for that is if we
have 30k renames, doing 30k * 30k = 900M strset_contains() calls
becomes extraordinarily expensive and defeats the performance gains
from this change; we only want to do 30k such calls instead.
If callers pass NULL for relevant_sources, that is special cases to
treat all sources as relevant. Since all callers currently pass NULL,
this optimization does not yet have any effect. Subsequent commits will
have merge-ort compute a set of relevant_sources to restrict which
sources we detect renames for, and have merge-ort pass that set of
relevant_sources to diffcore_rename_extended().
Signed-off-by: Elijah Newren <redacted>
---
diffcore-rename.c | 26 +++++++++++++++++++-------
diffcore.h | 1 +
merge-ort.c | 1 +
3 files changed, 21 insertions(+), 7 deletions(-)
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 1fe902ed2af0..7f6115fd9018 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c@@ -991,11 +991,12 @@ static int find_renames(struct diff_score *mx, return count; } -static void remove_unneeded_paths_from_src(int detecting_copies) +static void remove_unneeded_paths_from_src(int detecting_copies, + struct strset *interesting) { int i, new_num_src; - if (detecting_copies) + if (detecting_copies && !interesting) return; /* nothing to remove */ if (break_idx) return; /* culling incompatible with break detection */
@@ -1022,12 +1023,18 @@ static void remove_unneeded_paths_from_src(int detecting_copies) * from rename_src here. */ for (i = 0, new_num_src = 0; i < rename_src_nr; i++) { + struct diff_filespec *one = rename_src[i].p->one; + /* * renames are stored in rename_dst, so if a rename has * already been detected using this source, we can just * remove the source knowing rename_dst has its info. */ - if (rename_src[i].p->one->rename_used) + if (!detecting_copies && one->rename_used) + continue; + + /* If we don't care about the source path, skip it */ + if (interesting && !strset_contains(interesting, one->path)) continue; if (new_num_src < i)
@@ -1040,6 +1047,7 @@ static void remove_unneeded_paths_from_src(int detecting_copies) } void diffcore_rename_extended(struct diff_options *options, + struct strset *relevant_sources, struct strset *dirs_removed, struct strmap *dir_rename_count) {
@@ -1060,6 +1068,8 @@ void diffcore_rename_extended(struct diff_options *options, want_copies = (detect_rename == DIFF_DETECT_COPY); if (dirs_removed && (break_idx || want_copies)) BUG("dirs_removed incompatible with break/copy detection"); + if (break_idx && relevant_sources) + BUG("break detection incompatible with source specification"); if (!minimum_score) minimum_score = DEFAULT_RENAME_SCORE;
@@ -1127,9 +1137,10 @@ void diffcore_rename_extended(struct diff_options *options, /* * Cull sources: * - remove ones corresponding to exact renames + * - remove ones not found in relevant_sources */ trace2_region_enter("diff", "cull after exact", options->repo); - remove_unneeded_paths_from_src(want_copies); + remove_unneeded_paths_from_src(want_copies, relevant_sources); trace2_region_leave("diff", "cull after exact", options->repo); } else { /* Determine minimum score to match basenames */
@@ -1148,7 +1159,7 @@ void diffcore_rename_extended(struct diff_options *options, * - remove ones involved in renames (found via exact match) */ trace2_region_enter("diff", "cull after exact", options->repo); - remove_unneeded_paths_from_src(want_copies); + remove_unneeded_paths_from_src(want_copies, NULL); trace2_region_leave("diff", "cull after exact", options->repo); /* Preparation for basename-driven matching. */
@@ -1167,9 +1178,10 @@ 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 */ trace2_region_enter("diff", "cull basename", options->repo); - remove_unneeded_paths_from_src(want_copies); + remove_unneeded_paths_from_src(want_copies, relevant_sources); trace2_region_leave("diff", "cull basename", options->repo); }
@@ -1342,5 +1354,5 @@ void diffcore_rename_extended(struct diff_options *options, void diffcore_rename(struct diff_options *options) { - diffcore_rename_extended(options, NULL, NULL); + diffcore_rename_extended(options, NULL, NULL, NULL); }
diff --git a/diffcore.h b/diffcore.h
index c6ba64abd198..737c93a6cc79 100644
--- a/diffcore.h
+++ b/diffcore.h@@ -166,6 +166,7 @@ void partial_clear_dir_rename_count(struct strmap *dir_rename_count); void diffcore_break(struct repository *, int); void diffcore_rename(struct diff_options *); void diffcore_rename_extended(struct diff_options *options, + struct strset *relevant_sources, struct strset *dirs_removed, struct strmap *dir_rename_count); void diffcore_merge_broken(void);
diff --git a/merge-ort.c b/merge-ort.c
index 467404cc0a35..aba0b9fa54c3 100644
--- a/merge-ort.c
+++ b/merge-ort.c@@ -2029,6 +2029,7 @@ static void detect_regular_renames(struct merge_options *opt, diff_queued_diff = renames->pairs[side_index]; trace2_region_enter("diff", "diffcore_rename", opt->repo); diffcore_rename_extended(&diff_opts, + NULL, &renames->dirs_removed[side_index], &renames->dir_rename_count[side_index]); trace2_region_leave("diff", "diffcore_rename", opt->repo);
--
gitgitgadget