Hash-Based Bisect Debugging in Compilers and Runtimes
Russ Cox
July 18, 2024
research.swtch.com/bisect

Setting the Stage
Does this sound familar? You make a change to a library to optimize its performance or clean up technical debt or fix a bug, only to get a bug report: somevery large, incomprehensibly opaque test is now failing. Or you add a new compiler optimization with a similar result. Now you have a major debugging job in
an unfamiliar code base.
What if I told you that a magic wand exists that can pinpoint the relevant lineof code or call stack in that unfamiliar code base? It exists. It is a real tool, andI’m going to show it to you. This description might seem a bit over the top, butevery time I use this tool, it really does feel like magic. Not just any magic either, but the best kind of magic: delightful to watch even when you know exactly how it works.

Binary Search and Bisecting Data
Before we get to the new trick, let’s take a look at some simpler, older tricks. Every good magician starts with mastery of the basic techniques. In our case, thattechnique is binary search. Most presentations of binary search talk about finding an item in a sorted list, but there are far more interesting uses. Here is an
example I wrote long ago for Go’s sort.Search documentation:
func GuessingGame() {var s string
fmt.Printf("Pick an integer from 0 to 100.\n")answer := sort.Search(100, func(i int) bool {fmt.Printf("Is your number <= %d? ", i)fmt.Scanf("%s", &s)
return s != "" && s[0] == ’y’})
fmt.Printf("Your number is %d.\n", answer)}
If we run this code, it plays a guessing game with us:% go run guess.go
Pick an integer from 0 to 100.
Is your number <= 50? y
Is your number <= 25? n
Is your number <= 38? y
Is your number <= 32? y
Is your number <= 29? n
Is your number <= 31? n
Your number is 32.
%
The same guessing game can be applied to debugging. In his Programming
Pearls column titled “Aha! Algorithms” in Communications of the ACM (September 1983), Jon Bentley called binary search “a solution that looks for problems.”
Here’s one of his examples:
Roy Weil applied the technique [binary search] in cleaning a deckH-B B D  C  R

of about a thousand punched cards that contained a single badcard. Unfortunately the bad card wasn’t known by sight; it could
only be identified by running some subset of the cards through a
program and seeing a wildly erroneous answer—this process took
several minutes. His predecessors at the task tried to solve it byrunning a few cards at a time through the program, and were making steady (but slow) progress toward a solution. How did Weil findthe culprit in just ten runs of the program?
Obviously, Weil played the guessing game using binary search. Is the bad cardin the first 500? Yes. The first 250? No. And so on. This is the earliest publisheddescription of debugging by binary search that I have been able to find. In thiscase, it was for debugging data.

Bisecting Version History
We can apply binary search to a program’s version history instead of data. Everytime we notice a new bug in an old program, we play the guessing game “whendid this program last work?”– Did it work 50 days ago? Yes.
– Did it work 25 days ago? No.
– Did it work 38 days ago? Yes.
And so on, until we find that the program last worked correctly 32 days ago,meaning the bug was introduced 31 days ago.
Debugging through time with binary search is a very old trick, independently
discovered many times by many people. For example, we could play the guessing game using commands like cvs checkout -D ’31 days ago’ or Plan 9’s
more musical yesterday -n 31. To some programmers, the techniques of using
binary search to debug data or debug through time seem “so basic that there isno need to write them down.” But writing a trick down is the first step to making sure everyone can do it: magic tricks can be basic but not obvious. In software, writing a trick down is also the first step to automating it and building
good tools.
In the late-1990s, the idea of binary search over version history was written
down at least twice. Brian Ness and Viet Ngo published “Regression containment through source change isolation” at COMPSAC ’97 (August 1997) describing a system built at Cray Research that they used to deliver much more frequent non-regressing compiler releases. Independently, Larry McVoy publisheda file “Documentation/BUG-HUNTING” in the Linux 1.3.73 release (March
1996). He captured how magical it feels that the trick works even if you have noparticular expertise in the code being tested:
This is how to track down a bug if you know nothing about kernelhacking. It’s a brute force approach but it works pretty well.
You need:– A reproducible bug - it has to happen predictably (sorry)– All the kernel tar files from a revision that worked to the revision that doesn’t
You will then do:– Rebuild a revision that you believe works, install, and verify
that.



H-B B D  C  R

