Re: [Monotone-devel] responses to some IRC discussion of 'automate'

[Nathaniel Smith]

On Mon, Aug 07, 2006 at 10:21:44AM +0200, Thomas Moschny wrote:
> Now, while I am not familiar with the inner workings of erase_ancestors, I 
> suppose it's runtime is not linear in the size of it's argument list. So we 
> should recuce that list. Obviously, only those revisions qualify as branch 
> heads that either don't have children at all, or only have children carrying 
> different branch tags. Using this criterion (and having an indexed  
> revision_ancestry table) it should be possible to scrub the list easily 
> before feeding it to erase_ancestors.

It's an interesting question.  The speed of erase_ancestors is very
hard to quantify; it has to scan over large portions of the graph,
regardless of how many revisions it is passed.  For example, if you
have a graph like:
  A -> B -> C -> D -> E -> F -> G -> H -> I
and you pass erase_ancestors {A, I}, it's going to have to scan the
whole graph.  If you pass it {A, F, I}, it's also going to have to
scan the whole graph -- so the F is probably free.

erase_ancestors does already load the entire graph as its first step,
though; if you think that it might be faster if it first threw out all
the items that are _obviously_ ancestors, then it's easy to test --
just scan over the graph and do it, before running the main algorithm,
and see if things get any faster.  (Or do some tests by hand using
'automate erase_ancestors'.)

> However I am not sure whether this can be done using SQL, because all tags 
> (includung the branch tags) have to be validated before any reasoning can be 
> done based on their values.

In principle it could -- just add a sqlite function that checks cert
validity, and include that in your WHERE clause :-).  (In fact, back
before we understood the difference between "ancestor" and "parent",
and when we used an SQL query just like the ones you guys have
mentioned to implement 'heads', this is what we did.)

However, there isn't much to gain by doing this.  'for' loops run just
as fast whether it's SQLite or us that runs them.  Using SQL is fast
when it can take advantage of indexes, and sometimes convenient at
other times; when it's neither fast nor convenient, well... :-)

-- Nathaniel

-- 
"Of course, the entire effort is to put oneself
 Outside the ordinary range
 Of what are called statistics."
  -- Stephan Spender