Bounds Check Elimination in Go and When It Pays Off

Go checks every slice index. If i is not below len(a), a[i] panics instead of reading past the end, which is the main reason Go programs do not have buffer overflows. The check costs a comparison and a branch, and for years the folklore has been that this adds up in tight loops, so performance guides teach tricks to remove the checks. The compiler removes many of them itself, with a pass called bounds check elimination (BCE). This article asks the compiler which checks it kept, applies the two classic hints that remove them, and then measures whether it mattered. On this machine, it did not.

It belongs with inlining and escape analysis as the third compiler topic in the performance cluster. The practical conclusion matters for how you spend your time: check the benchmarking article before bending code into shapes the compiler likes. The cornerstone is the Go performance guide.

Asking the compiler

The compiler can print every bounds check it left in the generated code:

go build -gcflags='-d=ssa/check_bce/debug=1'

Each line reads Found IsInBounds (an index check) or Found IsSliceInBounds (a slice expression check), with the file and line. A line that does not appear is a check the compiler proved unnecessary. The lab compiles eight small functions and counts the findings per source line.

The functions

package main

import "encoding/binary"

// checkedLoop: the compiler cannot prove i is in range of b when it indexes b with an index taken from a.
func sumPairs(a, b []int) int {
	s := 0
	for i := range a {
		s += a[i] * b[i]
	}
	return s
}

// hinted: one reslice up front proves the length, and the checks inside disappear.
func sumPairsHinted(a, b []int) int {
	b = b[:len(a)]
	s := 0
	for i := range a {
		s += a[i] * b[i]
	}
	return s
}

// plain: indexing with the loop variable of the same slice needs no check.
func sum(a []int) int {
	s := 0
	for i := 0; i < len(a); i++ {
		s += a[i]
	}
	return s
}

// load32 reads four bytes the long way: each index is checked.
func load32(b []byte) uint32 {
	return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
}

// load32Hinted asserts the highest index first, one check instead of four.
func load32Hinted(b []byte) uint32 {
	_ = b[3]
	return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
}

// load32Std uses the library, which does the same hint inside.
func load32Std(b []byte) uint32 { return binary.LittleEndian.Uint32(b) }

// strided: indexing ahead of the loop variable needs a check per access.
func diffs(a []int) int {
	s := 0
	for i := 0; i < len(a)-1; i++ {
		s += a[i+1] - a[i]
	}
	return s
}

func diffsWindow(a []int) int {
	s := 0
	for i := 1; i < len(a); i++ {
		s += a[i] - a[i-1]
	}
	return s
}

package main

import (
	"fmt"
	"testing"
)

var x uint64

func main() {
	a := make([]int, 4096)
	b := make([]int, 4096)
	for i := range a {
		a[i], b[i] = i, i+1
	}
	buf := make([]byte, 4096+8)
	for i := range buf {
		buf[i] = byte(i)
	}
	cases := []struct {
		name string
		f    func(*testing.B)
	}{
		{"sumPairs", func(t *testing.B) {
			for t.Loop() {
				x += uint64(sumPairs(a, b))
			}
		}},
		{"sumPairsHinted", func(t *testing.B) {
			for t.Loop() {
				x += uint64(sumPairsHinted(a, b))
			}
		}},
		{"sum (one slice)", func(t *testing.B) {
			for t.Loop() {
				x += uint64(sum(a))
			}
		}},
		{"diffs, a[i+1] - a[i]", func(t *testing.B) {
			for t.Loop() {
				x += uint64(diffs(a))
			}
		}},
		{"diffsWindow, a[i] - a[i-1]", func(t *testing.B) {
			for t.Loop() {
				x += uint64(diffsWindow(a))
			}
		}},
		{"load32 over 4096 offsets", func(t *testing.B) {
			for t.Loop() {
				for i := 0; i < 4096; i++ {
					x += uint64(load32(buf[i:]))
				}
			}
		}},
		{"load32Hinted", func(t *testing.B) {
			for t.Loop() {
				for i := 0; i < 4096; i++ {
					x += uint64(load32Hinted(buf[i:]))
				}
			}
		}},
		{"load32Std (binary.LittleEndian)", func(t *testing.B) {
			for t.Loop() {
				for i := 0; i < 4096; i++ {
					x += uint64(load32Std(buf[i:]))
				}
			}
		}},
	}
	for _, c := range cases {
		bench(c.name, c.f)
	}
	fmt.Println(x != 0)
}

package main

import (
	"flag"
	"fmt"
	"sort"
	"testing"
)

func init() {
	testing.Init()
	flag.Set("test.benchtime", "200ms")
}

// bench runs f five times and prints the median, which damps the noise of a laptop.
func bench(name string, f func(b *testing.B)) {
	const runs = 5
	ns := make([]float64, 0, runs)
	bs := make([]int64, 0, runs)
	as := make([]int64, 0, runs)
	for i := 0; i < runs; i++ {
		r := testing.Benchmark(f)
		ns = append(ns, float64(r.T.Nanoseconds())/float64(r.N))
		bs = append(bs, r.AllocedBytesPerOp())
		as = append(as, r.AllocsPerOp())
	}
	sort.Float64s(ns)
	sort.Slice(bs, func(i, j int) bool { return bs[i] < bs[j] })
	sort.Slice(as, func(i, j int) bool { return as[i] < as[j] })
	fmt.Printf("%-38s %12.1f ns/op %9d B/op %6d allocs/op\n", name, ns[runs/2], bs[runs/2], as[runs/2])
}

