Re: Generalised bisection

From: Ealdwulf Wuffinga <ealdwulf@googlemail.com>
To: Steven Tweed <orthochronous@gmail.com>
Cc: Johannes Schindelin <Johannes.Schindelin@gmx.de>,
	John Tapsell <johnflux@gmail.com>,
	Christian Couder <chriscool@tuxfamily.org>,
	Git List <git@vger.kernel.org>
Subject: Re: Generalised bisection
Date: Mon, 16 Mar 2009 22:08:15 +0000	[thread overview]
Message-ID: <efe2b6d70903161508i19c16f6bm7f695452748a06a1@mail.gmail.com> (raw)
In-Reply-To: <d9c1caea0903160329v3c1a1600m9913eafa00cc2f37@mail.gmail.com>

On Mon, Mar 16, 2009 at 10:29 AM, Steven Tweed <orthochronous@gmail.com> 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