Bisection (software engineering)

Code Bisection is a method used in software development to identify change sets that result in a specific behavior change. It is mostly employed for finding the patch that introduced a bug. Another application area is finding the patch that indirectly fixed a bug.

Overview

The code bisection method is a divide and conquer algorithm that tries to minimize the effort to find a specific change set.

It depends on the having access to the code history which is usually preserved by revision control in a code repository.

The Bisection Method

Since code history has the structure of an acyclic directed graph which can be topologically sorted it is possible split up a search space, test for the behavior in question and depending on the result reducing the search space further for a next iteration step.

Desirable Repository Properties

For code bisection it is desirable that each revision in the search space can be compiled and tested independently.

Algorithmic complexity

Code bisection as a divide and conquer algorithm is in LSPACE having an algorithmic complexity of $O(\log _{2}N)$ with $N$ denoting the number of revisions in the search space.

Support by Revision Control Systems

Some revision control systems like Git or Mercurial directly support ^[1]^[2] the code bisection method.

References

[1] ttp://www.kernel.org/pub/software/scm/git/docs/v1.7.10/git-bisect.html

[2] ttp://www.selenic.com/mercurial/hg.1.html#bisect

[1]

[2]