Initial benchmarks for checkout performance improvements

[Aaron Bentley]

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

Hi all,

One of our goals is to improve the performance of tree-building
operations for large trees.  To that end, I've started benchmarking
various tree-building strategies.  I used the linux kernel, version
2.6.21.3 as my example tree.  Runs are immediately consecutive, so the
cache is hot on runs 2-10.  (And benching the previous strategy may also
heat the cache for run 1, though perhaps not as well.)

The scripts I'm using are here:
http://code.aaronbentley.com/bzr/build-testbed/

Timings are hugely variable.  One run may be 5x faster than the next.
So I'm running each test 10 times and reporting the best performance.
Raw scores are attached.

cp -R is what we are being compared to.  Note that the best time happens
to also be the first run, so the cache isn't necessarily not.
cp 1
real	0m2.183s
user	0m0.076s
sys	0m1.656s
(wait time: ~ 0.45s)

Python's shutil.copytree is an imitation of cp -R.  On this hardware, it
is about 39.6% the speed of cp -R.  On my laptop, it is ~ equivalent to
cp -R.  I assume this is because my laptop's hard drive is slow enough
that IO dominates the cost.
copytree 4
real	0m5.513s
user	0m1.584s
sys	0m2.324s

Naive is my naive implementation of cp -R, with no optimization.  On
this hardware, we can see similar performance to Python's copytree.
naive 4
real	0m5.744s
user	0m0.704s
sys	0m2.284s

Rename is a simulation of TreeTransform.  It is like Naive, except that
it creates each file in a temp directory first, then renames it into
place.  On this hardware, it is much, much slower than Naive.  (On my
laptop, it was about 80% of the speed of Naive)  Yikes.
rename 6
real	0m16.736s
user	0m1.368s
sys	0m14.145s

Transform is TreeTransform itself.  Rather than being built from a
repository tree, this TreeTransform is built from a directory, just like
the other examples.  This helps us isolate performance factors.
transform 8
real	0m26.227s
user	0m6.676s
sys	0m18.241s

I should point out that transform's numbers are much more stable than cp
- -R's.  So the worst-case Transform is
transform 7
real	0m28.912s
user	0m6.912s
sys	0m20.353s

And the worst-case for cp is
cp 2
real	0m12.050s
user	0m0.092s
sys	0m1.640s

So in the best case, cp is 12x faster than TreeTransform.  In the worst
case, it's about 2.4x as fast.  The common case is something like 3x faster.

Then there's "bzr checkout --lightweight".  It's about 2.39% of the
speed of cp -R, and 28% of the speed of TreeTransform.

checkout 9
real    1m31.190s
user    1m5.888s
sys     0m21.505s

Gah!

So yes, we can and should improve the speed of TreeTransform.  But the
lion's share of the performance degradation seems to come from elsewhere.

Note that the difference from Transform is mainly from increased user
time.  The system time is only 1.17x longer.

Anyone feel like hacking up a flat-file based repository?  I'm curious
whether knit repos are the largest factor.  Mind you, there was only a
single commit in the branch I used for the checkout, so every file knit
should have had only a single snapshot in it.

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

iD8DBQFGXa0/0F+nu1YWqI0RArD9AJ9KG//nHuqZQO6VbjojLcihlzDKDQCfQIeM
vigmYSKPuBUi+h5g8klMfOg=
=3/ep
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: bench
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20070530/e7934dd6/attachment.diff 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: bench.checkout
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20070530/e7934dd6/attachment-0001.diff