Re: Stochastic bisection support

[Christian Couder <christian.couder@gmail.com>]

Hi,

On Thu, Nov 18, 2021 at 9:33 PM Jan Kara <jack@suse.cz> wrote:
>
> Hello,
>
> In some cases regressions (or generally changes) we are trying to bisect have
> probabilistic nature. This can for example happen for hard to trigger race
> condition where it is difficult to distinguish working state from just not
> hitting the race or it can happen for performance regressions where it is
> sometimes difficult to distinguish random workload fluctuations from the
> regression we are looking for. With standard bisection the only option we have
> is to repeatedly test suggested bisection point until we are sure enough which
> way to go. This leads to rather long bisection times and still a single wrong
> decision whether a commit is good to bad renders the whole bisection useless.
>
> Stochastic bisection tries to address these problems. When deciding whether a
> commit is good or bad, you can also specify your confidence in the decision.
> For performance tests you can usually directly infer this confidence from the
> distance of your current result from good/bad values, for hard to reproduce
> races you are usually 100% confident for bad commits, for good commits you need
> to somehow estimate your confidence based on past experience with reproducing
> the issue. The stochastic bisection algorithm then uses these test results
> and confidences to suggest next commit to try, tracking for each commit the
> probability the commit is the bad one given current test results. Once some
> commit reaches high enough probability (set when starting bisection) of being
> the bad one, we stop bisecting and annouce this commit.

The following project is based on Bayesian Search Theory and might be
interesting if you haven't looked at it:

https://github.com/Ealdwulf/BBChop

Best,
Christian.



















> Example:
>
> Consider an example of a stochastic bisection of the following commits:
>
> A--B--C--D-----F-----H--------K
>  \     \  \-E-/     /        /
>   \     \--------G-/        /
>    \------------------I--J-/
>
> And suppose commit I is the bad one. Let's start bisection with:
>
> # We ask bisection for 90% confidence in the identified commit being bad
> git bisect start --confidence 0.9 %K %A
>
> # Bisection tells us to test %F. Let's assume test went well and we trust
> # our test results on 70%. So:
> git bisect good --confidence 0.7
>
> # Bisection tells us to test %H. Again same result:
> git bisect good --confidence 0.7
>
> # Bisection tells us to test %J. The test should fail for %J (remember %I is
> # the bad commit) but let's assume the test is falsely positive. So:
> git bisect good --confidence 0.7
>
> # We are asked to test %H second time. Assume correct result so:
> git bisect good --confidence 0.7
>
> # We are asked to test %J second time. Assume correct result so:
> git bisect bad --confidence 0.7
>
> # We are asked to test %J again. Assume correct result so:
> git bisect bad --confidence 0.7
>
> # And %J once more. Assume false positive so:
> git bisect good --confidence 0.7
>
> # And %J once more. Assume correct result so:
> git bisect bad --confidence 0.7
>
> # And %J again. Assume correct result so:
> git bisect bad --confidence 0.7
>
> # And now we are asked to test %I. Assume correct result so:
> git bisect bad --confidence 0.7
>
> # We are asked to test %I second time. Assume false positive so:
> git bisect good --confidence 0.7
>
> # And %I once again. Assume correct result so:
> git bisect bad --confidence 0.7
>
> # And %I once again. Assume correct result so:
> git bisect bad --confidence 0.7
>
> # And %I once again. Assume correct result so:
> git bisect bad --confidence 0.7
>
> And now git tells us %I is the bad commit with desired confidence. We can see
> the bisection was able to identify the bad commit although there were three
> false positive tests (out of total 14 tests).
>
> ------
>
> This patch set implements stochastic bisection for git. The first part of the
> series improves some tests so that they accept other valid decisions for
> bisection points. This is needed because to make it easier to share some logic
> between normal and stochastic bisection, I needed to slightly change some bits
> for normal bisection and then since commit weights will be computed in a
> somewhat different order, also chosen bisection points are sometimes different.
>
> The second part of the series then implements stochastic bisection itself.
> Note that I didn't integrate any tests for stochastic bisection into 'make
> test' run yet (so far I did only manual tests) and I still need to update
> manpages etc. I plan to do that but I've decided to post the series now to get
> some early feedback.
>
>                                                                 Honza
>
> PS: Please leave me in CC for replies. I'm not subscribed to the git mailing
> list.