Re: [Monotone-devel] Suspend certs...

[William Uther]

On 12/08/2007, at 12:06 AM, Thomas Moschny wrote:

> On Saturday 11 August 2007, William Uther wrote:
> > > > In particular, mtn ls branches is a fair bit slower now.  It  
> > > > would be
> > > > much better if it were incremental, then it wouldn't seem quite so
> > > > bad.
> > >
> > > Ouch, 35.92 user against 0.06 user before.
> >
> > Yeah.
>
> Especially, if we don't find a way to speed up things, we need
> the --ignore_suspend_certs for the automate version of heads,  
> otherwise it
> will slow down e.g. TracMtn a lot.

I'm actually not keen on doing work to just speed up that version, as  
it means that people listing heads will just use that version.  Then  
you lose the feature this was designed to implement - suspending  
branches.

> > The problem is that we are now running "mtn heads" on every branch to
> > see if it has heads.  "mtn heads" is an inefficient operation.  (See
> > project_t::get_branch_heads() in project.cc, and
> > erase_ancestors_and_failures() in revision.cc if you're following
> > along at home.)
> >
> > To get the heads of a branch, we first get every revision that has a
> > cert with that branch name.  Then we go through and erase ancestors
> > and failures on that list.  This means that a full list of all
> > branches requires getting every revision in the db at least once, and
> > running erase ancestors on them all, one branch at a time.
>
> A quick valgrind run shows that about 60 percent of the execution  
> time for mtn
> ls heads on a typical nvm database (with 184 branches) is spent in
> get_revision_ancestry. It may be worth caching the ancestry, so it  
> is not
> re-fetched while processing each branch.

Interesting. :)

After getting the ancestry, heads also goes and inverts it each  
time.  It would be worth caching the inverted version.

Busy today, but I'll look into it soon.  My first pass would be to  
cache the inverted ancestry just for 'get_heads()', and only for a  
single instantiation of mtn.  Can anyone imagine a case where that  
would get out of date?

> > This was discussed recently:
> >
> > http://thread.gmane.org/gmane.comp.version-control.monotone.devel/ 
> > 11737
>
> About a year ago (when mtn heads was still terribly slow), some  
> similar SQL
> statements were proposed by tommyd and me, but then we realized  
> that the real
> solution was to interweave ancestry walking and cert checking, and  
> Nathaniel
> wrote the erase_ancestors_and_failures method. Since then, mtn  
> heads needs to
> check only a few certs (look for 'called predicate XX times'  
> messages), and
> things improved a lot. Still, getting /all/ heads is slow.

> > Some caching would be better I suspect, but you'd need to be able to
> > regenerate the cache when any of the trust hooks changed.
>
> See above. Caching the result of trust hook evaluations might help  
> a bit, but
> not too much (in the normal use case where the majority of certs is  
> indeed
> valid), because erase_ancestors_and_failures doesn't need to call the
> predicate very often.

Again, interesting.  I spent last night thinking of a version of  
'get_heads()' that used the ancestry to get candidate heads, then  
checked the certs on them crawling back up the ancestry tree when  
there were failures.  The idea was that in the usual case you  
wouldn't need to crawl very far.  This would avoid passing around the  
set of candidates that is every revision in the branch.

If what you say is true, that might not be a big win, but I guess I'd  
need to implement and test.

> > > Can you elaborate a bit more what you mean with "incremental"?
> >
> > At the moment the 'ls branches' command gathers the list of branches,
> > then prints them all out.  This puts a large pause at the beginning.
> > It would be better if it printed out the results as it gathered
> > them.
>
> Nice for the gui, but probably not needed for automate, and doesn't  
> speed up
> things in general.

Nice for the UI in general.  The pause at the start is disconcerting  
for text UIs too.

> > > IMHO if
> > > we do not get the speed of ls branches down to only a few  
> > > seconds, we
> > > should make --ignore_suspend_certs the default for ls branches and
> > > other
> > >  affected commands.
> >
> > Well, I think there may be some other options.  e.g. ignore trust
> > hooks for 'ls branches'.  That should allow a version to be written
> > that was pretty quick.
>
> See above. Besides, evaluating certs without knowing whether to  
> trust them
> seems pointless to me.

fair enough.

Be well,

Will        :-}