Hoare’s Rebuttal and Bubble Sort’s Comeback

Even better is when you have tiny (<64) arrays of small numbers (<256) is just to use an array and write down the answer; integers that are small enough self-hash in a natural order, with very little stack pressure — certainly a lot less than the cost of half a dozen function calls.

And IIRC compilers have been somewhat chilly about cmov because (iirc) it can’t be speculatively executed.

It doesn't, but is intended to provide a strong hint to the compiler. A pre-386 one would probably turn the "comparison result in non-branching context" into a cmp/sbb/inc; 386+ could do that or use cmp/setcc depending on surrounding context, and in general a compiler could fold it even further. E.g. if pivot was in eax, it in ecx, and p in edi, that line might generate only two instructions:

    cmp [ecx], eax
    adc edi, 0

(Figuring out how the above works is left as an exercise for the reader.)

There’s two things at play here: what should the actual machine code do, and how do you get your program to compile to that machine code.

This article is about algorithms, not compilers, and cares only about what the actual instructions are, so it’s better to treat it as if you have a compiler that will just do what you mean instead of trying to be clever (because in this instance that “compiler” is the reader). You still need to get your actual compiler to generate the right code, but that’s something to worry about later.

> surely neither version guarantees that the generated code is branchless, it's all still up to the compiler.

That is true, and the article mentions that GCC did not want to generate branchless code in this case, and thus performed much worse. Only Clang reliably generated the branchless code, and thus Clang was used for all of the benchmarking.

> the compiler was also free to turn the original 'if/then' structure into branchless code using conditional instructions

If we were just talking about:

   if (*it < pivot) p++;

then I would agree with you. Optimizing this into the branchless version is a relatively trivial operation:

   p += (*it < pivot);

However the actual code was:

    if (*it < pivot) {
      std::swap(*it, *p);   // Could be a self-swap
      p++;
    }

This std::swap() line performs two memory reads and a memory write, but only if the condition is true. Eliminating the branch in this case will cause these memory operations to happen unconditionally, which means the optimizer will actually be introducing extra memory operations. This is the opposite of what you generally expect an optimizer to do: if anything you usually want an optimizer to reduce the number of memory operations being performed! The compiler would need to be extremely confident that this will somehow speed up the program overall, and it will also need to guarantee that none of these new loads/stores can possibly introduce memory errors (out-of-bounds reads or writes).

For these reasons, I don't expect real compilers to ever translate the example above into the equivalent branchless code, as given in Andrei's article:

    auto x = *read;
    auto smaller = -int(x < pivot);
    auto delta = smaller & (read - first);
    first[delta] = *first;
    read[-delta] = x;
    first -= smaller;

Pierre Terdiman's "Radix sort revisited" for O(N) sorting (linear worst case!), from the same era:

http://www.codercorner.com/RadixSortRevisited.htm

> In every decent programmer’s toolbox lies a strange weapon called a Radix Sort. Where does it come from ? Who invented it ? I don’t know. As far as I can remember it was there, fast, easy, effective. Really effective. So unbelievably useful I’ve never really understood why people would want to use something else. The reasons ? Most of the time, they tell me about floats, negative values, and why their new quick-sort code rocks.

> Enough, I’m tired. Although the standard Radix Sort doesn’t work very well with floating point values, this is something actually very easy to fix. In this little article I will review the standard Radix Sort algorithm, and enhance it.

> The C++ standard requires that std::sort work for "move-only types", so you can't copy the pivot

Do you mean internally/due to subtle complexity requirements? Cause std::sort works just fine on copyable types like integers and complexity is only defined in terms of swaps.

it's not difficult to swap the pivot with the last element and have the compiler figure out it can keep pivot in register most of the time.

Then I suggest you implement it and prove the author wrong by providing a benchmark where your implementation outperform the algorithm provided in the article.

Absolutely right, if I had any students to teach I'd start with bogosort. It's arguably the best one.

If you don't believe it, benchmark it.

On very small arrays bubble sort is faster than quicksort as quicksort has a large constant overhead.

Constant overheads are usually disregarded in complexity analysis but in practice, it can be significant.

When used as an algorithm (as opposed to a sorting network), insertion sort only inserts "as far as it needs to". In other words: it moves the new element to the correct position, then stops going back through the array. This is the aspect of insertion sort that makes it very fast for "almost sorted" data: each element is only moved a few spots. However, this is a branch that is difficult to predict: this is the author's point. For very small amounts of data, branch misprediction for this branch dominates.

This is not the case when insertion sort is expressed as a sorting network. Take a look at this image [1]: the final "insert" has comparators that go through the entire network. The "algorithm" version wouldn't do that: it would stop (using a branch) as soon as the entry hits the correct place. If you remove that branch (which, remember, is the thing that makes insertion sort faster in the general case), insertion and bubble sort are indeed very similar.

The point here is that "sorting algorithms" and "sorting networks" are not the same thing: a sorting algorithm can branch, a sorting network cannot. The same principles of bubbling and insertion can apply to both, but that does not mean that an insight that applies to sorting networks necessarily applies to sorting algorithms.

[1]: https://en.wikipedia.org/wiki/Sorting_network#/media/File:Re...

(PS: I actually wrote most of that wikipedia article years ago! I did the illustrations too! I basically just wrote down and made diagrams for whatever I could understand from The Art of Computer Programming vol 3. The insight about how bubble sort and insertion sort are essentially the same when expressed as sorting network is from Knuth, though I doubt it's original with him)

I remember seeing one occurence of bubblesort in the source code of Crafty chess engine with a comment explaining that this was unexpectingly the fastest sort in that particular case. (It was the ordering of a few moves in the quiesce algorithm I think).

There is a nice variant of bubble sort called comb sort. It uses a variable stride between compared elements. IIRC stride = len/1.3 and then shrink it by the same amount each pass. It's way faster than plain bubble sort.

I still dont know why quicksort is so common given its worst case performance.

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".

The array is a pretty safe bet in most circumstances, on modern hardware. Without a benchmark showing otherwise, I would always default to arrays.

I find this very informal and lacking much rigor.