– Do a binary search over the kernels to figure out which one
introduced the bug. I.e., suppose 1.3.28 didn’t have the bug,
but you know that 1.3.69 does. Pick a kernel in the middle
and build that, like 1.3.50. Build & test; if it works, pick the mid
point between .50 and .69, else the mid point between .28 and.50.
– You’ll narrow it down to the kernel that introduced the bug.
You can probably do better than this but it gets tricky.
...
My apologies to Linus and the other kernel hackers for describing thisbrute force approach, it’s hardly what a kernel hacker would do. However, it does work and it lets non-hackers help bug fix. And it is coolbecause Linux snapshots will let you do this - something that you can’t
do with vender supplied releases.
Later, Larry McVoy created Bitkeeper, which Linux used as its first source
control system. Bitkeeper provided a way to print the longest straight line ofchanges through the directed acyclic graph of commits, providing a more finegrained timeline for binary search. When Linus Torvalds created Git, he carried
that idea forward as git rev-list --bisect, which enabled the same kind of
manual binary search. A few days after adding it, he explained how to use it on
the Linux kernel mailing list:
Hmm.. Since you seem to be a git user, maybe you could try the git"bisect" thing to help narrow down exactly where this happened(and help test that thing too ;).
You can basically use git to find the half-way point between a set of"known good" points and a "known bad" point ("bisecting" the setof commits), and doing just a few of those should give us a muchbetter view of where things started going wrong.
For example, since you know that 2.6.12-rc3 is good, and 2.6.12 isbad, you’d do
git-rev-list --bisect v2.6.12 ^v2.6.12-rc3
where the "v2.6.12 ^v2.6.12-rc3" thing basically means "everythingin v2.6.12 but _not_ in v2.6.12-rc3" (that’s what the ^ marks), andthe "--bisect" flag just asks git-rev-list to list the middle-most commit, rather than all the commits in between those kernel versions.
This response started a separate discussion about making the process easier,which led eventually to the git bisect tool that exists today.
Here’s an example. We tried updating to a newer version of Go and found thata test fails. We can use git bisect to pinpoint the specific commit that caused
the failure:H-B B D  C  R

% git bisect start master go1.21.0
Previous HEAD position was 3b8b550a35 doc: document run..
Switched to branch ’master’Your branch is ahead of ’origin/master’ by 5 commits.
Bisecting: a merge base must be tested[2639a17f146cc7df0778298c6039156d7ca68202] doc: run rel...
% git bisect run sh -c ’
git clean -df
cd src./make.bash || exit 125
cd $HOME/src/rsc.io/tmp/timertest/retry
go list || exit 0
go test -count=5’
It takes some care to write a correct git bisect invocation, but once you get
it right, you can walk away while git bisect works its magic. In this case, thescript we pass to git bisect run cleans out any stale files and then builds the
Go toolchain (./make.bash). If that step fails, it exits with code 125, a special
inconclusive answer for git bisect: something else is wrong with this commit
and we can’t say whether or not the bug we’re looking for is present. Otherwise
it changes into the directory of the failing test. If go list fails, which happens
if the bisect uses a version of Go that’s too old, the script exits successfully, indicating that the bug is not present. Otherwise the script runs go test and exits with the status from that command. The -count=5 is there because this is aflaky failure that does not always happen: running five times is enough to makesure we observe the bug if it is present.
When we run this command, git bisect prints a lot of output, along withthe output of our test script, to make sure we can see the progress:% git bisect run ...
...
go: download go1.23 for darwin/arm64: toolchain not available
Bisecting: 1360 revisions left to test after this (roughly 10 steps)[752379113b7c3e2170f790ec8b26d590defc71d1]
runtime/race: update race syso for PPC64LE...
go: download go1.23 for darwin/arm64: toolchain not available
Bisecting: 680 revisions left to test after this (roughly 9 steps)[ff8a2c0ad982ed96aeac42f0c825219752e5d2f6]
go/types: generate mono.go from types2 source...
okrsc.io/tmp/timertest/retry 10.142s
Bisecting: 340 revisions left to test after this (roughly 8 steps)[97f1b76b4ba3072ab50d0d248fdce56e73b45baf]
runtime: optimize timers.cleanHead...
FAIL
rsc.io/tmp/timertest/retry 22.136s
Bisecting: 169 revisions left to test after this (roughly 7 steps)[80157f4cff014abb418004c0892f4fe48ee8db2e]
io: close PipeReader in test...
ok
rsc.io/tmp/timertest/retry 10.145s
Bisecting: 84 revisions left to test after this (roughly 6 steps)[8f7df2256e271c8d8d170791c6cd90ba9cc69f5e]H-B B D  C  R

