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

[Łukasz Krotowski]

2007/8/11, Nathaniel Smith <address@hidden>:
> > 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.)

Well, it bisecting using toposort needs manual adjustments. Nevertheless
it's still helpful. Don't know about git-bisect algorithms, thou.

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

Well, it's been couple of years since my graph theory classes, but I still
remember something -- so it's clear. ;)

As usual, it's a matter of time -- current version is just, more or less,
one-day tcl script for particular purpose. Right now I'm considering
automation for building and running test. Fire-and-forgot tool, similar
to git-bisect run. Well, I will think about graphs, thou. Graphs are fun,
you know... ;)

Cheers,
Ł.