News for hackers. Stuff that matters.
Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by ncmncm on Saturday May 30, 2020 @06:54PM (#23365558)
If you define

  inline bool swap_if(
    bool c, int& a, int& b)
  {
    int ta = a, tb = b;
    a = c ? tb : ta;
    b = c ? ta : tb;
    return c;
  }
and then use it in partition's inner loop like

   right += swap_if(
     *left < pivot,
     *left, *right);
..., compiled with Clang (which generates `cmov` instructions), a simplest-possible quicksort is more than twice as fast as `std::sort`. Then you can doctor up the endgame with heapsort, insertion sort, even bubble sort if you like, and get an incremental improvement.

But using AVX machinery to implement an optimal sorting network for small arrays is faster, if you are sorting scalars. See <https://arxiv.org/abs/1704.08579>

A fully general swap_if,

  template <typename T>
  bool swap_if(
    bool c, T& a, T& b)
  {
    T v[2] = { a, b };
    b = v[c], a = v[1-c];
    return c;
  }
could and should be peephole-optimized to use a pair of `cmov` instructions, but is not in Clang, Gcc, Icc, or MSVC. But even without such an optimization, it makes Quicksort much faster than std::sort. It is slower than the cmov version probably because it costs more L1-bus traffic.

(Gcc, incidentally, is very, very sensitive to details of this version. Change the order of assigning a and b, or use `[!c]` in place of `[1-c]`, and it gets much slower, on Intel, for very non-(to me-)obvious reasons. Gcc also will never, ever produce two `cmov` instructions in a basic block. I have filed a bug.)

Another formulation is

  template <>
  bool swap_if(
    bool c, int& a, int& b)
  {
    int ta = a, tb = b;
    a =  -c&tb | c-1&ta;
    b = c-1&ta |  -c&tb;
    return c;
  }
which Clang also optimizes to a pair of `cmov` instructions. Gcc (like Icc and MSVC) emits the literal and/and/or instructions, which is also faster than std::sort, but less so than the array version.

If `swap_if` were in the Standard Library, it would probably be implemented optimally on all compilers, and almost half of the Standard algorithms could use it to get, often, ~2x performance improvement.

A partition using AVX machinery is potentially much faster, although not as much faster as one might hope. See

<https://bits.houmus.org/2020-02-02/this-goes-to-eleven-pt5>

That took much of a year to implement. AVX512 instructions enable even better optimizations, but AVX512 might not come out in AMD until Zen-4. (We are at Zen-2 now.)

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by haberman on Saturday May 30, 2020 @07:44PM (#23365867)
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.

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by ncmncm on Saturday May 30, 2020 @10:51PM (#23366750)
Thank 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.