Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Git bayesect – Bayesian Git bisection for non-deterministic bugs

github.com

Post reply on HN
Print view View original

21–30 of 56 posts

Re: Show HN: Git bayesect – Bayesian Git bisection for non-deterministic bugs

#21

Post by sfink »

rs545837 wrote: post #20

Really fun work, and the writeup on the math is great. The Beta-Bernoulli conjugacy trick making the marginal likelihood closed-form is elegant. We ran benchmarks comparing bisect vs bayesect across flakiness levels. At 90/10, bisect drops to ~44% accuracy while bayesect holds at ~96%. At 70/30 it's 9% vs 67%. The entropy-minimization selection is key here since naive median splitting converges much slower. One thing…

> We ran benchmarks comparing bisect vs bayesect across flakiness levels. At 90/10, bisect drops to ~44% accuracy while bayesect holds at ~96%. At 70/30 it's 9% vs 67%.

I don't understand what you're comparing. Can't you increase bayesect accuracy arbitrarily by running it longer? When are you choosing to terminate? Perhaps I don't understand this after all.

Re: Show HN: Git bayesect – Bayesian Git bisection for non-deterministic bugs

#22

Post by ajb »

sfink wrote: post #18
ajb wrote: post #15

Earlier quoted context omitted.

In theory, the algorithm could deal with that by choosing the commit at each step, which gives the best expected information gain; divided by expected test time. In most cases it would be more efficient just to cache the compiled output though.

This doesn't sound quite right, but I'm not sure why. Perhaps: a reasonable objective would be to say that for N bits of information, I would like to pick the test schedule that requires the least total elapsed time. If you have two candidate commits and a slow recompile time, it seems like your algorithm would do many repeats of commit A until the gain in information per run drops below the expected gain from B divi…

The general requirement for this approach to be optimal, is called "dynamical consistency". A good description is in [1]. It is the situation where, suppose you have a budget B , and you search until your budget is exhausted. Then you are informed that there is an additional budget, B2, and you can continue searching until that is exhausted. A situation is dynamically consistent if, for any B,B2, the optimal strategy is such that you would make the same choices whether you know that you will get B2 or not.

So you are correct that discreteness is a problem, because if you are nearing the end of the budget you may optimally prefer to get more dice rolls than take bigger bets. But the optimal solution is then often analytically intractable (or at least it was - I last read about this a while back), and the entropy approach is often reasonable anyway. (For cases where search effort is significant, a good search plan can be found by simulation).

[1] https://bayes.wustl.edu/etj/articles/search.pdf

Re: Show HN: Git bayesect – Bayesian Git bisection for non-deterministic bugs

#24

Post by rs545837 »

sfink wrote: post #21
rs545837 wrote: post #20

Really fun work, and the writeup on the math is great. The Beta-Bernoulli conjugacy trick making the marginal likelihood closed-form is elegant. We ran benchmarks comparing bisect vs bayesect across flakiness levels. At 90/10, bisect drops to ~44% accuracy while bayesect holds at ~96%. At 70/30 it's 9% vs 67%. The entropy-minimization selection is key here since naive median splitting converges much slower. One thing…

> We ran benchmarks comparing bisect vs bayesect across flakiness levels. At 90/10, bisect drops to ~44% accuracy while bayesect holds at ~96%. At 70/30 it's 9% vs 67%. I don't understand what you're comparing. Can't you increase bayesect accuracy arbitrarily by running it longer? When are you choosing to terminate? Perhaps I don't understand this after all.

Yes, bayesect accuracy increases with more iterations. The comparison was at a fixed budget(300 test runs) when I was running. Sorry should have clarified more on that.

Re: Show HN: Git bayesect – Bayesian Git bisection for non-deterministic bugs

#25

Post by IshKebab »

Does this tool assume it takes the same amount of time to test two commits once as it does to test one commit twice? Maybe true for interpreted languages, but if you're waiting 15 minutes to compile LLVM you're probably going to want to run your 1 second flaky test more than once. Probably pretty trivial to fix this though?

Great idea anyway!

Re: Show HN: Git bayesect – Bayesian Git bisection for non-deterministic bugs

#26

Post by ncruces »

SugarReflex wrote: post #9

I hope this comment is not out of place, but I am wondering what the application for all this is? How can this help us or what does it teach us or help us prove? I am asking out of genuine curiosity as I barely understand it but I believe it has something to do with probability. edit: thanks for the responses! I was not even familiar with `git bisect` before this, so I've got some new things to learn.

If you want to read more about the bisect idea itself, this link has a bunch of interesting use cases:

https://research.swtch.com/bisect

TLDR: you can bisect on more than just "time".

Re: Show HN: Git bayesect – Bayesian Git bisection for non-deterministic bugs

#29

Post by ajb »

convexly wrote: post #23

Do you expose the posterior probabilities anywhere so you can see how confident it is in the result?

Not the OP, but Fyi you know that to some extent anyway, because the termination condition is that confidence is above a specified value. This is one of the advantages over just doing git bisect with some finger-in-air test repeat factor. But yeah it can print that too.
Post reply on HN