Best way to get a revno & depth from a revision-id?

[John Arbash Meinel]

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

Ian Clatworthy wrote:
> If I have a branch & revision_id, is there an easy way to get the
> revno & depth?
> 
> I'm asking because I want "log one rev" to be quick.
> We convert the -rx.y.z option to a revision_id and
> seem to throw away the mapping? To get it back, it looks
> like we need to rebuild the whole rev_id_to_renvo map?
> 
> branch.revision_id_to_revno() doesn't look right either.
> The revno I get back from that won't be x.y.z?
> 
> Ian C.
> 
> 

Branch objects should cache their "revision_id_to_revno_map" for the
duration of a lock.

So while finding the dotted revno x.y.z is a whole-history operation, it
should only need to be performed one time.

On the other hand, revision_id_to_revno_map doesn't save the 'depth'
information. So we may want to bring in a
Branch.merge_sorted_revisions() which could be cached, and then have
revision_id_to_revno() layered on top of that instead.

There is also this branch:
  http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/lazy_revno/

Which was working on being a replacement for 'revision_id_to_revno' that
wouldn't have to number *all* revisions *all* of the time.

In testing, it works when your ancestries are trivial enough. However,
performance tends to depend as much on the direct ancestry as on the
neighboring ancestry. What I mean by that...

If I have a simple graph like this:

  :
  A
  |\
  B C
  |/
  D

That should be rather trivial to compute the dotted revno for C. And
with my lazy revno code, it is. However, the actual computation time
depends a lot on how "B" existed. For example:

  :
  A :
  |X
  B C
  | |
  | D
  |/
  E

So to compute the dotted revno for D, we need to know the numbering for
C. However, we need to be sure that C was not merged into B. To do so,
we have to search all of the ancestors of B. So the complexity of the
graph of the neighbor B has a large impact of the time to compute the
dotted revno of the revision C.

If we changed how numbers are derived (by using the merged revision
rather than the branched revision) some things get a bit easier. There
are a few more cases where you can stop early. Primarily because we only
store the *ancestor* graph at the moment, and not the *descendants*. If
we changed the indexes to store both, we could actually be in a better
position. (Though branch tips are always at the end, so we are still
better with merge-numbered revnos.)

In the above example, merge-based revnos don't have an advantage over
our current numbers. Where they have an advantage is in:

  : :
  A B
  |/|
  C D
  |/
  E

With our current scheme, you have to keep walking the ancestry of B
until you get to a mainline. With merge-based you get to stop since you
know that whatever comes before B has already been merged.


The lazy-revno branch was, indeed, an attempt at caching things like
'merged into' so that you could do a merge-sorted log without having to
grab the whole graph. I just found in testing that we seemed to grab 90%
of the graph for a lot of cases.


Oh, and another way that merge-based would be 'faster'. Is that if you
want to look up 'x.y.z'. You can walk back the mainline revisions until
you find 'x', and then walk its ancestors until you find enough to
determine 'x.y.z'.

The problem with the current scheme is that if you walk back to 'x', you
know the earliest revision that you care about, but you still have to
walk the ancestors of all the other branches to find the .y.z (because
we don't have children pointers).

Vincent did some thinking about merge-based revnos, and I've talked
about it with him. Fundamentally in any numbering scheme you'll probably
be "racing" between branches, and have to do a bit more searching than
the 'optimal' case.

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

iEYEARECAAYFAklsvKAACgkQJdeBCYSNAAOXggCeLVzohZsoMDFZDjJw65Ar3HyO
BA4An3ZF8WrGV9RYt1QJCyVGWPwiD7RR
=Q6gM
-----END PGP SIGNATURE-----