Improve the documentation and warnings dealing with rename/copy limits

Fix a few small issues with documentation and warnings around the limits for the quadratic portion of rename (&copy) detection.

I also sent out a separate RFC about how and whether to bump {diff,merge}.renameLimit [1]. If there's a quick consensus there, I may add a patch to this series that bumps the limits, but that could also just be done separately afterward.

[1]
https://lore.kernel.org/git/CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com/T/#u

Elijah Newren (3):
doc: clarify documentation for rename/copy limits
doc: document the special handling of -l0
diff: correct warning message when renameLimit exceeded

 Documentation/config/diff.txt  |  7 ++++---
 Documentation/config/merge.txt | 10 ++++++----
 Documentation/diff-options.txt | 14 +++++++++-----
 diff.c                         |  2 +-
 4 files changed, 20 insertions(+), 13 deletions(-)

base-commit: 670b81a890388c60b7032a4f5b879f2ece8c4558
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1044%2Fnewren%2Frename-limit-documentation-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1044/newren/rename-limit-documentation-v1
Pull-Request: https://github.com/git/git/pull/1044

gitgitgadget

From: Elijah Newren <[email protected]>

A few places in the docs implied that rename/copy detection is always quadratic or that all (unpaired) files were involved in the quadratic portion of rename/copy detection. The following two commits each introduced an exception to this:

9027f53cb505 (Do linear-time/space rename logic for exact renames,
2007-10-25)
bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based
on basenames, 2021-02-14)

(As a side note, for copy detection, the basename guided inexact rename detection is turned off and the exact renames will only result in sources (without the dests) being removed from the set of files used in quadratic detection. So, for copy detection, the documentation was closer to correct.)

Avoid implying that all files involved in rename/copy detection are subject to the full quadratic algorithm. While at it, also note the default values for all these settings.

---
 Documentation/config/diff.txt  |  7 ++++---
 Documentation/config/merge.txt | 10 ++++++----
 Documentation/diff-options.txt | 11 ++++++-----
 3 files changed, 16 insertions(+), 12 deletions(-)

index 2d3331f55c2..31b96e8294f 100644
@@ -118,9 +118,10 @@ diff.orderFile::
 	relative to the top of the working tree.
 
 diff.renameLimit::
-	The number of files to consider when performing the copy/rename
-	detection; equivalent to the 'git diff' option `-l`. This setting
-	has no effect if rename detection is turned off.
+	The number of files to consider in the quadratic portion of
+	copy/rename detection; equivalent to the 'git diff' option
+	`-l`.  If not set, the default value is 400.  This setting has
+	no effect if rename detection is turned off.
 
 diff.renames::
 	Whether and how Git detects renames.  If set to "false",

index cb2ed589075..d030b936d1f 100644
@@ -33,10 +33,12 @@ merge.verifySignatures::
 include::fmt-merge-msg.txt[]
 
 merge.renameLimit::
-	The number of files to consider when performing rename detection
-	during a merge; if not specified, defaults to the value of
-	diff.renameLimit. This setting has no effect if rename detection
-	is turned off.
+	The number of files to consider in the quadratic portion of
+	rename detection during a merge.  If not specified, defaults
+	to the value of diff.renameLimit.  If neither
+	merge.renameLimit nor diff.renameLimit are specified, defaults
+	to 1000.  This setting has no effect if rename detection is
+	turned off.
 
 merge.renames::
 	Whether Git detects renames.  If set to "false", rename detection

index 32e6dee5ac3..b5682b83956 100644
@@ -588,11 +588,12 @@ When used together with `-B`, omit also the preimage in the deletion part
 of a delete/create pair.
 
 -l<num>::
-	The `-M` and `-C` options require O(n^2) processing time where n
-	is the number of potential rename/copy targets.  This
-	option prevents rename/copy detection from running if
-	the number of rename/copy targets exceeds the specified
-	number.
+	The `-M` and `-C` options can require O(n^2) processing time
+	where n is the number of potential rename/copy targets.  This
+	option prevents the quadratic portion of rename/copy detection
+	from running if the number of rename/copy targets exceeds the
+	specified number.  Defaults to diff.renameLimit, or if that is
+	also unspecified, to 400.
 
 ifndef::git-format-patch[]
 --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::

gitgitgadget

From: Elijah Newren <[email protected]>

As noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0 mean -l<large>, 2017-11-29), -l0 has had a magical special "large" historical value associated with it. Document this value, particularly since it is not large enough for some uses -- see commit 9f7e4bfa3b6d (diff: remove silent clamp of renameLimit, 2017-11-13).

---
 Documentation/diff-options.txt | 3 +++
 1 file changed, 3 insertions(+)

index b5682b83956..17c8455b908 100644
@@ -595,6 +595,9 @@ of a delete/create pair.
 	specified number.  Defaults to diff.renameLimit, or if that is
 	also unspecified, to 400.
 
+	Note that for backward compatibility reasons, a value of 0 is treated
+	the same as if 32767 was passed.
+
 ifndef::git-format-patch[]
 --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::
 	Select only files that are Added (`A`), Copied (`C`),

gitgitgadget

From: Elijah Newren <[email protected]>

The warning when quadratic rename detection was skipped referred to "inexact rename detection". For years, the only linear portion of rename detection was looking for exact renames, so "inexact rename detection" was an accurate way to refer to the quadratic portion of rename detection. However, that changed with commit bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based on basenames, 2021-02-14), so now the correct way to refer to quadratic rename detection is "quadratic rename detection". Fix the warning accordingly.

---
 diff.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 52c791574b7..343f391edf8 100644
@@ -6284,7 +6284,7 @@ static int is_summary_empty(const struct diff_queue_struct *q)
 }
 
 static const char rename_limit_warning[] =
-N_("inexact rename detection was skipped due to too many files.");
+N_("quadratic rename detection was skipped due to too many files.");
 
 static const char degrade_cc_to_c_warning[] =
 N_("only found copies from modified paths due to too many files.");

gitgitgadget

Good point; I'll make that change and include it in the next re-roll.

Ok, will do. Thanks.

...

...

...

Now that I read this more specific reason for using "quadratic", my earlier comments on patch 1 are slightly less helpful. Specifically, I was recommending to continue using "inexact renames" but that is not 100% true anymore.

I still think this "quadratic rename detection" is perhaps hard to parse as a non-expert. This subtlety of some "easy" inexact renames definitely makes the definition harder.

Since the steps that find inexact renames without the quadratic algorithm are heuristics, perhaps this portion could instead be called "exhaustive rename detection" or even "expensive rename detection"? It perhaps implies more directly that the limit exists as a way to prevent an expensive operation.

Thanks,
-Stolee

The name "exhaustive rename detection" seems reasonable to me. I'll resubmit using that term and see what folks think.

