{"thread":{"id":"12021","subject":"limiting rename detection during merge is a really bad idea","startedAt":"2008-02-11T06:19:32Z","lastAt":"2008-02-11T13:29:34Z","messageCount":11,"participants":["Steffen Prohaska","Marco Costalba","Jeff King","Lars Hjemli","Santi Béjar"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"68327","messageId":"CF28A4AE-62F0-4E41-9794-2CF85C2C7855@zib.de","threadId":"12021","inReplyTo":null,"subject":"limiting rename detection during merge is a really bad idea","fromName":"Steffen Prohaska","fromEmail":"prohaska@zib.de","sentAt":"2008-02-11T06:19:32Z","receivedAt":"2008-02-11T06:19:32Z","isPatch":false,"sender":{"key":"prohaska@zib.de","avatar":"https://avatars.githubusercontent.com/u/217580?v=4"},"body":"I almost lost faith in git's merging capabilities because merge-\nrecursive limits rename detection to the default limit if not\nconfigured otherwise. I tried to do a large merge and was pretty\nconvinced that git would handle the merge easily. But it\nunexpectedly failed to detect the renames. The reason is that\nmerge-recursive uses the diff_rename_limit_default, which is 100,\nand this was too low in my case.\n\nAfter debugging all the merge and diff machinery I found out that\nI just need to set diff.renamelimit=0 and everything works smoothly.\n\nWell, it was an interesting debugging experience and I learnt a\nlot about the diffcore. Nonetheless this was one of the worst\nexperiences I had with git and it kept me from doing more important\nwork.\n\nI think that limiting rename detection during merge is a really\nbad idea. Either we should set it to unlimited, or at least we\nshould print a BIG WARNING that rename detection is limited\nduring the merge. I'd propose to override diff.renamelimit\nto unlimited for a merge, even if diff.renamelimit is explicitly\nconfigured by the user. It doesn't make sense not to detect\nrenames during a merge.\n\nOpinions?\n\n\tSteffen\n"},{"id":"68333","messageId":"e5bfff550802102342r4b4d4c83mb3c9871d0206b2fa@mail.gmail.com","threadId":"12021","inReplyTo":"CF28A4AE-62F0-4E41-9794-2CF85C2C7855@zib.de","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2008-02-11T07:42:06Z","receivedAt":"2008-02-11T07:42:06Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Feb 11, 2008 7:19 AM, Steffen Prohaska wrote:\n>\n>\n> It doesn't make sense not to detect\n> renames during a merge.\n>\n> Opinions?\n>\n\nI agree 100%, merge is a very important and sensible task and git\nshould push as much as possible to avoid fails.\n\nA failed merge is always an hassle for the developer also in simple\ncases and when a successful merge is possible git should really try to\nachieve that also if it takes a little time more.\n\nSo I second overriding diff.renamelimit in this case.\n\nMarco\n"},{"id":"68334","messageId":"20080211074817.GA18898@sigill.intra.peff.net","threadId":"12021","inReplyTo":"CF28A4AE-62F0-4E41-9794-2CF85C2C7855@zib.de","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-02-11T07:48:17Z","receivedAt":"2008-02-11T07:48:17Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Feb 11, 2008 at 07:19:32AM +0100, Steffen Prohaska wrote:\n\n> I think that limiting rename detection during merge is a really\n> bad idea. Either we should set it to unlimited, or at least we\n> should print a BIG WARNING that rename detection is limited\n> during the merge. I'd propose to override diff.renamelimit\n> to unlimited for a merge, even if diff.renamelimit is explicitly\n> configured by the user. It doesn't make sense not to detect\n> renames during a merge.\n>\n> Opinions?\n\nThe point of diff.renamelimit was that some rename detection is\nliterally so time-consuming that we might as well not bother starting\nit. The number '100' was pulled out of Linus', er, hat. Perhaps a better\nargument is that the renamelimit should be set much higher to accomplish\nthat goal?\n\nIt may also be that multiple rename limits are appropriate. I don't mind\nwaiting 30 seconds for rename detection during a particularly tricky\nmerge. I probably do when running 'git-log -p'.\n\n-Peff\n"},{"id":"68335","messageId":"e5bfff550802102355n3076ae6ax636e6c5635e6a0ab@mail.gmail.com","threadId":"12021","inReplyTo":"20080211074817.GA18898@sigill.intra.peff.net","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2008-02-11T07:55:07Z","receivedAt":"2008-02-11T07:55:07Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On Feb 11, 2008 8:48 AM, Jeff King wrote:\n>\n> It may also be that multiple rename limits are appropriate. I don't mind\n> waiting 30 seconds for rename detection during a particularly tricky\n> merge. I probably do when running 'git-log -p'.\n>\n\nThat's exactly my point: ignoring diff.renamelimit in case of merges.\n"},{"id":"68336","messageId":"20080211080325.GA2706@coredump.intra.peff.net","threadId":"12021","inReplyTo":"e5bfff550802102355n3076ae6ax636e6c5635e6a0ab@mail.gmail.com","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-02-11T08:03:25Z","receivedAt":"2008-02-11T08:03:25Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Feb 11, 2008 at 08:55:07AM +0100, Marco Costalba wrote:\n\n> On Feb 11, 2008 8:48 AM, Jeff King wrote:\n> >\n> > It may also be that multiple rename limits are appropriate. I don't mind\n> > waiting 30 seconds for rename detection during a particularly tricky\n> > merge. I probably do when running 'git-log -p'.\n> >\n> \n> That's exactly my point: ignoring diff.renamelimit in case of merges.\n\nI think you missed my point. You never want to _ignore_ it. You want to\nset it higher.\n\n-Peff\n"},{"id":"68367","messageId":"8c5c35580802110241i72169620s693a31f9a098f596@mail.gmail.com","threadId":"12021","inReplyTo":"20080211074817.GA18898@sigill.intra.peff.net","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Lars Hjemli","fromEmail":"hjemli@gmail.com","sentAt":"2008-02-11T10:41:05Z","receivedAt":"2008-02-11T10:41:05Z","isPatch":false,"sender":{"key":"hjemli@gmail.com","avatar":null},"body":"On Feb 11, 2008 8:48 AM, Jeff King wrote:\n> On Mon, Feb 11, 2008 at 07:19:32AM +0100, Steffen Prohaska wrote:\n>\n> > I think that limiting rename detection during merge is a really\n> > bad idea. Either we should set it to unlimited, or at least we\n> > should print a BIG WARNING that rename detection is limited\n> > during the merge. I'd propose to override diff.renamelimit\n> > to unlimited for a merge, even if diff.renamelimit is explicitly\n> > configured by the user. It doesn't make sense not to detect\n> > renames during a merge.\n> >\n> > Opinions?\n>\n> The point of diff.renamelimit was that some rename detection is\n> literally so time-consuming that we might as well not bother starting\n> it. The number '100' was pulled out of Linus', er, hat.\n\nFWIW, prior to 07b45f8c merge-recursive ignored diff.renamelimit. The\neffect of this was that 'git diff HEAD somebranch' could detect\nrenames which 'git merge somebranch' couldn't; Teaching\nmerge-recursive about diff.renamelimit made sense IMHO since 'git\nmerge' then would agree with 'git diff' regarding renames.\n\n> It may also be that multiple rename limits are appropriate. I don't mind\n> waiting 30 seconds for rename detection during a particularly tricky\n> merge. I probably do when running 'git-log -p'.\n\nYeah, I guess we could add support for merge.renamelimit in addition\nto diff.renamelimit (i.e. use diff.renamelimit if merge.renamelimit is\nunspecified). And/or add the -l option of git-diff-* to\ngit-merge.sh/merge-recursive.c.\n\n--\nlarsh\n"},{"id":"68373","messageId":"20080211110816.GA6344@coredump.intra.peff.net","threadId":"12021","inReplyTo":"8c5c35580802110241i72169620s693a31f9a098f596@mail.gmail.com","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-02-11T11:08:16Z","receivedAt":"2008-02-11T11:08:16Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Feb 11, 2008 at 11:41:05AM +0100, Lars Hjemli wrote:\n\n> > It may also be that multiple rename limits are appropriate. I don't mind\n> > waiting 30 seconds for rename detection during a particularly tricky\n> > merge. I probably do when running 'git-log -p'.\n> \n> Yeah, I guess we could add support for merge.renamelimit in addition\n> to diff.renamelimit (i.e. use diff.renamelimit if merge.renamelimit is\n> unspecified). And/or add the -l option of git-diff-* to\n> git-merge.sh/merge-recursive.c.\n\nPerhaps we should first figure out what reasonable default values are. I\nthink the reported problem was not \"Oh, I didn't expect my tweaked\ndiff.renamelimit to affect merge\" but rather \"I didn't tweak\ndiff.renamelimit at all\".\n\nThe mega-commit I was playing with that caused Linus to suggest\ndiff.renamelimit in the first place is 374 by 641 (src by dest) and\ncompletes in ~15 minutes. The case recently reported in \"git-revert is a\nmemory hog\" is 3541 by 8043, and doesn't complete ever. We limit to 100\nby 100 by default.\n\nSteffen, can you tell us how large your rename set is (unfortunately,\nthere is no way to get this information easily; you can stop\nmerge-recursive in the debugger at diffcore-rename.c:457 and look at\nnum_src and num_create). And how long it takes to run with\ndiff.renamelimit turned off?\n\nThat might give us a clue where a reasonable value is.\n\n-Peff\n"},{"id":"68374","messageId":"8aa486160802110320h78f7228fg84ae2c4986f67372@mail.gmail.com","threadId":"12021","inReplyTo":"20080211110816.GA6344@coredump.intra.peff.net","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Santi Béjar","fromEmail":"sbejar@gmail.com","sentAt":"2008-02-11T11:20:37Z","receivedAt":"2008-02-11T11:20:37Z","isPatch":false,"sender":{"key":"santi@agolina.net","avatar":null},"body":"On Feb 11, 2008 12:08 PM, Jeff King wrote:\n> On Mon, Feb 11, 2008 at 11:41:05AM +0100, Lars Hjemli wrote:\n>\n> > > It may also be that multiple rename limits are appropriate. I don't mind\n> > > waiting 30 seconds for rename detection during a particularly tricky\n> > > merge. I probably do when running 'git-log -p'.\n> >\n> > Yeah, I guess we could add support for merge.renamelimit in addition\n> > to diff.renamelimit (i.e. use diff.renamelimit if merge.renamelimit is\n> > unspecified). And/or add the -l option of git-diff-* to\n> > git-merge.sh/merge-recursive.c.\n>\n> Perhaps we should first figure out what reasonable default values are. I\n> think the reported problem was not \"Oh, I didn't expect my tweaked\n> diff.renamelimit to affect merge\" but rather \"I didn't tweak\n> diff.renamelimit at all\".\n>\n> The mega-commit I was playing with that caused Linus to suggest\n> diff.renamelimit in the first place is 374 by 641 (src by dest) and\n> completes in ~15 minutes. The case recently reported in \"git-revert is a\n> memory hog\" is 3541 by 8043, and doesn't complete ever. We limit to 100\n> by 100 by default.\n>\n> Steffen, can you tell us how large your rename set is (unfortunately,\n> there is no way to get this information easily; you can stop\n> merge-recursive in the debugger at diffcore-rename.c:457 and look at\n> num_src and num_create). And how long it takes to run with\n> diff.renamelimit turned off?\n>\n> That might give us a clue where a reasonable value is.\n\nAdditionally git could warn if the limit is reached in the merge.\nSanti\n"},{"id":"68376","messageId":"20080211113516.GB6344@coredump.intra.peff.net","threadId":"12021","inReplyTo":"20080211110816.GA6344@coredump.intra.peff.net","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-02-11T11:35:16Z","receivedAt":"2008-02-11T11:35:16Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Feb 11, 2008 at 06:08:16AM -0500, Jeff King wrote:\n\n> The mega-commit I was playing with that caused Linus to suggest\n> diff.renamelimit in the first place is 374 by 641 (src by dest) and\n> completes in ~15 minutes. The case recently reported in \"git-revert is a\n> memory hog\" is 3541 by 8043, and doesn't complete ever. We limit to 100\n> by 100 by default.\n\nI tried putting together a simple test script to see how much processing\ntime was taken. It basically does rename detection on an NxN matrix.\nEach file is about 21K (the average size of a file in the linux-2.6\nrepository).\n\nThe results are what you would expect from an O(n^2) algorithm:\n\n N CPU seconds\n 10 0.43\n 100 0.44\n 200 1.40\n 400 4.87\n 800 18.08\n1000 27.82\n\nSo for average repositories, we could probably bump the default rename\nlimit by a factor of 10 for merges (though I think I would keep it under\n400 or so for \"git log\"). Note that this conflicts with the\n\"mega-commit\" I mentioned above; that repository has a much larger\naverage file size (around 1M). But I think it makes sense to set the\ndefault based on more common repositories.\n\nAn alternative would be to set an alarm and just give up on rename\ndetection after N seconds (which is really what the user wants anyway).\n\nMy test script is below (it references the file 'sample', which is\nactually a copy of arch/m68/Kconfig, which just happens to have a\nsize close to the repository mean).\n\n-Peff\n\n-- >8 --\n#!/bin/sh\n\nn=$1; shift\n\nrm -rf repo\nmkdir repo && cd repo\ngit init\n\nmkdata() {\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\nmkdata initial $n\ngit add .\ngit commit -m initial\n\nmkdata new $n\ngit add .\nrm -rf initial\ngit commit -a -m new\n\ntime git-diff-tree -M -l0 --summary HEAD^ HEAD\n"},{"id":"68378","messageId":"20080211114050.GC6344@coredump.intra.peff.net","threadId":"12021","inReplyTo":"8aa486160802110320h78f7228fg84ae2c4986f67372@mail.gmail.com","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-02-11T11:40:50Z","receivedAt":"2008-02-11T11:40:50Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Feb 11, 2008 at 12:20:37PM +0100, Santi Béjar wrote:\n\n> Additionally git could warn if the limit is reached in the merge.\n\nI think that is reasonable. It feels a little wrong, though, to be\nspewing user messages from such a deep library-ish function (and those\nmessages will probably be lost for commands with a pager). But something\nlike this?\n\n---\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3d37725..31941bc 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -468,10 +468,11 @@ void diffcore_rename(struct diff_options *options)\n \t */\n \tif (rename_limit <= 0 || rename_limit > 32767)\n \t\trename_limit = 32767;\n-\tif (num_create > rename_limit && num_src > rename_limit)\n-\t\tgoto cleanup;\n-\tif (num_create * num_src > rename_limit * rename_limit)\n+\tif ((num_create > rename_limit && num_src > rename_limit) ||\n+\t (num_create * num_src > rename_limit * rename_limit)) {\n+\t\twarning(\"too many files, skipping inexact rename detection\");\n \t\tgoto cleanup;\n+\t}\n \n \tmx = xmalloc(sizeof(*mx) * num_create * num_src);\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n"},{"id":"68388","messageId":"EFA2BCB7-B552-4952-B1EC-53307DA9972E@zib.de","threadId":"12021","inReplyTo":"8aa486160802110320h78f7228fg84ae2c4986f67372@mail.gmail.com","subject":"Re: limiting rename detection during merge is a really bad idea","fromName":"Steffen Prohaska","fromEmail":"prohaska@zib.de","sentAt":"2008-02-11T13:29:34Z","receivedAt":"2008-02-11T13:29:34Z","isPatch":false,"sender":{"key":"prohaska@zib.de","avatar":"https://avatars.githubusercontent.com/u/217580?v=4"},"body":"\nOn Feb 11, 2008, at 12:20 PM, Santi Béjar wrote:\n\n>> Steffen, can you tell us how large your rename set is (unfortunately,\n>> there is no way to get this information easily; you can stop\n>> merge-recursive in the debugger at diffcore-rename.c:457 and look at\n>> num_src and num_create). And how long it takes to run with\n>> diff.renamelimit turned off?\n\nI don't know the size. I can only say that it took a few\nseconds on a MacBook Pro.\n\n\n>> That might give us a clue where a reasonable value is.\n>\n> Additionally git could warn if the limit is reached in the merge.\n\nI think this would have saved me. I did not know about the\nrename limit. Therefore I did not understand why the merge\nfailed. If git merge had reported that the rename detection\nlimit was reached, I probably would have looked up what this\nlimit is about. At least git should tell when rename detection\ngets disabled. Users expect that renames work and git should tell\nthe user when it does not even try to detect renames.\n\nPersonally, I can easily switch to a larger machine if this\nhelps completing a merge and I think I would do this. But\nI also know that I shouldn't expect too much from a larger\nmachine for an O(n^2) algorithm.\n\n\tSteffen\n"}]}