From: Elijah Newren <newren@xxxxxxxxx>
We have to look at each entry in rename_src a total of rename_dst_nr
times. When we're not detecting copies, any exact renames or ignorable
rename paths will just be skipped over. While checking that these can
be skipped over is a relatively cheap check, it's still a waste of time
to do that check more than once, let alone rename_dst_nr times. When
rename_src_nr is a few thousand times bigger than the number of relevant
sources (such as when cherry-picking a commit that only touched a
handful of files, but from a side of history that has different names
for some high level directories), this time can add up.
First make an initial pass over the rename_src array and move all the
relevant entries to the front, so that we can iterate over just those
relevant entries.
For the testcases mentioned in commit 557ac0350d ("merge-ort: begin
performance work; instrument with trace2_region_* calls", 2020-10-28),
this change improves the performance as follows:
Before After
no-renames: 14.119 s ± 0.101 s 13.815 s ± 0.062 s
mega-renames: 1802.044 s ± 0.828 s 1799.937 s ± 0.493 s
just-one-mega: 51.391 s ± 0.028 s 51.289 s ± 0.019 s
Signed-off-by: Elijah Newren <newren@xxxxxxxxx>
---
diffcore-rename.c | 67 ++++++++++++++++++++++++++++++++++++++++-------
1 file changed, 57 insertions(+), 10 deletions(-)
diff --git a/diffcore-rename.c b/diffcore-rename.c
index e3047da3aaf..2a8e7b84b9c 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -454,6 +454,55 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i
return count;
}
+static int remove_unneeded_paths_from_src(int num_src,
+ int detecting_copies)
+{
+ int i, new_num_src;
+
+ /*
+ * Note on reasons why we cull unneeded sources but not destinations:
+ * 1) Pairings are stored in rename_dst (not rename_src), which we
+ * need to keep around. So, we just can't cull rename_dst even
+ * if we wanted to. But doing so wouldn't help because...
+ *
+ * 2) There is a matrix pairwise comparison that follows the
+ * "Performing inexact rename detection" progress message.
+ * Iterating over the destinations is done in the outer loop,
+ * hence we only iterate over each of those once and we can
+ * easily skip the outer loop early if the destination isn't
+ * relevant. That's only one check per destination path to
+ * skip.
+ *
+ * By contrast, the sources are iterated in the inner loop; if
+ * we check whether a source can be skipped, then we'll be
+ * checking it N separate times, once for each destination.
+ * We don't want to have to iterate over known-not-needed
+ * sources N times each, so avoid that by removing the sources
+ * from rename_src here.
+ */
+ if (detecting_copies)
+ return num_src; /* nothing to remove */
+ if (break_idx)
+ return num_src; /* culling incompatbile with break detection */
+
+ for (i = 0, new_num_src = 0; i < num_src; i++) {
+ /*
+ * 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)
+ continue;
+
+ if (new_num_src < i)
+ memcpy(&rename_src[new_num_src], &rename_src[i],
+ sizeof(struct diff_rename_src));
+ new_num_src++;
+ }
+
+ return new_num_src;
+}
+
void diffcore_rename(struct diff_options *options)
{
int detect_rename = options->detect_rename;
@@ -463,10 +512,11 @@ void diffcore_rename(struct diff_options *options)
struct diff_score *mx;
int i, j, rename_count, skip_unmodified = 0;
int num_destinations, dst_cnt;
- int num_sources;
+ int num_sources, want_copies;
struct progress *progress = NULL;
trace2_region_enter("diff", "setup", options->repo);
+ want_copies = (detect_rename == DIFF_DETECT_COPY);
if (!minimum_score)
minimum_score = DEFAULT_RENAME_SCORE;
@@ -529,13 +579,10 @@ void diffcore_rename(struct diff_options *options)
goto cleanup;
/*
- * Calculate how many renames are left (but all the source
- * files still remain as options for rename/copies!)
+ * Calculate how many renames are left
*/
num_destinations = (rename_dst_nr - rename_count);
- num_sources = rename_src_nr;
- if (detect_rename != DIFF_DETECT_COPY)
- num_sources -= rename_count;
+ num_sources = remove_unneeded_paths_from_src(rename_src_nr, want_copies);
/* All done? */
if (!num_destinations || !num_sources)
@@ -573,13 +620,13 @@ void diffcore_rename(struct diff_options *options)
for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
m[j].dst = -1;
- for (j = 0; j < rename_src_nr; j++) {
+ for (j = 0; j < num_sources; j++) {
struct diff_filespec *one = rename_src[j].p->one;
struct diff_score this_src;
- if (one->rename_used &&
- detect_rename != DIFF_DETECT_COPY)
- continue;
+ assert(!one->rename_used ||
+ detect_rename == DIFF_DETECT_COPY ||
+ break_idx);
if (skip_unmodified &&
diff_unmodified_pair(rename_src[j].p))
--
gitgitgadget
