Stochastic bisection support

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.

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.