"bzr log" by revision-id is slow

[Eli Zaretskii]

> Date: Thu, 13 Oct 2011 10:23:18 +1100
> From: Andrew Bennetts <andrew at bemusement.org>
> Cc: bazaar at lists.canonical.com
> 
>  * “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.

That part I expected.

>  * “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).

But what I see is O(1), and the time is very long.  It almost sounds
like bzr searches the entire ancestry, not just follows CURR_REVNO-N
links, because using REVID that is the parent of the tip takes the
same 19 seconds that it takes to follow all the ancestry down to revno
1.  _That_ was unexpected.

Btw, there's one hint in the REVID to perhaps guide the search: the
date of the commit.  Can that be used to speed up the search?

>    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.

If most of the time it takes is to look up the revno, then indeed not
showing the revno would be a very good optimization.

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

Can you name those, please?  I already have history_db, but the time
this takes with and without it is the same.