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

[Thomas Moschny]

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.

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

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

> The impression I got from that discussion was that adding heights to
> the erase_ancestors() code wouldn't make much difference.  (I think I
> get heights now, in general.)

Well, I did some benchmarking, and it turned out that, for large revision 
sets, it's not worth the effort fetching all heights, whereas it can speed up 
things for small sets. So, we could have two versions of this method, and 
only one of them using heights, and switch between them depending of the 
revision set size. Additionally, a get_revision_heights method might be 
useful that fetches all heights at once, similar to get_revision_ancestry.

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

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

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

Regards,
Thomas

signature.asc
Description: This is a digitally signed message part.