"bzr log" by revision-id is slow

[Andrew Bennetts]

On Thu, Oct 13, 2011 at 12:18:24AM +0200, Eli Zaretskii wrote:
> It looks like "bzr log -r REVID" is O(1), but with a very large
> constant.  The time is roughly the same as it takes "bzr
> revision-info" to return the revno by revision-id.
> 
> Here are a few examples from the Emacs repository, which show that the
> time taken by "bzr log -r REVNO" grows for older revisions, but the
> same command by REVID takes constant time, which happens to be the
> same as for "bzr log -r 1".

Each branch stores its current (or “tip”) revno and revid, so looking
that up is virtually free.  Anything else requires some work, because
each revision links just to its parent revid(s), and doesn't
intrisically store its revno (because the revno is always w.r.t. to some
tip).  So AIUI:

 * “bzr log -r -N” has to follow N links from the current tip (for
   non-dotted revnos; dotted is obviously trickier), one-by-one, to find
   the the specified revision.  So that's O(N).

 * “bzr log -r N”, similarly has to follow CURR_REVNO-N links.

 * “bzr log -r REVID” can find the revision object in O(1) time, but the
   log output needs its revno too, and determining its revno requires
   searching the ancestry of the tip revision to find out where it is in
   the ancestry.  There's not any particularly good clues in the
   revision object to guide the search, so that's O(revs-in-ancestry).
   In principle a log format that doesn't show the revno can avoid this
   cost, but I don't know if such a thing has been implemented.

I suspect installing one of the experimental ancestry-graph/revno
caching plugins can help these cases a great deal.

Also, if you're writing a script that does a lot of these calls, you'll
get much better performance writing it as a Python script using bzrlib,
because then you can do these lookups in a single read_lock and benefit
from having (probably) most of the metadata cached.  (This is why e.g.
logging a range of 100 revisions from the command line is going to be
much faster than calling "bzr log" 100 times.)

> Is this expected?

For some values of “expected”, yes ;)

-Andrew.