Generalised bisection

[whoops, mail server does not like html. trying again...]

Hi,

I have developed a generalised bisection algorithm, for the case where a bug is intermittent. The code may be found at git://github.com/Ealdwulf/bbchop.git. It should be considered experimental.

This should cover the use cases requested by Ingo (http://article.gmane.org/gmane.comp.version-control.git/108565) and John  (http://article.gmane.org/gmane.comp.version-control.git/112280), although it does not work in the same way as your proposed solutions - it is intended to be more general, working when the bug is not almost-deterministic. It is based on Bayesian Search Theory (http://en.wikipedia.org/wiki/Bayesian_search_theory, although that description is a bit simplistic) which is usually used to find submarines, or people lost on mountains.

To try it out, you need python and mpmath (from http://code.google.com/p/mpmath/ or your distribution). Once your have obtained the source, you can immediately run BBChop/source/bbchop which is the main driver program.

It is not currently integrated into git, although doing so should only involve minor scriptery.

The simplest way to try it out to is run it in manual mode:

This means, search in a linear history of 10 revisions, numbered 0 to 9, until bbchop thinks it has found the faulty location with probability at least 0.9. It will start asking questions:

] Most likely location is 0 (probability 0.100000). ] Please test at location 3. ] Target detected at 3? Y/N/S(kip)

Eventually the search will terminate and BBChop will print out its conclusion, with evidence, eg:

] Search complete.  Most likely location is 3 (probability 0.919614). ] Number of tests at 3: 3 of which 1 detected ] Number of tests at parents of 3: ]         At 2, 5 of which 0 detected

More information canbe found in the readme file.

Feel free to reply with any comments, questions, etc. If anyone tries it out on a real bug, please let me know how it goes.

regards,

Ealdwulf