diff mbox series

[v2,1/8] diffcore-rename: enable filtering possible rename sources

Message ID dab8e3c6aee5a852ad46c569c0be729d64310ad9.1615248599.git.gitgitgadget@gmail.com (mailing list archive)
State Superseded
Headers show
Series Optimization batch 9: avoid detecting irrelevant renames | expand

Commit Message

Elijah Newren March 9, 2021, 12:09 a.m. UTC 
From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 diffcore-rename.c | 26 +++++++++++++++++++-------
 diffcore.h        |  1 +
 merge-ort.c       |  1 +
 3 files changed, 21 insertions(+), 7 deletions(-)

Comments

Derrick Stolee March 9, 2021, 10:21 p.m. UTC | #1 
On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:> @@ -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);

In this case, we are checking for copies. Perhaps there is a reason
why we want to include relevant_sources in that case, so I'll look
for it later.

>  	} 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);

This seems backwards from your cover letter. You are using the exact renames
_and_ basename matches to remove the unneeded paths. Why are we not stripping
out the relevant_sources in the call further up, before we call
find_basename_matches()?

Thanks,
-Stolee
Elijah Newren March 9, 2021, 10:40 p.m. UTC | #2 
On Tue, Mar 9, 2021 at 2:21 PM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:> @@ -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);
>
> In this case, we are checking for copies. Perhaps there is a reason
> why we want to include relevant_sources in that case, so I'll look
> for it later.

There is no current caller making use of this.  I could have just
marked the two options as incompatible and passed NULL here for
relevant sources, but...I didn't see a compelling reason to.  If some
caller wanted copy detection and were only interested in copies from a
subset of sources, they could take advantage of relevant_sources in
the same way to limit to those paths that are relevant.  I guess it
comes down to whether you view this as designing the code for future
theoretical cases, or explicitly taking steps to limit future
possibilities.  I don't have a strong opinion here, but tried to
enable other future uses since diffcore-rename.c is used by many other
callers too.

> >       } 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);
>
> This seems backwards from your cover letter. You are using the exact renames
> _and_ basename matches to remove the unneeded paths. Why are we not stripping
> out the relevant_sources in the call further up, before we call
> find_basename_matches()?

Yeah, good flag.  I should add a comment to the commit message about
how these are still needed in initialize_dir_rename_info() for
basename-guided directory rename detection...and will also play a role
in some of the special cases where renames are needed for more than
three-way content merges.  And add a comment about how by the end of
the series, relevant_sources will be passed to find_basename_matches()
so that it can skip over those paths.
Derrick Stolee March 9, 2021, 10:45 p.m. UTC | #3 
On 3/9/2021 5:40 PM, Elijah Newren wrote:
> On Tue, Mar 9, 2021 at 2:21 PM Derrick Stolee <stolee@gmail.com> wrote:
>>
>> On 3/8/2021 7:09 PM, Elijah Newren via GitGitGadget wrote:
>>> @@ -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);
>>
>> This seems backwards from your cover letter. You are using the exact renames
>> _and_ basename matches to remove the unneeded paths. Why are we not stripping
>> out the relevant_sources in the call further up, before we call
>> find_basename_matches()?
> 
> Yeah, good flag.  I should add a comment to the commit message about
> how these are still needed in initialize_dir_rename_info() for
> basename-guided directory rename detection...and will also play a role
> in some of the special cases where renames are needed for more than
> three-way content merges.  And add a comment about how by the end of
> the series, relevant_sources will be passed to find_basename_matches()
> so that it can skip over those paths.
 
Ah, so by the end, find_basename_matches() will be coupled to the
relevant_sources set directory instead of relying on the culling
happening earlier? Interesting. It seems to me like it would be
better to have them be less coupled by relying on the culling
before calling find_basename_matches(), but I'll keep reading to
see your good reason for not doing that.

Thanks,
-Stolee
diff mbox series

Patch

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);