[Merge] performance increases for 'bzr status'

[John Arbash Meinel]

I spent some time profiling the 'bzr status' calls, and came up with a
few changes. I'm using the new benchmark stuff, and its pretty nice.
(Though the nicest thing is because of lsprof).

changes are here:
http://bzr.arbash-meinel.com/branches/bzr/minor-performance


first 'bzrlib.delta.compare_trees' now uses 'Tree.list_files()' rather
than iterating randomly. This eliminates all of the 'id2path' calls,
since list_files builds up the paths as it goes along.

Basically it uses the iterators from the pre and post trees, and then
syncs up based on path. keeping track of file ids that don't match, and
matching them up if they show up later.

second WorkingTree.list_files uses a stack rather than using a recursive
function. This shaves off a few hundred ms. I tuned list_files quite a bit.

third bzrlib.osutils.file_kind can be done with a single lstat and
dictionary lookup. this function gets called a lot, and optimizing it
has some pretty good performance benefits.

fourth Inventory._read_tree_state already knows what path the file is
at, it has to be passed in, but it doesn't pass that path to
WorkingTree. So make path an optional component of get_file_sha1 and
is_executable

fifth Inventory.iter_entries also doesn't need to be a recursive
function. Using properly designed stacks gets the profiled time down as
much as to 1/6th for a kernel sized tree.

Do we still want to pre-scan the hashcache when we create a WorkingTree?
I know the point was to load up the inode cache by scanning in-order
rather than doing a random walk. It costs us by require a stat of every
file in the tree, which we then effectively throw away.
I realize it isn't something that benchmarks well, because benchmarks
pretty much always run hot. But in my testing, it shaves 500ms off the
'bzr status' time for a kernel sized tree.
And now that my 'compare_trees' is at least going in sorted filesystem
order, it may be closer to inode order than going in a random file_id
hash sorted order.


Before my changes the times looked like this:
test_no_changes_known_kernel_like_tree        OK  5174ms/91565ms
test_no_ignored_unknown_kernel_like_tree      OK  1665ms/15044ms

test_no_changes_known_kernel_like_tree        OK  3591ms/83970ms
test_no_ignored_unknown_kernel_like_tree      OK  1432ms/14309ms


the 'no_ignored' tree is a kernel_like tree where everything is added,
but nothing has been committed yet. Which is only one side of status
(since one tree is empty).
After the first commit 'bzr status' now has to compare both trees. So it
is quite a bit slower. (It has to check the difference for each file, etc).

Anyway, attached is the diff.

John
=:->

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: status-tuning.diff
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20060527/6e25e963/attachment.diff 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 254 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060527/6e25e963/attachment.pgp