[PATCH 0 of 5] Implement O(n) algorithm for findrenames() [version 2]

[Benoit Boissinot]

On Sun, Mar 21, 2010 at 06:33:25PM +1100, David Greenaway wrote:
> 
> Hi all,
> 
> The current findrenames() algorithm requires O(n^2) time complexity
> (where 'n' is the number of files needed to be added/removed). This is
> problematic on large projects (for example, attempting to move
> a repository from Linux 2.6.24 to 2.6.33 using 'hg addremove -s75'), as
> the number of comparisons that need to take place starts reaching into
> the tens-of-millions.
> 
[snip]
> 
> Final notes
> -----------
> 
> Any comments would be much appreciated. If people are keen to introduce
> this type of functionality to mercurial (and are happy with this
> particular approach), I will be happy to continue to tweak these patches
> based on any feedback.

Thanks, I've sent a couple remarks. Otherwise it looks quite nice, I
need to review the hashing stuff more thoroughly (and I think 3 and 5
should be folded together, you already have the C implementation, so
just introduce them in the same patch).

Did you have the time to look at the earlier findrenames() attempt? If
yes could you outline the differences?

Thanks,

Benoit

-- 
:wq