[MERGE] [BUG #172657][1.0] make 'bzr status' after merge faster

Aaron Bentley aaron.bentley at utoronto.ca
Wed Dec 5 03:58:04 GMT 2007


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

John Arbash Meinel wrote:

> The attached patch updates the code to use Graph.find_difference() which
> only searches the tips of the graph, and stops once it finds things in
> common.

bb:abstain

I was very tempted to vote "reject", because I don't consider
Graph.find_difference to be trustworthy, as I wrote about in the
"Merging a bundle w/ a pack repository is slow" thread.

> I know Robert was talking about adding a Graph.symmetric_difference() but
> Graph.find_difference() actually provides all of that, and does so in a
> way that you don't have to tease out what belongs to each side.

Actually, I thought Robert was working a trustworthy
Graph.find_difference.  I agree that a fast find_difference is more
useful than a fast symmetric_difference.

> Hmm... I wonder about Graph() keeping a cache (LRUCache?) of parents that
> it has seen. It wouldn't help much for a single query, but it would help
> between queries.

I think it would be better to provide a CachedParentsProvider, to be
used only with ParentsProviders that are slow.  Caching knit indices or
DictParentsProvider would be wasteful.

> Anyway, this patch is good, please accept it.

The patch may be fine, but the API it uses isn't up to scratch.  Please
don't merge it at this time.

In the bug report thread, you asked me to explain what's wrong with this
approach to graph difference.  The problem is the algorithm.  It starts
by finding the border common ancestors, but it does so imperfectly.

Consider this graph (oldest nodes at the top)

A
|\
B |
| |
C |
|\|
D F

If we look at the traversal from D and F:
1: D, F (no common ancestors)
2: C, A (C common, A possibly unique)
3: B (search in A terminates.  All searches terminate because all
remaining active searchers are searching through common ancestors.)

This will lead to A appearing to be a unique ancestor of F.

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

iD8DBQFHViHM0F+nu1YWqI0RAjYOAJ9tQ1+EBCvNKg3e4mpvMD+gmNoEWQCfZz+L
eSO1rBRCAFh/Bt9iGGx+D7g=
=x5U+
-----END PGP SIGNATURE-----



More information about the bazaar mailing list