so-branch-prediction-demo
The classic branch prediction demo works in Go 1.26, but with a critical caveat: the Go compiler optimizes simple if statements into branchless CMOV (Conditional Move) instructions, eliminating the branch entirely. To demonstrate the real effect, we must use a //go:noinline function to force a real conditional branch.
Core code (main.go):
//go:noinline
func addIfGe128(sum *int, v int) {
if v >= 128 {
*sum += v
}
}
Without //go:noinline, the compiler emits CMPQ + CMOVG — no branch, no misprediction, no speed difference. With it, we get CMPQ + JLE — a real branch that the CPU must predict.
Benchmark file (branch_test.go) compares five scenarios:
| Benchmark | Data | Implementation | Description |
|---|---|---|---|
BenchmarkUnsorted |
Random | addIfGe128 (real branch) |
Branch predictor sees random pattern → ~50% mispredict |
BenchmarkSorted |
Sorted | addIfGe128 (real branch) |
Clean pattern → ~100% correct prediction |
BenchmarkBranchless |
Random | Bitmask trick (no branch) | Same result, no misprediction cost |
BenchmarkUnsortedInline |
Random | Inline if v >= 128 |
Compiler uses CMOV — no branch |
BenchmarkSortedInline |
Sorted | Inline if v >= 128 |
CMOV — no branch to mispredict |
Results (AMD Ryzen 7 7840HS, Go 1.26):
BenchmarkUnsorted 200 591,102 ns/op ← real branch, random data: SLOW
BenchmarkSorted 200 209,586 ns/op ← real branch, sorted data: 2.8× faster
BenchmarkBranchless 200 67,348 ns/op ← no branch at all
BenchmarkUnsortedInline 200 59,117 ns/op ← CMOV (branchless)
BenchmarkSortedInline 200 76,369 ns/op ← CMOV (branchless)
**How it was verified:** 1. **Assembly verification** — `go tool objdump` confirms the `//go:noinline` function emits a real branch (`JLE`), while the inline version uses `CMOVG` (branchless). ``` // noinline version (real branch): CMPQ BX, $0x7f // compare v with 127 JLE skip // JUMP if v <= 127 — BRANCH PREDICTOR NEEDED! ADDQ BX, (AX) // *sum += v skip: RET // inline version (branchless): CMPQ DI, $0x7f // compare v with 127 CMOVG R8, SI // conditionally move — NO BRANCH ``` 2. **Correctness tests** — All methods produce identical sums regardless of sort order or implementation: - `TestCorrectness`: Random vs sorted vs branchless vs inline — all agree. - `TestEdgeCases`: Empty arrays, nil slices, all-below-threshold, all-above-threshold, single elements — all pass. 3. **Main program** — Running `go run main.go` shows the timing difference live: ``` Unsorted total: 956169900, time: 40.15ms Sorted total: 956169900, time: 16.33ms Speedup factor: 2.46x (sorted is 59.3% faster) ``` **Edge cases tested:** - `nil` and empty slices → sum = 0 - All values below 128 → sum = 0 - All values ≥ 128 → sum = sum of all elements - Single element at threshold (128) → sum = 128 - Single element below threshold (127) → sum = 0 - Branchless bitmask technique produces identical results for all above cases **Why the unsorted/sorted inline benchmarks appear similar:** Modern Go emits `CMOVG` for simple conditional accumulations. `CMOV` is a single fused uop that doesn't involve the branch predictor — both paths are computed and one result is selected. There is **no branch to mispredict**, so data ordering is irrelevant. This is an important lesson in itself: compilers and CPUs are constantly evolving to mitigate branch misprediction! ---
{"model": "gpt-4o", "problem_class": "so-branch-prediction-demo", "result": "passed", "tests": 6}