[PATCH 4 of 5] findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes

[David Greenaway]

On Sun, Mar 07, 2010 at 05:00:53PM +0100, Benoit Boissinot wrote:
> On Sun, Mar 7, 2010 at 5:12 AM, David Greenaway
> <hg-dev at davidgreenaway.com> wrote:
> > findrenames: Optimise "addremove -s100" by matching files by their SHA1 hashes.
> >
> > We speed up usecase when a user specifies "addremove -s100" by only matching
> > files by their exact SHA1 hash value.
> 
> I didn't look carefully, but FYI, the current code already does that
> (and it's probably more clever since it reuses the hashes from
> filelogs).
> 
> See the line doing fctx.cmp(text) in findrenames().

The current findrenames() code does this (relatively quick) compare
O(m * n) times, while my patch needlessly recalculates the SHA1 hash
O(m + n) times.

The best approach may be to combine the two: Use the precalculated SHA1
hashes, but place them into a dictionary to avoid the need to perform
O(m * n) compares.

Cheers,
David