[PATCH 0 of 5] RFC: Implement O(n + m) algorithm for findrenames()

[Matt Mackall]

On Sun, 2010-03-07 at 04:12 +0000, David Greenaway wrote:
> Hi all,
> 
> I maintain a mercurial repository that tracks my company's local changes
> to the Linux sources. Attempting to upgrade from Linux 2.6.24 to the
> latest mainline, I tried the following:
> 
>     hg update -C linux-2.6.24-mainline
>     rm -rf *
>     tar -xzvf ~/linux-2.6.33.tar.gz
>     hg addremove -s75
> 
> After leaving that last hg command for twelve hours on my 2.4GHz Core II
> Duo, I decided that it was probably time to give up.
> 
> The problem is the algorithm used in findrenames() requires
> approximately O(m * n) file comparisons, making it infeasable to use
> once 'm' and 'n' become large.

You're not the first person to look into this, I'm sorry to say: 

http://mercurial.markmail.org/thread/wychixgy5ffotvjs

Herbert found a number of shortcomings here, put a lot of work into it,
then never tidied things up enough for inclusion. Please see if there's
anything you can borrow from his work.

-- 
http://selenic.com : development and support for Mercurial and Linux