[PATCH v3 0/5] Optimization batch 7: use file basenames to guide rename detection

["Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com>]

This series depends on ort-perf-batch-6[1].

This series uses file basenames (portion of the path after final '/',
including extension) in a basic fashion to guide rename detection.

Changes since v2:

 * insert a new patch at the beginning to test expected old behavior, then
   have later patches change the test expectation
 * tweak commit message wording to clarify that rename stats merely
   motivated the optimization
 * factor out a simple get_basename() helper; have it document why we don't
   use gitbasename()
 * use a higher required threshold to mark same-basename files as a rename,
   defaulting to average of minimum_score and MAX_SCORE (since default
   rename threshold is 50%, this implies default basename threshold is 75%)
 * provide an environment variable (undocumented) that can be used to test
   appropriate threshold for basename-sameness
 * updated the timings based on the new threshold
 * modify the documentation with Junio's suggested simpler and clearer
   wording
 * clean up the wording on a few comments

[1] https://lore.kernel.org/git/xmqqlfc4byt6.fsf@gitster.c.googlers.com/ [2]
https://github.com/newren/presentations/blob/pdfs/merge-performance/merge-performance-slides.pdf

Elijah Newren (5):
  t4001: add a test comparing basename similarity and content similarity
  diffcore-rename: compute basenames of all source and dest candidates
  diffcore-rename: complete find_basename_matches()
  diffcore-rename: guide inexact rename detection based on basenames
  gitdiffcore doc: mention new preliminary step for rename detection

 Documentation/gitdiffcore.txt |  17 +++
 diffcore-rename.c             | 202 +++++++++++++++++++++++++++++++++-
 t/t4001-diff-rename.sh        |  24 ++++
 3 files changed, 239 insertions(+), 4 deletions(-)


base-commit: 7ae9460d3dba84122c2674b46e4339b9d42bdedd
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-843%2Fnewren%2Fort-perf-batch-7-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-843/newren/ort-perf-batch-7-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/843

Range-diff vs v2:

 4:  a0e75d8cd6bd ! 1:  3e6af929d135 gitdiffcore doc: mention new preliminary step for rename detection
     @@ Metadata
      Author: Elijah Newren <newren@gmail.com>
      
       ## Commit message ##
     -    gitdiffcore doc: mention new preliminary step for rename detection
     +    t4001: add a test comparing basename similarity and content similarity
      
     -    The last few patches have introduced a new preliminary step when rename
     -    detection is on but both break detection and copy detection are off.
     -    Document this new step.  While we're at it, add a testcase that checks
     -    the new behavior as well.
     +    Add a simple test where a removed file is similar to two different added
     +    files; one of them has the same basename, and the other has a slightly
     +    higher content similarity.  Without break detection, filename similarity
     +    of 100% trumps content similarity for pairing up related files.  For
     +    any filename similarity less than 100%, the opposite is true -- content
     +    similarity is all that matters.  Add a testcase that documents this.
      
     -    Signed-off-by: Elijah Newren <newren@gmail.com>
     +    Subsequent commits will add a new rule that includes an inbetween state,
     +    where a mixture of filename similarity and content similarity are
     +    weighed, and which will change the outcome of this testcase.
      
     - ## Documentation/gitdiffcore.txt ##
     -@@ Documentation/gitdiffcore.txt: a similarity score different from the default of 50% by giving a
     - number after the "-M" or "-C" option (e.g. "-M8" to tell it to use
     - 8/10 = 80%).
     - 
     -+Note that when rename detection is on but both copy and break
     -+detection are off, rename detection adds a preliminary step that first
     -+checks files with the same basename.  If files with the same basename
     -+are sufficiently similar, it will mark them as renames and exclude
     -+them from the later quadratic step (the one that pairwise compares all
     -+unmatched files to find the "best" matches, determined by the highest
     -+content similarity).  So, for example, if docs/extensions.txt and
     -+docs/config/extensions.txt have similar content, then they will be
     -+marked as a rename even if it turns out that docs/extensions.txt was
     -+more similar to src/extension-checks.c.  At most, one comparison is
     -+done per file in this preliminary pass; so if there are several
     -+extensions.txt files throughout the directory hierarchy that were
     -+added and deleted, this preliminary step will be skipped for those
     -+files.
     -+
     - Note.  When the "-C" option is used with `--find-copies-harder`
     - option, 'git diff-{asterisk}' commands feed unmodified filepairs to
     - diffcore mechanism as well as modified ones.  This lets the copy
     +    Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## t/t4001-diff-rename.sh ##
      @@ t/t4001-diff-rename.sh: test_expect_success 'diff-tree -l0 defaults to a big rename limit, not zero' '
     @@ t/t4001-diff-rename.sh: test_expect_success 'diff-tree -l0 defaults to a big ren
      +	# subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,
      +	# but since same basenames are checked first...
      +	cat >expected <<-\EOF &&
     -+	A	file.md
     -+	R078	subdir/file.txt	file.txt
     ++	R088	subdir/file.txt	file.md
     ++	A	file.txt
      +	EOF
      +	test_cmp expected actual
      +'
 1:  381a45d239bb ! 2:  4fff9b1ff57b diffcore-rename: compute basenames of all source and dest candidates
     @@ Commit message
          basenames still show up in the map, but have an invalid index (-1).
      
          This function was inspired by the fact that in real world repositories,
     -    most renames often do not involve a basename change.  Here are some
     -    sample repositories and the percentage of their historical renames (as of
     -    early 2020) that did not involve a basename change:
     +    files are often moved across directories without changing names.  Here
     +    are some sample repositories and the percentage of their historical
     +    renames (as of early 2020) that preserved basenames:
            * linux: 76%
            * gcc: 64%
            * gecko: 79%
            * webkit: 89%
     +    These statistics alone don't prove that an optimization in this area
     +    will help or how much it will help, since there are also unpaired adds
     +    and deletes, restrictions on which basenames we consider, etc., but it
     +    certainly motivated the idea to try something in this area.
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
     @@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
       	return renames;
       }
       
     ++static const char *get_basename(const char *filename)
     ++{
     ++	/*
     ++	 * gitbasename() has to worry about special drivers, multiple
     ++	 * directory separator characters, trailing slashes, NULL or
     ++	 * empty strings, etc.  We only work on filenames as stored in
     ++	 * git, and thus get to ignore all those complications.
     ++	 */
     ++	const char *base = strrchr(filename, '/');
     ++	return base ? base + 1 : filename;
     ++}
     ++
      +MAYBE_UNUSED
      +static int find_basename_matches(struct diff_options *options,
      +				 int minimum_score,
     @@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
      +	strintmap_init_with_options(&dests, -1, NULL, 0);
      +	for (i = 0; i < num_src; ++i) {
      +		char *filename = rename_src[i].p->one->path;
     -+		char *base;
     ++		const char *base;
      +
      +		/* exact renames removed in remove_unneeded_paths_from_src() */
      +		assert(!rename_src[i].p->one->rename_used);
      +
     -+		base = strrchr(filename, '/');
     -+		base = (base ? base+1 : filename);
     -+
      +		/* Record index within rename_src (i) if basename is unique */
     ++		base = get_basename(filename);
      +		if (strintmap_contains(&sources, base))
      +			strintmap_set(&sources, base, -1);
      +		else
     @@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
      +	}
      +	for (i = 0; i < rename_dst_nr; ++i) {
      +		char *filename = rename_dst[i].p->two->path;
     -+		char *base;
     ++		const char *base;
      +
      +		if (rename_dst[i].is_rename)
      +			continue; /* involved in exact match already. */
      +
     -+		base = strrchr(filename, '/');
     -+		base = (base ? base+1 : filename);
     -+
      +		/* Record index within rename_dst (i) if basename is unique */
     ++		base = get_basename(filename);
      +		if (strintmap_contains(&dests, base))
      +			strintmap_set(&dests, base, -1);
      +		else
 2:  dcd0175229aa ! 3:  dc26881e4ed3 diffcore-rename: complete find_basename_matches()
     @@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
       {
      -	int i;
      +	/*
     -+	 * When I checked, over 76% of file renames in linux just moved
     -+	 * files to a different directory but kept the same basename.  gcc
     -+	 * did that with over 64% of renames, gecko did it with over 79%,
     -+	 * and WebKit did it with over 89%.
     ++	 * When I checked in early 2020, over 76% of file renames in linux
     ++	 * just moved files to a different directory but kept the same
     ++	 * basename.  gcc did that with over 64% of renames, gecko did it
     ++	 * with over 79%, and WebKit did it with over 89%.
      +	 *
      +	 * Therefore we can bypass the normal exhaustive NxM matrix
      +	 * comparison of similarities between all potential rename sources
     -+	 * and destinations by instead using file basename as a hint, checking
     -+	 * for similarity between files with the same basename, and if we
     -+	 * find a pair that are sufficiently similar, record the rename
     -+	 * pair and exclude those two from the NxM matrix.
     ++	 * and destinations by instead using file basename as a hint (i.e.
     ++	 * the portion of the filename after the last '/'), checking for
     ++	 * similarity between files with the same basename, and if we find
     ++	 * a pair that are sufficiently similar, record the rename pair and
     ++	 * exclude those two from the NxM matrix.
      +	 *
      +	 * This *might* cause us to find a less than optimal pairing (if
      +	 * there is another file that we are even more similar to but has a
     @@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
      +	 * basename matching provides, and given the frequency with which
      +	 * people use the same basename in real world projects, that's a
      +	 * trade-off we are willing to accept when doing just rename
     -+	 * detection.  However, if someone wants copy detection that
     -+	 * implies they are willing to spend more cycles to find
     -+	 * similarities between files, so it may be less likely that this
     -+	 * heuristic is wanted.
     ++	 * detection.
     ++	 *
     ++	 * If someone wants copy detection that implies they are willing to
     ++	 * spend more cycles to find similarities between files, so it may
     ++	 * be less likely that this heuristic is wanted.  If someone is
     ++	 * doing break detection, that means they do not want filename
     ++	 * similarity to imply any form of content similiarity, and thus
     ++	 * this heuristic would definitely be incompatible.
      +	 */
      +
      +	int i, renames = 0;
     @@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
       	struct strintmap dests;
       
      +	/*
     -+	 * The prefeteching stuff wants to know if it can skip prefetching blobs
     -+	 * that are unmodified.  unmodified blobs are only relevant when doing
     -+	 * copy detection.  find_basename_matches() is only used when detecting
     -+	 * renames, not when detecting copies, so it'll only be used when a file
     -+	 * only existed in the source.  Since we already know that the file
     -+	 * won't be unmodified, there's no point checking for it; that's just a
     -+	 * waste of resources.  So set skip_unmodified to 0 so that
     -+	 * estimate_similarity() and prefetch() won't waste resources checking
     -+	 * for something we already know is false.
     ++	 * The prefeteching stuff wants to know if it can skip prefetching
     ++	 * blobs that are unmodified...and will then do a little extra work
     ++	 * to verify that the oids are indeed different before prefetching.
     ++	 * Unmodified blobs are only relevant when doing copy detection;
     ++	 * when limiting to rename detection, diffcore_rename[_extended]()
     ++	 * will never be called with unmodified source paths fed to us, so
     ++	 * the extra work necessary to check if rename_src entries are
     ++	 * unmodified would be a small waste.
      +	 */
      +	int skip_unmodified = 0;
      +
     @@ diffcore-rename.c: static int find_basename_matches(struct diff_options *options
      +	/* Now look for basename matchups and do similarity estimation */
      +	for (i = 0; i < num_src; ++i) {
      +		char *filename = rename_src[i].p->one->path;
     -+		char *base = NULL;
     ++		const char *base = NULL;
      +		intptr_t src_index;
      +		intptr_t dst_index;
      +
     -+		/* Get the basename */
     -+		base = strrchr(filename, '/');
     -+		base = (base ? base+1 : filename);
     -+
      +		/* Find out if this basename is unique among sources */
     ++		base = get_basename(filename);
      +		src_index = strintmap_get(&sources, base);
      +		if (src_index == -1)
      +			continue; /* not a unique basename; skip it */
 3:  ce2173aa1fb7 ! 4:  2493f4b2f55d diffcore-rename: guide inexact rename detection based on basenames
     @@ Commit message
          this change improves the performance as follows:
      
                                      Before                  After
     -        no-renames:       13.815 s ±  0.062 s    13.138 s ±  0.086 s
     -        mega-renames:   1799.937 s ±  0.493 s   169.488 s ±  0.494 s
     -        just-one-mega:    51.289 s ±  0.019 s     5.061 s ±  0.017 s
     +        no-renames:       13.815 s ±  0.062 s    13.294 s ±  0.103 s
     +        mega-renames:   1799.937 s ±  0.493 s   187.248 s ±  0.882 s
     +        just-one-mega:    51.289 s ±  0.019 s     5.557 s ±  0.017 s
      
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## diffcore-rename.c ##
     -@@ diffcore-rename.c: static int find_exact_renames(struct diff_options *options)
     - 	return renames;
     +@@ diffcore-rename.c: static const char *get_basename(const char *filename)
     + 	return base ? base + 1 : filename;
       }
       
      -MAYBE_UNUSED
     @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
      +		trace2_region_leave("diff", "cull after exact", options->repo);
      +	} else {
      +		/* Determine minimum score to match basenames */
     -+		int min_basename_score = (int)(5*minimum_score + 0*MAX_SCORE)/5;
     ++		double factor = 0.5;
     ++		char *basename_factor = getenv("GIT_BASENAME_FACTOR");
     ++		int min_basename_score;
     ++
     ++		if (basename_factor)
     ++			factor = strtol(basename_factor, NULL, 10)/100.0;
     ++		assert(factor >= 0.0 && factor <= 1.0);
     ++		min_basename_score = minimum_score +
     ++			(int)(factor * (MAX_SCORE - minimum_score));
      +
      +		/*
      +		 * Cull sources:
      +		 *   - remove ones involved in renames (found via exact match)
      +		 */
     -+		trace2_region_enter("diff", "cull exact", options->repo);
     ++		trace2_region_enter("diff", "cull after exact", options->repo);
      +		remove_unneeded_paths_from_src(want_copies);
     -+		trace2_region_leave("diff", "cull exact", options->repo);
     ++		trace2_region_leave("diff", "cull after exact", options->repo);
      +
      +		/* Utilize file basenames to quickly find renames. */
      +		trace2_region_enter("diff", "basename matches", options->repo);
     @@ diffcore-rename.c: void diffcore_rename(struct diff_options *options)
       
       		m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
       		for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)
     +
     + ## t/t4001-diff-rename.sh ##
     +@@ t/t4001-diff-rename.sh: test_expect_success 'basename similarity vs best similarity' '
     + 	# subdir/file.txt is 89% similar to file.md, 78% similar to file.txt,
     + 	# but since same basenames are checked first...
     + 	cat >expected <<-\EOF &&
     +-	R088	subdir/file.txt	file.md
     +-	A	file.txt
     ++	A	file.md
     ++	R078	subdir/file.txt	file.txt
     + 	EOF
     + 	test_cmp expected actual
     + '
 -:  ------------ > 5:  fc72d24a3358 gitdiffcore doc: mention new preliminary step for rename detection

-- 
gitgitgadget