From: "Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: Derrick Stolee <dstolee@microsoft.com>,
Jonathan Tan <jonathantanmy@google.com>,
Taylor Blau <me@ttaylorr.com>, Junio C Hamano <gitster@pobox.com>,
Jeff King <peff@peff.net>, Karsten Blees <blees@dcon.de>,
Derrick Stolee <stolee@gmail.com>,
Elijah Newren <newren@gmail.com>,
Elijah Newren <newren@gmail.com>,
Elijah Newren <newren@gmail.com>
Subject: [PATCH v2 2/2] diffcore-rename: filter rename_src list when possible
Date: Wed, 03 Feb 2021 20:03:47 +0000 [thread overview]
Message-ID: <7ae9460d3dba84122c2674b46e4339b9d42bdedd.1612382628.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.842.v2.git.1612382628.gitgitgadget@gmail.com>
From: Elijah Newren <newren@gmail.com>
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@gmail.com>
---
diffcore-rename.c | 57 ++++++++++++++++++++++++++++++++++++++++++-----
1 file changed, 51 insertions(+), 6 deletions(-)
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 8b118628b4e..74930716e70 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -454,6 +454,54 @@ static int find_renames(struct diff_score *mx, int dst_cnt, int minimum_score, i
return count;
}
+static void remove_unneeded_paths_from_src(int detecting_copies)
+{
+ int i, new_num_src;
+
+ if (detecting_copies)
+ return; /* nothing to remove */
+ if (break_idx)
+ return; /* culling incompatbile with break detection */
+
+ /*
+ * 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.
+ */
+ for (i = 0, new_num_src = 0; i < rename_src_nr; 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++;
+ }
+
+ rename_src_nr = new_num_src;
+}
+
void diffcore_rename(struct diff_options *options)
{
int detect_rename = options->detect_rename;
@@ -530,13 +578,11 @@ 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);
+ remove_unneeded_paths_from_src(want_copies);
num_sources = rename_src_nr;
- if (!want_copies)
- num_sources -= rename_count;
/* All done? */
if (!num_destinations || !num_sources)
@@ -578,8 +624,7 @@ void diffcore_rename(struct diff_options *options)
struct diff_filespec *one = rename_src[j].p->one;
struct diff_score this_src;
- if (one->rename_used && !want_copies)
- continue;
+ assert(!one->rename_used || want_copies || break_idx);
if (skip_unmodified &&
diff_unmodified_pair(rename_src[j].p))
--
gitgitgadget
next prev parent reply other threads:[~2021-02-03 20:04 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-02-03 5:49 [PATCH 0/2] Optimization batch 6: make full use of exact renames Elijah Newren via GitGitGadget
2021-02-03 5:49 ` [PATCH 1/2] diffcore-rename: no point trying to find a match better than exact Elijah Newren via GitGitGadget
2021-02-03 11:44 ` Derrick Stolee
2021-02-03 16:31 ` Elijah Newren
2021-02-03 18:46 ` Junio C Hamano
2021-02-03 19:10 ` Elijah Newren
2021-02-03 5:49 ` [PATCH 2/2] diffcore-rename: filter rename_src list when possible Elijah Newren via GitGitGadget
[not found] ` <13feb106-c3a7-a26d-0e6e-013aa45c58d4@gmail.com>
2021-02-03 17:12 ` Elijah Newren
2021-02-03 19:12 ` Junio C Hamano
2021-02-03 19:19 ` Elijah Newren
2021-02-03 20:03 ` [PATCH v2 0/2] Optimization batch 6: make full use of exact renames Elijah Newren via GitGitGadget
2021-02-03 20:03 ` [PATCH v2 1/2] diffcore-rename: no point trying to find a match better than exact Elijah Newren via GitGitGadget
2021-02-03 20:03 ` Elijah Newren via GitGitGadget [this message]
2021-02-13 1:04 ` [PATCH v2 2/2] diffcore-rename: filter rename_src list when possible Junio C Hamano
2021-02-13 4:24 ` Elijah Newren
2021-02-13 1:06 ` Junio C Hamano
2021-02-13 4:43 ` Elijah Newren
2021-02-03 21:56 ` [PATCH v2 0/2] Optimization batch 6: make full use of exact renames Junio C Hamano
2021-02-03 23:06 ` Elijah Newren
2021-02-03 23:26 ` Junio C Hamano
2021-02-03 23:36 ` Jeff King
2021-02-04 0:05 ` Elijah Newren
2021-02-14 7:34 ` [PATCH v3 " Elijah Newren via GitGitGadget
2021-02-14 7:35 ` [PATCH v3 1/2] diffcore-rename: no point trying to find a match better than exact Elijah Newren via GitGitGadget
2021-02-14 7:35 ` [PATCH v3 2/2] diffcore-rename: filter rename_src list when possible Elijah Newren via GitGitGadget
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=7ae9460d3dba84122c2674b46e4339b9d42bdedd.1612382628.git.gitgitgadget@gmail.com \
--to=gitgitgadget@gmail.com \
--cc=blees@dcon.de \
--cc=dstolee@microsoft.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=jonathantanmy@google.com \
--cc=me@ttaylorr.com \
--cc=newren@gmail.com \
--cc=peff@peff.net \
--cc=stolee@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).