Bisection (software engineering)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.


Code bisection has the goal of minimizing the effort to find a specific change set.

It employs a divide and conquer algorithm that depends on having access to the code history which is usually preserved by revision control in a code repository.

Bisection method[edit]

Code bisection algorithm[edit]

Code history has the structure of a directed acyclic graph which can be topologically sorted. This makes it possible to use a divide and conquer search algorithm which:

  • splits up the search space of candidate revisions
  • tests for the behavior in question
  • reduces the search space depending on the test result
  • re-iterates the steps above until a range with at most one bisectable patch candidate remains

Algorithmic complexity[edit]

Bisection is in LSPACE having an algorithmic complexity of with denoting the number of revisions in the search space, and is similar to a binary search.

Desirable repository properties[edit]

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

Support by revision control systems[edit]

Revision control systems like Git or Mercurial directly support[1][2] code bisection.

Other revision control systems like Bazaar or Subversion support it indirectly employing plugins[3] or external scripts.[4]

Support by other systems[edit]


  1. ^ "git-bisect(1)". 2012-05-09. Retrieved 2017-01-09. 
  2. ^ "hg". Retrieved 2017-01-09. 
  3. ^ "bisect - Find the revision introducing a bug using a binary search — Bazaar 2.8.0dev1 documentation". Retrieved 2017-01-09. 
  4. ^ "svn-bisect". Retrieved 2017-01-09.