Get the latest tech news
Do low-level optimizations matter? Faster quicksort with cmov (2020)
by Nathan Myers, ncm at cantrip dot org, 2020-01-09 Collectively, we have been thinking about sorting for longer than we have had computers. There is still an active literature 1,2,3.
There may be other reasons: radix sort sweeps majestically, sequentially through the whole sequence, relying on the prefetcher to keep ahead of it, while quicksort spends much of its time noodling around with values in L1 cache. Then, implementers could ensure it uses cmov for machine-word types (including pointers and floating-point values, and even small objects like std::string_view), and use it in their sorting and partitioning code. But a lesson for the working programmer might be that, sometimes, you know the problem better than the compiler or cache systems, and measuring can lead you to simple code changes that avoid costly misses, with sometimes dramatic results.
Or read this on Hacker News