internal/asan: match runtime.asan{read,write} len parameter type...
FAIL
rsc.io/tmp/timertest/retry 20.148s
Bisecting: 42 revisions left to test after this (roughly 5 steps)[c9ed561db438ba413ba8cfac0c292a615bda45a8]
debug/elf: avoid using binary.Read() in NewFile()...
FAIL
rsc.io/tmp/timertest/retry 14.146s
Bisecting: 20 revisions left to test after this (roughly 4 steps)[2965dc989530e1f52d80408503be24ad2582871b]
runtime: fix lost sleep causing TestZeroTimer flakes...
FAIL
rsc.io/tmp/timertest/retry 18.152s
Bisecting: 10 revisions left to test after this (roughly 3 steps)[b2e9221089f37400f309637b205f21af7dcb063b]
runtime: fix another lock ordering problem...
ok
rsc.io/tmp/timertest/retry 10.142s
Bisecting: 5 revisions left to test after this (roughly 3 steps)[418e6d559e80e9d53e4a4c94656e8fb4bf72b343]
os,internal/godebugs: add missing IncNonDefault calls...
ok
rsc.io/tmp/timertest/retry 10.163s
Bisecting: 2 revisions left to test after this (roughly 2 steps)[6133c1e4e202af2b2a6d4873d5a28ea3438e5554]
internal/trace/v2: support old trace format...
FAIL
rsc.io/tmp/timertest/retry 22.164s
Bisecting: 0 revisions left to test after this (roughly 1 step)[508bb17edd04479622fad263cd702deac1c49157]
time: garbage collect unstopped Tickers and Timers...
FAIL
rsc.io/tmp/timertest/retry 16.159s
Bisecting: 0 revisions left to test after this (roughly 0 steps)[74a0e3160d969fac27a65cd79a76214f6d1abbf5]
time: clean up benchmarks...
okrsc.io/tmp/timertest/retry 10.147s
508bb17edd04479622fad263cd702deac1c49157 is the first bad commit
commit 508bb17edd04479622fad263cd702deac1c49157
Author:Russ Cox <rsc@golang.org>
AuthorDate: Wed Feb 14 20:36:47 2024 -0500
Commit:Russ Cox <rsc@golang.org>
CommitDate: Wed Mar 13 21:36:04 2024 +0000
time: garbage collect unstopped Tickers and Timers...
This CL adds an undocumented GODEBUG asynctimerchan=1
that will disable the change. The documentation happens in
the CL 568341.
...
bisect found first bad commit%H-B B D  C  R

This bug appears to be caused by my new garbage-collection-friendly timer implementation that will be in Go 1.23. Abracadabra!

A New Trick: Bisecting Program Locations
The culprit commit that git bisect identified is a significant change to thetimer implementation. I anticipated that it might cause subtle test failures, so
I included a GODEBUG setting to toggle between the old implementation andthe new one. Sure enough, toggling it makes the bug disappear:% GODEBUG=asynctimerchan=1 go test -count=5 # oldPASSokrsc.io/tmp/timertest/retry 10.117s% GODEBUG=asynctimerchan=0 go test -count=5 # new--- FAIL: TestDo (4.00s)...
--- FAIL: TestDo (6.00s)...
--- FAIL: TestDo (4.00s)...
FAIL
rsc.io/tmp/timertest/retry 18.133s%
Knowing which commit caused a bug, along with minimal information about
the failure, is often enough to help identify the mistake. But what if it’s not?
What if the test is large and complicated and entirely code you’ve never seen before, and it fails in some inscrutable way that doesn’t seem to have anything to
do with your change? When you work on compilers or low-level libraries, thishappens quite often. For that, we have a new magic trick: bisecting program locations.
That is, we can run binary search on a different axis: over the program’s code,
not its version history. We’ve implemented this search in a new tool unimaginatively named bisect. When applied to library function behavior like the timer
change, bisect can search over all stack traces leading to the new code, enabling the new code for some stacks and disabling it for others. By repeated execution, it can narrow the failure down to enabling the code only for one specific stack:% go install golang.org/x/tools/cmd/bisect@latest% bisect -godebug asynctimerchan=1 go test -count=5...
bisect: FOUND failing change set--- change set #1 (disabling changes causes failure)internal/godebug.(*Setting).Value()/Users/rsc/go/src/internal/godebug/godebug.go:165
time.syncTimer()/Users/rsc/go/src/time/sleep.go:25
time.NewTimer()/Users/rsc/go/src/time/sleep.go:145
time.After()/Users/rsc/go/src/time/sleep.go:203
rsc.io/tmp/timertest/retry.Do()/Users/rsc/src/rsc.io/tmp/timertest/retry/retry.go:37
rsc.io/tmp/timertest/retry.TestDo()/Users/rsc/src/rsc.io/tmp/timertest/retry/retry_test.go:63H-B B D  C  R

Here the bisect tool is reporting that disabling asynctimerchan=1 (that is, enabling the new implementation) only for this one call stack suffices to provoke
the test failure.
One of the hardest things about debugging is running a program backward:
there’s a data structure with a bad value, or the control flow has zigged insteadof zagged, and it’s very difficult to understand how it could have gotten into thatstate. In contrast, this bisect tool is showing the stack at the moment just before
things go wrong: the stack identifies the critical decision point that determines
whether the test passes or fails. In contrast to puzzling backward, it is usuallyeasy to look forward in the program execution to understand why this specificdecision would matter. Also, in an enormous code base, the bisection has identified the specific few lines where we should start debugging. We can read thecode responsible for that specific sequence of calls and look into why the newtimers would change the code’s behavior.
When you are working on a compiler or runtime and cause a test failure in anenormous, unfamiliar code base, and then this bisect tool narrows down thecause to a few specific lines of code, it is truly a magical experience.
The rest of this post explains the inner workings of this bisect tool, which
Keith Randall, David Chase, and I developed and refined over the past decade ofwork on Go. Other people and projects have realized the idea of bisecting program locations too: I am not claiming that we were the first to discover it. However, I think we have developed the approach further and systematized it morethan others. This post documents what we’ve learned, so that others can build
on our efforts rather than rediscover them.

