intermediate

Sorting the Input Made the Loop Faster

Read the counters before the options. Nothing here is labelled with the answer.

The report

A colleague claims that sorting our data before the filter loop makes the loop three times faster, even counting the sort. That makes no sense — sorting is strictly more work and the loop does exactly the same comparisons either way. One of us is measuring wrong.

The filter loop, unchanged; only the input order differs

total = 0
for i in 0 .. n-1:
    if data[i] >= threshold:      // ~50% of elements pass
        total += data[i]

CountersSIMULATED

instructions	unsorted 1.00×, sorted 0.97×	Both runs retire essentially the same number of instructions.
cycles	unsorted 3.2× sorted	The unsorted run takes over three times as many cycles for the same instructions.
branch-instructions	identical in both runs	The same number of branches is executed either way.
branch-misses	unsorted 48.7% of branches, sorted 0.1%	Almost half the branches are mispredicted in one run and almost none in the other.
L1-dcache-load-misses	1.9% in both runs	Cache behaviour is the same in both runs.
IPC	unsorted 0.61, sorted 1.98	Per-cycle progress is roughly three times better in the sorted run.

What is the hardware doing?

Branch Prediction: Guessing Well Enough to Matter Misprediction: What a Wrong Guess Costs Branchless Code: A Trade, Not an Upgrade Speculative Execution: Doing Work Before You Know You Need It Control Hazards: The CPU Does Not Know Where You Are Going Pipelining: Throughput Without Making Anything Faster