Debugging with binary search (git bisect)

Debugging with Binary Search (git bisect)

Git bisect is a powerful debugging tool that quickly locates the commit introducing a problem using a binary search algorithm. When a bug appears in a project but the exact commit that caused it is unknown, bisect can automatically check historical commits, significantly reducing troubleshooting time.

How git bisect Works

Git bisect is based on the binary search algorithm, dividing commit history into "good" and "bad" parts. The process requires:

1. Specifying a known good commit (good)
2. Specifying a known bad commit (bad)
3. Git automatically checks out a middle commit for testing
4. Marking the current commit as good or bad based on test results
5. Repeating this process until the first problematic commit is found

The algorithm reduces time complexity from O(n) to O(log n), making it particularly effective for projects with hundreds of commits.

Basic Usage Workflow

# Start a bisect session
git bisect start

# Mark the current version as bad
git bisect bad

# Mark an older version as good
git bisect good v1.2.0

# Mark test results for the current version
git bisect good  # If the current version is good
git bisect bad   # If the current version is bad

# End the bisect session
git bisect reset

Practical Example

Suppose a rendering bug is discovered in a React project, and the last known working version was a commit from two weeks ago:

git bisect start
git bisect bad HEAD      # Current version is bad
git bisect good abc1234  # abc1234 is a known good commit

Git will automatically check out a middle commit. You then need to:

1. Run project tests or manually check for the issue
2. Execute git bisect good or git bisect bad based on results
3. Repeat until the problematic commit is found

Automated Testing

For scenarios where tests can be automated, use a test script with bisect:

git bisect start HEAD abc1234
git bisect run npm test

Git will use the script's exit code to determine commit status (0 for good, 1-127 for bad).

Practical Tips for Frontend Projects

1. Complex Build Environments: Use git bisect run with build scripts

git bisect run sh -c "npm install && npm build && npm test"

2. Skipping Untestable Commits:

git bisect skip

3. Visualizing Progress:

git bisect visualize

4. Logging Results:

git bisect log > bisect.log

Handling Special Cases

Merge Commits: When encountering merge commits, bisect checks all parent commits. Use:

git bisect skip $(git merge-base <good> <bad>)

Test Environment Differences: If intermediate commits depend on environment changes:

git bisect run sh -c "check_env.sh && npm test"

Performance Optimization Tips

1. Use shallow cloning to reduce data:

git clone --depth=500 <repo>

2. For large repositories, narrow the range first:

git bisect start --term-old=working --term-new=broken

3. Use reflog to recover from incorrect markings:

git bisect reset
git reflog bisect

Integration with Other Tools

VS Code Integration:

1. Install the GitLens extension
2. Right-click a commit and select "Start Bisect"
3. Mark good/bad via the GUI interface

GitHub Actions Integration:

- name: Bisect
  run: |
    git bisect start
    git bisect bad
    git bisect good ${{ env.GOOD_COMMIT }}
    git bisect run npm test

Advanced Usage

Custom Terminology: Change good/bad labels:

git bisect start --term-new=failed --term-old=passed

Partial Bisect: When unsure about exact results:

git bisect skip

Multi-Branch Search: Cross-branch problem detection:

git bisect start <bad-commit> <good-commit> -- <path>

Troubleshooting Common Issues

Build Errors:

git bisect run sh -c "npm install || exit 125 && npm test"

(Exit code 125 tells Git to skip the current commit)

Non-Deterministic Bugs: For flaky tests:

git bisect run sh -c "for i in {1..10}; do npm test && exit 0; done; exit 1"

Insufficient Memory: Limit test range:

git bisect start HEAD~100 HEAD