Example: Bisecting Function Optimization
Let’s start with a simple example and work back up to stack traces. Suppose weare working on a compiler and know that a test program fails only when compiled with optimizations enabled. We could make a list of all the functions in the
program and then try disabling optimization of functions one at a time until wefind a minimal set of functions (probably just one) whose optimization triggers
the bug. Unsurprisingly, we can speed up that process using binary search:
1. Change the compiler to print a list of every function it considers for
optimization.
2. Change the compiler to accept a list of functions where optimizationis allowed. Passing it an empty list (optimize no functions) shouldmake the test pass, while passing the complete list (optimize all functions) should make the test fail.
3. Use binary search to determine the shortest list prefix that can bepassed to the compiler to make the test fail. The last function in thatlist prefix is one that must be optimized for the test to fail (but perhaps not the only one).
4. Forcing that function to always be optimized, we can repeat the process to find any other functions that must also be optimized to provoke the bug.
For example, suppose there are ten functions in the program and we run thesethree binary search trials:

H-B B D  C  R

add
cos
div
exp
mod
mul
sin
sqr
sub
tan

add
cos
div
exp
mod
mul
sin
sqr
sub
tan

add
cos
div
exp
mod
mul
sin
sqr
sub
tan

pass

FAIL!

pass

When we optimize the first 5 functions, the test passes. 7? fail. 6? still pass. This
tells us that the seventh function, sin, is one function that must be optimized to
provoke the failure. More precisely, with sin optimized, we know that no functions later in the list need to be optimized, but we don’t know whether any offunctions earlier in the list must also be optimized. To check the earlier locations, we can run another binary search over the other remaining six list entries,
always adding sin as well:
add
cos
div
exp
mod

add
cos
div
exp
mod

sin

sin

cos
sin

FAIL!

pass

FAIL!

add

This time, optimizing the first two (plus the hard-wired sin) fails, but optimizing the first one passes, indicating that cos must also be optimized. Then we
have just one suspect location left: add. A binary search over that one-entry list
(plus the two hard-wired cos and sin) shows that add can be left off the list
without losing the failure.
Now we know the answer: one locally minimal set of functions to optimize
to cause the test failure is cos and sin. By locally minimal, I mean that removing any function from the set makes the test failure disappear: optimizing cos
or sin by itself is not enough. However, the set may still not be globally minimal: perhaps optimizing only tan would cause a different failure (or not).
It might be tempting to run the search more like a traditional binary search,cutting the list being searched in half at each step. That is, after confirming thatthe program passes when optimizing the first half, we might consider discarding that half of the list and continuing the binary search on the other half. Applied to our example, that algorithm would run like this:
add
cos
div
exp
mod
mul
sin
sqr
sub
tan

mul
sin
sqr
sub
tan

sqr
sub
tan

sub
tan

tan
pass

pass
pass

pass

pass

The first trial passing would suggest the incorrect optimization is in the second
half of the list, so we discard the first half. But now cos is never optimized (itjust got discarded), so all future trials pass too, leading to a contradiction: weH-B B D  C  R

lost track of the way to make the program fail. The problem is that discarding
part of the list is only justified if we know that part doesn’t matter. That’s only
true if the bug is caused by optimizing a single function, which may be likely
but is not guaranteed. If the bug only manifests when optimizing multiple functions at once, discarding half the list discards the failure. That’s why the binary
search must in general be over list prefix lengths, not list subsections.

Bisect-Reduce
The “repeated binary search” algorithm we just looked at does work, but theneed for the repetition suggests that binary search may not be the right core algorithm. Here is a more direct algorithm, which I’ll call the “bisect-reduce” algorithm, since it is a bisection-based reduction.
For simplicity, let’s assume we have a global function buggy that reports
whether the bug is triggered when our change is enabled at the given list of locations:// buggy reports whether the bug is triggered// by enabling the change at the listed locations.
func buggy(locations []string) bool
BisectReduce takes a single input list targets for which buggy(targets) istrue and returns a locally minimal subset x for which buggy(x) remains true. It
invokes a more generalized helper bisect, which takes an additional argument:a forced list of locations to keep enabled during the reduction.
// BisectReduce returns a locally minimal subset x of targets// where buggy(x) is true, assuming that buggy(targets) is true.
func BisectReduce(targets []string) []string {return bisect(targets, []string{})}// bisect returns a locally minimal subset x of targets// where buggy(x+forced) is true, assuming that// buggy(targets+forced) is true.
//// Precondition: buggy(targets+forced) = true.
//// Postcondition: buggy(result+forced) = true,// and buggy(x+forced) = false for any x result.
func bisect(targets []string, forced []string) []string {if len(targets) == 0 || buggy(forced) {// Targets are not needed at all.
return []string{}}
if len(targets) == 1 {// Reduced list to a single required entry.
return []string{targets[0]}}// Split targets in half and reduce each side separately.
m := len(targets)/2
left, right := targets[:m], targets[m:]leftReduced := bisect(left, slices.Concat(right, forced))rightReduced := bisect(right, slices.Concat(leftReduced, forced))return slices.Concat(leftReduced, rightReduced)}H-B B D  C  R