Phrases like "finding inexact renames" and "finding which files were moved with changes" may tell what we are spending cycles on to the end user, but I have to say I agree that "quadratic portion" would not resonate with the intended audiences at all.

Funny. In a sense, since computing content similarity is _more_ precise way to find a pair that is a likely rename than the more recent heuristics, the more expensive "exhaustive" one can be called "more precise rename detection", even though it is tempting to use "inexact" to call it, too ;-)

I'm afraid I'm not following. The more recent heuristics use content similarity as well; in fact, they use the exact same function with a higher threshold: estimate_similarity().

The exhaustiveness of the quadratic portion comes from comparing each file to more other files, not in using a different type of comparison.

Exactly. By culling potential matches early with heuristics, we make a trade-off of risking false-negatives but save a lot of cycles while trying to find "renames with modifications (which is what we called 'inexact rename')", and my comment equated fewer false-negatives with more precision.

Fix a few small issues with documentation and warnings around the limits for the quadratic portion of rename (&copy) detection, and bump the default limits.

Discussion on bumping the limits can be found at [1]. Although it appears we generally agree we could switch to an unlimited setting for merge.renameLimit, that would require some changes to progress bars to notify users how to take action once things start taking a while. So, for now, just bump the limits.

[1]
https://lore.kernel.org/git/CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com/T/#u

Changes since v1:

* Shuffled patch order since the explanation of why "inexact rename detection" is incorrect was in the third patch
* Use the term "exhaustive rename detection" for the quadratic portion
* Simplify -l description by just stating that it defaults to diff.renameLimit (since it in turn has the right default value)
* Fix asciidoc formating
* Include bump of the limits in a new patch

Elijah Newren (4):
diff: correct warning message when renameLimit exceeded
doc: clarify documentation for rename/copy limits
doc: document the special handling of -l0
Bump rename limit defaults (yet again)

 Documentation/config/diff.txt  |  7 ++++---
 Documentation/config/merge.txt | 10 ++++++----
 Documentation/diff-options.txt | 12 ++++++++----
 diff.c                         |  4 ++--
 merge-ort.c                    |  2 +-
 merge-recursive.c              |  2 +-
 6 files changed, 22 insertions(+), 15 deletions(-)

base-commit: d486ca60a51c9cb1fe068803c3f540724e95e83a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1044%2Fnewren%2Frename-limit-documentation-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1044/newren/rename-limit-documentation-v2
Pull-Request: https://github.com/git/git/pull/1044

Range-diff vs v1:

3: 44a5d5efaa6 ! 1: 0d1d0f180a3 diff: correct warning message when renameLimit exceeded
@@ Commit message
detection" was an accurate way to refer to the quadratic portion of rename detection. However, that changed with commit bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based on basenames,
- 2021-02-14), so now the correct way to refer to quadratic rename
- detection is "quadratic rename detection". Fix the warning accordingly.
+ 2021-02-14). Let's instead use the term "exhaustive rename detection"
+ to refer to the quadratic portion.

@@ diff.c: static int is_summary_empty(const struct diff_queue_struct *q)

static const char rename_limit_warning[] =
-N_("inexact rename detection was skipped due to too many files.");
-+N_("quadratic rename detection was skipped due to too many files."); ++N_("exhaustive rename detection was skipped due to too many files.");

static const char degrade_cc_to_c_warning[] =
N_("only found copies from modified paths due to too many files.");
1: 7dc448df6ec ! 2: 4046993a9a2 doc: clarify documentation for rename/copy limits
@@ Documentation/config/diff.txt: diff.orderFile::
- The number of files to consider when performing the copy/rename
- detection; equivalent to the 'git diff' option -l. This setting
- has no effect if rename detection is turned off.
-+ The number of files to consider in the quadratic portion of
++ The number of files to consider in the exhaustive portion of
+ copy/rename detection; equivalent to the 'git diff' option
+ -l. If not set, the default value is 400. This setting has
+ no effect if rename detection is turned off.
@@ Documentation/config/merge.txt: merge.verifySignatures::
- during a merge; if not specified, defaults to the value of
- diff.renameLimit. This setting has no effect if rename detection
- is turned off.
-+ The number of files to consider in the quadratic portion of
++ The number of files to consider in the exhaustive portion of
+ rename detection during a merge. If not specified, defaults
+ to the value of diff.renameLimit. If neither
+ merge.renameLimit nor diff.renameLimit are specified, defaults
@@ Documentation/diff-options.txt: When used together with -B, omit also the prei
- The -M and -C options require O(n^2) processing time where n
- is the number of potential rename/copy targets. This
- option prevents rename/copy detection from running if
-- the number of rename/copy targets exceeds the specified
++ The -M and -C options have an exhaustive portion that
++ requires O(n^2) processing time where n is the number of
++ potential rename/copy targets. This option prevents the
++ exhaustive portion of rename/copy detection from running if
+ the number of rename/copy targets exceeds the specified
- number.
-+ The -M and -C options can require O(n^2) processing time
-+ where n is the number of potential rename/copy targets. This
-+ option prevents the quadratic portion of rename/copy detection
-+ from running if the number of rename/copy targets exceeds the
-+ specified number. Defaults to diff.renameLimit, or if that is
-+ also unspecified, to 400.
++ number. Defaults to diff.renameLimit.

ifndef::git-format-patch[] --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::
2: ee0969429cb ! 3: 6f5767607cd doc: document the special handling of -l0
@@ Commit message

## Documentation/diff-options.txt ##
@@ Documentation/diff-options.txt: of a delete/create pair.
- specified number. Defaults to diff.renameLimit, or if that is
- also unspecified, to 400.
+ exhaustive portion of rename/copy detection from running if
+ the number of rename/copy targets exceeds the specified
+ number. Defaults to diff.renameLimit.
+++
++Note that for backward compatibility reasons, a value of 0 is treated ++the same as if a large value was passed (currently, 32767).

-+ Note that for backward compatibility reasons, a value of 0 is treated
-+ the same as if 32767 was passed.
-+
ifndef::git-format-patch[] --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::
- Select only files that are Added (A), Copied (C),
-: ----------- > 4: 8f1deb6dd16 Bump rename limit defaults (yet again)

gitgitgadget

From: Elijah Newren <[email protected]>

The warning when quadratic rename detection was skipped referred to "inexact rename detection". For years, the only linear portion of rename detection was looking for exact renames, so "inexact rename detection" was an accurate way to refer to the quadratic portion of rename detection. However, that changed with commit bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based on basenames, 2021-02-14). Let's instead use the term "exhaustive rename detection" to refer to the quadratic portion.

---
 diff.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 52c791574b7..2454e34cf6d 100644
@@ -6284,7 +6284,7 @@ static int is_summary_empty(const struct diff_queue_struct *q)
 }
 
 static const char rename_limit_warning[] =
