Speeding up reannotate

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

John Arbash Meinel wrote:
> John Arbash Meinel wrote:
> 
> ...
> 
>> Writing this down did bring up 1 possibility. After we've annotated
>> with the left-hand parent, what if we do the diff versus the annotated
>> right-hand parent.

> I think I've implemented this, and it did indeed make it faster, but it
> seems to be generating different results.

It's surprising that it would we faster, because all that's needed to
compare the two versions is a simple linear scan.  And that has O(n)
complexity, compared to Patience, which has O(n²) complexity.

> 
> I'm trying to figure out why, at the moment the best I can come up with
> is that lines which used to be considered "common" and thus would not be
> points to line-up, now have a chance to be considered unique, because
> their annotation information is different.

By doing sequence matching, you're ignoring the eqivalence info we
already have.  I'm still surprised you found a difference, though.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHsNuQ0F+nu1YWqI0RAsQEAJ92myHRMYNSo720qiLJo30fAezN9gCfWyF7
z/fNgiOkstclsYMnTs/mJPs=
=YUPl
-----END PGP SIGNATURE-----