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

[Martin Geisler]

David Greenaway <hg-dev at davidgreenaway.com> writes:

> 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.
>
> This series of patches modifies findrenames() to use an O(n) time
> complexity algorithm, significantly improving its performance on larger
> projects.

Wow, this looks like a very well-made patch series! I just skimmed the
patches and I'm happy to see you've included relevant parts of this
introduction as comments in the code.

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

I wont have time to test the patches in the next week, so I hope someone
else will apply them.

-- 
Martin Geisler

Fast and powerful revision control: http://mercurial.selenic.com/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
URL: <http://selenic.com/pipermail/mercurial-devel/attachments/20100321/56ee2b23/attachment.pgp>