4 ms·
The point of the article is that performance on modern hardware can be determined by things that are usually neglected in the performance analyses that tell us,
by gjm11 5y ago
The point of the article is that performance on modern hardware can be determined by things that are usually neglected in the performance analyses that tell us, e.g., that "bubblesort is usually the worst in every conceivable way".
In particular, the author claims (and presents benchmarks that appear to verify) that for sorting very small arrays, bubblesort is better than insertion sort because you can do it with fewer unpredictable branches, and unpredictable branches are very bad for performance.
Maybe the same optimizations can be applied to insertion sort, but it's not obvious to me that they can; in particular, the inner loop of insertion sort is of variable length and necessarily involves a hard-to-predict branch. You could do away with that by always going all the way to the end of the array, but unless I'm confused this gives you an algorithm pretty much equivalent to bubblesort, and equally worthy (according to the usual sorts of analysis) of being called "usually the worst in every conceivable way".