[MERGE] TreeTransform avoids many renames when constructing trees

[Aaron Bentley]

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

Hi all,

This patch implements the top-rename strategy for TreeTransform, so that
building a tree only renames files in the top-level directory.

This optimization is mainly targeted at operations that build a tree
(like checkout and branch), but merge and revert may see some improvement.

The gist is that when a file is created, if its parent directory is
already in the "limbo" temporary directory, then it is created inside
its parent directory.  When the parent directory is renamed into place,
the file is already in the right place, so it needs no further renames.

Benchmarks show that tree-building operations are 3.09x faster

bench-standard transform 2
real 25.39
user 7.19
sys 18.13

bench-rename-top transform 7
real 8.21
user 5.79
sys 2.26

(heavyweight) checkout is 1.28x faster:

bench-standard checkout 4
real 88.79
user 64.99
sys 20.94

bench-rename-top checkout 4
real 69.14
user 61.88
sys 5.27

I am comfortable with these changes-- I believe they are safe, and of
course they pass the whole test suite.  To achieve optimum performance,
you must create parents before children, but if you do not, the
transform will be applied correctly, albeit more slowly.

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

iD8DBQFGYz1n0F+nu1YWqI0RAgdOAJ9qRYSbTJ+7owRcKLd6LOkcP7zH2gCfRpIf
wEv9gPzBRKiK96Swap4f0vk=
=cQF8
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rename-top.patch
Type: text/x-patch
Size: 50758 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070603/e8071a8b/attachment-0001.bin 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: bench-rename-top
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20070603/e8071a8b/attachment-0002.diff 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: bench-standard
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20070603/e8071a8b/attachment-0003.diff