set -e
echo "== bounds checks the compiler kept, by function (go build -gcflags=-d=ssa/check_bce/debug=1)"
go build -gcflags='-d=ssa/check_bce/debug=1' -o /dev/null . 2>&1 | grep -E 'access.go' | sed -E 's/^\.\/access.go:([0-9]+):[0-9]+: /line \1: /' | sort -t' ' -k2 -n | uniq -c
echo
echo "== what it costs (4096 elements per call, or 4096 reads)"
go run .

== bounds checks the compiler kept, by function (go build -gcflags=-d=ssa/check_bce/debug=1)
   1 line 9: Found IsInBounds
   1 line 16: Found IsSliceInBounds
   4 line 35: Found IsInBounds
   1 line 40: Found IsInBounds
   1 line 45: Found IsInBounds
   1 line 51: Found IsInBounds

== what it costs (4096 elements per call, or 4096 reads)
sumPairs                                     1315.3 ns/op         0 B/op      0 allocs/op
sumPairsHinted                               1296.5 ns/op         0 B/op      0 allocs/op
sum (one slice)                              1295.6 ns/op         0 B/op      0 allocs/op
diffs, a[i+1] - a[i]                         1788.4 ns/op         0 B/op      0 allocs/op
diffsWindow, a[i] - a[i-1]                   1988.8 ns/op         0 B/op      0 allocs/op
load32 over 4096 offsets                     8718.5 ns/op         0 B/op      0 allocs/op
load32Hinted                                 8854.7 ns/op         0 B/op      0 allocs/op
load32Std (binary.LittleEndian)              8711.7 ns/op         0 B/op      0 allocs/op
true

What the compiler kept

The output, by line:

• line 9, sumPairs: 1 IsInBounds (for b[i]).
• line 16, sumPairsHinted: 1 IsSliceInBounds, the b = b[:len(a)]. Nothing inside the loop.
• sum: none.
• line 35, load32: 4 IsInBounds, one per byte read.
• line 40, load32Hinted: 1, the _ = b[3].
• line 45, diffs: 1 (a[i+1]).
• line 51, diffsWindow: 1 (a[i-1]).

Each is a pattern worth recognising.

The loop variable of the same slice is free. In sum, for i := 0; i < len(a); i++ { s += a[i] } has no checks: the loop condition is the proof. So does for i := range a. In sumPairs, a[i] is free for the same reason, but b[i] is not: nothing tells the compiler that b is as long as a.

A reslice hint moves the check out of the loop. b = b[:len(a)] asserts the length once. After it, the compiler knows len(b) == len(a), and b[i] is provably in range for every i in range a. The one check that remains runs once per call and not once per element. This is the trick the standard library uses in hot loops over two slices.

An index hint collapses several checks into one. load32 reads b[0] to b[3] and each is checked, since the compiler checks them in source order. In load32Hinted, _ = b[3] comes first. If it passes, all four lower indexes are known to be in range, and the later checks vanish. binary.LittleEndian.Uint32 does exactly this inside, so load32Std has one check as well.

Offsets from the loop variable need the right shape. a[i+1] in a loop that runs to len(a)-1 keeps its check in this compiler version, because proving that i+1 < len(a) from i < len(a)-1 involves arithmetic the prover does not always do. Rewritten as diffsWindow, for i := 1; i < len(a); i++ { a[i] - a[i-1] }, the check on a[i-1] was still kept. The compiler improves in this area with every release, so a hint that was needed in Go 1.15 may be redundant now and one that is missing may arrive. Always look at the current output.

What it cost

Reading across: sumPairs with one check per element took 1315 ns, sumPairsHinted took 1297 and the single slice sum took 1296. The check cost 18 ns over 4096 elements, 0.0045 ns each. That is below the noise of the measurement. Likewise load32 with four checks per read took 8718 ns against 8855 for the hinted version with one check, and the hinted version was slightly slower (1.6 percent), well within the run to run variation. diffs and diffsWindow differ from each other (1788 and 1989 ns) for reasons unrelated to bounds checks: they differ in how the loop and the subtraction are scheduled.

The explanation is branch prediction. A bounds check is a comparison and a branch that is never taken in correct code. A modern processor predicts it perfectly and executes the comparison in parallel with the surrounding arithmetic, so it consumes an issue slot that was probably idle. On an Apple M1 Max, with its wide pipeline, it is invisible. On a narrower core, or in a loop that already saturates the execution units (vectorisable numeric kernels, hash functions, compression), the effect can be real, which is why the standard library applies these hints in such code.

When to bother

• Never first. Profile (the CPU profile article) and find that a specific loop is hot before considering it.
• For tight kernels over byte slices and numeric arrays that really are the program's cost: parsers, codecs, checksums, hash functions. The standard library does it there, and you can copy its patterns.
• When the hint is free. _ = b[3] before reading four bytes costs a line, documents the length requirement and is clear to a reader. A reslice before a two slice loop is also cheap and clear. Use hints that make the code more explicit; avoid ones that make it less.
• Never with unsafe to skip the checks. You lose the panic that stops a bug becoming memory corruption, for a gain this lab could not measure.

If you do change a loop for BCE, verify twice: the compiler output must show the check is gone, and a benchmark must show a difference outside the noise. Without the second, you have made the code stranger for nothing.

Checklist

• go build -gcflags=-d=ssa/check_bce/debug=1 lists the checks the compiler kept.
• Loop over the slice you index; reslice the other to its length; put _ = b[n] before fixed width reads.
• Re-check on each Go upgrade; the prover keeps improving.
• Benchmark before and after. A check removed is not a speedup until measured.
• Prefer clear code over compiler shaped code unless the loop is the profile's top entry.

The details are in the Go compiler's prove pass and the standard library's encoding/binary package.