Like any good divide-and-conquer algorithm, a few lines do quite a lot:
– If the target list has been reduced to nothing, or if buggy(forced)(without any targets) is true, then we can return an empty list. Otherwise we know something from targets is needed.
– If the target list is a single entry, that entry is what’s needed: we canreturn a single-element list.
– Otherwise, the recursive case: split the target list in half and reduceeach side separately. Note that it is important to force leftReduced(not left) while reducing right.
Applied to the function optimization example, BisectReduce would end up ata call tobisect([add cos div exp mod mul sin sqr sub tan], [])which would split the targets list intoleft = [add cos div exp mod]right = [mul sin sqr sub tan]
The recursive calls compute:bisect([add cos div exp mod], [mul sin sqr sub tan]) = [cos]bisect([mul sin sqr sub tan], [cos]) = [sin]Then the return puts the two halves together: [cos sin].
The version of BisectReduce we have been considering is the shortest one I
know; let’s call it the “short algorithm”. A longer version handles the “easy” caseof the bug being contained in one half before the “hard” one of needing partsof both halves. Let’s call it the “easy/hard algorithm”:// BisectReduce returns a locally minimal subset x of targets// where buggy(x) is true, assuming that buggy(targets) is true.
func BisectReduce(targets []string) []string {if len(targets) == 0 || buggy(nil) {return nil}
return bisect(targets, []string{})}// bisect returns a locally minimal subset x of targets// where buggy(x+forced) is true, assuming that// buggy(targets+forced) is true.
//// Precondition: buggy(targets+forced) = true,// and buggy(forced) = false.
//// Postcondition: buggy(result+forced) = true,// and buggy(x+forced) = false for any x result.
// Also, if there are any valid single-element results,// then bisect returns one of them.
func bisect(targets []string, forced []string) []string {if len(targets) == 1 {// Reduced list to a single required entry.
return []string{targets[0]}}H-B B D  C  R

// Split targets in half.
m := len(targets)/2
left, right := targets[:m], targets[m:]// If either half is sufficient by itself, focus there.
if buggy(slices.Concat(left, forced)) {return bisect(left, forced)}
if buggy(slices.Concat(right, forced)) {return bisect(right, forced)}// Otherwise need parts of both halves.
leftReduced := bisect(left, slices.Concat(right, forced))rightReduced := bisect(right, slices.Concat(leftReduced, forced))return slices.Concat(leftReduced, rightReduced)}
The easy/hard algorithm has two benefits and one drawback compared to theshort algorithm.
One benefit is that the easy/hard algorithm more directly maps to our intuitions about what bisecting should do: try one side, try the other, fall back tosome combination of both sides. In contrast, the short algorithm always relieson the general case and is harder to understand.
Another benefit of the easy/hard algorithm is that it guarantees to find a single-culprit answer when one exists. Since most bugs can be reduced to a single culprit, guaranteeing to find one when one exists makes for easier debugging sessions. Supposing that optimizing tan would have triggered the test failure, the easy/hard algorithm would try
buggy([add cos div exp mod]) = false // left
buggy([mul sin sqr sub tan]) = true // rightand then would discard the left side, focusing on the right side and eventuallyfinding [tan], instead of [sin cos].
The drawback is that because the easy/hard algorithm doesn’t often rely on
the general case, the general case needs more careful testing and is easier to
get wrong without noticing. For example, Andreas Zeller’s 1999 paper “Yesterday, my program worked. Today, it does not. Why?” gives what should be theeasy/hard version of the bisect-reduce algorithm as a way to bisect over independent program changes, except that the algorithm has a bug: in the “hard”
case, the right bisection forces left instead of leftReduced. The result is that
if there are two culprit pairs crossing the left/right boundary, the reductions
can choose one culprit from each pair instead of a matched pair. Simple test cases are all handled by the easy case, masking the bug. In contrast, if we insert thesame bug into the general case of the short algorithm, very simple test cases fail.
Real implementations are better served by the easy/hard algorithm, but theymust take care to implement it correctly.

List-Based Bisect-Reduce
Having established the algorithm, let’s now turn to the details of hooking it up
to a compiler. Exactly how do we obtain the list of source locations, and how
do we feed it back into the compiler?
The most direct answer is to implement one debug mode that prints
the full list of locations for the optimization in question and another debug mode that accepts a list indicating where the optimization is permitted.
H-B B D  C  R

