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

[William Uther]

On 18/01/2008, at 4:15 AM, Zack Weinberg wrote:

> On Jan 17, 2008 1:06 AM, William Uther
> <address@hidden> wrote:
> > On 17/01/2008, at 4:00 PM, Zack Weinberg wrote:
> > > 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.
> ...
>
> I found the code I was referring to - it has nothing to do with "ls
> branches", but I stand by my original statement.
> update.cc, function calculate_update_set:
>
> ...
>   bool have_non_suspended_rev = false;
>
>   for (set<revision_id>::const_iterator it = candidates.begin(); it !=
> candidates.end(); it++)
>     {
>       if (!app.get_project().revision_is_suspended_in_branch(*it,  
> branch))
>         {
>           have_non_suspended_rev = true;
>           break;
>         }
>     }
>   if (!app.opts.ignore_suspend_certs && have_non_suspended_rev)
>     {
>       // remove all suspended revisions
>       base64<cert_value> branch_encoded;
>       encode_base64(cert_value(branch()), branch_encoded);
>       suspended_in_branch s(app, branch_encoded);
>       for(std::set<revision_id>::iterator it = candidates.begin(); it
> != candidates.end(); it++)
>         if (s(*it))
>           candidates.erase(*it);
>     }

Yes, that is repeating some work.  Here is the intention:

  If there are any non-suspended update candidates then remove the  
suspended
  update candidates, otherwise leave all the suspended revs in the  
candidate
  set.

The goal of this is simple.  If you have a working copy for a branch and
all heads are suspended, then you should still be able to update - so
you need to be able to update to suspended heads.  If only some of the
heads are suspended then should be able to update as well - but this
time you only want to update to the non-suspended heads.

The first loop checks to see if we have ANY non suspended update  
candidates
and the second removes suspended update candidates if necessary.

I can see some some simple improvements:
  - move the ignore_suspend_certs check outside both loops (assuming  
that
doesn't have other affects outside the posted code).
  - move the creation of the suspended_in_branch object before the top
loop and use it in both.  This will slightly speed up the top loop.

However, you cannot simply merge the two loops - while you're in the  
first
loop you don't know if the second loop should run at all.  One change  
you
could make would be to cache the suspend cert checks... is it worth  
the hassle
to make that optimisation?  How large are the candidate update sets?   
How
slow are cert checks?

Cheers,

Will        :-}