Hi, On Thu, Nov 18, 2021 at 9:33 PM Jan Kara <jack@xxxxxxx> 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.
