Re: [Monotone-devel] speed of "mtn ls branches"

[William Uther]

On 17/01/2008, at 4:00 PM, Zack Weinberg wrote:

> On Jan 16, 2008 11:17 PM, William Uther
> <address@hidden> wrote:
> > On 17/01/2008, at 2:35 PM, Tony Tung wrote:
> > > I just downloaded monotone 0.38, and I found the command "mtn ls
> > > branches" to take a lot longer than the previous version I was
> > > using (0.35).
> >
> > That is almost certainly due to the introduction of 'suspend' certs.
>
> While working on something else today I noticed that the suspend-certs
> implementation appears to be doing redundant work.  I'm not
> remembering exact details, but it looked like: scan through all branch
> heads and make a list of non-suspended ones, then check
> --ignore-suspend-certs, then if it's not set, do that again.

Before suspend certs the algorithm was:

project_t::get_branch_list()
  Get a list of all branch certs used in the db.
  Loop over the list of strings adding them to a set of branch_name  
elements

Now that it checks the suspend certs, the algorithm is:

project_t::get_branch_list()
  Get a list of all branch certs used in the db.
  For each branch, get_branch_heads()
  if there are any heads then add the branch to the set of  
branch_name elements

As part of speeding that up get_branch_heads takes a new argument,  
the inverse_graph_cache.
This is populated inside get_branch_heads and is a cache of data used  
for erase_ancestors_and_failures.
Note that the app.db.get_branches() call only queries the DB for a  
list of branches, it doesn't check
cert validity or deal with suspend certs.  It is simply an SQL call.

The other thing you might be referring to is the way that  
get_branch_heads works...
  First, get all revs with a given branch cert using the db (i.e.  
without checking the cert is valid)
  Next, erase ancestors and failures (this checks all the branch certs)
  Finally, check that any revisions that still exist (which would  
have been heads before suspend certs were introduced) do not have  
suspend certs.

You cannot merge the suspend cert checking into the  
erase_ancestors_and_failures call there.  Adding a suspend cert is  
NOT the same as removing a branch cert.  If you remove a branch cert  
from a head then its parents become heads.  If you add a suspend cert  
to a head then its parents do not become heads.

I don't see any repeated work here.

Note that there is a subtle bug/design choice here: If the only  
instance of a revision on a particular branch happens to have an  
invalid branch cert (i.e. you have no valid branch certs with that  
branch), then the 'mtn ls branches' code without suspend cert checks  
(either the old code, or with --ignore-suspend-certs) will return it  
anyway.  The code with suspend cert checks will not return that as a  
valid branch, even though it isn't suspended.

Cheers,

Will       :-}