[MERGE] Repository.get_revision_graph improvements

[John Arbash Meinel]

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

The attached patch does a few things

1) Deprecate Repository.get_revision_graph_with_ghosts and
revision.common_ancestor. Neither are used anymore and ..._with_ghosts was
returning a deprecated_graph.Graph() object.
There was one place that thought get_revision_graph_with_ghosts().get_ancestry()
was returning a map with ghosts, a while ago I found out that it wasn't, so I
just switched the function because at least it isn't any worse.

2) Introduce Graph.iter_ancestry() which returns similar information.

3) Change KnitPackRepository.get_revision_graph to use the new function.

The big win here is that getting ancestry including ghosts avoids double lookups
at the pack layer, which you can then filter as you go. It means a bit of extra
book-keeping to track what nodes you may need to filter when you encounter a ghost.

On my current repository (which has expanded to 22 packs) the difference is:
$ time py -c "import bzrlib.branch; \
~  b = bzrlib.branch.Branch.open('bzr.dev'); \
~  b.get_revision_id_to_revno_map(); b.unlock()"

18.531s  down to  3.580s

After an autopack down to 8 packs, it is 2.65s versus 1.89s (1.4x).

I'm a little concerned that performance degraded from 2.65s to 18.5s when doing
nothing but a few "bzr commit" and maybe a "bzr up" from time to time. I suppose
with this patch at least it is only scaling from 1.9s => 3.5s. (1.8x versus 7x
performance swing.) I think that is a strong argument for reworking our index layer.

Another advantage is that it effects "bzr log" time as well.
John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHw1tXJdeBCYSNAAMRAo66AKC6NpSptx3qs8zu0Oz/1JUD04a6sgCdFEhX
i2z8S0Uji043lYr5zdDvrzs=
=Bb4L
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: revision_graph.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20080225/75ab7a7d/attachment-0001.diff