Modern CPUs stall on mispredicted branches, so dropping an 'if' can pay
off. A C loop copying values under 500 into a second array takes 0.345s
with a conditional; storing every value unconditionally and doing smlen +=
(numbers[i] < 500) cuts it to 0.036s on an Apple M1. Disassembly shows why:
the branchy code emits b.gt (or jg on x86), while the branchless version
uses cinc or setle and keeps control flow perfectly linear. Compilers won't
apply this automatically — they can't know the data distribution, and an
unconditional write may run past a buffer. Shrinking the array to 10,000
elements narrows the gap, because the predictor's history tables then learn
the pattern. Quicksort partitioning suits the same trick.
1
u/fagnerbrack 13h ago
For the skim-readers:
Modern CPUs stall on mispredicted branches, so dropping an 'if' can pay off. A C loop copying values under 500 into a second array takes 0.345s with a conditional; storing every value unconditionally and doing smlen += (numbers[i] < 500) cuts it to 0.036s on an Apple M1. Disassembly shows why: the branchy code emits b.gt (or jg on x86), while the branchless version uses cinc or setle and keeps control flow perfectly linear. Compilers won't apply this automatically — they can't know the data distribution, and an unconditional write may run past a buffer. Shrinking the array to 10,000 elements narrows the gap, because the predictor's history tables then learn the pattern. Quicksort partitioning suits the same trick.
If the summary seems inacurate, just downvote and I'll try to delete the comment eventually 👍
Click here for more info, I read all comments