[MERGE/RFC] faster send

[John Arbash Meinel]

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

Ian Clatworthy wrote:
> Looking into the performance of "bzr send -o xxx" on chk
> repositories today, I noticed it was walking all of history
> twice (repo.get_ancestry()) and then calculating the difference
> from there. We now have a special method (graph.find_difference())
> for doing this more efficiently. This patch changes the
> bundle serializer code to use it. Benchmarking the bundling of
> this patch, the time drops from 5.5 secs (bzr.dev) to 2.4 secs
> (bzr.dev + this patch).
> 
> I should mention that Robert suggested on IRC that
> graph.find_difference() has bugs and that these were documented
> in the tests or doc. I couldn't find any evidence of this
> and all the send tests pass. I can say that find_difference()
> is used by missing and that, at a glance, none of the bugs for
> missing indicate a problem along these lines. Even so, I'm
> marking this as RFC until this concern is better understood.
> 
> Ian C.
> 

I'm pretty sure I fixed the bugs with find_difference(), though you may
actually be looking for 'find_unique_ancestors()', since if given
revision A vs B for a bundle, you don't care what extra revisions B has,
just the extras that A has.

Anyway, the tradeoff is that find_unique_ancestors/find_difference give
correct results, but can be O(N^2), and can get slow for a few small
changes near big ancestry. (To say that under some circumstances,
find_unique_ancestors is actually slower than grabbing the whole
ancestry and taking the set difference, but not in the common cases.)

BB:tweak

Pending changing it from find_difference()[1] to find_unique_ancestors().

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkm/ossACgkQJdeBCYSNAAOnOwCgjEJ8766DB+caFk85qj40m7Y6
U5EAoNZmKdu2gJFg2OwzG+6SW5lsZiwV
=v7OA
-----END PGP SIGNATURE-----