Re: [Monotone-devel] [PATCH] mtn-bisect and toposort/log question

[Nathaniel Smith]

On Fri, Aug 10, 2007 at 06:21:18PM +0200, Łukasz Krotowski wrote:
> Also, I've got a question. With both mtn automate toposort and mtn log
> (monotone, branch net.venge.monotone) there is such output:
> 
> 1) 11a06ec25f1d3382189b3d39cc0f9e6c7983186f 2007-06-14T21:28:32
> 2) 55434f89a7caebea111d02af424d7bdd35b357a1 2007-05-25T17:15:33
> 3) 2d18283fb2482e98ac5f9d29076804b9d8adbb13 2007-05-24T20:41:22
> 4) 09655aae0a7b9ab2a30f5a9ed36cc8719838d5a1 2007-06-14T12:22:34
> ...
> 
> Revision (1) is merge of (2) and (4). I know it's topological order but it's
> also somehow illogical. ;) Is there possibility to adjust toposort algorithm
> to select such a order where merge ancestors are sorted by time cert?

Dunno, we do like to make our toposort as good as possible, though I
don't know how easy this tweak would be to make.

> It would make log output more readable. And when it comes to mtn-bisect
> order as above causes false positives (revisions 1 and 4 are marked bad and
> 2, 3 good, which make them local maximum): (1) can be found as first bad
> revision.

This worries me, though.  Bisection search should *definitely* not be
using toposort for anything, it won't work even if we do further tweak
the toposort used.  (Does git-bisect use a toposort?  I always assumed
not, but I never checked.)

You should use automate graph to get a graph structure in memory,
then each node in the graph can be in state "good", "bad", or
"unknown", and then assume when a node is bad every descendent of that
node is bad, and when a node is good every ancestor of that node is
good, and then when you have to pick a node to test, always pick the
node that has the best balance between unknown ancestors and unknown
descendents.  I guess "best balance" might be defined as the one with
the largest value of
   log(# of unknown ancestors) + log(# of unknown descendents)
though probably other things will work too, that's just the optimal
thing to use if we take an information-theoretic approach.

(Sorry if that's too telegraphic, on my way to bed, let me know if you
can't figure out what I'm talking about.)

-- Nathaniel

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