[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Monotone-devel] [PATCH] mtn-bisect and toposort/log question
From: |
Łukasz Krotowski |
Subject: |
Re: [Monotone-devel] [PATCH] mtn-bisect and toposort/log question |
Date: |
Sat, 11 Aug 2007 01:40:12 +0200 |
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,
Ł.