3 ms·
Your "simplest-possible quicksort" appears to be the same as the first branchless Lomuto partition given in the article. The premise of the article is that, wh
by haberman 6y ago
Your "simplest-possible quicksort" appears to be the same as the first branchless Lomuto partition given in the article.
The premise of the article is that, while branchless, this loop suffers from store/load dependencies that significantly inhibit instruction-level parallelism. Gerben's algorithm gets a 2x win over this approach by using a temporary buffer that prevents loads from aliasing previous stores.
- ncmncm 6y agoThank you for the correction. The best sort in the article appears to yield 3x vs. std::sort for an array that fits in L2 cache. In my testing (with much larger arrays) I got 2.5x without any small-array transition, and 3x with a branchless sorting-network for ranges of 3 or less, and dramatically less code than that presented in the article. I suspect that the algorithms used in the article, implemented just a little differently, could still yield substantially better performance, beating my simpler code. This is a consequence of our deal with the devil: caches and speculation make our code faster, but we can no longer know whether it is objectively fast, or how much faster it could be. What seemed fast becomes slow the moment somebody does it faster.