Re: Generalised bisection

On Mon, Mar 16, 2009 at 10:29 AM, Steven Tweed [off-list ref] wrote:

I had a look over the weekend, and got a bit sidetracked on one of
your assumptions. You seem to be assuming that the bug is such that
observing a single positive observation of the symptom at a position i
in the linear history _does not_ completely rule out that the guilty
commit occurs after that point. I would have thought the generally
more applicable assumption is that, given that generally you don't
have a bug ridden system where more than one bug causes the same
symptom _within the history of interest_, that a single observation of
the symptom does totally rule out the bug after that point (whilst
intermittency clearly not having observed the bug before that point
doesn't completely rule out the guilty commit being earlier, although
it should increase the liklihood estimate of the bug being later).

I must have been unclear somewhere, because I do indeed assume that
a single observation of the symptom rules out the origin of the bug being
later than that observation.

 If you have a play with the software in manual mode, you can see that its
behaviour reflects this  - it starts out doing something like an
ordinary binary search, albeit skewed towards older revisions (it
seems to go for
a roughly 1:2 division, rather than the usual 1:1). Then once it has got to the
point where a deterministic search would end, it hammers away at the parent(s)
of the newest revision where the fault was observed, until it is satisfied that
it cannot be found there. All this just emerges from the generic least-entropy
algorithm; I didn't know what it would do until I got it running.

I wonder what your thoughts are on this? (I started formulating a
model over the weekend, but work is a bit hectic so I may not get to
write it up in LaTeX very quickly.)

It will be interesting to see whether your model turns out to be different from
mine. I'm only doing this in my spare time, so I'm in no hurry.

Ealdwulf