Comment by globular-toast
14 hours ago
I was thinking that... When they say "modern CPUs", surely that includes any pipelined CPU? Maybe Pentium 4 era long pipelines in particular. But actual modern CPUs are much better at branch prediction.
But for something like sorting wouldn't the worst case be completely random data which would defeat any kind of branch prediction?
Branch prediction is indeed necessary for any pipelined CPU. It does not matter whether the CPU also has other more modern features, like being superscalar, having out-of-order execution, etc.
That is why the simplest kind of branch prediction, i.e. static branch prediction, had already been implemented in an early pipelined computer, the IBM Stretch, which was designed around 1959/1960, so it is hardly a "modern" computer.
When the result of a comparison is random, which happens frequently in certain kinds of sorting or searching applications, as you say, that defeats any kind of branch prediction.