Sorted vs. shuffled branch benchmark

Measure your machineNeeds C compiler, Python

Problem

A CPU guesses the outcome of every branch and runs ahead on the guess; a wrong guess throws that work away and costs about 10 to 20 cycles. On sorted data a comparison against a threshold gives a long run of one answer, then a long run of the other, and the predictor is almost always right; on shuffled data it is right half the time. The same work then costs several times more. Compilers can remove the branch altogether (a conditional select, or vector instructions), which removes the effect along with the branch.

Sum the elements above a threshold over shuffled data, then sorted data, 20 passes over 16 million values. The work is identical. Compile with -O1, -O2 and -O3, and once more at -O2 with a side effect in the branch that the compiler cannot convert to a select. The script reports whether the generated code contains a conditional select or a vector compare.

The question. How much faster is the sorted pass at each optimization level, and does the compiler leave a branch to mispredict?

Predict

Compiled at -O1, how much faster is the sorted pass than the shuffled one?

Hardly faster (under 1.5×)1.5 to 3×3 to 6×More than 6×

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

sorted-vs-shuffled-branch-benchmark.py63 linesDownload

View the code

sorted-vs-shuffled-branch-benchmark.py

# /// script
# requires-python = ">=3.10"
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Sorted against shuffled: the branch benchmark.

Sums the elements >= 128 of 16 million random bytes-as-ints, 20 times, first
shuffled and then sorted. The work is identical; only the branch's
predictability changes. Compiled at -O1, -O2 and -O3 (where the compiler may
make the loop branchless or vectorize it), and at -O2 with a branch the
compiler cannot remove. Needs cc.
"""
import argparse, json, os, subprocess, tempfile

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--opts", default="-O1,-O2,-O3", help="Optimization levels to compile with.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

C = r"""
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N (1 << 24)
static int data[N];
static int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }
static double run(void) {
    struct timespec a, b; clock_gettime(CLOCK_MONOTONIC, &a);
    long sum = 0;
    for (int rep = 0; rep < 20; rep++)
        for (int i = 0; i < N; i++)
#ifdef FORCE_BRANCH
            if (data[i] >= 128) { sum += data[i]; __asm__ volatile(""); }   /* a side effect the compiler cannot if-convert */
#else
            if (data[i] >= 128) sum += data[i];
#endif
    clock_gettime(CLOCK_MONOTONIC, &b);
    fprintf(stderr, "  sum=%ld\n", sum);                       /* stops the compiler removing the loop */
    return (b.tv_sec - a.tv_sec) + (b.tv_nsec - a.tv_nsec) / 1e9;
}
int main(void) {
    for (int i = 0; i < N; i++) data[i] = rand() % 256;
    double s = run();
    qsort(data, N, sizeof(int), cmp);
    printf("%f %f\n", s, run());
}
"""
d = tempfile.mkdtemp(); src = os.path.join(d, "branch.c"); open(src, "w").write(C); rows = []
builds = [(o, []) for o in args.opts.split(",")] + [("-O2", ["-DFORCE_BRANCH"])]
for opt, extra in builds:
    exe = os.path.join(d, "b" + opt + "".join(extra)); subprocess.run(["cc", opt, *extra, src, "-o", exe], check=True)
    shuffled, sorted_ = map(float, subprocess.run([exe], capture_output=True, text=True, check=True).stdout.split())
    asm = subprocess.run(["cc", opt, *extra, "-S", "-o", "-", src], capture_output=True, text=True).stdout
    branchless = any(x in asm for x in ("csel", "cmov", "cmhs", "cmgt", "vpcmp"))     # select or vector compare: no branch
    rows.append({"opt": opt + (" + forced branch" if extra else ""), "shuffled_s": shuffled, "sorted_s": sorted_, "ratio": shuffled / sorted_,
                 "branchless": "yes" if branchless else "no"})
for r in rows: print(f"{r['opt']}: shuffled {r['shuffled_s']:.2f} s, sorted {r['sorted_s']:.2f} s -> {r['ratio']:.1f}x   (conditional select in the code: {r['branchless']})")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"builds": rows}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.
Terminal
```
uv run sorted-vs-shuffled-branch-benchmark.py
uv run sorted-vs-shuffled-branch-benchmark.py --help     # every knob
```

Knobs
Knob · default	What it changes
--opts-O1, -O2, -O3	Optimization levels to compile with.

Our run

Shuffled against sorted

Shuffled against sorted
Build	Shuffled	Sorted	Ratio	Branch-free code
-O1	122 ms	116 ms	1.06×	yes
-O2	27.5 ms	27 ms	1.02×	yes
-O3	28.4 ms	26.6 ms	1.07×	yes
-O2 + forced branch	1.1 s	110 ms	9.94×	no

Reference runApple M2 · 8 cores · 8 GB

Output · uv run sorted-vs-shuffled-branch-benchmark.py

-O1: shuffled 0.12 s, sorted 0.12 s -> 1.1x   (conditional select in the code: yes)
-O2: shuffled 0.03 s, sorted 0.03 s -> 1.0x   (conditional select in the code: yes)
-O3: shuffled 0.03 s, sorted 0.03 s -> 1.1x   (conditional select in the code: yes)
-O2 + forced branch: shuffled 1.10 s, sorted 0.11 s -> 9.9x   (conditional select in the code: no)

macOS 26.6.2 · Python 3.13.3 · run 2026-10-20

What we found

On this machine (Apple clang, arm64) even -O1 produced branch-free code, and shuffled and sorted ran at the same speed (1.06×); -O2 and -O3 vectorized the loop and were faster still, also with no difference. With a branch the compiler could not remove, shuffled took 1.1 s and sorted 110 ms: 9.94×, above the expected 3–6×.

Read it

Branch misprediction is real and large when there is a branch, and modern compilers remove the simple ones. Whether your code pays it depends on the compiler, the flags and the shape of the loop, so the honest version of the claim is "unpredictable branches that survive compilation are expensive", and the way to know is to check the generated code or measure both orders.