[MERGE][bug #172657] Graph.find_differences() and status after merge

[John Arbash Meinel]

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

Attached is an updated form of my previous submission, which I now
consider at least ready for review.

I managed to tweak it here and there so that it performs reasonably on
my test cases. It isn't always faster than bzr.dev. Specifically, if one
side has a lot of revisions, it can be more expensive than I think it
should be. (Having an old branch, and merging it into bzr.dev causes one
side to be much longer than the other.) In my test case, this means it
takes ~ as long as the current whole-graph code.

In a more standard "recent branch off the tip of bzr.dev" 'bzr status'
time is cut in ~1/2.

I also have an idea to create a "find_unique_ancestors()" function, as
opposed to "find_difference()". Specifically, 'find_difference()' has to
find the unique ancestors on both sides, but often you only care about
the unique ones on one side. (bzr status is one of these cases, bzr
missing --mine/theirs is another)

In something like my test case, you wouldn't have to check all of the
unique nodes from the bzr.dev branch, because you only care about the
ones from the short branch.

I set up a test, where I found merge points in bzr.dev, and then
computed find_differences() for the merge node versus both parents, and
then the parents against each other. The average time was down in the
0.1s range, with a max ~2s (with the graph already loaded in memory).
Since 'bzr.dev status' is almost 2s right now, that makes me feel
comfortable that this is generally an improvement.

It is fairly algorithmic, and there are certainly possibilities that it
can be improved further. Though I think find_unique_ancestors() is going
to be a much bigger win.

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

iD8DBQFID8hYJdeBCYSNAAMRAhpUAJ4zUvf9QUHX77t0FwJOvu6L79u9lgCguU4r
eHha2SgT49tbx87nQ205Ets=
=uUEA
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: find_differences.patch
Type: text/x-diff
Size: 56552 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20080423/188085a2/attachment.bin