[MERGE] Make merge more than 2x faster

[Aaron Bentley]

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

Aaron Bentley wrote:
> This patch improves the speed of merge by
> - avoiding a pointless round of conflict detection
> - avoiding duplicate_entry detection when no files have been added
> - avoiding checking whether the base revision is an ancestor if it was
>   selected via least-common-ancestor
> - using set_parent_trees instead of add_parent
> - using dirstate revision trees where possible
> - caching revision trees for later use
> 
> Combined, for my example, they reduce total execution time from ~3.2
> seconds to ~1.5 seconds.

I meant to also mention: there isn't much low-hanging fruit left in
"merge".  Conflict handling could probably get slightly smarter, but
that's only 10%.  Content merging is limited by file access time, and
that's the largest cost in the merge operation.

To ramp up the speed further, we really need
- - faster access to file versions
- - graph operations that don't scale with the size of history
- - fast comparison of historical trees

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

iD8DBQFGloqg0F+nu1YWqI0RArYTAKCAhgaPhBn1Og76GYU2F49UFcLYiwCaAo3W
lICqoQLNP3XKTT/zSDGl91U=
=tQ3p
-----END PGP SIGNATURE-----