Re: limiting rename detection during merge is a really bad idea

From: Jeff King <peff@peff.net>
Date: Feb 11, 2008, 11:35 UTC
Message-ID: <20080211113516.GB6344@coredump.intra.peff.net>
In-Reply-To: <20080211110816.GA6344@coredump.intra.peff.net>

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

Show 5 quoted lines

> 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.

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