Meta’s Cinder JIT for Python, published in 2021, takes this approach for deciding which functions to compile with the JIT (as opposed to interpret). Its
Tools/scripts/jitlist_bisect.py is the earliest correct published versionof the bisect-reduce algorithm that I’m aware of, using the easy/hard form.
The only downside to this approach is the potential size of the lists, especially since bisect debugging is critical for reducing failures in very large programs.
If there is some way to reduce the amount of data that must be sent back to thecompiler on each iteration, that would be helpful. In complex build systems, thefunction lists may be too large to pass on the command line or in an environment variable, and it may be difficult or even impossible to arrange for a new input file to be passed to every compiler invocation. An approach that can specify
the target list as a short command line argument will be easier to use in practice.

Counter-Based Bisect-ReduceJava’s HotSpot C2 just-in-time (JIT) compiler provided a debug mechanism tocontrol which functions to compile with the JIT, but instead of using an explicit list of functions like in Cinder, HotSpot numbered the functions as it considered them. The compiler flags -XX:CIStart and -XX:CIStop set the range offunction numbers that were eligible to be compiled. Those flags are still present
today (in debug builds), and you can find uses of them in Java bug reports dating back at least to early 2000.
There are at least two limitations to numbering functions.
The first limitation is minor and easily fixed: allowing only a single contiguous range enables binary search for a single culprit but not the general bisectreduce for multiple culprits. To enable bisect-reduce, it would suffice to accept
a list of integer ranges, like -XX:CIAllow=1-5,7-10,12,15.
The second limitation is more serious: it can be difficult to keep the numbering stable from run to run. Implementation strategies like compiling functions in parallel might mean considering functions in varying orders based on
thread interleaving. In the context of a JIT, even threaded runtime execution
might change the order that functions are considered for compilation. Twentyfive years ago, threads were rarely used and this limitation may not have beenmuch of a problem. Today, assuming a consistent function numbering is a showstopper.

Hash-Based Bisect-Reduce
A different way to keep the location list implicit is to hash each location to a(random-looking) integer and then use bit suffixes to identify sets of locations.
The hash computation does not depend on the sequence in which the source locations are encountered, making hashing compatible with parallel compilation,
thread interleaving, and so on. The hashes effectively arrange the functions intoa binary tree:H-B B D  C  R

H=*
H=*0

H=*1

H=*00

H=*10

H=*000

H=*010

H=*0000

H=*0010

H=*01
H=*001

H=*101

H=*1010

H=*11
H=*011
H=*0011

H=*111

H=*1011

H=*0111
H=*00111

H=*00000 H=*10000

H=*000111
H=*1000111
H=*01000111 H=*11000111
sub
cos
add
div
tan
mod
mul
exp
sqr
sin
01000000 00010000 00110010 00101010 10010001 10100101 01010011 11111011 01000111 11000111

Looking for a single culprit is a basic walk down the tree. Even better, the general bisect-reduce algorithm is easily adapted to hash suffix patterns. First we haveto adjust the definition of buggy: we need it to tell us the number of matches
for the suffix we are considering, so we know whether we can stop reducing thecase:// buggy reports whether the bug is triggered// by enabling the change at the locations with// hashes ending in suffix or any of the extra suffixes.
// It also returns the number of locations found that// end in suffix (only suffix, ignoring extra).
func buggy(suffix string, extra []string) (fail bool, n int)
Now we can translate the easy/hard algorithm more or less directly:// BisectReduce returns a locally minimal list of hash suffixes,// each of which uniquely identifies a single location hash,// such that buggy(list) is true.
func BisectReduce() []string {if fail, _ := buggy("none", nil); fail {return nil}
return bisect("", []string{})}// bisect returns a locally minimal list of hash suffixes,// each of which uniquely identifies a single location hash,// and all of which end in suffix,// such that buggy(result+forced) = true.
//// Precondition: buggy(suffix, forced) = true, _.
// and buggy("none", forced) = false, 0.
//// Postcondition: buggy("none", result+forced) = true, 0;// each suffix in result matches a single location hash;// and buggy("none", x+forced) = false for any x result.
// Also, if there are any valid single-element results,// then bisect returns one of them.
H-B B D  C  R

