Re: git-diff-tree -M performance regression in 'next'

Fredrik Kuivinen [off-list ref] writes:

I turned out that the rename detection took almost 10 minutes on my
machine. More specifically,

   git-diff-tree -r -M --diff-filter=R v2.6.12 v2.6.14

takes ~9 minutes with the current 'next'.

I have some updates to "next" tonight.

On my otherwise idle Duron 750 with slow disks, I am getting
something like these:

0.99.9m : 130m virtual, 40m resident, (0major+14205minor)
          67.62user 0.08system 1:15.95elapsed
master  : 130m virtual, 40m resident, (0major+12510minor)
          66.06user 0.07system 1:10.95elapsed
"next"  : 150m virtual, 65m resident, (0major+49858minor)
          51.41user 0.45system 0.57.55elapsed

The result will _not_ exactly match, because the similarity
estimation algorithms are different.

Judging the differences objectively is a bit hard, but my
impression is that the "next" one tends to find more sensible
renames.  To name a few:

* Documentation/dvb/README.dibusb from v2.6.12 seems pretty
  similar to Documentation/dvb/README.dvb-usb from v2.6.14, and
  "next" finds them, but "master" does not.

* "master" says arch/arm/configs/omnimeter_defconfig was
  copy-edited to produce arch/arm/configs/collie_defconfig; The
  diff output shows ~350 new lines and ~270 deleted lines, while
  these files are 800-900 lines long; "next" rejects them.  I
  think this is a border-line case.

* "next" finds Kconfig and Makefile in arch/arm/mach-omap-1/ are
  derived from arch/arm/mach-omap/; manual inspection of these
  files makes me feel that decision is sensible.  "master" does
  not find them.

* Same thing for config.c in arch/m68knommu/platform/68VZ328/;
  found to be derived from arch/m68knommu/platform/68VZ328/de2/ by
  "next" but not by "master".

* Other examples "next" finds but "master" misses include:

  arch/um/kernel/process.c	arch/um/os-Linux/start_up.c
  arch/um/kernel/tt/unmap.c	arch/um/sys-x86_64/unmap.c
  drivers/ide/cris/ide-v10.c	drivers/ide/cris/ide-cris.c
  include/asm-ppc/cputime.h	include/asm-xtensa/cputime.h
  include/asm-ppc64/ioctl.h	include/asm-xtensa/ioctl.h
  include/asm-ppc64/ioctls.h	include/asm-xtensa/ioctls.h
  include/asm-ppc64/mman.h	include/asm-xtensa/mman.h
  include/asm-ppc64/poll.h	include/asm-xtensa/poll.h
  include/asm-ppc64/shmbuf.h	include/asm-xtensa/shmbuf.h
  include/asm-ppc64/socket.h	include/asm-xtensa/socket.h
  include/asm-ppc64/termbits.h	include/asm-xtensa/termbits.h

* The "next" one is not perfect.  There are some quite bad
  choices made by it:

  include/asm-ppc64/timex.h	include/asm-powerpc/bugs.h
  include/asm-ppc64/iSeries/LparData.h	include/linux/i2c-isa.h