New public Graph.revision_relation method

[John Arbash Meinel]

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

Andrew Bennetts wrote:
> Martin von Gagern wrote:
> [...]
>> I propose to add a method Graph.revision_relation (no plural) that does
>> a two-way comparison, and to also have global constants for the possible
>> return values. Both Branch._revision_relations and Graph.is_ancestor
> 
> Sounds reasonable to me.  (As you probably guessed from IRC ;)
> 
> I think maybe “find_relation” would be a better name.  It's at least
> superficially more consistent with other Graph methods, and it's a verb phrase
> rather than a noun phrase.  I don't feel very strongly about it though.
> 
> -Andrew.
> 
> 
> 

You may also want to look at the KnownGraph code. It has different
constraints. Namely "Graph" tries to be as 'lazy-as-possible' to nodes
in the graph, and in doing so, many of its algorithms scale poorly.
(Quadratic, Cubic? in the number of nodes it walks over.)

KnownGraph changes this, and starts by assuming it has all the nodes,
and thus can create an ordering (leveling?) for them. Namely, adding
gdfo (greatest distance from origin). It also changes the internals so
that instead of having lots of dicts and sets, you have one dict of
objects, and those objects point to eachother. It also has a Pyrex
implementation.

All of this combines to make KG approximately OMG faster than regular
Graph at heads() checks. I would imagine you would get similar boosts
for 'find_relation' if implemented appropriately.

For example, given "GDFO" you immediately know if one revision *could*
be an ancestor of the other. If one revs gdfo is 10 and the other is 20,
then the gdfo=20 revision cannot be an ancestor of gdfo=10. (Otherwise
it would be >= 21.)

This actually holds all the way, such that 2 revs with gdfo the same
cannot be ancestors of eachother.


However, loading the whole graph has its tradeoffs. Namely, loading all
of emacs takes ~1s on my machine. And if the revisions are close to
eachother, the O(N^2) behavior doesn't dominate.

Ideally, we'd end up saving gdfo information at commit time (with
caveats for ghosts, where the data is stored, how to efficiently access
it, transmit it, etc).

John
=:->

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

iEYEARECAAYFAksfvLEACgkQJdeBCYSNAANeHgCgpjykIrH+iC1cZUfwK+0q5DnI
5RAAnRKAvPjZ+c9s/O7jrVbhzQMTk6U4
=qX4e
-----END PGP SIGNATURE-----