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

[William Uther]

On 12/08/2007, at 7:02 AM, William Uther wrote:

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

I pushed a change that caches this data.  mtn ls branches for n.v.m.*  
is down to 6 seconds from 30 on my machine.

This is already below my "hrm, has it frozen?" threshold.  If we  
wanted to get it down further...

At the moment when erasing ancestry, we grab revisions in random  
order, and find all their ancestors.  For most n.v.m branches, this  
is going to mean traversing the entire n.v.m.* ancestry graph back to  
the root.

My first thought was that we should use something like this sql I  
posted before:

> SELECT revision_certs.id FROM revision_certs,
> revision_ancestry                      // get the id of revs
>    WHERE revision_certs.id =
> revision_ancestry.child                                  // that  
> are children in the ancestry table
>    AND revision_certs.name = ? AND revision_certs.value
> = ?                           // and are in the branch we're  
> looking for
>    AND revision_ancestry.child NOT
> IN                                                 // and are not
>       (SELECT revision_ancestry.parent FROM revision_ancestry,
> revision_certs WHERE   // parents in the ancestry table
>           revision_ancestry.child = revision_certs.id
> AND                             // where the corresponding child's
> branch
>           revision_certs.name = ? AND revision_certs.value
> = ?                        // is the branch we're looking for
>       )

which tries to use SQL to find heads ignoring trust.  Once you have  
those, search back from them to the first trusted rev in the  
appropriate branch.  I think that should give you the heads, and in  
most cases be quite efficient.  I couldn't convince myself that it  
was 100% correct though (I could sorta prove it to myself, but it was  
more complex than I wanted to trust).

The next thought was to use heights (as suggested in the comment).   
That would stop short branches from iterating over the entire  
ancestry.  I have a fairly busy week, and mtn ls branches is not  
horrendous any more.  I'll look at it when I have time.

Be well,

Will          :-}