The Binary Search Idea for Narrowing Down Problem Space

Binary search algorithm is a search algorithm that finds the position of a target value within a sorted array. It cuts off the target array in half in a pass, so that it has a worst-case performance of O(log n).

https://upload.wikimedia.org/wikipedia/commons/8/83/Binary_Search_Depiction.svg — Visualization of the binary search algorithm where 7 is the target value(@wikipedia)

We all know that it's an efficient searching algorithm, but the strategy behind it also applies for narrowing down other problem space, for example, finding out when a bug is first introduced in a series of git commits.

Let's say I have a git repo of 8 commits, the first 5 of which are good, but then the 6th commit introduces a bug, so I have a git commit history looks like below:

 |g|g|g|g|g|b|b|b|
---------------------> the git commit history

So I know that the first commit is good and the last (8th) commit is bad (these are initial problem space), by leveraging the strategy of binary search, it can quickly find out that the 6th commit is the first bad commit. (Check the 4th element first, then the 6th.)

Well, that's basically how git bisect works, and it's more powerful, it can be run with a script to determine if current commit is good or not, saving time to verify it manually.

Recently, I finally managed to use git bisect to find out a recession bug (#1410) of qtile, which reports that qtile-cmd doesn't work anymore which the HEAD commit (0617235c), but it works with tag v0.14.2.

With those in mind, here are the steps to catch the first bad commit:

Start the bisect session: git bisect start 0617235c v0.14.2

$ git bisect start 0617235c v0.14.2
Bisecting: 88 revisions left to test after this (roughly 7 steps)
[082e4c7248ac40b69dbe94cfdc4de6aecc5f74ba] Fix debian version

Make a judge script(attached at the end) and find out the commit by running git bisect run ./scripts/git-bisect-judge

It only takes git 6 steps to find the first broken commit, the output is following with qtile logs being removed:

$ git bisect run ./scripts/git-bisect-judge
running ./scripts/git-bisect-judge
Bisecting: 44 revisions left to test after this (roughly 6 steps)
[fdb3a324aadb0f934080a703d6835a9a7d203720] Delay power renormalization
running ./scripts/git-bisect-judge
...

Bisecting: 21 revisions left to test after this (roughly 5 steps)
[0262fbc2ca23d27fa33c4903d7e8a9b8c14d42eb] Move around modules
running ./scripts/git-bisect-judge
...

Bisecting: 10 revisions left to test after this (roughly 4 steps)
[a3ae3c623859b247813fc1876b188c4d40e84df0] Move calls out of the command graph
running ./scripts/git-bisect-judge
...

Bisecting: 5 revisions left to test after this (roughly 3 steps)
[036dbcb1b7c5c0fff00fbfbb9688597e2d2f188c] Add tests to the command graph
running ./scripts/git-bisect-judge
...

Bisecting: 2 revisions left to test after this (roughly 1 step)
[9c3c78ca66905b4e11bfd7a155cfe883cbe12ad6] Create new command graph
running ./scripts/git-bisect-judge
...

Bisecting: 0 revisions left to test after this (roughly 0 steps)
[ed5eefbf3482481c1f0f4c1cb2eb79e571fec835] Use correct type annotations in IPC module
running ./scripts/git-bisect-judge
...

ed5eefbf3482481c1f0f4c1cb2eb79e571fec835 is the first bad commit
commit ed5eefbf3482481c1f0f4c1cb2eb79e571fec835
Author: Sean Vig <sean.v.775@gmail.com>
Date:   Wed Jun 19 22:33:45 2019 -0400

    Use correct type annotations in IPC module
    
    With python/typeshed#3061 making it into the most recent release of
    mypy, remove the hacks on the type annotations around the marshal
    module.

:040000 040000 d21cc05b503a0f4658647adad3169efbd84eaa16 f80f29304abd86da9299dfaf22f6719698a37e63 M	libqtile
bisect run success

End the session by running git bisect reset, git will restores your previouse HEAD commit.

The judge script git-bisect-judege is as follows:

#!/bin/sh

HERE=$(dirname $(readlink -f $0))
SCREEN_SIZE=${SCREEN_SIZE:-1000x800}
XDISPLAY=${XDISPLAY:-:1}
LOG_LEVEL=${LOG_LEVEL:-DEBUG}
LOG_LEVEL=INFO
if [[ -z $PYTHON ]]; then
    PYTHON=python
fi

./scripts/ffibuild

CLIENT="urxvt"

Xephyr +extension RANDR -screen ${SCREEN_SIZE} ${XDISPLAY} -ac &
XEPHYR_PID=$!
sleep 0.5
source ~/workspace/virtualenv/qtile-devel/bin/activate
env DISPLAY=${XDISPLAY} ${PYTHON} "${HERE}"/../bin/qtile -l ${LOG_LEVEL} $@ &
QTILE_PID=$!

export DISPLAY=${XDISPLAY}
cd ~/workspace/python/qtile
sleep 0.5
./bin/qtile-cmd -o screen -f info
EXIT_CODE=$?

kill -9 $QTILE_PID
kill $XEPHYR_PID

exit $EXIT_CODE

Git troubleshooting

See also