2 ms·

Since this is the third recent item on HN featuring the impact of branch prediction on code performance, let's make sure we keep our heads on straight: a good a

Since this is the third recent item on HN featuring the impact of branch prediction on code performance, let's make sure we keep our heads on straight: a good algorithm will outperform a bad algorithm that's tuned for branch prediction. Quicksort infamously abuses branch prediction, yet is still the standard against which all other sorting algorithms are compared. Some work is being done to improve Quicksort's branch prediction performance [1], but that's mostly focusing on choosing better pivots. A perfect sorting algorithm, something like a very large sorting network, will necessarily make any processor's branch predictor give up and go home -- and that'll still be faster to execute than a naive algorithm tuned for branch prediction. [1]: http://www.cs.auckland.ac.nz/~mcw/Teaching/refs/sorting/quicksort-branch-prediction.pdf http://www.cs.auckland.ac.nz/~mcw/Teaching/refs/sorting/quic...

martincmartin 14y ago
On the other hand, quicksort scans memory in-order. Random access to memory is much, much worse than bad branch prediction. Using a heap in merge sort, for example, screws with both branch prediction and memory access. For sorting, if you're minimizing the number of comparisons, the result of each compare should be random and independent of all others. So the only way to have "good" branch prediction when sorting an array of random numbers is to do lots of extra, superfluous compares, e.g. using an O(n^2) algorithm instead of an O(n log n) one. The base case for std::sort in glibc is insertion sort. It's used for less than 6 elements. Nice and linear memory access patterns. Martin
nicknash 14y ago
Agreed. The post wasn't meant to suggest anybody should go and optimize! Just that simple looking code can be tricky/interesting. Also, even artificially skewing the pivot in quicksort as suggested in the paper you reference doesn't work except on /very/ long pipeline machines, because it worsens cache performance & increases instruction count. Also, even then, it's expensive to randomly sample to generate a skewed pivot (a cost they negelect in that paper, assuming it is free)
hristov 14y ago
I think it may actually be provable that as a sorting algorithm gets more efficient, the branches of that algorithm will get harder to predict. When you think about it, an efficient comparison is one in which each result is equally likely, and that is difficult to branch predict.

martincmartin 14y ago

On the other hand, quicksort scans memory in-order. Random access to memory is much, much worse than bad branch prediction. Using a heap in merge sort, for example, screws with both branch prediction and memory access. For sorting, if you're minimizing the number of comparisons, the result of each compare should be random and independent of all others. So the only way to have "good" branch prediction when sorting an array of random numbers is to do lots of extra, superfluous compares, e.g. using an O(n^2) algorithm instead of an O(n log n) one. The base case for std::sort in glibc is insertion sort. It's used for less than 6 elements. Nice and linear memory access patterns. Martin

nicknash 14y ago

Agreed. The post wasn't meant to suggest anybody should go and optimize! Just that simple looking code can be tricky/interesting. Also, even artificially skewing the pivot in quicksort as suggested in the paper you reference doesn't work except on /very/ long pipeline machines, because it worsens cache performance & increases instruction count. Also, even then, it's expensive to randomly sample to generate a skewed pivot (a cost they negelect in that paper, assuming it is free)

hristov 14y ago

I think it may actually be provable that as a sorting algorithm gets more efficient, the branches of that algorithm will get harder to predict. When you think about it, an efficient comparison is one in which each result is equally likely, and that is difficult to branch predict.