limiting rename detection during merge is a really bad idea

I almost lost faith in git's merging capabilities because merge- recursive limits rename detection to the default limit if not configured otherwise. I tried to do a large merge and was pretty convinced that git would handle the merge easily. But it unexpectedly failed to detect the renames. The reason is that merge-recursive uses the diff_rename_limit_default, which is 100, and this was too low in my case.

After debugging all the merge and diff machinery I found out that I just need to set diff.renamelimit=0 and everything works smoothly.

Well, it was an interesting debugging experience and I learnt a lot about the diffcore. Nonetheless this was one of the worst experiences I had with git and it kept me from doing more important work.

I think that limiting rename detection during merge is a really bad idea. Either we should set it to unlimited, or at least we should print a BIG WARNING that rename detection is limited during the merge. I'd propose to override diff.renamelimit to unlimited for a merge, even if diff.renamelimit is explicitly configured by the user. It doesn't make sense not to detect renames during a merge.

Opinions?

	Steffen

On Feb 11, 2008 7:19 AM, Steffen Prohaska <prohaska@zib.de> wrote:

I agree 100%, merge is a very important and sensible task and git should push as much as possible to avoid fails.

A failed merge is always an hassle for the developer also in simple cases and when a successful merge is possible git should really try to achieve that also if it takes a little time more.

So I second overriding diff.renamelimit in this case.

Marco

On Mon, Feb 11, 2008 at 07:19:32AM +0100, Steffen Prohaska wrote:

The point of diff.renamelimit was that some rename detection is literally so time-consuming that we might as well not bother starting it. The number '100' was pulled out of Linus', er, hat. Perhaps a better argument is that the renamelimit should be set much higher to accomplish that goal?

It may also be that multiple rename limits are appropriate. I don't mind waiting 30 seconds for rename detection during a particularly tricky merge. I probably do when running 'git-log -p'.

-Peff

On Feb 11, 2008 8:48 AM, Jeff King <peff@peff.net> wrote:

That's exactly my point: ignoring diff.renamelimit in case of merges.

On Mon, Feb 11, 2008 at 08:55:07AM +0100, Marco Costalba wrote:

I think you missed my point. You never want to _ignore_ it. You want to set it higher.

-Peff

On Feb 11, 2008 8:48 AM, Jeff King <peff@peff.net> wrote:

FWIW, prior to 07b45f8c merge-recursive ignored diff.renamelimit. The effect of this was that 'git diff HEAD somebranch' could detect renames which 'git merge somebranch' couldn't; Teaching merge-recursive about diff.renamelimit made sense IMHO since 'git merge' then would agree with 'git diff' regarding renames.

Yeah, I guess we could add support for merge.renamelimit in addition to diff.renamelimit (i.e. use diff.renamelimit if merge.renamelimit is unspecified). And/or add the -l option of git-diff-* to git-merge.sh/merge-recursive.c.

-- larsh

On Mon, Feb 11, 2008 at 11:41:05AM +0100, Lars Hjemli wrote:

Perhaps we should first figure out what reasonable default values are. I think the reported problem was not "Oh, I didn't expect my tweaked diff.renamelimit to affect merge" but rather "I didn't tweak diff.renamelimit at all".

The mega-commit I was playing with that caused Linus to suggest diff.renamelimit in the first place is 374 by 641 (src by dest) and completes in ~15 minutes. The case recently reported in "git-revert is a memory hog" is 3541 by 8043, and doesn't complete ever. We limit to 100 by 100 by default.

Steffen, can you tell us how large your rename set is (unfortunately, there is no way to get this information easily; you can stop merge-recursive in the debugger at diffcore-rename.c:457 and look at num_src and num_create). And how long it takes to run with diff.renamelimit turned off?

That might give us a clue where a reasonable value is.

-Peff

On Feb 11, 2008 12:08 PM, Jeff King <peff@peff.net> wrote:

Additionally git could warn if the limit is reached in the merge. Santi

On Mon, Feb 11, 2008 at 12:20:37PM +0100, Santi Béjar wrote:

I think that is reasonable. It feels a little wrong, though, to be spewing user messages from such a deep library-ish function (and those messages will probably be lost for commands with a pager). But something like this?

---

On Feb 11, 2008, at 12:20 PM, Santi Béjar wrote:

I don't know the size. I can only say that it took a few seconds on a MacBook Pro.

I think this would have saved me. I did not know about the rename limit. Therefore I did not understand why the merge failed. If git merge had reported that the rename detection limit was reached, I probably would have looked up what this limit is about. At least git should tell when rename detection gets disabled. Users expect that renames work and git should tell the user when it does not even try to detect renames.

Personally, I can easily switch to a larger machine if this helps completing a merge and I think I would do this. But I also know that I shouldn't expect too much from a larger machine for an O(n^2) algorithm.

	Steffen

On Mon, Feb 11, 2008 at 06:08:16AM -0500, Jeff King wrote:

I tried putting together a simple test script to see how much processing time was taken. It basically does rename detection on an NxN matrix. Each file is about 21K (the average size of a file in the linux-2.6 repository).

The results are what you would expect from an O(n^2) algorithm:

   N   CPU seconds
  10          0.43
 100          0.44
 200          1.40
 400          4.87
 800         18.08
1000         27.82

So for average repositories, we could probably bump the default rename limit by a factor of 10 for merges (though I think I would keep it under 400 or so for "git log"). Note that this conflicts with the "mega-commit" I mentioned above; that repository has a much larger average file size (around 1M). But I think it makes sense to set the default based on more common repositories.

An alternative would be to set an alarm and just give up on rename detection after N seconds (which is really what the user wants anyway).

My test script is below (it references the file 'sample', which is actually a copy of arch/m68/Kconfig, which just happens to have a size close to the repository mean).

-Peff

-- >8 -- #!/bin/sh

n=$1; shift

rm -rf repo mkdir repo && cd repo git init

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

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

mkdata new $n git add . rm -rf initial git commit -a -m new

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