-N_("inexact rename detection was skipped due to too many files.");
+N_("exhaustive rename detection was skipped due to too many files.");
 
 static const char degrade_cc_to_c_warning[] =
 N_("only found copies from modified paths due to too many files.");

gitgitgadget

From: Elijah Newren <[email protected]>

A few places in the docs implied that rename/copy detection is always quadratic or that all (unpaired) files were involved in the quadratic portion of rename/copy detection. The following two commits each introduced an exception to this:

9027f53cb505 (Do linear-time/space rename logic for exact renames,
2007-10-25)
bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based
on basenames, 2021-02-14)

(As a side note, for copy detection, the basename guided inexact rename detection is turned off and the exact renames will only result in sources (without the dests) being removed from the set of files used in quadratic detection. So, for copy detection, the documentation was closer to correct.)

Avoid implying that all files involved in rename/copy detection are subject to the full quadratic algorithm. While at it, also note the default values for all these settings.

---
 Documentation/config/diff.txt  |  7 ++++---
 Documentation/config/merge.txt | 10 ++++++----
 Documentation/diff-options.txt |  9 +++++----
 3 files changed, 15 insertions(+), 11 deletions(-)

index 2d3331f55c2..e26a63d0d42 100644
@@ -118,9 +118,10 @@ diff.orderFile::
 	relative to the top of the working tree.
 
 diff.renameLimit::
-	The number of files to consider when performing the copy/rename
-	detection; equivalent to the 'git diff' option `-l`. This setting
-	has no effect if rename detection is turned off.
+	The number of files to consider in the exhaustive portion of
+	copy/rename detection; equivalent to the 'git diff' option
+	`-l`.  If not set, the default value is 400.  This setting has
+	no effect if rename detection is turned off.
 
 diff.renames::
 	Whether and how Git detects renames.  If set to "false",

index 6b66c83eabe..aca0c92dbe6 100644
@@ -33,10 +33,12 @@ merge.verifySignatures::
 include::fmt-merge-msg.txt[]
 
 merge.renameLimit::
-	The number of files to consider when performing rename detection
-	during a merge; if not specified, defaults to the value of
-	diff.renameLimit. This setting has no effect if rename detection
-	is turned off.
+	The number of files to consider in the exhaustive portion of
+	rename detection during a merge.  If not specified, defaults
+	to the value of diff.renameLimit.  If neither
+	merge.renameLimit nor diff.renameLimit are specified, defaults
+	to 1000.  This setting has no effect if rename detection is
+	turned off.
 
 merge.renames::
 	Whether Git detects renames.  If set to "false", rename detection

index 32e6dee5ac3..11e08c3fd36 100644
@@ -588,11 +588,12 @@ When used together with `-B`, omit also the preimage in the deletion part
 of a delete/create pair.
 
 -l<num>::
-	The `-M` and `-C` options require O(n^2) processing time where n
-	is the number of potential rename/copy targets.  This
-	option prevents rename/copy detection from running if
+	The `-M` and `-C` options have an exhaustive portion that
+	requires O(n^2) processing time where n is the number of
+	potential rename/copy targets.  This option prevents the
+	exhaustive portion of rename/copy detection from running if
 	the number of rename/copy targets exceeds the specified
-	number.
+	number.  Defaults to diff.renameLimit.
 
 ifndef::git-format-patch[]
 --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::

gitgitgadget

From: Elijah Newren <[email protected]>

As noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0 mean -l<large>, 2017-11-29), -l0 has had a magical special "large" historical value associated with it. Document this value, particularly since it is not large enough for some uses -- see commit 9f7e4bfa3b6d (diff: remove silent clamp of renameLimit, 2017-11-13).

---
 Documentation/diff-options.txt | 3 +++
 1 file changed, 3 insertions(+)

index 11e08c3fd36..ba40ac66cc9 100644
@@ -594,6 +594,9 @@ of a delete/create pair.
 	exhaustive portion of rename/copy detection from running if
 	the number of rename/copy targets exceeds the specified
 	number.  Defaults to diff.renameLimit.
++
+Note that for backward compatibility reasons, a value of 0 is treated
+the same as if a large value was passed (currently, 32767).
 
 ifndef::git-format-patch[]
 --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::

gitgitgadget

From: Elijah Newren <[email protected]>

These were last bumped in commit 92c57e5c1d29 (bump rename limit defaults (again), 2011-02-19), and were bumped both because processors had gotten faster, and because people were getting ugly merges that caused problems and reporting it to the mailing list (suggesting that folks were willing to spend more time waiting).

Since that time:
* Linus has continued recommending kernel folks to set diff.renameLimit=0 (maps to 32767, currently)
* Folks with repositories with lots of renames were happy to set merge.renameLimit above 32767, once the code supported that, to get correct cherry-picks
* Processors have gotten faster
* It has been discovered that the timing methodology used last time probably used too large example files.

The last point is probably worth explaining a bit more:

* The "average" file size used appears to have been average blob size in the linux kernel history at the time (probably v2.6.25 or something close to it).
* Since bigger files are modified more frequently, such a computation weights towards larger files.
* Larger files may be more likely to be modified over time, but are not more likely to be renamed -- the mean and median blob size within a tree are a bit higher than the mean and median of blob sizes in the history leading up to that version for the linux kernel.
* The mean blob size in v2.6.25 was half the average blob size in history leading to that point
* The median blob size in v2.6.25 was about 40% of the mean blob size

    in v2.6.25.

