{"thread":{"id":"56091","subject":"[PATCH 2/3] doc: document the special handling of -l0","startedAt":"2021-07-11T00:47:12Z","lastAt":"2021-07-15T23:20:52Z","messageCount":44,"participants":["Elijah Newren via GitGitGadget","Bagas Sanjaya","Elijah Newren","Eric Sunshine","Derrick Stolee","Junio C Hamano","Ævar Arnfjörð Bjarmason","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"429661","messageId":"ee0969429cba837ba6d79712706c899d5b231798.1625964399.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.git.git.1625964399.gitgitgadget@gmail.com","subject":"[PATCH 2/3] doc: document the special handling of -l0","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-11T00:46:37Z","receivedAt":"2021-07-11T00:47:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAs noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0\nmean -l, 2017-11-29), -l0 has had a magical special \"large\"\nhistorical value associated with it. Document this value, particularly\nsince it is not large enough for some uses -- see commit 9f7e4bfa3b6d\n(diff: remove silent clamp of renameLimit, 2017-11-13).\n\nSigned-off-by: Elijah Newren \n---\n Documentation/diff-options.txt | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex b5682b83956..17c8455b908 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -595,6 +595,9 @@ of a delete/create pair.\n \tspecified number. Defaults to diff.renameLimit, or if that is\n \talso unspecified, to 400.\n \n+\tNote that for backward compatibility reasons, a value of 0 is treated\n+\tthe same as if 32767 was passed.\n+\n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\n \tSelect only files that are Added (`A`), Copied (`C`),\n-- \ngitgitgadget\n\n"},{"id":"429662","messageId":"7dc448df6ec6edb41464a4115017064cf41b2d83.1625964399.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.git.git.1625964399.gitgitgadget@gmail.com","subject":"[PATCH 1/3] doc: clarify documentation for rename/copy limits","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-11T00:46:36Z","receivedAt":"2021-07-11T00:47:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nA few places in the docs implied that rename/copy detection is always\nquadratic or that all (unpaired) files were involved in the quadratic\nportion of rename/copy detection. The following two commits each\nintroduced an exception to this:\n\n 9027f53cb505 (Do linear-time/space rename logic for exact renames,\n 2007-10-25)\n bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based\n on basenames, 2021-02-14)\n\n(As a side note, for copy detection, the basename guided inexact rename\ndetection is turned off and the exact renames will only result in\nsources (without the dests) being removed from the set of files used in\nquadratic detection. So, for copy detection, the documentation was\ncloser to correct.)\n\nAvoid implying that all files involved in rename/copy detection are\nsubject to the full quadratic algorithm. While at it, also note the\ndefault values for all these settings.\n\nSigned-off-by: Elijah Newren \n---\n Documentation/config/diff.txt | 7 ++++---\n Documentation/config/merge.txt | 10 ++++++----\n Documentation/diff-options.txt | 11 ++++++-----\n 3 files changed, 16 insertions(+), 12 deletions(-)\n\ndiff --git a/Documentation/config/diff.txt b/Documentation/config/diff.txt\nindex 2d3331f55c2..31b96e8294f 100644\n--- a/Documentation/config/diff.txt\n+++ b/Documentation/config/diff.txt\n@@ -118,9 +118,10 @@ diff.orderFile::\n \trelative to the top of the working tree.\n \n diff.renameLimit::\n-\tThe number of files to consider when performing the copy/rename\n-\tdetection; equivalent to the 'git diff' option `-l`. This setting\n-\thas no effect if rename detection is turned off.\n+\tThe number of files to consider in the quadratic portion of\n+\tcopy/rename detection; equivalent to the 'git diff' option\n+\t`-l`. If not set, the default value is 400. This setting has\n+\tno effect if rename detection is turned off.\n \n diff.renames::\n \tWhether and how Git detects renames. If set to \"false\",\ndiff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt\nindex cb2ed589075..d030b936d1f 100644\n--- a/Documentation/config/merge.txt\n+++ b/Documentation/config/merge.txt\n@@ -33,10 +33,12 @@ merge.verifySignatures::\n include::fmt-merge-msg.txt[]\n \n merge.renameLimit::\n-\tThe number of files to consider when performing rename detection\n-\tduring a merge; if not specified, defaults to the value of\n-\tdiff.renameLimit. This setting has no effect if rename detection\n-\tis turned off.\n+\tThe number of files to consider in the quadratic portion of\n+\trename detection during a merge. If not specified, defaults\n+\tto the value of diff.renameLimit. If neither\n+\tmerge.renameLimit nor diff.renameLimit are specified, defaults\n+\tto 1000. This setting has no effect if rename detection is\n+\tturned off.\n \n merge.renames::\n \tWhether Git detects renames. If set to \"false\", rename detection\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex 32e6dee5ac3..b5682b83956 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -588,11 +588,12 @@ When used together with `-B`, omit also the preimage in the deletion part\n of a delete/create pair.\n \n -l::\n-\tThe `-M` and `-C` options require O(n^2) processing time where n\n-\tis the number of potential rename/copy targets. This\n-\toption prevents rename/copy detection from running if\n-\tthe number of rename/copy targets exceeds the specified\n-\tnumber.\n+\tThe `-M` and `-C` options can require O(n^2) processing time\n+\twhere n is the number of potential rename/copy targets. This\n+\toption prevents the quadratic portion of rename/copy detection\n+\tfrom running if the number of rename/copy targets exceeds the\n+\tspecified number. Defaults to diff.renameLimit, or if that is\n+\talso unspecified, to 400.\n \n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\n-- \ngitgitgadget\n\n"},{"id":"429663","messageId":"44a5d5efaa637d01ec3266b34f31d46acce5ef24.1625964399.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.git.git.1625964399.gitgitgadget@gmail.com","subject":"[PATCH 3/3] diff: correct warning message when renameLimit exceeded","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-11T00:46:38Z","receivedAt":"2021-07-11T00:47:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe warning when quadratic rename detection was skipped referred to\n\"inexact rename detection\". For years, the only linear portion of\nrename detection was looking for exact renames, so \"inexact rename\ndetection\" was an accurate way to refer to the quadratic portion of\nrename detection. However, that changed with commit bd24aa2f97a0\n(diffcore-rename: guide inexact rename detection based on basenames,\n2021-02-14), so now the correct way to refer to quadratic rename\ndetection is \"quadratic rename detection\". Fix the warning accordingly.\n\nSigned-off-by: Elijah Newren \n---\n diff.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diff.c b/diff.c\nindex 52c791574b7..343f391edf8 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -6284,7 +6284,7 @@ static int is_summary_empty(const struct diff_queue_struct *q)\n }\n \n static const char rename_limit_warning[] =\n-N_(\"inexact rename detection was skipped due to too many files.\");\n+N_(\"quadratic rename detection was skipped due to too many files.\");\n \n static const char degrade_cc_to_c_warning[] =\n N_(\"only found copies from modified paths due to too many files.\");\n-- \ngitgitgadget\n"},{"id":"429664","messageId":"pull.1044.git.git.1625964399.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":null,"subject":"[PATCH 0/3] Improve the documentation and warnings dealing with rename/copy limits","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-11T00:46:35Z","receivedAt":"2021-07-11T00:47:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Fix a few small issues with documentation and warnings around the limits for\nthe quadratic portion of rename (©) detection.\n\nI also sent out a separate RFC about how and whether to bump\n{diff,merge}.renameLimit [1]. If there's a quick consensus there, I may add\na patch to this series that bumps the limits, but that could also just be\ndone separately afterward.\n\n[1]\nhttps://lore.kernel.org/git/CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com/T/#u\n\nElijah Newren (3):\n doc: clarify documentation for rename/copy limits\n doc: document the special handling of -l0\n diff: correct warning message when renameLimit exceeded\n\n Documentation/config/diff.txt | 7 ++++---\n Documentation/config/merge.txt | 10 ++++++----\n Documentation/diff-options.txt | 14 +++++++++-----\n diff.c | 2 +-\n 4 files changed, 20 insertions(+), 13 deletions(-)\n\n\nbase-commit: 670b81a890388c60b7032a4f5b879f2ece8c4558\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1044%2Fnewren%2Frename-limit-documentation-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1044/newren/rename-limit-documentation-v1\nPull-Request: https://github.com/git/git/pull/1044\n-- \ngitgitgadget\n"},{"id":"429666","messageId":"450310cd-7b01-58f5-1f74-739d61db97fa@gmail.com","threadId":"56091","inReplyTo":"7dc448df6ec6edb41464a4115017064cf41b2d83.1625964399.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] doc: clarify documentation for rename/copy limits","fromName":"Bagas Sanjaya","fromEmail":"bagasdotme@gmail.com","sentAt":"2021-07-11T04:37:34Z","receivedAt":"2021-07-11T04:44:28Z","isPatch":true,"sender":{"key":"bagasdotme@gmail.com","avatar":"https://avatars.githubusercontent.com/u/40219486?v=4"},"body":"On 11/07/21 07.46, Elijah Newren via GitGitGadget wrote:\n> -l::\n> -\tThe `-M` and `-C` options require O(n^2) processing time where n\n> -\tis the number of potential rename/copy targets. This\n> -\toption prevents rename/copy detection from running if\n> -\tthe number of rename/copy targets exceeds the specified\n> -\tnumber.\n> +\tThe `-M` and `-C` options can require O(n^2) processing time\n> +\twhere n is the number of potential rename/copy targets. This\n> +\toption prevents the quadratic portion of rename/copy detection\n> +\tfrom running if the number of rename/copy targets exceeds the\n> +\tspecified number. Defaults to diff.renameLimit, or if that is\n> +\talso unspecified, to 400.\n\nWhy not just defaults to diff.renameLimit if the default for it and -l \nare both 400?\n\n-- \nAn old man doll... just what I always wanted! - Clara\n"},{"id":"429667","messageId":"CABPp-BGQtYeRtK77=7fn7xJPPYV9h=duroTw1tQqbz-9-BXP=A@mail.gmail.com","threadId":"56091","inReplyTo":"450310cd-7b01-58f5-1f74-739d61db97fa@gmail.com","subject":"Re: [PATCH 1/3] doc: clarify documentation for rename/copy limits","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-11T04:52:06Z","receivedAt":"2021-07-11T04:52:23Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Sat, Jul 10, 2021 at 9:37 PM Bagas Sanjaya wrote:\n>\n> On 11/07/21 07.46, Elijah Newren via GitGitGadget wrote:\n> > -l::\n> > - The `-M` and `-C` options require O(n^2) processing time where n\n> > - is the number of potential rename/copy targets. This\n> > - option prevents rename/copy detection from running if\n> > - the number of rename/copy targets exceeds the specified\n> > - number.\n> > + The `-M` and `-C` options can require O(n^2) processing time\n> > + where n is the number of potential rename/copy targets. This\n> > + option prevents the quadratic portion of rename/copy detection\n> > + from running if the number of rename/copy targets exceeds the\n> > + specified number. Defaults to diff.renameLimit, or if that is\n> > + also unspecified, to 400.\n>\n> Why not just defaults to diff.renameLimit if the default for it and -l\n> are both 400?\n\nGood point; I'll make that change and include it in the next re-roll.\n"},{"id":"429668","messageId":"CAPig+cTFoLaUd8+VRsaJuP24C7fnbTTFx0i7PizyasES7K2jdg@mail.gmail.com","threadId":"56091","inReplyTo":"ee0969429cba837ba6d79712706c899d5b231798.1625964399.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/3] doc: document the special handling of -l0","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2021-07-11T04:54:01Z","receivedAt":"2021-07-11T04:54:15Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sat, Jul 10, 2021 at 8:46 PM Elijah Newren via GitGitGadget\n wrote:\n> As noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0\n> mean -l, 2017-11-29), -l0 has had a magical special \"large\"\n> historical value associated with it. Document this value, particularly\n> since it is not large enough for some uses -- see commit 9f7e4bfa3b6d\n> (diff: remove silent clamp of renameLimit, 2017-11-13).\n>\n> Signed-off-by: Elijah Newren \n> ---\n> diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\n> @@ -595,6 +595,9 @@ of a delete/create pair.\n> specified number. Defaults to diff.renameLimit, or if that is\n> also unspecified, to 400.\n>\n> + Note that for backward compatibility reasons, a value of 0 is treated\n> + the same as if 32767 was passed.\n\nTo get this to format properly, you'll need to drop the indentation\nfrom the new paragraph and replace the blank line preceding it with a\nline containing just a plus (`+`).\n"},{"id":"429669","messageId":"CABPp-BErUpi8cS=-OQb3vLHDOSEygV1+bVbKRWWQ-eOvNQ561Q@mail.gmail.com","threadId":"56091","inReplyTo":"CAPig+cTFoLaUd8+VRsaJuP24C7fnbTTFx0i7PizyasES7K2jdg@mail.gmail.com","subject":"Re: [PATCH 2/3] doc: document the special handling of -l0","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-11T04:54:49Z","receivedAt":"2021-07-11T04:55:02Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Sat, Jul 10, 2021 at 9:54 PM Eric Sunshine wrote:\n>\n> On Sat, Jul 10, 2021 at 8:46 PM Elijah Newren via GitGitGadget\n> wrote:\n> > As noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0\n> > mean -l, 2017-11-29), -l0 has had a magical special \"large\"\n> > historical value associated with it. Document this value, particularly\n> > since it is not large enough for some uses -- see commit 9f7e4bfa3b6d\n> > (diff: remove silent clamp of renameLimit, 2017-11-13).\n> >\n> > Signed-off-by: Elijah Newren \n> > ---\n> > diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\n> > @@ -595,6 +595,9 @@ of a delete/create pair.\n> > specified number. Defaults to diff.renameLimit, or if that is\n> > also unspecified, to 400.\n> >\n> > + Note that for backward compatibility reasons, a value of 0 is treated\n> > + the same as if 32767 was passed.\n>\n> To get this to format properly, you'll need to drop the indentation\n> from the new paragraph and replace the blank line preceding it with a\n> line containing just a plus (`+`).\n\nOk, will do. Thanks.\n"},{"id":"429755","messageId":"c25e29a9-3a15-4079-43fd-b77746927b16@gmail.com","threadId":"56091","inReplyTo":"7dc448df6ec6edb41464a4115017064cf41b2d83.1625964399.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] doc: clarify documentation for rename/copy limits","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-07-12T15:03:09Z","receivedAt":"2021-07-12T15:03:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 7/10/2021 8:46 PM, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n...\n> diff.renameLimit::\n> -\tThe number of files to consider when performing the copy/rename\n> -\tdetection; equivalent to the 'git diff' option `-l`. This setting\n> -\thas no effect if rename detection is turned off.\n> +\tThe number of files to consider in the quadratic portion of\n> +\tcopy/rename detection; equivalent to the 'git diff' option\n> +\t`-l`. If not set, the default value is 400. This setting has\n> +\tno effect if rename detection is turned off.\n...\n> merge.renameLimit::\n> -\tThe number of files to consider when performing rename detection\n> -\tduring a merge; if not specified, defaults to the value of\n> -\tdiff.renameLimit. This setting has no effect if rename detection\n> -\tis turned off.\n> +\tThe number of files to consider in the quadratic portion of\n> +\trename detection during a merge. If not specified, defaults\n> +\tto the value of diff.renameLimit. If neither\n> +\tmerge.renameLimit nor diff.renameLimit are specified, defaults\n> +\tto 1000. This setting has no effect if rename detection is\n> +\tturned off.\n...\n> -l::\n> -\tThe `-M` and `-C` options require O(n^2) processing time where n\n> -\tis the number of potential rename/copy targets. This\n> -\toption prevents rename/copy detection from running if\n> -\tthe number of rename/copy targets exceeds the specified\n> -\tnumber.\n> +\tThe `-M` and `-C` options can require O(n^2) processing time\n> +\twhere n is the number of potential rename/copy targets. This\n> +\toption prevents the quadratic portion of rename/copy detection\n> +\tfrom running if the number of rename/copy targets exceeds the\n> +\tspecified number. Defaults to diff.renameLimit, or if that is\n> +\talso unspecified, to 400.\n\nThese changes are clear to me, but I also know how a bit about how\nthe rename algorithm works and what \"the quadratic portion\" means.\nI wonder if this is sufficient detail to help a user less versed in\nGit's internals.\n\nPerhaps we should instead be describing the set of \"potential inexact\nrenames\" as a more descriptive approach? Here is a possible way to\nuse this wording instead:\n\n merge.renameLimit::\n The number of potential inexact renames to consider when\n performing rename detection during a merge; if this limit\n is exceeded, then no inexact renames are computed. Renames\n where the content does not change are excluded from this\n limit. If not specified, defaults to...\n\nFeel free to take or leave any of this example.\n\nThanks,\n-Stolee\n"},{"id":"429756","messageId":"9707b299-3846-6388-36ba-e8d93a28e2ac@gmail.com","threadId":"56091","inReplyTo":"44a5d5efaa637d01ec3266b34f31d46acce5ef24.1625964399.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/3] diff: correct warning message when renameLimit exceeded","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-07-12T15:09:03Z","receivedAt":"2021-07-12T15:09:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 7/10/2021 8:46 PM, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n> \n> The warning when quadratic rename detection was skipped referred to\n> \"inexact rename detection\". For years, the only linear portion of\n> rename detection was looking for exact renames, so \"inexact rename\n> detection\" was an accurate way to refer to the quadratic portion of\n> rename detection. However, that changed with commit bd24aa2f97a0\n> (diffcore-rename: guide inexact rename detection based on basenames,\n> 2021-02-14), so now the correct way to refer to quadratic rename\n> detection is \"quadratic rename detection\". Fix the warning accordingly.\n\nNow that I read this more specific reason for using \"quadratic\", my\nearlier comments on patch 1 are slightly less helpful. Specifically,\nI was recommending to continue using \"inexact renames\" but that is\nnot 100% true anymore.\n\nI still think this \"quadratic rename detection\" is perhaps hard to\nparse as a non-expert. This subtlety of some \"easy\" inexact renames\ndefinitely makes the definition harder.\n\nSince the steps that find inexact renames without the quadratic\nalgorithm are heuristics, perhaps this portion could instead be\ncalled \"exhaustive rename detection\" or even \"expensive rename\ndetection\"? It perhaps implies more directly that the limit exists\nas a way to prevent an expensive operation.\n\nThanks,\n-Stolee\n"},{"id":"429808","messageId":"CABPp-BHF3Os7fOeaF_EQOo+Bs7f1DXbYr26WmAQrPjv63nq1Pg@mail.gmail.com","threadId":"56091","inReplyTo":"9707b299-3846-6388-36ba-e8d93a28e2ac@gmail.com","subject":"Re: [PATCH 3/3] diff: correct warning message when renameLimit exceeded","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-12T18:13:57Z","receivedAt":"2021-07-12T18:14:10Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Mon, Jul 12, 2021 at 8:09 AM Derrick Stolee wrote:\n>\n> On 7/10/2021 8:46 PM, Elijah Newren via GitGitGadget wrote:\n> > From: Elijah Newren \n> >\n> > The warning when quadratic rename detection was skipped referred to\n> > \"inexact rename detection\". For years, the only linear portion of\n> > rename detection was looking for exact renames, so \"inexact rename\n> > detection\" was an accurate way to refer to the quadratic portion of\n> > rename detection. However, that changed with commit bd24aa2f97a0\n> > (diffcore-rename: guide inexact rename detection based on basenames,\n> > 2021-02-14), so now the correct way to refer to quadratic rename\n> > detection is \"quadratic rename detection\". Fix the warning accordingly.\n>\n> Now that I read this more specific reason for using \"quadratic\", my\n> earlier comments on patch 1 are slightly less helpful. Specifically,\n> I was recommending to continue using \"inexact renames\" but that is\n> not 100% true anymore.\n>\n> I still think this \"quadratic rename detection\" is perhaps hard to\n> parse as a non-expert. This subtlety of some \"easy\" inexact renames\n> definitely makes the definition harder.\n>\n> Since the steps that find inexact renames without the quadratic\n> algorithm are heuristics, perhaps this portion could instead be\n> called \"exhaustive rename detection\" or even \"expensive rename\n> detection\"? It perhaps implies more directly that the limit exists\n> as a way to prevent an expensive operation.\n\nThe name \"exhaustive rename detection\" seems reasonable to me. I'll\nresubmit using that term and see what folks think.\n"},{"id":"429839","messageId":"xmqqh7gz2pfe.fsf@gitster.g","threadId":"56091","inReplyTo":"c25e29a9-3a15-4079-43fd-b77746927b16@gmail.com","subject":"Re: [PATCH 1/3] doc: clarify documentation for rename/copy limits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-07-12T21:27:33Z","receivedAt":"2021-07-12T21:27:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> merge.renameLimit::\n> The number of potential inexact renames to consider when\n> performing rename detection during a merge; if this limit\n> is exceeded, then no inexact renames are computed. Renames\n> where the content does not change are excluded from this\n> limit. If not specified, defaults to...\n>\n> Feel free to take or leave any of this example.\n\nPhrases like \"finding inexact renames\" and \"finding which files were\nmoved with changes\" may tell what we are spending cycles on to the\nend user, but I have to say I agree that \"quadratic portion\" would\nnot resonate with the intended audiences at all.\n\n\n"},{"id":"429970","messageId":"xmqqzgupzppb.fsf@gitster.g","threadId":"56091","inReplyTo":"CABPp-BHF3Os7fOeaF_EQOo+Bs7f1DXbYr26WmAQrPjv63nq1Pg@mail.gmail.com","subject":"Re: [PATCH 3/3] diff: correct warning message when renameLimit exceeded","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-07-14T00:47:28Z","receivedAt":"2021-07-14T00:47:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> On Mon, Jul 12, 2021 at 8:09 AM Derrick Stolee wrote:\n>>\n>> Since the steps that find inexact renames without the quadratic\n>> algorithm are heuristics, perhaps this portion could instead be\n>> called \"exhaustive rename detection\" or even \"expensive rename\n>> detection\"? It perhaps implies more directly that the limit exists\n>> as a way to prevent an expensive operation.\n>\n> The name \"exhaustive rename detection\" seems reasonable to me. I'll\n> resubmit using that term and see what folks think.\n\nFunny. In a sense, since computing content similarity is _more_\nprecise way to find a pair that is a likely rename than the more\nrecent heuristics, the more expensive \"exhaustive\" one can be called\n\"more precise rename detection\", even though it is tempting to use\n\"inexact\" to call it, too ;-)\n"},{"id":"429978","messageId":"CABPp-BHdAZYPf0QPOTiekU914u6pNxUSRQEmdN0xOLGv5hdkzA@mail.gmail.com","threadId":"56091","inReplyTo":"xmqqzgupzppb.fsf@gitster.g","subject":"Re: [PATCH 3/3] diff: correct warning message when renameLimit exceeded","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-14T01:06:06Z","receivedAt":"2021-07-14T01:06:19Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Jul 13, 2021 at 5:47 PM Junio C Hamano wrote:\n>\n> Elijah Newren writes:\n>\n> > On Mon, Jul 12, 2021 at 8:09 AM Derrick Stolee wrote:\n> >>\n> >> Since the steps that find inexact renames without the quadratic\n> >> algorithm are heuristics, perhaps this portion could instead be\n> >> called \"exhaustive rename detection\" or even \"expensive rename\n> >> detection\"? It perhaps implies more directly that the limit exists\n> >> as a way to prevent an expensive operation.\n> >\n> > The name \"exhaustive rename detection\" seems reasonable to me. I'll\n> > resubmit using that term and see what folks think.\n>\n> Funny. In a sense, since computing content similarity is _more_\n> precise way to find a pair that is a likely rename than the more\n> recent heuristics, the more expensive \"exhaustive\" one can be called\n> \"more precise rename detection\", even though it is tempting to use\n> \"inexact\" to call it, too ;-)\n\nI'm afraid I'm not following. The more recent heuristics use content\nsimilarity as well; in fact, they use the exact same function with a\nhigher threshold: estimate_similarity().\n\nThe exhaustiveness of the quadratic portion comes from comparing each\nfile to more other files, not in using a different type of comparison.\n"},{"id":"429980","messageId":"xmqqim1dzomt.fsf@gitster.g","threadId":"56091","inReplyTo":"CABPp-BHdAZYPf0QPOTiekU914u6pNxUSRQEmdN0xOLGv5hdkzA@mail.gmail.com","subject":"Re: [PATCH 3/3] diff: correct warning message when renameLimit exceeded","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-07-14T01:10:34Z","receivedAt":"2021-07-14T01:10:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> The exhaustiveness of the quadratic portion comes from comparing each\n> file to more other files, not in using a different type of comparison.\n\nExactly. By culling potential matches early with heuristics, we\nmake a trade-off of risking false-negatives but save a lot of cycles\nwhile trying to find \"renames with modifications (which is what we\ncalled 'inexact rename')\", and my comment equated fewer false-negatives\nwith more precision.\n\n\n"},{"id":"429982","messageId":"pull.1044.v2.git.git.1626225153.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.git.git.1625964399.gitgitgadget@gmail.com","subject":"[PATCH v2 0/4] Rename/copy limits -- docs, warnings, and new defaults","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-14T01:12:29Z","receivedAt":"2021-07-14T01:12:37Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Fix a few small issues with documentation and warnings around the limits for\nthe quadratic portion of rename (©) detection, and bump the default\nlimits.\n\nDiscussion on bumping the limits can be found at [1]. Although it appears we\ngenerally agree we could switch to an unlimited setting for\nmerge.renameLimit, that would require some changes to progress bars to\nnotify users how to take action once things start taking a while. So, for\nnow, just bump the limits.\n\n[1]\nhttps://lore.kernel.org/git/CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com/T/#u\n\nChanges since v1:\n\n * Shuffled patch order since the explanation of why \"inexact rename\n detection\" is incorrect was in the third patch\n * Use the term \"exhaustive rename detection\" for the quadratic portion\n * Simplify -l description by just stating that it defaults to\n diff.renameLimit (since it in turn has the right default value)\n * Fix asciidoc formating\n * Include bump of the limits in a new patch\n\nElijah Newren (4):\n diff: correct warning message when renameLimit exceeded\n doc: clarify documentation for rename/copy limits\n doc: document the special handling of -l0\n Bump rename limit defaults (yet again)\n\n Documentation/config/diff.txt | 7 ++++---\n Documentation/config/merge.txt | 10 ++++++----\n Documentation/diff-options.txt | 12 ++++++++----\n diff.c | 4 ++--\n merge-ort.c | 2 +-\n merge-recursive.c | 2 +-\n 6 files changed, 22 insertions(+), 15 deletions(-)\n\n\nbase-commit: d486ca60a51c9cb1fe068803c3f540724e95e83a\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1044%2Fnewren%2Frename-limit-documentation-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1044/newren/rename-limit-documentation-v2\nPull-Request: https://github.com/git/git/pull/1044\n\nRange-diff vs v1:\n\n 3: 44a5d5efaa6 ! 1: 0d1d0f180a3 diff: correct warning message when renameLimit exceeded\n @@ Commit message\n detection\" was an accurate way to refer to the quadratic portion of\n rename detection. However, that changed with commit bd24aa2f97a0\n (diffcore-rename: guide inexact rename detection based on basenames,\n - 2021-02-14), so now the correct way to refer to quadratic rename\n - detection is \"quadratic rename detection\". Fix the warning accordingly.\n + 2021-02-14). Let's instead use the term \"exhaustive rename detection\"\n + to refer to the quadratic portion.\n \n Signed-off-by: Elijah Newren \n \n @@ diff.c: static int is_summary_empty(const struct diff_queue_struct *q)\n \n static const char rename_limit_warning[] =\n -N_(\"inexact rename detection was skipped due to too many files.\");\n -+N_(\"quadratic rename detection was skipped due to too many files.\");\n ++N_(\"exhaustive rename detection was skipped due to too many files.\");\n \n static const char degrade_cc_to_c_warning[] =\n N_(\"only found copies from modified paths due to too many files.\");\n 1: 7dc448df6ec ! 2: 4046993a9a2 doc: clarify documentation for rename/copy limits\n @@ Documentation/config/diff.txt: diff.orderFile::\n -\tThe number of files to consider when performing the copy/rename\n -\tdetection; equivalent to the 'git diff' option `-l`. This setting\n -\thas no effect if rename detection is turned off.\n -+\tThe number of files to consider in the quadratic portion of\n ++\tThe number of files to consider in the exhaustive portion of\n +\tcopy/rename detection; equivalent to the 'git diff' option\n +\t`-l`. If not set, the default value is 400. This setting has\n +\tno effect if rename detection is turned off.\n @@ Documentation/config/merge.txt: merge.verifySignatures::\n -\tduring a merge; if not specified, defaults to the value of\n -\tdiff.renameLimit. This setting has no effect if rename detection\n -\tis turned off.\n -+\tThe number of files to consider in the quadratic portion of\n ++\tThe number of files to consider in the exhaustive portion of\n +\trename detection during a merge. If not specified, defaults\n +\tto the value of diff.renameLimit. If neither\n +\tmerge.renameLimit nor diff.renameLimit are specified, defaults\n @@ Documentation/diff-options.txt: When used together with `-B`, omit also the prei\n -\tThe `-M` and `-C` options require O(n^2) processing time where n\n -\tis the number of potential rename/copy targets. This\n -\toption prevents rename/copy detection from running if\n --\tthe number of rename/copy targets exceeds the specified\n ++\tThe `-M` and `-C` options have an exhaustive portion that\n ++\trequires O(n^2) processing time where n is the number of\n ++\tpotential rename/copy targets. This option prevents the\n ++\texhaustive portion of rename/copy detection from running if\n + \tthe number of rename/copy targets exceeds the specified\n -\tnumber.\n -+\tThe `-M` and `-C` options can require O(n^2) processing time\n -+\twhere n is the number of potential rename/copy targets. This\n -+\toption prevents the quadratic portion of rename/copy detection\n -+\tfrom running if the number of rename/copy targets exceeds the\n -+\tspecified number. Defaults to diff.renameLimit, or if that is\n -+\talso unspecified, to 400.\n ++\tnumber. Defaults to diff.renameLimit.\n \n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\n 2: ee0969429cb ! 3: 6f5767607cd doc: document the special handling of -l0\n @@ Commit message\n \n ## Documentation/diff-options.txt ##\n @@ Documentation/diff-options.txt: of a delete/create pair.\n - \tspecified number. Defaults to diff.renameLimit, or if that is\n - \talso unspecified, to 400.\n + \texhaustive portion of rename/copy detection from running if\n + \tthe number of rename/copy targets exceeds the specified\n + \tnumber. Defaults to diff.renameLimit.\n +++\n ++Note that for backward compatibility reasons, a value of 0 is treated\n ++the same as if a large value was passed (currently, 32767).\n \n -+\tNote that for backward compatibility reasons, a value of 0 is treated\n -+\tthe same as if 32767 was passed.\n -+\n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\n - \tSelect only files that are Added (`A`), Copied (`C`),\n -: ----------- > 4: 8f1deb6dd16 Bump rename limit defaults (yet again)\n\n-- \ngitgitgadget\n"},{"id":"429983","messageId":"0d1d0f180a35aaf355683909987731f1e0f4539b.1626225154.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v2.git.git.1626225153.gitgitgadget@gmail.com","subject":"[PATCH v2 1/4] diff: correct warning message when renameLimit exceeded","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-14T01:12:30Z","receivedAt":"2021-07-14T01:12:39Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe warning when quadratic rename detection was skipped referred to\n\"inexact rename detection\". For years, the only linear portion of\nrename detection was looking for exact renames, so \"inexact rename\ndetection\" was an accurate way to refer to the quadratic portion of\nrename detection. However, that changed with commit bd24aa2f97a0\n(diffcore-rename: guide inexact rename detection based on basenames,\n2021-02-14). Let's instead use the term \"exhaustive rename detection\"\nto refer to the quadratic portion.\n\nSigned-off-by: Elijah Newren \n---\n diff.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diff.c b/diff.c\nindex 52c791574b7..2454e34cf6d 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -6284,7 +6284,7 @@ static int is_summary_empty(const struct diff_queue_struct *q)\n }\n \n static const char rename_limit_warning[] =\n-N_(\"inexact rename detection was skipped due to too many files.\");\n+N_(\"exhaustive rename detection was skipped due to too many files.\");\n \n static const char degrade_cc_to_c_warning[] =\n N_(\"only found copies from modified paths due to too many files.\");\n-- \ngitgitgadget\n\n"},{"id":"429984","messageId":"4046993a9a2af79029c1ce94d20616831e94d786.1626225154.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v2.git.git.1626225153.gitgitgadget@gmail.com","subject":"[PATCH v2 2/4] doc: clarify documentation for rename/copy limits","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-14T01:12:31Z","receivedAt":"2021-07-14T01:12:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nA few places in the docs implied that rename/copy detection is always\nquadratic or that all (unpaired) files were involved in the quadratic\nportion of rename/copy detection. The following two commits each\nintroduced an exception to this:\n\n 9027f53cb505 (Do linear-time/space rename logic for exact renames,\n 2007-10-25)\n bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based\n on basenames, 2021-02-14)\n\n(As a side note, for copy detection, the basename guided inexact rename\ndetection is turned off and the exact renames will only result in\nsources (without the dests) being removed from the set of files used in\nquadratic detection. So, for copy detection, the documentation was\ncloser to correct.)\n\nAvoid implying that all files involved in rename/copy detection are\nsubject to the full quadratic algorithm. While at it, also note the\ndefault values for all these settings.\n\nSigned-off-by: Elijah Newren \n---\n Documentation/config/diff.txt | 7 ++++---\n Documentation/config/merge.txt | 10 ++++++----\n Documentation/diff-options.txt | 9 +++++----\n 3 files changed, 15 insertions(+), 11 deletions(-)\n\ndiff --git a/Documentation/config/diff.txt b/Documentation/config/diff.txt\nindex 2d3331f55c2..e26a63d0d42 100644\n--- a/Documentation/config/diff.txt\n+++ b/Documentation/config/diff.txt\n@@ -118,9 +118,10 @@ diff.orderFile::\n \trelative to the top of the working tree.\n \n diff.renameLimit::\n-\tThe number of files to consider when performing the copy/rename\n-\tdetection; equivalent to the 'git diff' option `-l`. This setting\n-\thas no effect if rename detection is turned off.\n+\tThe number of files to consider in the exhaustive portion of\n+\tcopy/rename detection; equivalent to the 'git diff' option\n+\t`-l`. If not set, the default value is 400. This setting has\n+\tno effect if rename detection is turned off.\n \n diff.renames::\n \tWhether and how Git detects renames. If set to \"false\",\ndiff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt\nindex 6b66c83eabe..aca0c92dbe6 100644\n--- a/Documentation/config/merge.txt\n+++ b/Documentation/config/merge.txt\n@@ -33,10 +33,12 @@ merge.verifySignatures::\n include::fmt-merge-msg.txt[]\n \n merge.renameLimit::\n-\tThe number of files to consider when performing rename detection\n-\tduring a merge; if not specified, defaults to the value of\n-\tdiff.renameLimit. This setting has no effect if rename detection\n-\tis turned off.\n+\tThe number of files to consider in the exhaustive portion of\n+\trename detection during a merge. If not specified, defaults\n+\tto the value of diff.renameLimit. If neither\n+\tmerge.renameLimit nor diff.renameLimit are specified, defaults\n+\tto 1000. This setting has no effect if rename detection is\n+\tturned off.\n \n merge.renames::\n \tWhether Git detects renames. If set to \"false\", rename detection\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex 32e6dee5ac3..11e08c3fd36 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -588,11 +588,12 @@ When used together with `-B`, omit also the preimage in the deletion part\n of a delete/create pair.\n \n -l::\n-\tThe `-M` and `-C` options require O(n^2) processing time where n\n-\tis the number of potential rename/copy targets. This\n-\toption prevents rename/copy detection from running if\n+\tThe `-M` and `-C` options have an exhaustive portion that\n+\trequires O(n^2) processing time where n is the number of\n+\tpotential rename/copy targets. This option prevents the\n+\texhaustive portion of rename/copy detection from running if\n \tthe number of rename/copy targets exceeds the specified\n-\tnumber.\n+\tnumber. Defaults to diff.renameLimit.\n \n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\n-- \ngitgitgadget\n\n"},{"id":"429985","messageId":"6f5767607cd2ed9d7d9f45e6dc60b07b29d70236.1626225154.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v2.git.git.1626225153.gitgitgadget@gmail.com","subject":"[PATCH v2 3/4] doc: document the special handling of -l0","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-14T01:12:32Z","receivedAt":"2021-07-14T01:12:43Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAs noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0\nmean -l, 2017-11-29), -l0 has had a magical special \"large\"\nhistorical value associated with it. Document this value, particularly\nsince it is not large enough for some uses -- see commit 9f7e4bfa3b6d\n(diff: remove silent clamp of renameLimit, 2017-11-13).\n\nSigned-off-by: Elijah Newren \n---\n Documentation/diff-options.txt | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex 11e08c3fd36..ba40ac66cc9 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -594,6 +594,9 @@ of a delete/create pair.\n \texhaustive portion of rename/copy detection from running if\n \tthe number of rename/copy targets exceeds the specified\n \tnumber. Defaults to diff.renameLimit.\n++\n+Note that for backward compatibility reasons, a value of 0 is treated\n+the same as if a large value was passed (currently, 32767).\n \n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\n-- \ngitgitgadget\n\n"},{"id":"429986","messageId":"8f1deb6dd16a0c0d88cf594d2019b3096dbe5383.1626225154.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v2.git.git.1626225153.gitgitgadget@gmail.com","subject":"[PATCH v2 4/4] Bump rename limit defaults (yet again)","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-14T01:12:33Z","receivedAt":"2021-07-14T01:12:43Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThese were last bumped in commit 92c57e5c1d29 (bump rename limit\ndefaults (again), 2011-02-19), and were bumped both because processors\nhad gotten faster, and because people were getting ugly merges that\ncaused problems and reporting it to the mailing list (suggesting that\nfolks were willing to spend more time waiting).\n\nSince that time:\n * Linus has continued recommending kernel folks to set\n diff.renameLimit=0 (maps to 32767, currently)\n * Folks with repositories with lots of renames were happy to set\n merge.renameLimit above 32767, once the code supported that, to\n get correct cherry-picks\n * Processors have gotten faster\n * It has been discovered that the timing methodology used last time\n probably used too large example files.\n\nThe last point is probably worth explaining a bit more:\n\n * The \"average\" file size used appears to have been average blob size\n in the linux kernel history at the time (probably v2.6.25 or\n something close to it).\n * Since bigger files are modified more frequently, such a computation\n weights towards larger files.\n * Larger files may be more likely to be modified over time, but are\n not more likely to be renamed -- the mean and median blob size\n within a tree are a bit higher than the mean and median of blob\n sizes in the history leading up to that version for the linux\n kernel.\n * The mean blob size in v2.6.25 was half the average blob size in\n history leading to that point\n * The median blob size in v2.6.25 was about 40% of the mean blob size\n in v2.6.25.\n * Since the mean blob size is more than double the median blob size,\n any file as big as the mean will not be compared to any files of\n median size or less (because they'd be more than 50% dissimilar).\n * Since it is the number of files compared that provides the O(n^2)\n behavior, median-sized files should matter more than mean-sized\n ones.\n\nThe combined effect of the above is that the file size used in past\ncalculations was likely about 5x too large. Combine that with a CPU\nperformance improvement of ~30%, and we can increase the limits by\na factor of sqrt(5/(1-.3)) = 2.67, while keeping the original stated\ntime limits.\n\nKeeping the same approximate time limit probably makes sense for\ndiff.renameLimit (there is no progress feedback in e.g. git log -p),\nbut the experience above suggests merge.renameLimit could be extended\nsignificantly. In fact, it probably would make sense to have an\nunlimited default setting for merge.renameLimit, but that would\nlikely need to be coupled with changes to how progress is displayed.\n(See https://lore.kernel.org/git/YOx+Ok%2FEYvLqRMzJ@coredump.intra.peff.net/\nfor details in that area.) For now, let's just bump the approximate\ntime limit from 10s to 1m.\n\n(Note: We do not want to use actual time limits, because getting results\nthat depend on how loaded your system is that day feels bad, and because\nwe don't discover that we won't get all the renames until after we've\nput in a lot of work rather than just upfront telling the user there are\ntoo many files involved.)\n\nUsing the original time limit of 2s for diff.renameLimit, and bumping\nmerge.renameLimit from 10s to 60s, I found the following timings using\nthe simple script at the end of this commit message (on an AWS c5.xlarge\nwhich reports as \"Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz\"):\n\n N Timing\n 1300 1.995s\n 7100 59.973s\n\nSo let's round down to nice even numbers and bump the limits from\n400->1000, and from 1000->7000.\n\nHere is the measure_rename_perf script (adapted from\nhttps://lore.kernel.org/git/20080211113516.GB6344@coredump.intra.peff.net/\nin particular to avoid triggering the linear handling from\nbasename-guided rename detection):\n\n #!/bin/bash\n\n n=$1; shift\n\n rm -rf repo\n mkdir repo && cd repo\n git init -q -b main\n\n mkdata() {\n mkdir $1\n for i in `seq 1 $2`; do\n (sed \"s/^/$i /\" <../sample\n echo tag: $1\n ) >$1/$i\n done\n }\n\n mkdata initial $n\n git add .\n git commit -q -m initial\n\n mkdata new $n\n git add .\n cd new\n for i in *; do git mv $i $i.renamed; done\n cd ..\n git rm -q -rf initial\n git commit -q -m new\n\n time git diff-tree -M -l0 --summary HEAD^ HEAD\n\nSigned-off-by: Elijah Newren \n---\n Documentation/config/diff.txt | 2 +-\n Documentation/config/merge.txt | 2 +-\n diff.c | 2 +-\n merge-ort.c | 2 +-\n merge-recursive.c | 2 +-\n 5 files changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/Documentation/config/diff.txt b/Documentation/config/diff.txt\nindex e26a63d0d42..167c479f376 100644\n--- a/Documentation/config/diff.txt\n+++ b/Documentation/config/diff.txt\n@@ -120,7 +120,7 @@ diff.orderFile::\n diff.renameLimit::\n \tThe number of files to consider in the exhaustive portion of\n \tcopy/rename detection; equivalent to the 'git diff' option\n-\t`-l`. If not set, the default value is 400. This setting has\n+\t`-l`. If not set, the default value is 1000. This setting has\n \tno effect if rename detection is turned off.\n \n diff.renames::\ndiff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt\nindex aca0c92dbe6..101eabb3f0c 100644\n--- a/Documentation/config/merge.txt\n+++ b/Documentation/config/merge.txt\n@@ -37,7 +37,7 @@ merge.renameLimit::\n \trename detection during a merge. If not specified, defaults\n \tto the value of diff.renameLimit. If neither\n \tmerge.renameLimit nor diff.renameLimit are specified, defaults\n-\tto 1000. This setting has no effect if rename detection is\n+\tto 7000. This setting has no effect if rename detection is\n \tturned off.\n \n merge.renames::\ndiff --git a/diff.c b/diff.c\nindex 2454e34cf6d..0244a371d32 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -35,7 +35,7 @@\n \n static int diff_detect_rename_default;\n static int diff_indent_heuristic = 1;\n-static int diff_rename_limit_default = 400;\n+static int diff_rename_limit_default = 1000;\n static int diff_suppress_blank_empty;\n static int diff_use_color_default = -1;\n static int diff_color_moved_default;\ndiff --git a/merge-ort.c b/merge-ort.c\nindex b954f7184a5..8a84375e940 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2558,7 +2558,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_opts.detect_rename = DIFF_DETECT_RENAME;\n \tdiff_opts.rename_limit = opt->rename_limit;\n \tif (opt->rename_limit <= 0)\n-\t\tdiff_opts.rename_limit = 1000;\n+\t\tdiff_opts.rename_limit = 7000;\n \tdiff_opts.rename_score = opt->rename_score;\n \tdiff_opts.show_rename_progress = opt->show_rename_progress;\n \tdiff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 4327e0cfa33..f19f8cc37bd 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -1879,7 +1879,7 @@ static struct diff_queue_struct *get_diffpairs(struct merge_options *opt,\n \t */\n \tif (opts.detect_rename > DIFF_DETECT_RENAME)\n \t\topts.detect_rename = DIFF_DETECT_RENAME;\n-\topts.rename_limit = (opt->rename_limit >= 0) ? opt->rename_limit : 1000;\n+\topts.rename_limit = (opt->rename_limit >= 0) ? opt->rename_limit : 7000;\n \topts.rename_score = opt->rename_score;\n \topts.show_rename_progress = opt->show_rename_progress;\n \topts.output_format = DIFF_FORMAT_NO_OUTPUT;\n-- \ngitgitgadget\n"},{"id":"429988","messageId":"CABPp-BFrLd+h0rzkY5nijVLzXh7bUK5t7Go=EY9jZksCeKqQLg@mail.gmail.com","threadId":"56091","inReplyTo":"xmqqim1dzomt.fsf@gitster.g","subject":"Re: [PATCH 3/3] diff: correct warning message when renameLimit exceeded","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-14T01:22:48Z","receivedAt":"2021-07-14T01:23:02Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Jul 13, 2021 at 6:10 PM Junio C Hamano wrote:\n>\n> Elijah Newren writes:\n>\n> > The exhaustiveness of the quadratic portion comes from comparing each\n> > file to more other files, not in using a different type of comparison.\n>\n> Exactly. By culling potential matches early with heuristics, we\n> make a trade-off of risking false-negatives but save a lot of cycles\n> while trying to find \"renames with modifications (which is what we\n> called 'inexact rename')\", and my comment equated fewer false-negatives\n> with more precision.\n\nOkay, I think I'm following what you're saying now, mostly, but I'm\ncurious about the false negative comment.\n\nAm I mixing up negatives/positives (as I'm prone to do), or would it\nbe more correct to say the new algorithm risks suboptimal positives\nrather than that it risks false negatives?\n\nIn particular, the new algorithm will compare files with the same\nbasename and just accept that pairing if they are similar enough, even\nif there might be a better match elsewhere. However, a lack of a\nmatch in same-basenamed files will not cause those files to have no\nmatch; they will instead just be included in the exhaustive detection\nportion, so we can still detect renames for such paths.\n"},{"id":"429996","messageId":"xmqq7dhtzd7n.fsf@gitster.g","threadId":"56091","inReplyTo":"CABPp-BFrLd+h0rzkY5nijVLzXh7bUK5t7Go=EY9jZksCeKqQLg@mail.gmail.com","subject":"Re: [PATCH 3/3] diff: correct warning message when renameLimit exceeded","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-07-14T05:17:16Z","receivedAt":"2021-07-14T05:17:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> Am I mixing up negatives/positives (as I'm prone to do), or would it\n> be more correct to say the new algorithm risks suboptimal positives\n> rather than that it risks false negatives?\n\nI'm prone to mixing them up, too, but I think they are the sides of\nthe same coin. Imagine there is a path X on the source side, and\ntwo paths Y and Z on the destination side. With exhaustive match,\nZ might be a better match (content-wise) to X than Y is to X.\n\nFor the path X on the source that is matched with a suboptimal\ncounterpart Y on the destination side, we may call the situation a\nfalse-positive because with a more exhaustive search we might have\nbeen able to find Z that is a better match. For the path Z on the\ndestination side that was culled too early with heuristics and\nfailed to be matched with the source path X that got matched with a\nsuboptimal destination path Y, it is a loss for Z---it wasn't chosen\nwhen it should have been (i.e. a false negative, as Z saw no\ncounterparts).\n\nIn any case, during the word search for \"inexact\", \"more precise\",\n\"more expensive\", I do not think negatives and positives will play a\nbig role anyway, so...\n"},{"id":"429997","messageId":"87tukx1gmi.fsf@evledraar.gmail.com","threadId":"56091","inReplyTo":"4046993a9a2af79029c1ce94d20616831e94d786.1626225154.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/4] doc: clarify documentation for rename/copy limits","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-07-14T07:37:58Z","receivedAt":"2021-07-14T07:47:32Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, Jul 14 2021, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n>\n> A few places in the docs implied that rename/copy detection is always\n> quadratic or that all (unpaired) files were involved in the quadratic\n> portion of rename/copy detection. The following two commits each\n> introduced an exception to this:\n>\n> 9027f53cb505 (Do linear-time/space rename logic for exact renames,\n> 2007-10-25)\n> bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based\n> on basenames, 2021-02-14)\n>\n> (As a side note, for copy detection, the basename guided inexact rename\n> detection is turned off and the exact renames will only result in\n> sources (without the dests) being removed from the set of files used in\n> quadratic detection. So, for copy detection, the documentation was\n> closer to correct.)\n>\n> Avoid implying that all files involved in rename/copy detection are\n> subject to the full quadratic algorithm. While at it, also note the\n> default values for all these settings.\n>\n> Signed-off-by: Elijah Newren \n> ---\n> Documentation/config/diff.txt | 7 ++++---\n> Documentation/config/merge.txt | 10 ++++++----\n> Documentation/diff-options.txt | 9 +++++----\n> 3 files changed, 15 insertions(+), 11 deletions(-)\n>\n> diff --git a/Documentation/config/diff.txt b/Documentation/config/diff.txt\n> index 2d3331f55c2..e26a63d0d42 100644\n> --- a/Documentation/config/diff.txt\n> +++ b/Documentation/config/diff.txt\n> @@ -118,9 +118,10 @@ diff.orderFile::\n> \trelative to the top of the working tree.\n> \n> diff.renameLimit::\n> -\tThe number of files to consider when performing the copy/rename\n> -\tdetection; equivalent to the 'git diff' option `-l`. This setting\n> -\thas no effect if rename detection is turned off.\n> +\tThe number of files to consider in the exhaustive portion of\n> +\tcopy/rename detection; equivalent to the 'git diff' option\n> +\t`-l`. If not set, the default value is 400. This setting has\n> +\tno effect if rename detection is turned off.\n\nFor both this...\n\n> diff.renames::\n> \tWhether and how Git detects renames. If set to \"false\",\n> diff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt\n> index 6b66c83eabe..aca0c92dbe6 100644\n> --- a/Documentation/config/merge.txt\n> +++ b/Documentation/config/merge.txt\n> @@ -33,10 +33,12 @@ merge.verifySignatures::\n> include::fmt-merge-msg.txt[]\n> \n> merge.renameLimit::\n> -\tThe number of files to consider when performing rename detection\n> -\tduring a merge; if not specified, defaults to the value of\n> -\tdiff.renameLimit. This setting has no effect if rename detection\n> -\tis turned off.\n> +\tThe number of files to consider in the exhaustive portion of\n> +\trename detection during a merge. If not specified, defaults\n> +\tto the value of diff.renameLimit. If neither\n> +\tmerge.renameLimit nor diff.renameLimit are specified, defaults\n> +\tto 1000. This setting has no effect if rename detection is\n> +\tturned off.\n\n...and this we should really have some wording to the effect of:\n\n ..., defaults to XYZ. The exact (or even approximate) default of XYZ\n should not be relied upon, and may be changed (or these limits even\n removed) in future versions of git.\n\nI.e. let's distinguish a \"this is how it works now, FYI\" from a forward\npromise that it's going to work like that forever.\n\nWhich also leads me to:\n\n> merge.renames::\n> \tWhether Git detects renames. If set to \"false\", rename detection\n> diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\n> index 32e6dee5ac3..11e08c3fd36 100644\n> --- a/Documentation/diff-options.txt\n> +++ b/Documentation/diff-options.txt\n> @@ -588,11 +588,12 @@ When used together with `-B`, omit also the preimage in the deletion part\n> of a delete/create pair.\n> \n> -l::\n> -\tThe `-M` and `-C` options require O(n^2) processing time where n\n> -\tis the number of potential rename/copy targets. This\n> -\toption prevents rename/copy detection from running if\n> +\tThe `-M` and `-C` options have an exhaustive portion that\n> +\trequires O(n^2) processing time where n is the number of\n> +\tpotential rename/copy targets. This option prevents the\n> +\texhaustive portion of rename/copy detection from running if\n> \tthe number of rename/copy targets exceeds the specified\n> -\tnumber.\n> +\tnumber. Defaults to diff.renameLimit.\n\nThis mention of O(n^2). This is not an issue with your patch/series, nd\nthis is an improvement.\n\nBut as a side-comment: Do we explain somewhere how exactly this\n{diff,merge}.renmeLimit=N works for values of N? It's probably fine to\ncontinue to handwave it away, but is there anything that say tells a\nuser what happens if they have 400 files in their repository in a \"x\"\ndirectory and \"git mv x y\"? Will it work, but if they add a 401th file\nit won't for diffs?\n\nI *think* given a skimming of previous discussions that it's \"no\",\ni.e. that this just kicks in for these expensive cases, and e.g. for\nsuch a case of moving the same tree OID from \"x\" to \"y\" we'd\nshort-circuit things, but maybe I'm just making things up at this point.\n\nFeel free to ignore me here, I guess this amounts to a request that it\nwould be great if we could point to some docs about how this works. It's\nprobably too much detail for Documentation/config/{merge,diff}.txt, so\nmaybe a section in either of git-{diff,merge}.txt ?\n"},{"id":"430058","messageId":"CABPp-BGj3JNDOOBcPfR9i1HxSq9e0UtC_O7MCQpweX2O-UTFjg@mail.gmail.com","threadId":"56091","inReplyTo":"xmqq7dhtzd7n.fsf@gitster.g","subject":"Re: [PATCH 3/3] diff: correct warning message when renameLimit exceeded","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-14T15:09:21Z","receivedAt":"2021-07-14T15:09:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Jul 13, 2021 at 10:17 PM Junio C Hamano wrote:\n>\n> Elijah Newren writes:\n>\n> > Am I mixing up negatives/positives (as I'm prone to do), or would it\n> > be more correct to say the new algorithm risks suboptimal positives\n> > rather than that it risks false negatives?\n>\n> I'm prone to mixing them up, too, but I think they are the sides of\n> the same coin. Imagine there is a path X on the source side, and\n> two paths Y and Z on the destination side. With exhaustive match,\n> Z might be a better match (content-wise) to X than Y is to X.\n>\n> For the path X on the source that is matched with a suboptimal\n> counterpart Y on the destination side, we may call the situation a\n> false-positive because with a more exhaustive search we might have\n> been able to find Z that is a better match. For the path Z on the\n> destination side that was culled too early with heuristics and\n> failed to be matched with the source path X that got matched with a\n> suboptimal destination path Y, it is a loss for Z---it wasn't chosen\n> when it should have been (i.e. a false negative, as Z saw no\n> counterparts).\n>\n> In any case, during the word search for \"inexact\", \"more precise\",\n> \"more expensive\", I do not think negatives and positives will play a\n> big role anyway, so...\n\nIndeed, I've gotten us off on a bit of a tangent, but thanks for\ntaking the time to answer my questions. :-)\n"},{"id":"430070","messageId":"CABPp-BHq5hYRa0eT1JcWedadw2O=uC=5v9FdM2gH+EgMeufEqQ@mail.gmail.com","threadId":"56091","inReplyTo":"87tukx1gmi.fsf@evledraar.gmail.com","subject":"Re: [PATCH v2 2/4] doc: clarify documentation for rename/copy limits","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-14T16:30:28Z","receivedAt":"2021-07-14T16:30:42Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jul 14, 2021 at 12:47 AM Ævar Arnfjörð Bjarmason\n wrote:\n>\n> On Wed, Jul 14 2021, Elijah Newren via GitGitGadget wrote:\n>\n> > From: Elijah Newren \n> >\n...\n> > diff --git a/Documentation/config/diff.txt b/Documentation/config/diff.txt\n> > index 2d3331f55c2..e26a63d0d42 100644\n> > --- a/Documentation/config/diff.txt\n> > +++ b/Documentation/config/diff.txt\n> > @@ -118,9 +118,10 @@ diff.orderFile::\n> > relative to the top of the working tree.\n> >\n> > diff.renameLimit::\n> > - The number of files to consider when performing the copy/rename\n> > - detection; equivalent to the 'git diff' option `-l`. This setting\n> > - has no effect if rename detection is turned off.\n> > + The number of files to consider in the exhaustive portion of\n> > + copy/rename detection; equivalent to the 'git diff' option\n> > + `-l`. If not set, the default value is 400. This setting has\n> > + no effect if rename detection is turned off.\n>\n> For both this...\n>\n> > diff.renames::\n> > Whether and how Git detects renames. If set to \"false\",\n> > diff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt\n> > index 6b66c83eabe..aca0c92dbe6 100644\n> > --- a/Documentation/config/merge.txt\n> > +++ b/Documentation/config/merge.txt\n> > @@ -33,10 +33,12 @@ merge.verifySignatures::\n> > include::fmt-merge-msg.txt[]\n> >\n> > merge.renameLimit::\n> > - The number of files to consider when performing rename detection\n> > - during a merge; if not specified, defaults to the value of\n> > - diff.renameLimit. This setting has no effect if rename detection\n> > - is turned off.\n> > + The number of files to consider in the exhaustive portion of\n> > + rename detection during a merge. If not specified, defaults\n> > + to the value of diff.renameLimit. If neither\n> > + merge.renameLimit nor diff.renameLimit are specified, defaults\n> > + to 1000. This setting has no effect if rename detection is\n> > + turned off.\n>\n> ...and this we should really have some wording to the effect of:\n>\n> ..., defaults to XYZ. The exact (or even approximate) default of XYZ\n> should not be relied upon, and may be changed (or these limits even\n> removed) in future versions of git.\n>\n> I.e. let's distinguish a \"this is how it works now, FYI\" from a forward\n> promise that it's going to work like that forever.\n\nPerhaps I could simplify that to \"...currently defaults to XYZ\"? Does\nthat capture your intent well enough?\n\nI agree very much that this shouldn't be a hard promise. If it was,\nwe've broken it repeatedly over the years. Not only have we modified\nthe default numbers multiple times, there have also been multiple\ntimes when we've been able to change how many renames could be handled\nwithout changing the default numbers for the rename limits. (This was\ndone by adding or improving special cases that allow us to exclude\npaths from the exhaustive comparison; exact rename detection that\nsomeone else added and my more recent improvements to exact rename\ndetection are two simple examples).\n\n> Which also leads me to:\n>\n> > merge.renames::\n> > Whether Git detects renames. If set to \"false\", rename detection\n> > diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\n> > index 32e6dee5ac3..11e08c3fd36 100644\n> > --- a/Documentation/diff-options.txt\n> > +++ b/Documentation/diff-options.txt\n> > @@ -588,11 +588,12 @@ When used together with `-B`, omit also the preimage in the deletion part\n> > of a delete/create pair.\n> >\n> > -l::\n> > - The `-M` and `-C` options require O(n^2) processing time where n\n> > - is the number of potential rename/copy targets. This\n> > - option prevents rename/copy detection from running if\n> > + The `-M` and `-C` options have an exhaustive portion that\n> > + requires O(n^2) processing time where n is the number of\n> > + potential rename/copy targets. This option prevents the\n> > + exhaustive portion of rename/copy detection from running if\n> > the number of rename/copy targets exceeds the specified\n> > - number.\n> > + number. Defaults to diff.renameLimit.\n>\n> This mention of O(n^2). This is not an issue with your patch/series, nd\n> this is an improvement.\n>\n> But as a side-comment: Do we explain somewhere how exactly this\n> {diff,merge}.renmeLimit=N works for values of N? It's probably fine to\n> continue to handwave it away, but is there anything that say tells a\n> user what happens if they have 400 files in their repository in a \"x\"\n> directory and \"git mv x y\"? Will it work, but if they add a 401th file\n> it won't for diffs?\n>\n> I *think* given a skimming of previous discussions that it's \"no\",\n> i.e. that this just kicks in for these expensive cases, and e.g. for\n> such a case of moving the same tree OID from \"x\" to \"y\" we'd\n> short-circuit things, but maybe I'm just making things up at this point.\n\nTree OIDs aren't used by the rename detection logic, but you're close.\n\n> Feel free to ignore me here, I guess this amounts to a request that it\n> would be great if we could point to some docs about how this works. It's\n> probably too much detail for Documentation/config/{merge,diff}.txt, so\n> maybe a section in either of git-{diff,merge}.txt ?\n\nIf git-merge.txt includes it, then rebase, cherry-pick, revert\nprobably should too. (and maybe the -3 option of git-am)\n\nAnyway...\n\nIn the \"git mv dir-x dir-y\" case, if no other changes are made to\nthose files, then the renames would be detectable via blobs having the\nsame hashes (i.e. exact renames). So all these renames would be found\nregardless of the number of files and without exhaustive detection\neven kicking in.\n\nIf there were thousands of such files, and every one of them were also\nmodified, then the basename-guided rename detection which operates in\nlinear time would still find all the renames, without the exhaustive\ndetection even kicking in (see commits bd24aa2f97a0 (diffcore-rename:\nguide inexact rename detection based on basenames, 2021-02-14) and\n37a251436447 (diffcore-rename: use directory rename guided basename\ncomparisons, 2021-02-27)).\n\nIf this were a merge, and there were thousands of such files renamed\nand modified, AND they were all further renamed to change their\nbasename, BUT the original directory was unmodified on the other side\nof history, then we wouldn't need any of the renames for the purposes\nof the merge and they'd all be excluded from the exhaustive rename\ndetection. Sure, we wouldn't find renames for those files, but that\nwouldn't change the result of the merge. So, again, no exhaustive\nrename detection. (See commit 174791f0fb23 (merge-ort: use\nrelevant_sources to filter possible rename sources, 2021-03-11))\n\n(Rebases & cherry-picks also have an advantage of caching renames from\nprevious picks on the upstream side of history to avoid needing to\nre-detect renames on that side...though it only caches renames that\nare either relevant or exact.)\n\nBasically, we bail on exhaustive rename detection if, after the linear\nor faster steps have run (excluding previously cached renames, exact\nrename detection, skipping irrelevant renames, basename guided rename\ndetection), the number of remaining unpaired source files times the\nnumber of remaining unpaired destination files is greater than\nrename_limit * rename_limit. (If we can assume the numbers match,\ni.e. N = number of remaining unpaired sources = number of remaining\nunpaired destinations, then that check simplifies to bailing once N >\nrename_limit)\n\n\nI'm not sure if these details are really going to help the users,\nespecially if more special cases are added (and more have been\nproposed by Johannes and became an Outreachy project, though that one\ndidn't get off the ground). And this explanation is not even fully\ndetailed; I'm still hand waving here in at least four different ways\n(mostly in ignoring special cases for different fast steps, but also\nby ignoring copy detection that itself messes with the explanation in\nmultiple ways).\n\nBut maybe someone else can figure out a way to hand wave my hand\nwaving down to a simple enough explanation, while also covering copy\ndetection, and managing to do so in a way that doesn't mislead. If\nso, we can include that in the docs somewhere.\n"},{"id":"430073","messageId":"YO8UPtFr4wRhVTXE@coredump.intra.peff.net","threadId":"56091","inReplyTo":"8f1deb6dd16a0c0d88cf594d2019b3096dbe5383.1626225154.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 4/4] Bump rename limit defaults (yet again)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-14T16:43:42Z","receivedAt":"2021-07-14T16:43:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 14, 2021 at 01:12:33AM +0000, Elijah Newren via GitGitGadget wrote:\n\n> The combined effect of the above is that the file size used in past\n> calculations was likely about 5x too large. Combine that with a CPU\n> performance improvement of ~30%, and we can increase the limits by\n> a factor of sqrt(5/(1-.3)) = 2.67, while keeping the original stated\n> time limits.\n\nIt's slightly sad that we only got a 30% CPU improvement in the past 10\nyears. Are you just counting clock speed as a short-hand here? I think\nthat doesn't tell the whole story. But all of this is a side-note\nanyway. What I care about is your actual timings. :)\n\n(It also seems like this rename detection is ripe for parallelization,\n but obviously that's a totally separate topic).\n\n> Using the original time limit of 2s for diff.renameLimit, and bumping\n> merge.renameLimit from 10s to 60s, I found the following timings using\n> the simple script at the end of this commit message (on an AWS c5.xlarge\n> which reports as \"Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz\"):\n> \n> N Timing\n> 1300 1.995s\n> 7100 59.973s\n> \n> So let's round down to nice even numbers and bump the limits from\n> 400->1000, and from 1000->7000.\n\nSounds good. Thanks for thoroughly measuring and updating.\n\n-Peff\n"},{"id":"430074","messageId":"YO8Ut9b+6D/wR6uf@coredump.intra.peff.net","threadId":"56091","inReplyTo":"6f5767607cd2ed9d7d9f45e6dc60b07b29d70236.1626225154.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 3/4] doc: document the special handling of -l0","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-14T16:45:43Z","receivedAt":"2021-07-14T16:45:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 14, 2021 at 01:12:32AM +0000, Elijah Newren via GitGitGadget wrote:\n\n> From: Elijah Newren \n> \n> As noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0\n> mean -l, 2017-11-29), -l0 has had a magical special \"large\"\n> historical value associated with it. Document this value, particularly\n> since it is not large enough for some uses -- see commit 9f7e4bfa3b6d\n> (diff: remove silent clamp of renameLimit, 2017-11-13).\n> \n> Signed-off-by: Elijah Newren \n> ---\n> Documentation/diff-options.txt | 3 +++\n> 1 file changed, 3 insertions(+)\n> \n> diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\n> index 11e08c3fd36..ba40ac66cc9 100644\n> --- a/Documentation/diff-options.txt\n> +++ b/Documentation/diff-options.txt\n> @@ -594,6 +594,9 @@ of a delete/create pair.\n> \texhaustive portion of rename/copy detection from running if\n> \tthe number of rename/copy targets exceeds the specified\n> \tnumber. Defaults to diff.renameLimit.\n> ++\n> +Note that for backward compatibility reasons, a value of 0 is treated\n> +the same as if a large value was passed (currently, 32767).\n\nGiven the confusion around what \"32767\" even means to users, I wonder if\nwe could just say: a value of 0 removes any artificial limits (but Git\nstill has some internal limits which real-world cases are not likely to\nhit).\n\nRemoving limits is after all the point of \"0\". I'm also not sure if it\nis simply for backwards compatibility. We commonly let \"0\" or \"-1\" mean\n\"no limit\" for convenience. It seems like something we'd want to\nsupport.\n\n-Peff\n"},{"id":"430080","messageId":"CABPp-BFu4-SJrGbeSQTum_JOq4PHAGwGPPLQA+sHZMP4wvqA1w@mail.gmail.com","threadId":"56091","inReplyTo":"YO8Ut9b+6D/wR6uf@coredump.intra.peff.net","subject":"Re: [PATCH v2 3/4] doc: document the special handling of -l0","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-14T17:17:21Z","receivedAt":"2021-07-14T17:17:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jul 14, 2021 at 9:45 AM Jeff King wrote:\n>\n> On Wed, Jul 14, 2021 at 01:12:32AM +0000, Elijah Newren via GitGitGadget wrote:\n>\n> > From: Elijah Newren \n> >\n> > As noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0\n> > mean -l, 2017-11-29), -l0 has had a magical special \"large\"\n> > historical value associated with it. Document this value, particularly\n> > since it is not large enough for some uses -- see commit 9f7e4bfa3b6d\n> > (diff: remove silent clamp of renameLimit, 2017-11-13).\n> >\n> > Signed-off-by: Elijah Newren \n> > ---\n> > Documentation/diff-options.txt | 3 +++\n> > 1 file changed, 3 insertions(+)\n> >\n> > diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\n> > index 11e08c3fd36..ba40ac66cc9 100644\n> > --- a/Documentation/diff-options.txt\n> > +++ b/Documentation/diff-options.txt\n> > @@ -594,6 +594,9 @@ of a delete/create pair.\n> > exhaustive portion of rename/copy detection from running if\n> > the number of rename/copy targets exceeds the specified\n> > number. Defaults to diff.renameLimit.\n> > ++\n> > +Note that for backward compatibility reasons, a value of 0 is treated\n> > +the same as if a large value was passed (currently, 32767).\n>\n> Given the confusion around what \"32767\" even means to users, I wonder if\n> we could just say: a value of 0 removes any artificial limits (but Git\n> still has some internal limits which real-world cases are not likely to\n> hit).\n\n32767 is not an internal limit; and as such, it is absolutely an\nartificial limit. I had to use 48941 just a few years ago, and that\nvalue (and others larger than 32767) are fully supported.\n\n> Removing limits is after all the point of \"0\". I'm also not sure if it\n> is simply for backwards compatibility. We commonly let \"0\" or \"-1\" mean\n> \"no limit\" for convenience. It seems like something we'd want to\n> support.\n\nMaking 0 mean unlimited could be done, and I think it'd be a one-line\nchange, but that's not what commit 89973554b52c (diffcore-rename: make\ndiff-tree -l0 mean -l, 2017-11-29) tried to do.\n\nI'm not opposed to such a change in the meaning of \"0\", but I am\nopposed to documenting this value as unlimited unless we make it so.\n"},{"id":"430092","messageId":"CABPp-BG7T2QP+6uP57NuE1Htr-vBzozL-aDxU4FsyQO+ELQ9Uw@mail.gmail.com","threadId":"56091","inReplyTo":"YO8UPtFr4wRhVTXE@coredump.intra.peff.net","subject":"Re: [PATCH v2 4/4] Bump rename limit defaults (yet again)","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-14T17:32:56Z","receivedAt":"2021-07-14T17:33:09Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jul 14, 2021 at 9:43 AM Jeff King wrote:\n>\n> On Wed, Jul 14, 2021 at 01:12:33AM +0000, Elijah Newren via GitGitGadget wrote:\n>\n> > The combined effect of the above is that the file size used in past\n> > calculations was likely about 5x too large. Combine that with a CPU\n> > performance improvement of ~30%, and we can increase the limits by\n> > a factor of sqrt(5/(1-.3)) = 2.67, while keeping the original stated\n> > time limits.\n>\n> It's slightly sad that we only got a 30% CPU improvement in the past 10\n> years. Are you just counting clock speed as a short-hand here? I think\n> that doesn't tell the whole story. But all of this is a side-note\n> anyway. What I care about is your actual timings. :)\n\nI'm using shorthand when discussing file sizes above (though I used\nactual measurements when picking new values below). But the 30% came\nfrom measuring the timings with the exact same sample file as you and\nusing a lightly modified version of your original script (tweaked to\nalso change file basenames) on an AWS c5xlarge instance. My timings\nshowed they were only about 30% faster than what you got when you last\nbumped the limits.\n\nAll my laptops and even my work machine are pretty old, so I picked an\nAWS c5xlarge instance hoping it'd represent a relatively new machine\n(since your benchmarks when you bumped were using a new machine at the\ntime). Maybe the stock c5xlarge instance I picked wasn't a good\nchoice (wasn't new enough? had a low relative clock speed? affected by\nSpectre patches? had slow disks? something else?). Or maybe single\nprocessor speed really did just hit up against Moore's law and nearly\nall gains have shifted to having more cores available which don't\nbenefit us here since our algorithm is serial.\n\n> (It also seems like this rename detection is ripe for parallelization,\n> but obviously that's a totally separate topic).\n\nTrue.\n\n> > Using the original time limit of 2s for diff.renameLimit, and bumping\n> > merge.renameLimit from 10s to 60s, I found the following timings using\n> > the simple script at the end of this commit message (on an AWS c5.xlarge\n> > which reports as \"Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz\"):\n> >\n> > N Timing\n> > 1300 1.995s\n> > 7100 59.973s\n> >\n> > So let's round down to nice even numbers and bump the limits from\n> > 400->1000, and from 1000->7000.\n>\n> Sounds good. Thanks for thoroughly measuring and updating.\n"},{"id":"430093","messageId":"YO8f/A8qnTEDlnAr@coredump.intra.peff.net","threadId":"56091","inReplyTo":"CABPp-BFu4-SJrGbeSQTum_JOq4PHAGwGPPLQA+sHZMP4wvqA1w@mail.gmail.com","subject":"Re: [PATCH v2 3/4] doc: document the special handling of -l0","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-14T17:33:48Z","receivedAt":"2021-07-14T17:33:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 14, 2021 at 10:17:21AM -0700, Elijah Newren wrote:\n\n> > > +Note that for backward compatibility reasons, a value of 0 is treated\n> > > +the same as if a large value was passed (currently, 32767).\n> >\n> > Given the confusion around what \"32767\" even means to users, I wonder if\n> > we could just say: a value of 0 removes any artificial limits (but Git\n> > still has some internal limits which real-world cases are not likely to\n> > hit).\n> \n> 32767 is not an internal limit; and as such, it is absolutely an\n> artificial limit. I had to use 48941 just a few years ago, and that\n> value (and others larger than 32767) are fully supported.\n\nOK, I thought there was still some 32-bit m*n limits, but I guess not.\n\n> > Removing limits is after all the point of \"0\". I'm also not sure if it\n> > is simply for backwards compatibility. We commonly let \"0\" or \"-1\" mean\n> > \"no limit\" for convenience. It seems like something we'd want to\n> > support.\n> \n> Making 0 mean unlimited could be done, and I think it'd be a one-line\n> change, but that's not what commit 89973554b52c (diffcore-rename: make\n> diff-tree -l0 mean -l, 2017-11-29) tried to do.\n> \n> I'm not opposed to such a change in the meaning of \"0\", but I am\n> opposed to documenting this value as unlimited unless we make it so.\n\nThanks for clarifying. It does seem silly that \"0\" means \"big, but kind\nof arbitrary\". But I'm OK to punt on that change for now (and in the\nmeantime, I have no real opinion on whether or how to document the\ncurrent behavior).\n\n-Peff\n"},{"id":"430095","messageId":"YO8lgYa5/RlL1zGp@coredump.intra.peff.net","threadId":"56091","inReplyTo":"CABPp-BG7T2QP+6uP57NuE1Htr-vBzozL-aDxU4FsyQO+ELQ9Uw@mail.gmail.com","subject":"Re: [PATCH v2 4/4] Bump rename limit defaults (yet again)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-14T17:57:21Z","receivedAt":"2021-07-14T17:57:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 14, 2021 at 10:32:56AM -0700, Elijah Newren wrote:\n\n> > It's slightly sad that we only got a 30% CPU improvement in the past 10\n> > years. Are you just counting clock speed as a short-hand here? I think\n> > that doesn't tell the whole story. But all of this is a side-note\n> > anyway. What I care about is your actual timings. :)\n> \n> I'm using shorthand when discussing file sizes above (though I used\n> actual measurements when picking new values below). But the 30% came\n> from measuring the timings with the exact same sample file as you and\n> using a lightly modified version of your original script (tweaked to\n> also change file basenames) on an AWS c5xlarge instance. My timings\n> showed they were only about 30% faster than what you got when you last\n> bumped the limits.\n\nInteresting. My timings are much faster. With a 20k file, I get (on my\nlaptop, which is an i9-9880H):\n\n N CPU (2008) CPU (now)\n 10 0.43s 0.007s\n 100 0.44s 0.071s\n 200 1.40s 0.226s\n 400 4.87s 0.788s\n 800 18.08s 2.887s\n 1000 27.82s 4.431s\n\nThe 2008 timings are from the old email you linked in your commit\nmessage, and the new one is from running the revised script you showed.\nThe savings seem like more than 30%. I don't know if that's all CPU or\nif something changed in the code.\n\nUsing a 3k file (the median for ls-tree), numbers are similar, but a\nlittle smaller (my n=1300 is about 1.4s). So I think we're both in the\nsame ballpark (and certainly an AWS machine is a perfectly fine\nrepresentative sample of where people might run Git).\n\n-Peff\n"},{"id":"430109","messageId":"CABPp-BGtdUcz1M2BZCNmX9XG=pxr2tdywgCR=X3Lgt6-o7aMiQ@mail.gmail.com","threadId":"56091","inReplyTo":"YO8f/A8qnTEDlnAr@coredump.intra.peff.net","subject":"Re: [PATCH v2 3/4] doc: document the special handling of -l0","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-14T19:32:52Z","receivedAt":"2021-07-14T19:33:06Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jul 14, 2021 at 10:33 AM Jeff King wrote:\n>\n> On Wed, Jul 14, 2021 at 10:17:21AM -0700, Elijah Newren wrote:\n>\n> > > > +Note that for backward compatibility reasons, a value of 0 is treated\n> > > > +the same as if a large value was passed (currently, 32767).\n> > >\n> > > Given the confusion around what \"32767\" even means to users, I wonder if\n> > > we could just say: a value of 0 removes any artificial limits (but Git\n> > > still has some internal limits which real-world cases are not likely to\n> > > hit).\n> >\n> > 32767 is not an internal limit; and as such, it is absolutely an\n> > artificial limit. I had to use 48941 just a few years ago, and that\n> > value (and others larger than 32767) are fully supported.\n>\n> OK, I thought there was still some 32-bit m*n limits, but I guess not.\n\nThere was once upon a time, but not since 9f7e4bfa3b6d (diff: remove\nsilent clamp of renameLimit, 2017-11-13).\n\n> > > Removing limits is after all the point of \"0\". I'm also not sure if it\n> > > is simply for backwards compatibility. We commonly let \"0\" or \"-1\" mean\n> > > \"no limit\" for convenience. It seems like something we'd want to\n> > > support.\n> >\n> > Making 0 mean unlimited could be done, and I think it'd be a one-line\n> > change, but that's not what commit 89973554b52c (diffcore-rename: make\n> > diff-tree -l0 mean -l, 2017-11-29) tried to do.\n> >\n> > I'm not opposed to such a change in the meaning of \"0\", but I am\n> > opposed to documenting this value as unlimited unless we make it so.\n>\n> Thanks for clarifying. It does seem silly that \"0\" means \"big, but kind\n> of arbitrary\". But I'm OK to punt on that change for now (and in the\n> meantime, I have no real opinion on whether or how to document the\n> current behavior).\n>\n> -Peff\n"},{"id":"430117","messageId":"CABPp-BE=Ghkm=sZ05=A=1vC1zscbVk7qXgeEjpA5gHxsfTGAyg@mail.gmail.com","threadId":"56091","inReplyTo":"YO8lgYa5/RlL1zGp@coredump.intra.peff.net","subject":"Re: [PATCH v2 4/4] Bump rename limit defaults (yet again)","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-14T20:03:43Z","receivedAt":"2021-07-14T20:08:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jul 14, 2021 at 10:57 AM Jeff King wrote:\n>\n> On Wed, Jul 14, 2021 at 10:32:56AM -0700, Elijah Newren wrote:\n>\n> > > It's slightly sad that we only got a 30% CPU improvement in the past 10\n> > > years. Are you just counting clock speed as a short-hand here? I think\n> > > that doesn't tell the whole story. But all of this is a side-note\n> > > anyway. What I care about is your actual timings. :)\n> >\n> > I'm using shorthand when discussing file sizes above (though I used\n> > actual measurements when picking new values below). But the 30% came\n> > from measuring the timings with the exact same sample file as you and\n> > using a lightly modified version of your original script (tweaked to\n> > also change file basenames) on an AWS c5xlarge instance. My timings\n> > showed they were only about 30% faster than what you got when you last\n> > bumped the limits.\n>\n> Interesting. My timings are much faster. With a 20k file, I get (on my\n> laptop, which is an i9-9880H):\n>\n> N CPU (2008) CPU (now)\n> 10 0.43s 0.007s\n> 100 0.44s 0.071s\n> 200 1.40s 0.226s\n> 400 4.87s 0.788s\n> 800 18.08s 2.887s\n> 1000 27.82s 4.431s\n>\n> The 2008 timings are from the old email you linked in your commit\n> message, and the new one is from running the revised script you showed.\n> The savings seem like more than 30%. I don't know if that's all CPU or\n> if something changed in the code.\n\nI was using the script you wrote in 2008, but comparing to your\nreported numbers in 2011[1]. When you bumped in 2011, you said you\npicked the limits of 400 & 1000 in order to give rough timings of 2s\nand 10s. So the table looks more like:\n\n N CPU (2008) CPU (2011) c5xlarge CPU (yours)\n 400 4.87s ~2s 1.106s 0.788s\n1000 27.82s ~10s 6.350s 4.431s\n\nSo, 2011->c5xlarge on these (just recomputed now numbers) show\nimprovements of ~45% and ~36%. Maybe I had an outlier run earlier\nthat was in the upper 6s range for N=1000 and I rounded off to 30% for\nthe commit message? Don't know, those numbers are on a laptop that\ndied in the last few days.\n\nBut yeah, you are seeing a bigger improvement than I did; 2011->your\ncurrent laptop shows roughly 56% - 60% improvement.\n\n[1] https://lore.kernel.org/git/20110219102128.GB22508@sigill.intra.peff.net/\n\n> Using a 3k file (the median for ls-tree), numbers are similar, but a\n> little smaller (my n=1300 is about 1.4s). So I think we're both in the\n> same ballpark (and certainly an AWS machine is a perfectly fine\n> representative sample of where people might run Git).\n\nYeah, dividing any of the timings I get by the ones you get seem to be\ngiving a value somewhere around 1.4, so that seems reassuring on the\nconsistency front. That doesn't fix my jealousy of your faster CPU,\nbut that's a separate problem. :-)\n"},{"id":"430126","messageId":"YO9NROIgMpo2zqU/@coredump.intra.peff.net","threadId":"56091","inReplyTo":"CABPp-BE=Ghkm=sZ05=A=1vC1zscbVk7qXgeEjpA5gHxsfTGAyg@mail.gmail.com","subject":"Re: [PATCH v2 4/4] Bump rename limit defaults (yet again)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-07-14T20:47:00Z","receivedAt":"2021-07-14T20:47:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 14, 2021 at 01:03:43PM -0700, Elijah Newren wrote:\n\n> > The 2008 timings are from the old email you linked in your commit\n> > message, and the new one is from running the revised script you showed.\n> > The savings seem like more than 30%. I don't know if that's all CPU or\n> > if something changed in the code.\n> \n> I was using the script you wrote in 2008, but comparing to your\n> reported numbers in 2011[1]. When you bumped in 2011, you said you\n> picked the limits of 400 & 1000 in order to give rough timings of 2s\n> and 10s. So the table looks more like:\n> \n> N CPU (2008) CPU (2011) c5xlarge CPU (yours)\n> 400 4.87s ~2s 1.106s 0.788s\n> 1000 27.82s ~10s 6.350s 4.431s\n> \n> So, 2011->c5xlarge on these (just recomputed now numbers) show\n> improvements of ~45% and ~36%. Maybe I had an outlier run earlier\n> that was in the upper 6s range for N=1000 and I rounded off to 30% for\n> the commit message? Don't know, those numbers are on a laptop that\n> died in the last few days.\n\nAh, right. I forgot about the 2011 update. So yeah, things are getting\nfaster, but not as much as I would have hoped as somebody who came of\nage during the clock speed boom of the 90's. :)\n\nThanks for humoring my puzzlement (I don't think any of this changes the\napplicability of your patch).\n\n-Peff\n"},{"id":"430148","messageId":"87mtqozg2q.fsf@evledraar.gmail.com","threadId":"56091","inReplyTo":"CABPp-BHq5hYRa0eT1JcWedadw2O=uC=5v9FdM2gH+EgMeufEqQ@mail.gmail.com","subject":"Re: [PATCH v2 2/4] doc: clarify documentation for rename/copy limits","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-07-14T22:08:17Z","receivedAt":"2021-07-14T22:27:40Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, Jul 14 2021, Elijah Newren wrote:\n\n> On Wed, Jul 14, 2021 at 12:47 AM Ævar Arnfjörð Bjarmason\n> wrote:\n>>\n>> On Wed, Jul 14 2021, Elijah Newren via GitGitGadget wrote:\n>>\n>> > From: Elijah Newren \n>> >\n> ...\n>> > diff --git a/Documentation/config/diff.txt b/Documentation/config/diff.txt\n>> > index 2d3331f55c2..e26a63d0d42 100644\n>> > --- a/Documentation/config/diff.txt\n>> > +++ b/Documentation/config/diff.txt\n>> > @@ -118,9 +118,10 @@ diff.orderFile::\n>> > relative to the top of the working tree.\n>> >\n>> > diff.renameLimit::\n>> > - The number of files to consider when performing the copy/rename\n>> > - detection; equivalent to the 'git diff' option `-l`. This setting\n>> > - has no effect if rename detection is turned off.\n>> > + The number of files to consider in the exhaustive portion of\n>> > + copy/rename detection; equivalent to the 'git diff' option\n>> > + `-l`. If not set, the default value is 400. This setting has\n>> > + no effect if rename detection is turned off.\n>>\n>> For both this...\n>>\n>> > diff.renames::\n>> > Whether and how Git detects renames. If set to \"false\",\n>> > diff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt\n>> > index 6b66c83eabe..aca0c92dbe6 100644\n>> > --- a/Documentation/config/merge.txt\n>> > +++ b/Documentation/config/merge.txt\n>> > @@ -33,10 +33,12 @@ merge.verifySignatures::\n>> > include::fmt-merge-msg.txt[]\n>> >\n>> > merge.renameLimit::\n>> > - The number of files to consider when performing rename detection\n>> > - during a merge; if not specified, defaults to the value of\n>> > - diff.renameLimit. This setting has no effect if rename detection\n>> > - is turned off.\n>> > + The number of files to consider in the exhaustive portion of\n>> > + rename detection during a merge. If not specified, defaults\n>> > + to the value of diff.renameLimit. If neither\n>> > + merge.renameLimit nor diff.renameLimit are specified, defaults\n>> > + to 1000. This setting has no effect if rename detection is\n>> > + turned off.\n>>\n>> ...and this we should really have some wording to the effect of:\n>>\n>> ..., defaults to XYZ. The exact (or even approximate) default of XYZ\n>> should not be relied upon, and may be changed (or these limits even\n>> removed) in future versions of git.\n>>\n>> I.e. let's distinguish a \"this is how it works now, FYI\" from a forward\n>> promise that it's going to work like that forever.\n>\n> Perhaps I could simplify that to \"...currently defaults to XYZ\"? Does\n> that capture your intent well enough?\n\nYes, and it's not as needlessly verbose :)\n\n> I agree very much that this shouldn't be a hard promise. If it was,\n> we've broken it repeatedly over the years. Not only have we modified\n> the default numbers multiple times, there have also been multiple\n> times when we've been able to change how many renames could be handled\n> without changing the default numbers for the rename limits. (This was\n> done by adding or improving special cases that allow us to exclude\n> paths from the exhaustive comparison; exact rename detection that\n> someone else added and my more recent improvements to exact rename\n> detection are two simple examples).\n>\n>> Which also leads me to:\n>>\n>> > merge.renames::\n>> > Whether Git detects renames. If set to \"false\", rename detection\n>> > diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\n>> > index 32e6dee5ac3..11e08c3fd36 100644\n>> > --- a/Documentation/diff-options.txt\n>> > +++ b/Documentation/diff-options.txt\n>> > @@ -588,11 +588,12 @@ When used together with `-B`, omit also the preimage in the deletion part\n>> > of a delete/create pair.\n>> >\n>> > -l::\n>> > - The `-M` and `-C` options require O(n^2) processing time where n\n>> > - is the number of potential rename/copy targets. This\n>> > - option prevents rename/copy detection from running if\n>> > + The `-M` and `-C` options have an exhaustive portion that\n>> > + requires O(n^2) processing time where n is the number of\n>> > + potential rename/copy targets. This option prevents the\n>> > + exhaustive portion of rename/copy detection from running if\n>> > the number of rename/copy targets exceeds the specified\n>> > - number.\n>> > + number. Defaults to diff.renameLimit.\n>>\n>> This mention of O(n^2). This is not an issue with your patch/series, nd\n>> this is an improvement.\n>>\n>> But as a side-comment: Do we explain somewhere how exactly this\n>> {diff,merge}.renmeLimit=N works for values of N? It's probably fine to\n>> continue to handwave it away, but is there anything that say tells a\n>> user what happens if they have 400 files in their repository in a \"x\"\n>> directory and \"git mv x y\"? Will it work, but if they add a 401th file\n>> it won't for diffs?\n>>\n>> I *think* given a skimming of previous discussions that it's \"no\",\n>> i.e. that this just kicks in for these expensive cases, and e.g. for\n>> such a case of moving the same tree OID from \"x\" to \"y\" we'd\n>> short-circuit things, but maybe I'm just making things up at this point.\n>\n> Tree OIDs aren't used by the rename detection logic, but you're close.\n>\n>> Feel free to ignore me here, I guess this amounts to a request that it\n>> would be great if we could point to some docs about how this works. It's\n>> probably too much detail for Documentation/config/{merge,diff}.txt, so\n>> maybe a section in either of git-{diff,merge}.txt ?\n>\n> If git-merge.txt includes it, then rebase, cherry-pick, revert\n> probably should too. (and maybe the -3 option of git-am)\n>\n> Anyway...\n\nSome of this we do via includes, but I also think we should have more\n\"concept docs\", like gitglossary, gitrevisions, so perhaps\ngitrenames(5)? Anyway, not for now...\n\n> In the \"git mv dir-x dir-y\" case, if no other changes are made to\n> those files, then the renames would be detectable via blobs having the\n> same hashes (i.e. exact renames). So all these renames would be found\n> regardless of the number of files and without exhaustive detection\n> even kicking in.\n>\n> If there were thousands of such files, and every one of them were also\n> modified, then the basename-guided rename detection which operates in\n> linear time would still find all the renames, without the exhaustive\n> detection even kicking in (see commits bd24aa2f97a0 (diffcore-rename:\n> guide inexact rename detection based on basenames, 2021-02-14) and\n> 37a251436447 (diffcore-rename: use directory rename guided basename\n> comparisons, 2021-02-27)).\n>\n> If this were a merge, and there were thousands of such files renamed\n> and modified, AND they were all further renamed to change their\n> basename, BUT the original directory was unmodified on the other side\n> of history, then we wouldn't need any of the renames for the purposes\n> of the merge and they'd all be excluded from the exhaustive rename\n> detection. Sure, we wouldn't find renames for those files, but that\n> wouldn't change the result of the merge. So, again, no exhaustive\n> rename detection. (See commit 174791f0fb23 (merge-ort: use\n> relevant_sources to filter possible rename sources, 2021-03-11))\n>\n> (Rebases & cherry-picks also have an advantage of caching renames from\n> previous picks on the upstream side of history to avoid needing to\n> re-detect renames on that side...though it only caches renames that\n> are either relevant or exact.)\n>\n> Basically, we bail on exhaustive rename detection if, after the linear\n> or faster steps have run (excluding previously cached renames, exact\n> rename detection, skipping irrelevant renames, basename guided rename\n> detection), the number of remaining unpaired source files times the\n> number of remaining unpaired destination files is greater than\n> rename_limit * rename_limit. (If we can assume the numbers match,\n> i.e. N = number of remaining unpaired sources = number of remaining\n> unpaired destinations, then that check simplifies to bailing once N >\n> rename_limit)\n>\n>\n> I'm not sure if these details are really going to help the users,\n> especially if more special cases are added (and more have been\n> proposed by Johannes and became an Outreachy project, though that one\n> didn't get off the ground). And this explanation is not even fully\n> detailed; I'm still hand waving here in at least four different ways\n> (mostly in ignoring special cases for different fast steps, but also\n> by ignoring copy detection that itself messes with the explanation in\n> multiple ways).\n>\n> But maybe someone else can figure out a way to hand wave my hand\n> waving down to a simple enough explanation, while also covering copy\n> detection, and managing to do so in a way that doesn't mislead. If\n> so, we can include that in the docs somewhere.\n\nI think it would be good to briefly explain it in the sense of not\nexplaining it, i.e. give the user who ran into this some idea of what\nthey're looking at. Perhaps something like (and maybe this is too\nlong...);\n\n [...] these limits are limits to the number of \"steps\" in an an\n algorithm that's subject to change, and whose number of steps will\n depend on your input data.\n\n They don't correspond to any easily tangible thing, e.g. a limit of\n 100 has no correspondence with detecting all renames in a commit\n that changed 10 files, but not a commit that changed 11 files.\n\n The limits were picked to limit runtime to an approximate desired\n value, given what was thought to be Representative data from a\n repository similar to linux.git.\n\n If you find your diff/merge take X amount of time doing rename\n detection, then generally speaking doubling the limit will about\n double the time we spend on it.\n\n So they're an indirect a way to get to a runtime limit of (what was\n it, 2 and 10 seconds?).\n\n The reason for this configuration not being a time limit is so that\n git can guarantee identical results for the same input data across\n different systems, given the same version and configuration.\n I.e. the common case of running your attempt at a diff/merge twice\n in a row, a time limit would produce unpredictable results.\n\n \n"},{"id":"430153","messageId":"CABPp-BFiw2PA6qz0uSCPXoSY9HDNc1NuwCxUJBnLU00mACAFqg@mail.gmail.com","threadId":"56091","inReplyTo":"87mtqozg2q.fsf@evledraar.gmail.com","subject":"Re: [PATCH v2 2/4] doc: clarify documentation for rename/copy limits","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-07-14T22:56:14Z","receivedAt":"2021-07-14T22:56:28Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jul 14, 2021 at 3:27 PM Ævar Arnfjörð Bjarmason\n wrote:\n>\n> On Wed, Jul 14 2021, Elijah Newren wrote:\n>\n> > On Wed, Jul 14, 2021 at 12:47 AM Ævar Arnfjörð Bjarmason\n> > wrote:\n> >>\n> >> On Wed, Jul 14 2021, Elijah Newren via GitGitGadget wrote:\n> >>\n...\n> >> ...and this we should really have some wording to the effect of:\n> >>\n> >> ..., defaults to XYZ. The exact (or even approximate) default of XYZ\n> >> should not be relied upon, and may be changed (or these limits even\n> >> removed) in future versions of git.\n> >>\n> >> I.e. let's distinguish a \"this is how it works now, FYI\" from a forward\n> >> promise that it's going to work like that forever.\n> >\n> > Perhaps I could simplify that to \"...currently defaults to XYZ\"? Does\n> > that capture your intent well enough?\n>\n> Yes, and it's not as needlessly verbose :)\n\nCool, I'll include that change then.\n\n> > I agree very much that this shouldn't be a hard promise. If it was,\n> > we've broken it repeatedly over the years. Not only have we modified\n> > the default numbers multiple times, there have also been multiple\n> > times when we've been able to change how many renames could be handled\n> > without changing the default numbers for the rename limits. (This was\n> > done by adding or improving special cases that allow us to exclude\n> > paths from the exhaustive comparison; exact rename detection that\n> > someone else added and my more recent improvements to exact rename\n> > detection are two simple examples).\n> >\n> >> Which also leads me to:\n> >>\n> >> > merge.renames::\n> >> > Whether Git detects renames. If set to \"false\", rename detection\n> >> > diff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\n> >> > index 32e6dee5ac3..11e08c3fd36 100644\n> >> > --- a/Documentation/diff-options.txt\n> >> > +++ b/Documentation/diff-options.txt\n> >> > @@ -588,11 +588,12 @@ When used together with `-B`, omit also the preimage in the deletion part\n> >> > of a delete/create pair.\n> >> >\n> >> > -l::\n> >> > - The `-M` and `-C` options require O(n^2) processing time where n\n> >> > - is the number of potential rename/copy targets. This\n> >> > - option prevents rename/copy detection from running if\n> >> > + The `-M` and `-C` options have an exhaustive portion that\n> >> > + requires O(n^2) processing time where n is the number of\n> >> > + potential rename/copy targets. This option prevents the\n> >> > + exhaustive portion of rename/copy detection from running if\n> >> > the number of rename/copy targets exceeds the specified\n> >> > - number.\n> >> > + number. Defaults to diff.renameLimit.\n> >>\n> >> This mention of O(n^2). This is not an issue with your patch/series, nd\n> >> this is an improvement.\n> >>\n> >> But as a side-comment: Do we explain somewhere how exactly this\n> >> {diff,merge}.renmeLimit=N works for values of N? It's probably fine to\n> >> continue to handwave it away, but is there anything that say tells a\n> >> user what happens if they have 400 files in their repository in a \"x\"\n> >> directory and \"git mv x y\"? Will it work, but if they add a 401th file\n> >> it won't for diffs?\n> >>\n> >> I *think* given a skimming of previous discussions that it's \"no\",\n> >> i.e. that this just kicks in for these expensive cases, and e.g. for\n> >> such a case of moving the same tree OID from \"x\" to \"y\" we'd\n> >> short-circuit things, but maybe I'm just making things up at this point.\n> >\n> > Tree OIDs aren't used by the rename detection logic, but you're close.\n> >\n> >> Feel free to ignore me here, I guess this amounts to a request that it\n> >> would be great if we could point to some docs about how this works. It's\n> >> probably too much detail for Documentation/config/{merge,diff}.txt, so\n> >> maybe a section in either of git-{diff,merge}.txt ?\n> >\n> > If git-merge.txt includes it, then rebase, cherry-pick, revert\n> > probably should too. (and maybe the -3 option of git-am)\n> >\n> > Anyway...\n>\n> Some of this we do via includes, but I also think we should have more\n> \"concept docs\", like gitglossary, gitrevisions, so perhaps\n> gitrenames(5)? Anyway, not for now...\n>\n> > In the \"git mv dir-x dir-y\" case, if no other changes are made to\n> > those files, then the renames would be detectable via blobs having the\n> > same hashes (i.e. exact renames). So all these renames would be found\n> > regardless of the number of files and without exhaustive detection\n> > even kicking in.\n> >\n> > If there were thousands of such files, and every one of them were also\n> > modified, then the basename-guided rename detection which operates in\n> > linear time would still find all the renames, without the exhaustive\n> > detection even kicking in (see commits bd24aa2f97a0 (diffcore-rename:\n> > guide inexact rename detection based on basenames, 2021-02-14) and\n> > 37a251436447 (diffcore-rename: use directory rename guided basename\n> > comparisons, 2021-02-27)).\n> >\n> > If this were a merge, and there were thousands of such files renamed\n> > and modified, AND they were all further renamed to change their\n> > basename, BUT the original directory was unmodified on the other side\n> > of history, then we wouldn't need any of the renames for the purposes\n> > of the merge and they'd all be excluded from the exhaustive rename\n> > detection. Sure, we wouldn't find renames for those files, but that\n> > wouldn't change the result of the merge. So, again, no exhaustive\n> > rename detection. (See commit 174791f0fb23 (merge-ort: use\n> > relevant_sources to filter possible rename sources, 2021-03-11))\n> >\n> > (Rebases & cherry-picks also have an advantage of caching renames from\n> > previous picks on the upstream side of history to avoid needing to\n> > re-detect renames on that side...though it only caches renames that\n> > are either relevant or exact.)\n> >\n> > Basically, we bail on exhaustive rename detection if, after the linear\n> > or faster steps have run (excluding previously cached renames, exact\n> > rename detection, skipping irrelevant renames, basename guided rename\n> > detection), the number of remaining unpaired source files times the\n> > number of remaining unpaired destination files is greater than\n> > rename_limit * rename_limit. (If we can assume the numbers match,\n> > i.e. N = number of remaining unpaired sources = number of remaining\n> > unpaired destinations, then that check simplifies to bailing once N >\n> > rename_limit)\n> >\n> >\n> > I'm not sure if these details are really going to help the users,\n> > especially if more special cases are added (and more have been\n> > proposed by Johannes and became an Outreachy project, though that one\n> > didn't get off the ground). And this explanation is not even fully\n> > detailed; I'm still hand waving here in at least four different ways\n> > (mostly in ignoring special cases for different fast steps, but also\n> > by ignoring copy detection that itself messes with the explanation in\n> > multiple ways).\n> >\n> > But maybe someone else can figure out a way to hand wave my hand\n> > waving down to a simple enough explanation, while also covering copy\n> > detection, and managing to do so in a way that doesn't mislead. If\n> > so, we can include that in the docs somewhere.\n>\n> I think it would be good to briefly explain it in the sense of not\n> explaining it, i.e. give the user who ran into this some idea of what\n> they're looking at. Perhaps something like (and maybe this is too\n> long...);\n>\n> [...] these limits are limits to the number of \"steps\" in an an\n> algorithm that's subject to change, and whose number of steps will\n> depend on your input data.\n>\n> They don't correspond to any easily tangible thing, e.g. a limit of\n> 100 has no correspondence with detecting all renames in a commit\n> that changed 10 files, but not a commit that changed 11 files.\n>\n> The limits were picked to limit runtime to an approximate desired\n> value, given what was thought to be Representative data from a\n> repository similar to linux.git.\n>\n> If you find your diff/merge take X amount of time doing rename\n> detection, then generally speaking doubling the limit will about\n> double the time we spend on it.\n\n...*quadruple* the time we spend on it.\n\n> So they're an indirect a way to get to a runtime limit of (what was\n> it, 2 and 10 seconds?).\n>\n> The reason for this configuration not being a time limit is so that\n> git can guarantee identical results for the same input data across\n> different systems, given the same version and configuration.\n> I.e. the common case of running your attempt at a diff/merge twice\n> in a row, a time limit would produce unpredictable results.\n\nSeems pretty lengthy. Thinking about it for a bit, perhaps we could\njust say something like:\n\n\nAfter preliminary steps that can detect subsets of renames quickly, an\nexhaustive fallback algorithm is used that compares all remaining\nunpaired sources with all remaining unpaired destinations looking for\nsimilar files that can be marked as renames. (Or, in the case of copy\ndetection, it compares all original sources with all remaining\nunpaired destinations). With N sources and N destinations, this\nalgorithm is O(N^2). The rename_limit says to skip this exhaustive\nstep if N is greater than the rename_limit. (More precisely, it says\nto skip the exhaustive step if number_sources * number_destinations >\nrename_limit * rename_limit, which handles the case where there are a\ndifferent number of sources and destinations.)\n"},{"id":"430162","messageId":"pull.1044.v3.git.git.1626309924.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v2.git.git.1626225153.gitgitgadget@gmail.com","subject":"[PATCH v3 0/4] Rename/copy limits -- docs, warnings, and new defaults","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-15T00:45:20Z","receivedAt":"2021-07-15T00:45:30Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Fix a few small issues with documentation and warnings around the limits for\nthe quadratic portion of rename (©) detection, and bump the default\nlimits.\n\nDiscussion on bumping the limits can be found at [1]. Although it appears we\ngenerally agree we could switch to an unlimited setting for\nmerge.renameLimit, that would require some changes to progress bars to\nnotify users how to take action once things start taking a while. So, for\nnow, just bump the limits.\n\n[1]\nhttps://lore.kernel.org/git/CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com/T/#u\n\nChanges since v2:\n\n * Change the meaning of \"0\" to actually mean unlimited, and modify the\n documentation to mention that.\n * Added 'currently' to descriptions to make it clear the defaults are\n likely to change (again).\n * Added a brief explanation of the exhaustive portion of rename detection,\n as requested by Ævar (though, honestly, I think the thing that actually\n helps people pick values for the limit is the warning that tells people\n that rename detection was skipped and how high they need to set the limit\n if they want to redo the operation and get renames).\n\nChanges since v1:\n\n * Shuffled patch order since the explanation of why \"inexact rename\n detection\" is incorrect was in the third patch\n * Use the term \"exhaustive rename detection\" for the quadratic portion\n * Simplify -l description by just stating that it defaults to\n diff.renameLimit (since it in turn has the right default value)\n * Fix asciidoc formating\n * Include bump of the limits in a new patch\n\nElijah Newren (4):\n diff: correct warning message when renameLimit exceeded\n doc: clarify documentation for rename/copy limits\n diffcore-rename: treat a rename_limit of 0 as unlimited\n Bump rename limit defaults (yet again)\n\n Documentation/config/diff.txt | 7 ++++---\n Documentation/config/merge.txt | 10 ++++++----\n Documentation/diff-options.txt | 16 +++++++++++-----\n diff.c | 4 ++--\n diffcore-rename.c | 2 +-\n merge-ort.c | 2 +-\n merge-recursive.c | 2 +-\n 7 files changed, 26 insertions(+), 17 deletions(-)\n\n\nbase-commit: d486ca60a51c9cb1fe068803c3f540724e95e83a\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1044%2Fnewren%2Frename-limit-documentation-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1044/newren/rename-limit-documentation-v3\nPull-Request: https://github.com/git/git/pull/1044\n\nRange-diff vs v2:\n\n 1: 0d1d0f180a3 = 1: 0d1d0f180a3 diff: correct warning message when renameLimit exceeded\n 2: 4046993a9a2 ! 2: 193385d7ca1 doc: clarify documentation for rename/copy limits\n @@ Documentation/config/diff.txt: diff.orderFile::\n -\thas no effect if rename detection is turned off.\n +\tThe number of files to consider in the exhaustive portion of\n +\tcopy/rename detection; equivalent to the 'git diff' option\n -+\t`-l`. If not set, the default value is 400. This setting has\n -+\tno effect if rename detection is turned off.\n ++\t`-l`. If not set, the default value is currently 400. This\n ++\tsetting has no effect if rename detection is turned off.\n \n diff.renames::\n \tWhether and how Git detects renames. If set to \"false\",\n @@ Documentation/config/merge.txt: merge.verifySignatures::\n +\tThe number of files to consider in the exhaustive portion of\n +\trename detection during a merge. If not specified, defaults\n +\tto the value of diff.renameLimit. If neither\n -+\tmerge.renameLimit nor diff.renameLimit are specified, defaults\n -+\tto 1000. This setting has no effect if rename detection is\n -+\tturned off.\n ++\tmerge.renameLimit nor diff.renameLimit are specified,\n ++\tcurrently defaults to 1000. This setting has no effect if\n ++\trename detection is turned off.\n \n merge.renames::\n \tWhether Git detects renames. If set to \"false\", rename detection\n @@ Documentation/diff-options.txt: When used together with `-B`, omit also the prei\n -\tThe `-M` and `-C` options require O(n^2) processing time where n\n -\tis the number of potential rename/copy targets. This\n -\toption prevents rename/copy detection from running if\n -+\tThe `-M` and `-C` options have an exhaustive portion that\n -+\trequires O(n^2) processing time where n is the number of\n -+\tpotential rename/copy targets. This option prevents the\n -+\texhaustive portion of rename/copy detection from running if\n - \tthe number of rename/copy targets exceeds the specified\n +-\tthe number of rename/copy targets exceeds the specified\n -\tnumber.\n -+\tnumber. Defaults to diff.renameLimit.\n ++\tThe `-M` and `-C` options involve some preliminary steps that\n ++\tcan detect subsets of renames/copies cheaply, followed by an\n ++\texhaustive fallback portion that compares all remaining\n ++\tunpaired destinations to all relevant sources. (For renames,\n ++\tonly remaining unpaired sources are relevant; for copies, all\n ++\toriginal sources are relevant.) For N sources and\n ++\tdestinations, this exhaustive check is O(N^2). This option\n ++\tprevents the exhaustive portion of rename/copy detection from\n ++\trunning if the number of source/destination files involved\n ++\texceeds the specified number. Defaults to diff.renameLimit.\n \n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\n 3: 6f5767607cd ! 3: 00a2072baea doc: document the special handling of -l0\n @@ Metadata\n Author: Elijah Newren \n \n ## Commit message ##\n - doc: document the special handling of -l0\n + diffcore-rename: treat a rename_limit of 0 as unlimited\n \n - As noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0\n - mean -l, 2017-11-29), -l0 has had a magical special \"large\"\n - historical value associated with it. Document this value, particularly\n - since it is not large enough for some uses -- see commit 9f7e4bfa3b6d\n - (diff: remove silent clamp of renameLimit, 2017-11-13).\n + In commit 89973554b52c (diffcore-rename: make diff-tree -l0 mean\n + -l, 2017-11-29), -l0 was given a special magical \"large\" value,\n + but one which was not large enough for some uses (as can be seen from\n + commit 9f7e4bfa3b6d (diff: remove silent clamp of renameLimit,\n + 2017-11-13). Make 0 (or a negative value) be treated as unlimited\n + instead and update the documentation to mention this.\n \n Signed-off-by: Elijah Newren \n \n ## Documentation/diff-options.txt ##\n @@ Documentation/diff-options.txt: of a delete/create pair.\n - \texhaustive portion of rename/copy detection from running if\n - \tthe number of rename/copy targets exceeds the specified\n - \tnumber. Defaults to diff.renameLimit.\n -++\n -+Note that for backward compatibility reasons, a value of 0 is treated\n -+the same as if a large value was passed (currently, 32767).\n + \tprevents the exhaustive portion of rename/copy detection from\n + \trunning if the number of source/destination files involved\n + \texceeds the specified number. Defaults to diff.renameLimit.\n ++\tNote that a value of 0 is treated as unlimited.\n \n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\n +\n + ## diffcore-rename.c ##\n +@@ diffcore-rename.c: static int too_many_rename_candidates(int num_destinations, int num_sources,\n + \t * memory for the matrix anyway.\n + \t */\n + \tif (rename_limit <= 0)\n +-\t\trename_limit = 32767;\n ++\t\treturn 0; /* treat as unlimited */\n + \tif (st_mult(num_destinations, num_sources)\n + \t <= st_mult(rename_limit, rename_limit))\n + \t\treturn 0;\n 4: 8f1deb6dd16 ! 4: b41278b6680 Bump rename limit defaults (yet again)\n @@ Documentation/config/diff.txt: diff.orderFile::\n diff.renameLimit::\n \tThe number of files to consider in the exhaustive portion of\n \tcopy/rename detection; equivalent to the 'git diff' option\n --\t`-l`. If not set, the default value is 400. This setting has\n -+\t`-l`. If not set, the default value is 1000. This setting has\n - \tno effect if rename detection is turned off.\n +-\t`-l`. If not set, the default value is currently 400. This\n ++\t`-l`. If not set, the default value is currently 1000. This\n + \tsetting has no effect if rename detection is turned off.\n \n diff.renames::\n \n @@ Documentation/config/merge.txt\n @@ Documentation/config/merge.txt: merge.renameLimit::\n \trename detection during a merge. If not specified, defaults\n \tto the value of diff.renameLimit. If neither\n - \tmerge.renameLimit nor diff.renameLimit are specified, defaults\n --\tto 1000. This setting has no effect if rename detection is\n -+\tto 7000. This setting has no effect if rename detection is\n - \tturned off.\n + \tmerge.renameLimit nor diff.renameLimit are specified,\n +-\tcurrently defaults to 1000. This setting has no effect if\n ++\tcurrently defaults to 7000. This setting has no effect if\n + \trename detection is turned off.\n \n merge.renames::\n \n\n-- \ngitgitgadget\n"},{"id":"430163","messageId":"0d1d0f180a35aaf355683909987731f1e0f4539b.1626309924.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v3.git.git.1626309924.gitgitgadget@gmail.com","subject":"[PATCH v3 1/4] diff: correct warning message when renameLimit exceeded","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-15T00:45:21Z","receivedAt":"2021-07-15T00:45:32Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe warning when quadratic rename detection was skipped referred to\n\"inexact rename detection\". For years, the only linear portion of\nrename detection was looking for exact renames, so \"inexact rename\ndetection\" was an accurate way to refer to the quadratic portion of\nrename detection. However, that changed with commit bd24aa2f97a0\n(diffcore-rename: guide inexact rename detection based on basenames,\n2021-02-14). Let's instead use the term \"exhaustive rename detection\"\nto refer to the quadratic portion.\n\nSigned-off-by: Elijah Newren \n---\n diff.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diff.c b/diff.c\nindex 52c791574b7..2454e34cf6d 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -6284,7 +6284,7 @@ static int is_summary_empty(const struct diff_queue_struct *q)\n }\n \n static const char rename_limit_warning[] =\n-N_(\"inexact rename detection was skipped due to too many files.\");\n+N_(\"exhaustive rename detection was skipped due to too many files.\");\n \n static const char degrade_cc_to_c_warning[] =\n N_(\"only found copies from modified paths due to too many files.\");\n-- \ngitgitgadget\n\n"},{"id":"430164","messageId":"193385d7ca11f5af74b88164062a9220956a5aaf.1626309924.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v3.git.git.1626309924.gitgitgadget@gmail.com","subject":"[PATCH v3 2/4] doc: clarify documentation for rename/copy limits","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-15T00:45:22Z","receivedAt":"2021-07-15T00:45:32Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nA few places in the docs implied that rename/copy detection is always\nquadratic or that all (unpaired) files were involved in the quadratic\nportion of rename/copy detection. The following two commits each\nintroduced an exception to this:\n\n 9027f53cb505 (Do linear-time/space rename logic for exact renames,\n 2007-10-25)\n bd24aa2f97a0 (diffcore-rename: guide inexact rename detection based\n on basenames, 2021-02-14)\n\n(As a side note, for copy detection, the basename guided inexact rename\ndetection is turned off and the exact renames will only result in\nsources (without the dests) being removed from the set of files used in\nquadratic detection. So, for copy detection, the documentation was\ncloser to correct.)\n\nAvoid implying that all files involved in rename/copy detection are\nsubject to the full quadratic algorithm. While at it, also note the\ndefault values for all these settings.\n\nSigned-off-by: Elijah Newren \n---\n Documentation/config/diff.txt | 7 ++++---\n Documentation/config/merge.txt | 10 ++++++----\n Documentation/diff-options.txt | 15 ++++++++++-----\n 3 files changed, 20 insertions(+), 12 deletions(-)\n\ndiff --git a/Documentation/config/diff.txt b/Documentation/config/diff.txt\nindex 2d3331f55c2..d1b5cfa3542 100644\n--- a/Documentation/config/diff.txt\n+++ b/Documentation/config/diff.txt\n@@ -118,9 +118,10 @@ diff.orderFile::\n \trelative to the top of the working tree.\n \n diff.renameLimit::\n-\tThe number of files to consider when performing the copy/rename\n-\tdetection; equivalent to the 'git diff' option `-l`. This setting\n-\thas no effect if rename detection is turned off.\n+\tThe number of files to consider in the exhaustive portion of\n+\tcopy/rename detection; equivalent to the 'git diff' option\n+\t`-l`. If not set, the default value is currently 400. This\n+\tsetting has no effect if rename detection is turned off.\n \n diff.renames::\n \tWhether and how Git detects renames. If set to \"false\",\ndiff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt\nindex 6b66c83eabe..7cd6d7883b6 100644\n--- a/Documentation/config/merge.txt\n+++ b/Documentation/config/merge.txt\n@@ -33,10 +33,12 @@ merge.verifySignatures::\n include::fmt-merge-msg.txt[]\n \n merge.renameLimit::\n-\tThe number of files to consider when performing rename detection\n-\tduring a merge; if not specified, defaults to the value of\n-\tdiff.renameLimit. This setting has no effect if rename detection\n-\tis turned off.\n+\tThe number of files to consider in the exhaustive portion of\n+\trename detection during a merge. If not specified, defaults\n+\tto the value of diff.renameLimit. If neither\n+\tmerge.renameLimit nor diff.renameLimit are specified,\n+\tcurrently defaults to 1000. This setting has no effect if\n+\trename detection is turned off.\n \n merge.renames::\n \tWhether Git detects renames. If set to \"false\", rename detection\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex 32e6dee5ac3..58acfff9289 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -588,11 +588,16 @@ When used together with `-B`, omit also the preimage in the deletion part\n of a delete/create pair.\n \n -l::\n-\tThe `-M` and `-C` options require O(n^2) processing time where n\n-\tis the number of potential rename/copy targets. This\n-\toption prevents rename/copy detection from running if\n-\tthe number of rename/copy targets exceeds the specified\n-\tnumber.\n+\tThe `-M` and `-C` options involve some preliminary steps that\n+\tcan detect subsets of renames/copies cheaply, followed by an\n+\texhaustive fallback portion that compares all remaining\n+\tunpaired destinations to all relevant sources. (For renames,\n+\tonly remaining unpaired sources are relevant; for copies, all\n+\toriginal sources are relevant.) For N sources and\n+\tdestinations, this exhaustive check is O(N^2). This option\n+\tprevents the exhaustive portion of rename/copy detection from\n+\trunning if the number of source/destination files involved\n+\texceeds the specified number. Defaults to diff.renameLimit.\n \n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\n-- \ngitgitgadget\n\n"},{"id":"430165","messageId":"00a2072baea435060b525b3907121bdf980461e9.1626309924.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v3.git.git.1626309924.gitgitgadget@gmail.com","subject":"[PATCH v3 3/4] diffcore-rename: treat a rename_limit of 0 as unlimited","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-15T00:45:23Z","receivedAt":"2021-07-15T00:45:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nIn commit 89973554b52c (diffcore-rename: make diff-tree -l0 mean\n-l, 2017-11-29), -l0 was given a special magical \"large\" value,\nbut one which was not large enough for some uses (as can be seen from\ncommit 9f7e4bfa3b6d (diff: remove silent clamp of renameLimit,\n2017-11-13). Make 0 (or a negative value) be treated as unlimited\ninstead and update the documentation to mention this.\n\nSigned-off-by: Elijah Newren \n---\n Documentation/diff-options.txt | 1 +\n diffcore-rename.c | 2 +-\n 2 files changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/diff-options.txt b/Documentation/diff-options.txt\nindex 58acfff9289..0aebe832057 100644\n--- a/Documentation/diff-options.txt\n+++ b/Documentation/diff-options.txt\n@@ -598,6 +598,7 @@ of a delete/create pair.\n \tprevents the exhaustive portion of rename/copy detection from\n \trunning if the number of source/destination files involved\n \texceeds the specified number. Defaults to diff.renameLimit.\n+\tNote that a value of 0 is treated as unlimited.\n \n ifndef::git-format-patch[]\n --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3375e24659e..513ba7b05f1 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -1021,7 +1021,7 @@ static int too_many_rename_candidates(int num_destinations, int num_sources,\n \t * memory for the matrix anyway.\n \t */\n \tif (rename_limit <= 0)\n-\t\trename_limit = 32767;\n+\t\treturn 0; /* treat as unlimited */\n \tif (st_mult(num_destinations, num_sources)\n \t <= st_mult(rename_limit, rename_limit))\n \t\treturn 0;\n-- \ngitgitgadget\n\n"},{"id":"430166","messageId":"b41278b6680f8b1f59e73c4eab24595a33f2f3c5.1626309924.git.gitgitgadget@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v3.git.git.1626309924.gitgitgadget@gmail.com","subject":"[PATCH v3 4/4] Bump rename limit defaults (yet again)","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-07-15T00:45:24Z","receivedAt":"2021-07-15T00:45:34Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThese were last bumped in commit 92c57e5c1d29 (bump rename limit\ndefaults (again), 2011-02-19), and were bumped both because processors\nhad gotten faster, and because people were getting ugly merges that\ncaused problems and reporting it to the mailing list (suggesting that\nfolks were willing to spend more time waiting).\n\nSince that time:\n * Linus has continued recommending kernel folks to set\n diff.renameLimit=0 (maps to 32767, currently)\n * Folks with repositories with lots of renames were happy to set\n merge.renameLimit above 32767, once the code supported that, to\n get correct cherry-picks\n * Processors have gotten faster\n * It has been discovered that the timing methodology used last time\n probably used too large example files.\n\nThe last point is probably worth explaining a bit more:\n\n * The \"average\" file size used appears to have been average blob size\n in the linux kernel history at the time (probably v2.6.25 or\n something close to it).\n * Since bigger files are modified more frequently, such a computation\n weights towards larger files.\n * Larger files may be more likely to be modified over time, but are\n not more likely to be renamed -- the mean and median blob size\n within a tree are a bit higher than the mean and median of blob\n sizes in the history leading up to that version for the linux\n kernel.\n * The mean blob size in v2.6.25 was half the average blob size in\n history leading to that point\n * The median blob size in v2.6.25 was about 40% of the mean blob size\n in v2.6.25.\n * Since the mean blob size is more than double the median blob size,\n any file as big as the mean will not be compared to any files of\n median size or less (because they'd be more than 50% dissimilar).\n * Since it is the number of files compared that provides the O(n^2)\n behavior, median-sized files should matter more than mean-sized\n ones.\n\nThe combined effect of the above is that the file size used in past\ncalculations was likely about 5x too large. Combine that with a CPU\nperformance improvement of ~30%, and we can increase the limits by\na factor of sqrt(5/(1-.3)) = 2.67, while keeping the original stated\ntime limits.\n\nKeeping the same approximate time limit probably makes sense for\ndiff.renameLimit (there is no progress feedback in e.g. git log -p),\nbut the experience above suggests merge.renameLimit could be extended\nsignificantly. In fact, it probably would make sense to have an\nunlimited default setting for merge.renameLimit, but that would\nlikely need to be coupled with changes to how progress is displayed.\n(See https://lore.kernel.org/git/YOx+Ok%2FEYvLqRMzJ@coredump.intra.peff.net/\nfor details in that area.) For now, let's just bump the approximate\ntime limit from 10s to 1m.\n\n(Note: We do not want to use actual time limits, because getting results\nthat depend on how loaded your system is that day feels bad, and because\nwe don't discover that we won't get all the renames until after we've\nput in a lot of work rather than just upfront telling the user there are\ntoo many files involved.)\n\nUsing the original time limit of 2s for diff.renameLimit, and bumping\nmerge.renameLimit from 10s to 60s, I found the following timings using\nthe simple script at the end of this commit message (on an AWS c5.xlarge\nwhich reports as \"Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz\"):\n\n N Timing\n 1300 1.995s\n 7100 59.973s\n\nSo let's round down to nice even numbers and bump the limits from\n400->1000, and from 1000->7000.\n\nHere is the measure_rename_perf script (adapted from\nhttps://lore.kernel.org/git/20080211113516.GB6344@coredump.intra.peff.net/\nin particular to avoid triggering the linear handling from\nbasename-guided rename detection):\n\n #!/bin/bash\n\n n=$1; shift\n\n rm -rf repo\n mkdir repo && cd repo\n git init -q -b main\n\n mkdata() {\n mkdir $1\n for i in `seq 1 $2`; do\n (sed \"s/^/$i /\" <../sample\n echo tag: $1\n ) >$1/$i\n done\n }\n\n mkdata initial $n\n git add .\n git commit -q -m initial\n\n mkdata new $n\n git add .\n cd new\n for i in *; do git mv $i $i.renamed; done\n cd ..\n git rm -q -rf initial\n git commit -q -m new\n\n time git diff-tree -M -l0 --summary HEAD^ HEAD\n\nSigned-off-by: Elijah Newren \n---\n Documentation/config/diff.txt | 2 +-\n Documentation/config/merge.txt | 2 +-\n diff.c | 2 +-\n merge-ort.c | 2 +-\n merge-recursive.c | 2 +-\n 5 files changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/Documentation/config/diff.txt b/Documentation/config/diff.txt\nindex d1b5cfa3542..32f84838ac1 100644\n--- a/Documentation/config/diff.txt\n+++ b/Documentation/config/diff.txt\n@@ -120,7 +120,7 @@ diff.orderFile::\n diff.renameLimit::\n \tThe number of files to consider in the exhaustive portion of\n \tcopy/rename detection; equivalent to the 'git diff' option\n-\t`-l`. If not set, the default value is currently 400. This\n+\t`-l`. If not set, the default value is currently 1000. This\n \tsetting has no effect if rename detection is turned off.\n \n diff.renames::\ndiff --git a/Documentation/config/merge.txt b/Documentation/config/merge.txt\nindex 7cd6d7883b6..e27cc639447 100644\n--- a/Documentation/config/merge.txt\n+++ b/Documentation/config/merge.txt\n@@ -37,7 +37,7 @@ merge.renameLimit::\n \trename detection during a merge. If not specified, defaults\n \tto the value of diff.renameLimit. If neither\n \tmerge.renameLimit nor diff.renameLimit are specified,\n-\tcurrently defaults to 1000. This setting has no effect if\n+\tcurrently defaults to 7000. This setting has no effect if\n \trename detection is turned off.\n \n merge.renames::\ndiff --git a/diff.c b/diff.c\nindex 2454e34cf6d..0244a371d32 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -35,7 +35,7 @@\n \n static int diff_detect_rename_default;\n static int diff_indent_heuristic = 1;\n-static int diff_rename_limit_default = 400;\n+static int diff_rename_limit_default = 1000;\n static int diff_suppress_blank_empty;\n static int diff_use_color_default = -1;\n static int diff_color_moved_default;\ndiff --git a/merge-ort.c b/merge-ort.c\nindex b954f7184a5..8a84375e940 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2558,7 +2558,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \tdiff_opts.detect_rename = DIFF_DETECT_RENAME;\n \tdiff_opts.rename_limit = opt->rename_limit;\n \tif (opt->rename_limit <= 0)\n-\t\tdiff_opts.rename_limit = 1000;\n+\t\tdiff_opts.rename_limit = 7000;\n \tdiff_opts.rename_score = opt->rename_score;\n \tdiff_opts.show_rename_progress = opt->show_rename_progress;\n \tdiff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 4327e0cfa33..f19f8cc37bd 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -1879,7 +1879,7 @@ static struct diff_queue_struct *get_diffpairs(struct merge_options *opt,\n \t */\n \tif (opts.detect_rename > DIFF_DETECT_RENAME)\n \t\topts.detect_rename = DIFF_DETECT_RENAME;\n-\topts.rename_limit = (opt->rename_limit >= 0) ? opt->rename_limit : 1000;\n+\topts.rename_limit = (opt->rename_limit >= 0) ? opt->rename_limit : 7000;\n \topts.rename_score = opt->rename_score;\n \topts.show_rename_progress = opt->show_rename_progress;\n \topts.output_format = DIFF_FORMAT_NO_OUTPUT;\n-- \ngitgitgadget\n"},{"id":"430199","messageId":"9ae3987e-2d28-a308-3d12-28ec3c8e996f@gmail.com","threadId":"56091","inReplyTo":"pull.1044.v3.git.git.1626309924.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/4] Rename/copy limits -- docs, warnings, and new defaults","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-07-15T13:36:35Z","receivedAt":"2021-07-15T13:36:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 7/14/2021 8:45 PM, Elijah Newren via GitGitGadget wrote:\n> Fix a few small issues with documentation and warnings around the limits for\n> the quadratic portion of rename (©) detection, and bump the default\n> limits.\n> \n> Discussion on bumping the limits can be found at [1]. Although it appears we\n> generally agree we could switch to an unlimited setting for\n> merge.renameLimit, that would require some changes to progress bars to\n> notify users how to take action once things start taking a while. So, for\n> now, just bump the limits.\n\nI briefly read through the responses to v2, and it looks like you\nupdated your v3 appropriately. I think the changes since v2 also\nsatisfy my comments on v1. This version LGTM.\n\nThanks,\n-Stolee\n"},{"id":"430274","messageId":"xmqqczrjrwug.fsf@gitster.g","threadId":"56091","inReplyTo":"00a2072baea435060b525b3907121bdf980461e9.1626309924.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 3/4] diffcore-rename: treat a rename_limit of 0 as unlimited","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-07-15T23:17:11Z","receivedAt":"2021-07-15T23:17:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> diff --git a/diffcore-rename.c b/diffcore-rename.c\n> index 3375e24659e..513ba7b05f1 100644\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -1021,7 +1021,7 @@ static int too_many_rename_candidates(int num_destinations, int num_sources,\n> \t * memory for the matrix anyway.\n> \t */\n> \tif (rename_limit <= 0)\n> -\t\trename_limit = 32767;\n> +\t\treturn 0; /* treat as unlimited */\n\nOK. As this short-cuts, the impact a non-positive value may have on\nall the remainder of the function (like limit squared must be larger\nthan the matrix) would not have to be compensated for. Very simple\nand clean.\n\n> \tif (st_mult(num_destinations, num_sources)\n> \t <= st_mult(rename_limit, rename_limit))\n> \t\treturn 0;\n"},{"id":"430275","messageId":"xmqq8s27rwoe.fsf@gitster.g","threadId":"56091","inReplyTo":"pull.1044.v3.git.git.1626309924.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/4] Rename/copy limits -- docs, warnings, and new defaults","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-07-15T23:20:49Z","receivedAt":"2021-07-15T23:20:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Elijah Newren via GitGitGadget\" writes:\n\n> Fix a few small issues with documentation and warnings around the limits for\n> the quadratic portion of rename (©) detection, and bump the default\n> limits.\n>\n> Discussion on bumping the limits can be found at [1]. Although it appears we\n> generally agree we could switch to an unlimited setting for\n> merge.renameLimit, that would require some changes to progress bars to\n> notify users how to take action once things start taking a while. So, for\n> now, just bump the limits.\n>\n> [1]\n> https://lore.kernel.org/git/CABPp-BFzp3TCWiF1QAVSfywDLYrz=GOQszVM-sw5p0rSB8RWvw@mail.gmail.com/T/#u\n>\n> Changes since v2:\n>\n> * Change the meaning of \"0\" to actually mean unlimited, and modify the\n> documentation to mention that.\n> * Added 'currently' to descriptions to make it clear the defaults are\n> likely to change (again).\n> * Added a brief explanation of the exhaustive portion of rename detection,\n> as requested by Ævar (though, honestly, I think the thing that actually\n> helps people pick values for the limit is the warning that tells people\n> that rename detection was skipped and how high they need to set the limit\n> if they want to redo the operation and get renames).\n\nLooks sensible. The final phrase chosen (\"exhaustive\" part) does\nsound easy-to-understand, too.\n\n"}]}