BBChop

Nice! I implemented a similar thing a while back: https://github.com/Ealdwulf/BBChop I'm going to have to check out how you got linear time with Shannon entropy, because I used Renyi entropy to do that, to make the algebra easier. It's also possible to do it over the DAG, rather than a linear history - although that makes the code a lot more complicated. Unfortunately there doesn't seem to be a linear time cumulative sum algorithm over dags, so it's super linear in some cases.

Here is a doc explaining a Bayesian search algorithm; not sure if it's precisely what GP has in mind. https://github.com/Ealdwulf/BBChop/blob/master/BBChop/doc/Ba... (Edit- had wrong link originally)

For git bisect, there is this: https://github.com/ealdwulf/bbchop But it seems likely that heuristically picking a multiple of times to run the test produces similar results

There is actually a bayesian version which I wrote: https://github.com/ealdwulf/bbchop Basically it calculates the commit to test at each step which gains the most information, under some trivial assumptions. The calculation is O(N) in the number of commits if you have a linear history, but it requires prefix-sum which is not O(N) on a DAG so it could be expensive if your history is complex. Never got round to integrating it into git though.

A while back, I wrote a Bayesian version of git bisect which -at least in theory - means you can fully automatically find your regression even if the bug is a nondeterministic one (intermittent): https://github.com/ealdwulf/bbchop Never actually used it in anger though. Unlikely to work in half an hour either. But you could leave a machine churning away and eventually get an answer.

An interesting exercise. Why do you think an increasing probability distribution makes this equivalent to the halting problem, though? Without loss of generality, an increasing probability is >= some P after some time T. Being conservative, we can assume the failure probability is zero before T and ==P after T. Of course, we don't actually know P or T, but they must be consistent with us having seen the bug at all. So we can use uninformative priors to define the posterior distribution of these values given the number of times we have seen the bug and the amount of time required in each case. Unless I'm missing something? I once wrote a probabilistic version of git bisect (https://github.com/Ealdwulf/bbchop) for use with intermittent bugs, but it hasn't seen real use.

Yeah, bayesian search theory is an interesting topic. A while back I wrote a program to search for intermittent bugs using it (a sort of bayesian version of 'git bisect') It hasn't seen real use (Intermittent bugs tend to involve real hardware, so you can't just try it out on any bug database) . But if anyone wants to try it out, it is at https://github.com/Ealdwulf/bbchop

This comes up every few years. Please, guys, before you conclude that probabilistic computers are the future, think about what it would be like debugging a program running on one. Speaking as someone who has implemented a probabilistic version of 'git bisect'[1], I think it would be hard. That's not to say that the idea is completely dumb. A probabilistic GPU would be useful, although it would go against the trend of being able to use them for general computation. [1] That is, one that looks for probabilistic bugs, not one that runs on a probabilistic CPU. See https://github.com/Ealdwulf/bbchop

Not built in, on the other hand, is 'bbchop', which is like bisect, but for intermittent bugs: http://github.com/Ealdwulf/bbchop

If anyone needs to bisect an intermittent bug, I have written a bayesian version of git bisect. It can be found at: http://github.com/Ealdwulf/bbchop/tree/master