func bisect(suffix string, forced []string) []string {if _, n := buggy(suffix, forced); n == 1 {// Suffix identifies a single location.
return []string{suffix}}// If either of 0suffix or 1suffix is sufficient// by itself, focus there.
if fail, _ := buggy("0"+suffix, forced); fail {return bisect("0"+suffix, forced)}
if fail, _ := buggy("1"+suffix, forced); fail {return bisect("1"+suffix, forced)}// Matches from both extensions are needed.
// Otherwise need parts of both halves.
leftReduced := bisect("0"+suffix,
slices.Concat([]string{"1"+suffix"}, forced))rightReduced := bisect("1"+suffix,
slices.Concat(leftReduced, forced))return slices.Concat(leftReduce, rightReduce)}
Careful readers might note that in the easy cases, the recursive call to bisect
starts by repeating the same call to buggy that the caller did, this time to countthe number of matches for the suffix in question. An efficient implementation
could pass the result of that run to the recursive call, avoiding redundant trials.
In this version, bisect does not guarantee to cut the search space in half at
each level of the recursion. Instead, the randomness of the hashes means that it
cuts the search space roughly in half on average. That’s still enough for logarithmic behavior when there are just a few culprits. The algorithm would also work
correctly if the suffixes were applied to match a consistent sequential numbering instead of hashes; the only problem is obtaining the numbering.
The hash suffixes are about as short as the function number ranges and easily
passed on the command line. For example, a hypothetical Java compiler could
use -XX:CIAllowHash=000,10,111.

Use Case: Function Selection
The earliest use of hash-based bisect-reduce in Go was for selecting functions, asin the example we’ve been considering. In 2015, Keith Randall was working on
a new SSA backend for the Go compiler. The old and new backends coexisted,
and the compiler could use either for any given function in the program being
compiled. Keith introduced an environment variable GOSSAHASH that specified the last few binary digits of the hash of function names that should use thenew backend: GOSSAHASH=0110 meant “compile only those functions whosenames hash to a value with last four bits 0110.” When a test was failing with
the new backend, a person debugging the test case tried GOSSAHASH=0 and
GOSSAHASH=1 and then used binary search to progressively refine the pattern, narrowing the failure down until only a single function was being compiled
with the new backend. This was invaluable for approaching failures in large real-world tests (tests for libraries or production code, not for the compiler) that
we had not written and did not understand. The approach assumed that the failure could always be reduced to a single culprit function.
It is fascinating that HotSpot, Cinder, and Go all hit upon the idea of binaryH-B B D  C  R

search to find miscompiled functions in a compiler, and yet all three used different selection mechanisms (counters, function lists, and hashes).

Use Case: SSA Rewrite Selection
In late 2016, David Chase was debugging a new optimizer rewrite rule thatshould have been correct but was causing mysterious test failures. He reused thesame technique but at finer granularity: the bit pattern now controlled whichfunctions that rewrite rule could be used in.
David also wrote the initial version of a tool, gossahash, for taking on thejob of binary search. Although gossahash only looked for a single failure, but
it was remarkably helpful. It served for many years and eventually became bisect.

Use Case: Fused Multiply-Add
Having a tool available, instead of needing to bisect manually, made us keep
finding problems we could solve. In 2022, another presented itself. We had updated the Go compiler to use floating-point fused multiply-add (FMA) instructions on a new architecture, and some tests were failing. By making the FMA
rewrite conditional on a suffix of a hash that included the current file name andline number, we could apply bisect-reduce to identify the specific line in thesource code where FMA instruction broke the test.
For example, this bisection finds that b.go:7 is the culprit line:
a.go:9a.go:15
a.go:16
a.go:21b.go:7b.go:9b.go:11c.go:23c.go:29

a.go:9a.go:15
a.go:16
a.go:21b.go:7b.go:9b.go:11c.go:23c.go:29

a.go:9a.go:15
a.go:16
a.go:21b.go:7b.go:9b.go:11c.go:23c.go:29

pass

FAIL!

FAIL!

FMA is not something most programmers encounter. If they do get an FMAinduced test failure, having a tool that automatically identifies the exact culprit
line is invaluable.

Use Case: Language Changes
The next problem that presented itself was a language change. Go, like C# and
JavaScript, learned the hard way that loop-scoped loop variables don’t mix wellwith closures and concurrency. Like those languages, Go recently changed to iteration-scoped loop variables, correcting many buggy programs in the process.
Unfortunately, sometimes tests unintentionally check for buggy behavior. Deploying the loop change in a large code base, we confronted truly mysterious
failures in complex, unfamiliar code. Conditioning the loop change on a suffix
of a hash of the source file name and line number enabled bisect-reduce to pinpoint the specific loop or loops that triggered the test failures. We even founda few cases where changing any one loop did not cause a failure, but changing
a specific pair of loops did. The generality of finding multiple culprits is necessary in practice.
The loop change would have been far more difficult without automated diagnosis.

H-B B D  C  R

Use Case: Library Changes
Bisect-reduce also applies to library changes: we can hash the caller, or more
precisely the call stack, and then choose between the old and new implementation based on a hash suffix.
For example, suppose you add a new sort implementation and a large program fails. Assuming the sort is correct, the problem is almost certainly thatthe new sort and the old sort disagree about the final order of some values thatcompare equal. Or maybe the sort is buggy. Either way, the large program probably calls sort in many different places. Running bisect-reduce over hashes of thecall stacks will identify the exact call stack where using the new sort causes a
failure. This is what was happening in the example at the start of the post, witha new timer implementation instead of a new sort.
Call stacks are a use case that only works with hashing, not with sequential
numbering. For the examples up to this point, a setup pass could number all thefunctions in a program or number all the source lines presented to the compiler, and then bisect-reduce could apply to binary suffixes of the sequence number. But there is no dense sequential numbering of all the possible call stacks aprogram will encounter. On the other hand, hashing a list of program counters
is trivial.
We realized that bisect-reduce would apply to library changes around thetime we were introducing the GODEBUG mechanism, which provides a framework for tracking and toggling these kinds of compatible-but-breaking changes.
We arranged for that framework to provide bisect support for all GODEBUG
settings automatically.
For Go 1.23, we rewrote the time.Timer implementation and changed its semantics slightly, to remove some races in existing APIs and also enable earlier
garbage collection in some common cases. One effect of the new implementation is that very short timers trigger more reliably. Before, a 0ns or 1ns timer(which are often used in tests) could take many microseconds to trigger. Now,
they trigger on time. But of course, buggy code (mostly in tests) exists that fails
when the timers start triggering as early as they should. We debugged a dozen
or so of these inside Google’s source tree—all of them complex and unfamiliar—and bisect made the process painless and maybe even fun.
For one failing test case, I made a mistake. The test looked simple enoughto eyeball, so I spent half an hour puzzling through how the only timer in thecode under test, a hard-coded one minute timer, could possibly be affected by
the new implementation. Eventually I gave up and ran bisect. The stack trace
showed immediately that there was a testing middleware layer that was rewriting the one-minute timeout into a 1ns timeout to speed the test. Tools see what
people cannot.

Interesting Lessons Learned
One interesting thing we learned while working on bisect is that it is important to try to detect flaky tests. Early in debugging loop change failures, bisect
pointed at a completely correct, trivial loop in a cryptography package. At first,
we were very scared: if that loop was changing behavior, something would haveto be very wrong in the compiler. We realized the problem was flaky tests. A test
that fails randomly causes bisect to make a random walk over the source code,
eventually pointing a finger at entirely innocent code. After that, we added a count=N flag to bisect that causes it to run every trial N times and bail out
entirely if they disagree. We set the default to -count=2 so that bisect always
does basic flakiness checking.
Flaky tests remain an area that needs more work. If the problem being deH-B B D  C  R

bugged is that a test went from passing reliably to failing half the time, runninggo test -count=5 increases the chance of failure by running the test five times.
Equivalently, it can help to use a tiny shell script like% cat bin/allpass#!/bin/sh
n=$1
shift
for i in $(seq $n); do"$@" || exit 1
done
Then bisect can be invoked as:% bisect -godebug=timer allpass 5 ./flakytest
Now bisect only sees ./flakytest passing five times in a row as a successfulrun.
Similarly, if a test goes from passing unreliably to failing all the time, an anypass variant works instead:% cat bin/anypass#!/bin/sh
n=$1
shift
for i in $(seq $n); do"$@" && exit 0
done
exit 1
The timeout command is also useful if the change has made a test run forever instead of failing.
The tool-based approach to handling flakiness works decently but does notseem like a complete solution. A more principled approach inside bisect would
be better. We are still working out what that would be.
Another interesting thing we learned is that when bisecting over run-timechanges, hash decisions are made so frequently that it is too expensive to print
the full stack trace of every decision made at every stage of the bisect-reduce,(The first run uses an empty suffix that matches every hash!) Instead, bisect hashpatterns default to a “quiet” mode where each decision prints only the hash bits,
since that’s all bisect needs to guide the search and narrow down the relevant
stacks. Once bisect has identified a minimal set of relevant stacks, it runs thetest once more with the hash pattern in “verbose” mode. That causes the bisectlibrary to print both the hash bits and the corresponding stack traces, and bisect displays those stack traces in its report.

Try Bisect
The bisect tool can be downloaded and used today:% go install golang.org/x/tools/cmd/bisect@latest
If you are debugging a loop variable problem in Go 1.22, you can use a command like% bisect -compile=loopvar go test
If you are debugging a timer problem in Go 1.23, you can use:H-B B D  C  R

% bisect -godebug asynctimerchan=1 go test
The -compile and -godebug flags are conveniences. The general form of thecommand is% bisect [KEY=value...] cmd [args...]where the leading KEY=value arguments set environment variables before invoking the command with the remaining arguments. Bisect expects to findthe literal string PATTERN somewhere on its command line, and it replaces thatstring with a hash pattern each time it repeats the command.
You can use bisect to debug problems in your own compilers or libraries by
having them accept a hash pattern either in the environment or on the command line and then print specially formatted lines for bisect on standard output or standard error. The easiest way to do this is to use the bisect package.
That package is not available for direct import yet (there is a pending proposal
to add it to the Go standard library), but the package is only a single file withno imports, so it is easily copied into new projects or even translated to otherlanguages. The package documentation also documents the hash pattern syntax
and required output format.
If you work on compilers or libraries and ever need to debug why a seemingly correct change you made broke a complex program, give bisect a try. It never stops feeling like magic.