* Since the mean blob size is more than double the median blob size, any file as big as the mean will not be compared to any files of median size or less (because they'd be more than 50% dissimilar).
* Since it is the number of files compared that provides the O(n^2) behavior, median-sized files should matter more than mean-sized ones.

The combined effect of the above is that the file size used in past calculations was likely about 5x too large. Combine that with a CPU performance improvement of ~30%, and we can increase the limits by a factor of sqrt(5/(1-.3)) = 2.67, while keeping the original stated time limits.

Keeping the same approximate time limit probably makes sense for diff.renameLimit (there is no progress feedback in e.g. git log -p), but the experience above suggests merge.renameLimit could be extended significantly. In fact, it probably would make sense to have an unlimited default setting for merge.renameLimit, but that would likely need to be coupled with changes to how progress is displayed. (See https://lore.kernel.org/git/YOx+Ok%[email protected]/
for details in that area.) For now, let's just bump the approximate time limit from 10s to 1m.

(Note: We do not want to use actual time limits, because getting results that depend on how loaded your system is that day feels bad, and because we don't discover that we won't get all the renames until after we've put in a lot of work rather than just upfront telling the user there are too many files involved.)

Using the original time limit of 2s for diff.renameLimit, and bumping merge.renameLimit from 10s to 60s, I found the following timings using the simple script at the end of this commit message (on an AWS c5.xlarge which reports as "Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz"):

N Timing
1300 1.995s
7100 59.973s

So let's round down to nice even numbers and bump the limits from 400->1000, and from 1000->7000.

Here is the measure_rename_perf script (adapted from
https://lore.kernel.org/git/[email protected]/
in particular to avoid triggering the linear handling from basename-guided rename detection):

#!/bin/bash

n=$1; shift

rm -rf repo
mkdir repo && cd repo
git init -q -b main

mkdata() {
mkdir $1
for i in seq 1 $2; do
(sed "s/^/$i /" <../sample
echo tag: $1
) >$1/$i
done
}

mkdata initial $n
git add .
git commit -q -m initial

mkdata new $n
git add .
cd new
for i in *; do git mv $i $i.renamed; done
cd ..
git rm -q -rf initial
git commit -q -m new

time git diff-tree -M -l0 --summary HEAD^ HEAD

---
 Documentation/config/diff.txt  | 2 +-
 Documentation/config/merge.txt | 2 +-
 diff.c                         | 2 +-
 merge-ort.c                    | 2 +-
 merge-recursive.c              | 2 +-
 5 files changed, 5 insertions(+), 5 deletions(-)

index e26a63d0d42..167c479f376 100644
@@ -120,7 +120,7 @@ diff.orderFile::
 diff.renameLimit::
 	The number of files to consider in the exhaustive portion of
 	copy/rename detection; equivalent to the 'git diff' option
-	`-l`.  If not set, the default value is 400.  This setting has
+	`-l`.  If not set, the default value is 1000.  This setting has
 	no effect if rename detection is turned off.
 
 diff.renames::

index aca0c92dbe6..101eabb3f0c 100644
@@ -37,7 +37,7 @@ merge.renameLimit::
 	rename detection during a merge.  If not specified, defaults
 	to the value of diff.renameLimit.  If neither
 	merge.renameLimit nor diff.renameLimit are specified, defaults
-	to 1000.  This setting has no effect if rename detection is
+	to 7000.  This setting has no effect if rename detection is
 	turned off.
 
 merge.renames::

index 2454e34cf6d..0244a371d32 100644
@@ -35,7 +35,7 @@
 
 static int diff_detect_rename_default;
 static int diff_indent_heuristic = 1;
-static int diff_rename_limit_default = 400;
+static int diff_rename_limit_default = 1000;
 static int diff_suppress_blank_empty;
 static int diff_use_color_default = -1;
 static int diff_color_moved_default;

index b954f7184a5..8a84375e940 100644
@@ -2558,7 +2558,7 @@ static void detect_regular_renames(struct merge_options *opt,
 	diff_opts.detect_rename = DIFF_DETECT_RENAME;
 	diff_opts.rename_limit = opt->rename_limit;
 	if (opt->rename_limit <= 0)
-		diff_opts.rename_limit = 1000;
+		diff_opts.rename_limit = 7000;
 	diff_opts.rename_score = opt->rename_score;
 	diff_opts.show_rename_progress = opt->show_rename_progress;
 	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;

index 4327e0cfa33..f19f8cc37bd 100644
@@ -1879,7 +1879,7 @@ static struct diff_queue_struct *get_diffpairs(struct merge_options *opt,
 	 */
 	if (opts.detect_rename > DIFF_DETECT_RENAME)
 		opts.detect_rename = DIFF_DETECT_RENAME;
-	opts.rename_limit = (opt->rename_limit >= 0) ? opt->rename_limit : 1000;
+	opts.rename_limit = (opt->rename_limit >= 0) ? opt->rename_limit : 7000;
 	opts.rename_score = opt->rename_score;
 	opts.show_rename_progress = opt->show_rename_progress;
 	opts.output_format = DIFF_FORMAT_NO_OUTPUT;

gitgitgadget

Okay, I think I'm following what you're saying now, mostly, but I'm curious about the false negative comment.

Am I mixing up negatives/positives (as I'm prone to do), or would it be more correct to say the new algorithm risks suboptimal positives rather than that it risks false negatives?

In particular, the new algorithm will compare files with the same basename and just accept that pairing if they are similar enough, even if there might be a better match elsewhere. However, a lack of a match in same-basenamed files will not cause those files to have no match; they will instead just be included in the exhaustive detection portion, so we can still detect renames for such paths.

I'm prone to mixing them up, too, but I think they are the sides of the same coin. Imagine there is a path X on the source side, and two paths Y and Z on the destination side. With exhaustive match, Z might be a better match (content-wise) to X than Y is to X.

For the path X on the source that is matched with a suboptimal counterpart Y on the destination side, we may call the situation a false-positive because with a more exhaustive search we might have been able to find Z that is a better match. For the path Z on the destination side that was culled too early with heuristics and failed to be matched with the source path X that got matched with a suboptimal destination path Y, it is a loss for Z---it wasn't chosen when it should have been (i.e. a false negative, as Z saw no counterparts).

In any case, during the word search for "inexact", "more precise", "more expensive", I do not think negatives and positives will play a big role anyway, so...

Indeed, I've gotten us off on a bit of a tangent, but thanks for taking the time to answer my questions. :-)

...

Perhaps I could simplify that to "...currently defaults to XYZ"? Does that capture your intent well enough?

I agree very much that this shouldn't be a hard promise. If it was, we've broken it repeatedly over the years. Not only have we modified the default numbers multiple times, there have also been multiple times when we've been able to change how many renames could be handled without changing the default numbers for the rename limits. (This was done by adding or improving special cases that allow us to exclude paths from the exhaustive comparison; exact rename detection that someone else added and my more recent improvements to exact rename detection are two simple examples).

Tree OIDs aren't used by the rename detection logic, but you're close.

If git-merge.txt includes it, then rebase, cherry-pick, revert probably should too. (and maybe the -3 option of git-am)

Anyway...

In the "git mv dir-x dir-y" case, if no other changes are made to those files, then the renames would be detectable via blobs having the same hashes (i.e. exact renames). So all these renames would be found regardless of the number of files and without exhaustive detection even kicking in.

If there were thousands of such files, and every one of them were also modified, then the basename-guided rename detection which operates in linear time would still find all the renames, without the exhaustive detection even kicking in (see commits bd24aa2f97a0 (diffcore-rename:
guide inexact rename detection based on basenames, 2021-02-14) and 37a251436447 (diffcore-rename: use directory rename guided basename comparisons, 2021-02-27)).

If this were a merge, and there were thousands of such files renamed and modified, AND they were all further renamed to change their basename, BUT the original directory was unmodified on the other side of history, then we wouldn't need any of the renames for the purposes of the merge and they'd all be excluded from the exhaustive rename detection. Sure, we wouldn't find renames for those files, but that wouldn't change the result of the merge. So, again, no exhaustive rename detection. (See commit 174791f0fb23 (merge-ort: use relevant_sources to filter possible rename sources, 2021-03-11))

(Rebases & cherry-picks also have an advantage of caching renames from previous picks on the upstream side of history to avoid needing to re-detect renames on that side...though it only caches renames that are either relevant or exact.)

Basically, we bail on exhaustive rename detection if, after the linear or faster steps have run (excluding previously cached renames, exact rename detection, skipping irrelevant renames, basename guided rename detection), the number of remaining unpaired source files times the number of remaining unpaired destination files is greater than rename_limit * rename_limit. (If we can assume the numbers match, i.e. N = number of remaining unpaired sources = number of remaining unpaired destinations, then that check simplifies to bailing once N > rename_limit)

I'm not sure if these details are really going to help the users, especially if more special cases are added (and more have been proposed by Johannes and became an Outreachy project, though that one didn't get off the ground). And this explanation is not even fully detailed; I'm still hand waving here in at least four different ways (mostly in ignoring special cases for different fast steps, but also by ignoring copy detection that itself messes with the explanation in multiple ways).

But maybe someone else can figure out a way to hand wave my hand waving down to a simple enough explanation, while also covering copy detection, and managing to do so in a way that doesn't mislead. If so, we can include that in the docs somewhere.

It's slightly sad that we only got a 30% CPU improvement in the past 10 years. Are you just counting clock speed as a short-hand here? I think that doesn't tell the whole story. But all of this is a side-note anyway. What I care about is your actual timings. :)

(It also seems like this rename detection is ripe for parallelization,
but obviously that's a totally separate topic).

Sounds good. Thanks for thoroughly measuring and updating.

-Peff

32767 is not an internal limit; and as such, it is absolutely an artificial limit. I had to use 48941 just a few years ago, and that value (and others larger than 32767) are fully supported.

Making 0 mean unlimited could be done, and I think it'd be a one-line change, but that's not what commit 89973554b52c (diffcore-rename: make diff-tree -l0 mean -l<large>, 2017-11-29) tried to do.

I'm not opposed to such a change in the meaning of "0", but I am opposed to documenting this value as unlimited unless we make it so.

I'm using shorthand when discussing file sizes above (though I used actual measurements when picking new values below). But the 30% came from measuring the timings with the exact same sample file as you and using a lightly modified version of your original script (tweaked to also change file basenames) on an AWS c5xlarge instance. My timings showed they were only about 30% faster than what you got when you last bumped the limits.

All my laptops and even my work machine are pretty old, so I picked an AWS c5xlarge instance hoping it'd represent a relatively new machine (since your benchmarks when you bumped were using a new machine at the time). Maybe the stock c5xlarge instance I picked wasn't a good choice (wasn't new enough? had a low relative clock speed? affected by Spectre patches? had slow disks? something else?). Or maybe single processor speed really did just hit up against Moore's law and nearly all gains have shifted to having more cores available which don't benefit us here since our algorithm is serial.

True.

OK, I thought there was still some 32-bit m*n limits, but I guess not.

Thanks for clarifying. It does seem silly that "0" means "big, but kind of arbitrary". But I'm OK to punt on that change for now (and in the meantime, I have no real opinion on whether or how to document the current behavior).

-Peff

Interesting. My timings are much faster. With a 20k file, I get (on my laptop, which is an i9-9880H):

     N     CPU (2008)    CPU (now)
    10          0.43s       0.007s
   100          0.44s       0.071s
   200          1.40s       0.226s
   400          4.87s       0.788s
   800         18.08s       2.887s
  1000         27.82s       4.431s

The 2008 timings are from the old email you linked in your commit message, and the new one is from running the revised script you showed. The savings seem like more than 30%. I don't know if that's all CPU or if something changed in the code.

Using a 3k file (the median for ls-tree), numbers are similar, but a little smaller (my n=1300 is about 1.4s). So I think we're both in the same ballpark (and certainly an AWS machine is a perfectly fine representative sample of where people might run Git).

-Peff

There was once upon a time, but not since 9f7e4bfa3b6d (diff: remove silent clamp of renameLimit, 2017-11-13).

I was using the script you wrote in 2008, but comparing to your reported numbers in 2011[1]. When you bumped in 2011, you said you picked the limits of 400 & 1000 in order to give rough timings of 2s and 10s. So the table looks more like:

N CPU (2008) CPU (2011) c5xlarge CPU (yours)

 400    4.87s         ~2s      1.106s      0.788s
1000   27.82s        ~10s      6.350s      4.431s

So, 2011->c5xlarge on these (just recomputed now numbers) show improvements of ~45% and ~36%. Maybe I had an outlier run earlier that was in the upper 6s range for N=1000 and I rounded off to 30% for the commit message? Don't know, those numbers are on a laptop that died in the last few days.

But yeah, you are seeing a bigger improvement than I did; 2011->your current laptop shows roughly 56% - 60% improvement.

[1] https://lore.kernel.org/git/[email protected]/

Yeah, dividing any of the timings I get by the ones you get seem to be giving a value somewhere around 1.4, so that seems reassuring on the consistency front. That doesn't fix my jealousy of your faster CPU, but that's a separate problem. :-)

Ah, right. I forgot about the 2011 update. So yeah, things are getting faster, but not as much as I would have hoped as somebody who came of age during the clock speed boom of the 90's. :)

Thanks for humoring my puzzlement (I don't think any of this changes the applicability of your patch).

-Peff

Yes, and it's not as needlessly verbose :)

Some of this we do via includes, but I also think we should have more "concept docs", like gitglossary, gitrevisions, so perhaps gitrenames(5)? Anyway, not for now...

I think it would be good to briefly explain it in the sense of not explaining it, i.e. give the user who ran into this some idea of what they're looking at. Perhaps something like (and maybe this is too long...);

[...] these limits are limits to the number of "steps" in an an algorithm that's subject to change, and whose number of steps will depend on your input data.

They don't correspond to any easily tangible thing, e.g. a limit of 100 has no correspondence with detecting all renames in a commit that changed 10 files, but not a commit that changed 11 files.

The limits were picked to limit runtime to an approximate desired value, given what was thought to be Representative data from a repository similar to linux.git.

If you find your diff/merge take X amount of time doing rename detection, then generally speaking doubling the limit will about double the time we spend on it.

So they're an indirect a way to get to a runtime limit of (what was it, 2 and 10 seconds?).

The reason for this configuration not being a time limit is so that git can guarantee identical results for the same input data across different systems, given the same version and configuration. I.e. the common case of running your attempt at a diff/merge twice in a row, a time limit would produce unpredictable results.

...

Cool, I'll include that change then.

...*quadruple* the time we spend on it.

Seems pretty lengthy. Thinking about it for a bit, perhaps we could just say something like:

After preliminary steps that can detect subsets of renames quickly, an exhaustive fallback algorithm is used that compares all remaining unpaired sources with all remaining unpaired destinations looking for similar files that can be marked as renames. (Or, in the case of copy detection, it compares all original sources with all remaining unpaired destinations). With N sources and N destinations, this algorithm is O(N^2). The rename_limit says to skip this exhaustive step if N is greater than the rename_limit. (More precisely, it says to skip the exhaustive step if number_sources * number_destinations > rename_limit * rename_limit, which handles the case where there are a different number of sources and destinations.)

Fix a few small issues with documentation and warnings around the limits for the quadratic portion of rename (&copy) detection, and bump the default limits.

Discussion on bumping the limits can be found at [1]. Although it appears we generally agree we could switch to an unlimited setting for merge.renameLimit, that would require some changes to progress bars to notify users how to take action once things start taking a while. So, for now, just bump the limits.

[1]
https://lore.kernel.org/git/CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com/T/#u

Changes since v2:

* Change the meaning of "0" to actually mean unlimited, and modify the documentation to mention that.
* Added 'currently' to descriptions to make it clear the defaults are likely to change (again).
* Added a brief explanation of the exhaustive portion of rename detection, as requested by Ævar (though, honestly, I think the thing that actually helps people pick values for the limit is the warning that tells people that rename detection was skipped and how high they need to set the limit if they want to redo the operation and get renames).

Changes since v1:

* Shuffled patch order since the explanation of why "inexact rename detection" is incorrect was in the third patch
* Use the term "exhaustive rename detection" for the quadratic portion
* Simplify -l description by just stating that it defaults to diff.renameLimit (since it in turn has the right default value)
* Fix asciidoc formating
* Include bump of the limits in a new patch

Elijah Newren (4):
diff: correct warning message when renameLimit exceeded
doc: clarify documentation for rename/copy limits
diffcore-rename: treat a rename_limit of 0 as unlimited Bump rename limit defaults (yet again)

 Documentation/config/diff.txt  |  7 ++++---
 Documentation/config/merge.txt | 10 ++++++----
 Documentation/diff-options.txt | 16 +++++++++++-----
 diff.c                         |  4 ++--
 diffcore-rename.c              |  2 +-
 merge-ort.c                    |  2 +-
 merge-recursive.c              |  2 +-
 7 files changed, 26 insertions(+), 17 deletions(-)

base-commit: d486ca60a51c9cb1fe068803c3f540724e95e83a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1044%2Fnewren%2Frename-limit-documentation-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1044/newren/rename-limit-documentation-v3
Pull-Request: https://github.com/git/git/pull/1044

Range-diff vs v2:

 1:  0d1d0f180a3 = 1:  0d1d0f180a3 diff: correct warning message when renameLimit exceeded
 2:  4046993a9a2 ! 2:  193385d7ca1 doc: clarify documentation for rename/copy limits

@@ Documentation/config/diff.txt: diff.orderFile::
- has no effect if rename detection is turned off.
+ The number of files to consider in the exhaustive portion of
+ copy/rename detection; equivalent to the 'git diff' option
-+ -l. If not set, the default value is 400. This setting has
-+ no effect if rename detection is turned off.
++ -l. If not set, the default value is currently 400. This
++ setting has no effect if rename detection is turned off.

diff.renames::
Whether and how Git detects renames. If set to "false",
@@ Documentation/config/merge.txt: merge.verifySignatures::
+ The number of files to consider in the exhaustive portion of
+ rename detection during a merge. If not specified, defaults
+ to the value of diff.renameLimit. If neither
-+ merge.renameLimit nor diff.renameLimit are specified, defaults
-+ to 1000. This setting has no effect if rename detection is
-+ turned off.
++ merge.renameLimit nor diff.renameLimit are specified,
++ currently defaults to 1000. This setting has no effect if
++ rename detection is turned off.

merge.renames::
Whether Git detects renames. If set to "false", rename detection
@@ Documentation/diff-options.txt: When used together with -B, omit also the prei
- The -M and -C options require O(n^2) processing time where n
- is the number of potential rename/copy targets. This
- option prevents rename/copy detection from running if
-+ The -M and -C options have an exhaustive portion that
-+ requires O(n^2) processing time where n is the number of
-+ potential rename/copy targets. This option prevents the
-+ exhaustive portion of rename/copy detection from running if
- the number of rename/copy targets exceeds the specified
+- the number of rename/copy targets exceeds the specified
- number.
-+ number. Defaults to diff.renameLimit.
++ The -M and -C options involve some preliminary steps that
++ can detect subsets of renames/copies cheaply, followed by an
++ exhaustive fallback portion that compares all remaining
++ unpaired destinations to all relevant sources. (For renames,
++ only remaining unpaired sources are relevant; for copies, all
++ original sources are relevant.) For N sources and
++ destinations, this exhaustive check is O(N^2). This option
++ prevents the exhaustive portion of rename/copy detection from
++ running if the number of source/destination files involved
++ exceeds the specified number. Defaults to diff.renameLimit.

ifndef::git-format-patch[] --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::
3: 6f5767607cd ! 3: 00a2072baea doc: document the special handling of -l0
@@ Metadata
Author: Elijah Newren <[email protected]>

## Commit message ##
- doc: document the special handling of -l0
+ diffcore-rename: treat a rename_limit of 0 as unlimited

- As noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0
- mean -l<large>, 2017-11-29), -l0 has had a magical special "large"
- historical value associated with it. Document this value, particularly
- since it is not large enough for some uses -- see commit 9f7e4bfa3b6d
- (diff: remove silent clamp of renameLimit, 2017-11-13).
+ In commit 89973554b52c (diffcore-rename: make diff-tree -l0 mean
+ -l<large>, 2017-11-29), -l0 was given a special magical "large" value,
+ but one which was not large enough for some uses (as can be seen from
+ commit 9f7e4bfa3b6d (diff: remove silent clamp of renameLimit,
+ 2017-11-13). Make 0 (or a negative value) be treated as unlimited
+ instead and update the documentation to mention this.

## Documentation/diff-options.txt ##
@@ Documentation/diff-options.txt: of a delete/create pair.
- exhaustive portion of rename/copy detection from running if
- the number of rename/copy targets exceeds the specified
- number. Defaults to diff.renameLimit.
-++
-+Note that for backward compatibility reasons, a value of 0 is treated -+the same as if a large value was passed (currently, 32767).
+ prevents the exhaustive portion of rename/copy detection from
+ running if the number of source/destination files involved
+ exceeds the specified number. Defaults to diff.renameLimit.
++ Note that a value of 0 is treated as unlimited.

ifndef::git-format-patch[]
--diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::
+
+ ## diffcore-rename.c ##
+@@ diffcore-rename.c: static int too_many_rename_candidates(int num_destinations, int num_sources,
+ * memory for the matrix anyway.
+ */
+ if (rename_limit <= 0)
+- rename_limit = 32767;
++ return 0; /* treat as unlimited */
+ if (st_mult(num_destinations, num_sources)
+ <= st_mult(rename_limit, rename_limit))
+ return 0;
4: 8f1deb6dd16 ! 4: b41278b6680 Bump rename limit defaults (yet again)
@@ Documentation/config/diff.txt: diff.orderFile::
diff.renameLimit::
The number of files to consider in the exhaustive portion of
copy/rename detection; equivalent to the 'git diff' option
-- -l. If not set, the default value is 400. This setting has
-+ -l. If not set, the default value is 1000. This setting has
- no effect if rename detection is turned off.
+- -l. If not set, the default value is currently 400. This
++ -l. If not set, the default value is currently 1000. This
+ setting has no effect if rename detection is turned off.

diff.renames::

@@ Documentation/config/merge.txt
@@ Documentation/config/merge.txt: merge.renameLimit::
rename detection during a merge. If not specified, defaults to the value of diff.renameLimit. If neither
- merge.renameLimit nor diff.renameLimit are specified, defaults
-- to 1000. This setting has no effect if rename detection is
-+ to 7000. This setting has no effect if rename detection is
- turned off.
+ merge.renameLimit nor diff.renameLimit are specified,
+- currently defaults to 1000. This setting has no effect if
++ currently defaults to 7000. This setting has no effect if
+ rename detection is turned off.

merge.renames::

gitgitgadget

From: Elijah Newren <[email protected]>

The warning when quadratic rename detection was skipped referred to "inexact rename detection". For years, the only linear portion of rename detection was looking for exact renames, so "inexact rename detection" was an accurate way to refer to the quadratic portion of rename detection. However, that changed with commit bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based on basenames, 2021-02-14). Let's instead use the term "exhaustive rename detection" to refer to the quadratic portion.

---
 diff.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 52c791574b7..2454e34cf6d 100644
@@ -6284,7 +6284,7 @@ static int is_summary_empty(const struct diff_queue_struct *q)
 }
 
 static const char rename_limit_warning[] =
-N_("inexact rename detection was skipped due to too many files.");
+N_("exhaustive rename detection was skipped due to too many files.");
 
 static const char degrade_cc_to_c_warning[] =
 N_("only found copies from modified paths due to too many files.");

gitgitgadget

From: Elijah Newren <[email protected]>

A few places in the docs implied that rename/copy detection is always quadratic or that all (unpaired) files were involved in the quadratic portion of rename/copy detection. The following two commits each introduced an exception to this:

9027f53cb505 (Do linear-time/space rename logic for exact renames,
2007-10-25)
bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based
on basenames, 2021-02-14)

(As a side note, for copy detection, the basename guided inexact rename detection is turned off and the exact renames will only result in sources (without the dests) being removed from the set of files used in quadratic detection. So, for copy detection, the documentation was closer to correct.)

Avoid implying that all files involved in rename/copy detection are subject to the full quadratic algorithm. While at it, also note the default values for all these settings.

---
 Documentation/config/diff.txt  |  7 ++++---
 Documentation/config/merge.txt | 10 ++++++----
 Documentation/diff-options.txt | 15 ++++++++++-----
 3 files changed, 20 insertions(+), 12 deletions(-)

index 2d3331f55c2..d1b5cfa3542 100644
@@ -118,9 +118,10 @@ diff.orderFile::
 	relative to the top of the working tree.
 
 diff.renameLimit::
-	The number of files to consider when performing the copy/rename
-	detection; equivalent to the 'git diff' option `-l`. This setting
-	has no effect if rename detection is turned off.
+	The number of files to consider in the exhaustive portion of
+	copy/rename detection; equivalent to the 'git diff' option
+	`-l`.  If not set, the default value is currently 400.  This
+	setting has no effect if rename detection is turned off.
 
 diff.renames::
 	Whether and how Git detects renames.  If set to "false",

index 6b66c83eabe..7cd6d7883b6 100644
@@ -33,10 +33,12 @@ merge.verifySignatures::
 include::fmt-merge-msg.txt[]
 
 merge.renameLimit::
-	The number of files to consider when performing rename detection
-	during a merge; if not specified, defaults to the value of
-	diff.renameLimit. This setting has no effect if rename detection
-	is turned off.
+	The number of files to consider in the exhaustive portion of
+	rename detection during a merge.  If not specified, defaults
+	to the value of diff.renameLimit.  If neither
+	merge.renameLimit nor diff.renameLimit are specified,
+	currently defaults to 1000.  This setting has no effect if
+	rename detection is turned off.
 
 merge.renames::
 	Whether Git detects renames.  If set to "false", rename detection

index 32e6dee5ac3..58acfff9289 100644
@@ -588,11 +588,16 @@ When used together with `-B`, omit also the preimage in the deletion part
 of a delete/create pair.
 
 -l<num>::
-	The `-M` and `-C` options require O(n^2) processing time where n
-	is the number of potential rename/copy targets.  This
-	option prevents rename/copy detection from running if
-	the number of rename/copy targets exceeds the specified
-	number.
+	The `-M` and `-C` options involve some preliminary steps that
+	can detect subsets of renames/copies cheaply, followed by an
+	exhaustive fallback portion that compares all remaining
+	unpaired destinations to all relevant sources.  (For renames,
+	only remaining unpaired sources are relevant; for copies, all
+	original sources are relevant.)  For N sources and
+	destinations, this exhaustive check is O(N^2).  This option
+	prevents the exhaustive portion of rename/copy detection from
+	running if the number of source/destination files involved
+	exceeds the specified number.  Defaults to diff.renameLimit.
 
 ifndef::git-format-patch[]
 --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::

gitgitgadget

From: Elijah Newren <[email protected]>

In commit 89973554b52c (diffcore-rename: make diff-tree -l0 mean -l<large>, 2017-11-29), -l0 was given a special magical "large" value, but one which was not large enough for some uses (as can be seen from commit 9f7e4bfa3b6d (diff: remove silent clamp of renameLimit, 2017-11-13). Make 0 (or a negative value) be treated as unlimited instead and update the documentation to mention this.

---
 Documentation/diff-options.txt | 1 +
 diffcore-rename.c              | 2 +-
 2 files changed, 2 insertions(+), 1 deletion(-)

index 58acfff9289..0aebe832057 100644
@@ -598,6 +598,7 @@ of a delete/create pair.
 	prevents the exhaustive portion of rename/copy detection from
 	running if the number of source/destination files involved
 	exceeds the specified number.  Defaults to diff.renameLimit.
+	Note that a value of 0 is treated as unlimited.
 
 ifndef::git-format-patch[]
 --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::

index 3375e24659e..513ba7b05f1 100644
@@ -1021,7 +1021,7 @@ static int too_many_rename_candidates(int num_destinations, int num_sources,
 	 * memory for the matrix anyway.
 	 */
 	if (rename_limit <= 0)
-		rename_limit = 32767;
+		return 0; /* treat as unlimited */
 	if (st_mult(num_destinations, num_sources)
 	    <= st_mult(rename_limit, rename_limit))
 		return 0;

gitgitgadget

From: Elijah Newren <[email protected]>

These were last bumped in commit 92c57e5c1d29 (bump rename limit defaults (again), 2011-02-19), and were bumped both because processors had gotten faster, and because people were getting ugly merges that caused problems and reporting it to the mailing list (suggesting that folks were willing to spend more time waiting).

Since that time:
* Linus has continued recommending kernel folks to set diff.renameLimit=0 (maps to 32767, currently)
* Folks with repositories with lots of renames were happy to set merge.renameLimit above 32767, once the code supported that, to get correct cherry-picks
* Processors have gotten faster
* It has been discovered that the timing methodology used last time probably used too large example files.

The last point is probably worth explaining a bit more:

* The "average" file size used appears to have been average blob size in the linux kernel history at the time (probably v2.6.25 or something close to it).
* Since bigger files are modified more frequently, such a computation weights towards larger files.
* Larger files may be more likely to be modified over time, but are not more likely to be renamed -- the mean and median blob size within a tree are a bit higher than the mean and median of blob sizes in the history leading up to that version for the linux kernel.
* The mean blob size in v2.6.25 was half the average blob size in history leading to that point
* The median blob size in v2.6.25 was about 40% of the mean blob size

    in v2.6.25.

* Since the mean blob size is more than double the median blob size, any file as big as the mean will not be compared to any files of median size or less (because they'd be more than 50% dissimilar).
* Since it is the number of files compared that provides the O(n^2) behavior, median-sized files should matter more than mean-sized ones.

The combined effect of the above is that the file size used in past calculations was likely about 5x too large. Combine that with a CPU performance improvement of ~30%, and we can increase the limits by a factor of sqrt(5/(1-.3)) = 2.67, while keeping the original stated time limits.

Keeping the same approximate time limit probably makes sense for diff.renameLimit (there is no progress feedback in e.g. git log -p), but the experience above suggests merge.renameLimit could be extended significantly. In fact, it probably would make sense to have an unlimited default setting for merge.renameLimit, but that would likely need to be coupled with changes to how progress is displayed. (See https://lore.kernel.org/git/YOx+Ok%[email protected]/
for details in that area.) For now, let's just bump the approximate time limit from 10s to 1m.

(Note: We do not want to use actual time limits, because getting results that depend on how loaded your system is that day feels bad, and because we don't discover that we won't get all the renames until after we've put in a lot of work rather than just upfront telling the user there are too many files involved.)

Using the original time limit of 2s for diff.renameLimit, and bumping merge.renameLimit from 10s to 60s, I found the following timings using the simple script at the end of this commit message (on an AWS c5.xlarge which reports as "Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz"):

N Timing
1300 1.995s
7100 59.973s

So let's round down to nice even numbers and bump the limits from 400->1000, and from 1000->7000.

Here is the measure_rename_perf script (adapted from
https://lore.kernel.org/git/[email protected]/
in particular to avoid triggering the linear handling from basename-guided rename detection):

#!/bin/bash

n=$1; shift

rm -rf repo
mkdir repo && cd repo
git init -q -b main

mkdata() {
mkdir $1
for i in seq 1 $2; do
(sed "s/^/$i /" <../sample
echo tag: $1
) >$1/$i
done
}

mkdata initial $n
git add .
git commit -q -m initial

mkdata new $n
git add .
cd new
for i in *; do git mv $i $i.renamed; done
cd ..
git rm -q -rf initial
git commit -q -m new

time git diff-tree -M -l0 --summary HEAD^ HEAD

---
 Documentation/config/diff.txt  | 2 +-
 Documentation/config/merge.txt | 2 +-
 diff.c                         | 2 +-
 merge-ort.c                    | 2 +-
 merge-recursive.c              | 2 +-
 5 files changed, 5 insertions(+), 5 deletions(-)

index d1b5cfa3542..32f84838ac1 100644
@@ -120,7 +120,7 @@ diff.orderFile::
 diff.renameLimit::
 	The number of files to consider in the exhaustive portion of
 	copy/rename detection; equivalent to the 'git diff' option
-	`-l`.  If not set, the default value is currently 400.  This
+	`-l`.  If not set, the default value is currently 1000.  This
 	setting has no effect if rename detection is turned off.
 
 diff.renames::

index 7cd6d7883b6..e27cc639447 100644
@@ -37,7 +37,7 @@ merge.renameLimit::
 	rename detection during a merge.  If not specified, defaults
 	to the value of diff.renameLimit.  If neither
 	merge.renameLimit nor diff.renameLimit are specified,
-	currently defaults to 1000.  This setting has no effect if
+	currently defaults to 7000.  This setting has no effect if
 	rename detection is turned off.
 
 merge.renames::

index 2454e34cf6d..0244a371d32 100644
@@ -35,7 +35,7 @@
 
 static int diff_detect_rename_default;
 static int diff_indent_heuristic = 1;
-static int diff_rename_limit_default = 400;
+static int diff_rename_limit_default = 1000;
 static int diff_suppress_blank_empty;
 static int diff_use_color_default = -1;
 static int diff_color_moved_default;

index b954f7184a5..8a84375e940 100644
@@ -2558,7 +2558,7 @@ static void detect_regular_renames(struct merge_options *opt,
 	diff_opts.detect_rename = DIFF_DETECT_RENAME;
 	diff_opts.rename_limit = opt->rename_limit;
 	if (opt->rename_limit <= 0)
-		diff_opts.rename_limit = 1000;
+		diff_opts.rename_limit = 7000;
 	diff_opts.rename_score = opt->rename_score;
 	diff_opts.show_rename_progress = opt->show_rename_progress;
 	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;

index 4327e0cfa33..f19f8cc37bd 100644
@@ -1879,7 +1879,7 @@ static struct diff_queue_struct *get_diffpairs(struct merge_options *opt,
 	 */
 	if (opts.detect_rename > DIFF_DETECT_RENAME)
 		opts.detect_rename = DIFF_DETECT_RENAME;
-	opts.rename_limit = (opt->rename_limit >= 0) ? opt->rename_limit : 1000;
+	opts.rename_limit = (opt->rename_limit >= 0) ? opt->rename_limit : 7000;
 	opts.rename_score = opt->rename_score;
 	opts.show_rename_progress = opt->show_rename_progress;
 	opts.output_format = DIFF_FORMAT_NO_OUTPUT;

gitgitgadget

I briefly read through the responses to v2, and it looks like you updated your v3 appropriately. I think the changes since v2 also satisfy my comments on v1. This version LGTM.

Thanks,
-Stolee

Looks sensible. The final phrase chosen ("exhaustive" part) does sound easy-to-understand, too.