3 ms·
Modern processors have at least a dozen pipeline stages. In this case, every other instruction is a branch and they are completely unpredictable so it's possibl
by xigency 9y ago
Modern processors have at least a dozen pipeline stages. In this case, every other instruction is a branch and they are completely unpredictable so it's possible to see a 12.0 x 0.50 x 0.50 or 3x slowdown. If you can sort or partition the data in effectively 2N time for the size, then you can beat the misprediction.
The important thing is to be keenly aware that this is how a processor works. Branch predictors take up a big chunk of silicon on the CPU and keep very complicated histories, and in certain cases the compiler can outsmart some bad code, but in general it's way too easy to make this kind of mistake.
- Veedrac 9y ago> 12.0 x 0.50 x 0.50 I assume this means "12 cycles delay × 50% instructions can miss × 50% miss rate". But that's not really right; you're comparing against an IPC of 1 sans misprediction, with each instruction latency-1 and all of them dependent on the prior. Less importantly, you're assuming 50% of the instruction are branches, where it's really more like 25% since you have the load and add as well. Your mispredict penalty also seems a tad small. A not-horrific compiler and a fast CPU should do far better than that, with peak IPC of just under 4 (since theoretical peak is 4 and there's generally a little overhead). Mispredicts linearize the graph, reducing IPC to some fraction, which you can guess is a bit over 1/2, since you average ~2 loops of 4 instructions per mispredict. This means you've got a reduction of slightly less than 8x.