Hoare’s Rebuttal and Bubble Sort’s Comeback(blog.reverberate.org)
blog.reverberate.org
Hoare’s Rebuttal and Bubble Sort’s Comeback
https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html
55 comments
...It’s easy to see that the above loop can be implemented without conditional branches. The conditional swapping can be implemented by conditional moves and the conditional pointer increase could be implemented as a unconditional
Or, to put it another way, the compiler was also free to turn the original 'if/then' structure into branchless code using conditional instructions. My point is, surely neither version guarantees that the generated code is branchless, it's all still up to the compiler.
p += (*it < pivot)
Or, to put it another way, the compiler was also free to turn the original 'if/then' structure into branchless code using conditional instructions. My point is, surely neither version guarantees that the generated code is branchless, it's all still up to the compiler.
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.
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.
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
> 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:
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:
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++;
p += (*it < pivot);
if (*it < pivot) {
std::swap(*it, *p); // Could be a self-swap
p++;
}
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;And IIRC compilers have been somewhat chilly about cmov because (iirc) it can’t be speculatively executed.
CMOV is a win if the speculation won't work. HN regular Nathan Myers (ncmncm) wrote a proposal for C++ saying the compilers should offer a way to, in effect, signal that yeah, you really can't guess this one (thus, try CMOV).
The key point of this article (I'm the author) is that even if cmov would be like 50 cycle latency instruction and the penalty of a mispredicted branch is 0 (ie. after the cpu sees a branch is mispredicted it would immediately start executing the instructions from the correct branch), than cmov would still be faster on modern CPU's.
Because in branchless quicksort, no matter how long it takes to figure out where the element has to go relative to the pivot it doesn't obstruct the CPU's ability in this algorithm to start working on the next element the next cycle.
Because in branchless quicksort, no matter how long it takes to figure out where the element has to go relative to the pivot it doesn't obstruct the CPU's ability in this algorithm to start working on the next element the next cycle.
> Many vulnerabilities stem from accessing/modifying memory that should not be accessed/modified.
So a complement to the likely/unlikely annotations?
So a complement to the likely/unlikely annotations?
Got a link?
https://cantrip.org/swap_if.pdf
It probably depends on a core language accommodation because bitwise-swapping objects, or even primitive elements of objects, with constructors is UB.
Arthur O'Dwyer's P1144 https://wg21.link/p1144 explores that territory too.
Gcc has weird limits on generating CMOV instructions to implement this sort of optimization.
It probably depends on a core language accommodation because bitwise-swapping objects, or even primitive elements of objects, with constructors is UB.
Arthur O'Dwyer's P1144 https://wg21.link/p1144 explores that territory too.
Gcc has weird limits on generating CMOV instructions to implement this sort of optimization.
It seems possible that Rust could make better progress than C++ on incorporating this optimization into its standard library because it does not allow programmed move constructors, so "knows" more about its types. This is not assured, because it needs other declarative features that might not be in the core language yet, and might not be on the road map.
But running industrially important generic algorithms twice as fast as C++, automatically and without heroics, would be a Feather in Rust's Cap, and a Black Eye for C++. ("!!!!", as it were.) Or vice versa. Best would be if both got it, of course.
At present, both languages need heroics. I don't know of any other language where there is a reasonable prospect of getting such an optimization implemented generically, but that doesn't mean there aren't any.
But running industrially important generic algorithms twice as fast as C++, automatically and without heroics, would be a Feather in Rust's Cap, and a Black Eye for C++. ("!!!!", as it were.) Or vice versa. Best would be if both got it, of course.
At present, both languages need heroics. I don't know of any other language where there is a reasonable prospect of getting such an optimization implemented generically, but that doesn't mean there aren't any.
Why not use combsort, which is generally
does similar swaps and outperforms bubble sort
in all cases?
https://en.wikipedia.org/wiki/Comb_sort
https://www.geeksforgeeks.org/comb-sort/
This is well known to game developers, and common advice in 3d engines for sorting for z-culling.
You can look this advice up in a raft of 1990s books when we were implementing our own 3d, eg Michael Abrash's Graphics Programming Black Book
You can look this advice up in a raft of 1990s books when we were implementing our own 3d, eg Michael Abrash's Graphics Programming Black Book
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.
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.
It’s linear worst case if your values are unique (equivalent to hashing). If your values aren’t unique you will explode the search space on average to nlogn which is equivalent to open addressed hashing and thus iterating over sorted value set is going to take longer instead of sorting.
This is basically a bullshit post.
This is basically a bullshit post.
Your assertion is contradicted by the article itself, which explains this point clearly. I.e., you're wrong.
Isn't it curious how often people with the most strongly voiced opinions ("bullshit post") are bullshitters themselves? There's some interesting dynamic going on, psychologically.
Isn't it curious how often people with the most strongly voiced opinions ("bullshit post") are bullshitters themselves? There's some interesting dynamic going on, psychologically.
Have you read the article? It uses simple bubble sorting algorithm.
90% of it is discussing the instruction complexity of it. Which is not the same as “informational complexity”
Just to be clear it’s information-theoretically impossible to beat nlogn complexity.
90% of it is discussing the instruction complexity of it. Which is not the same as “informational complexity”
Just to be clear it’s information-theoretically impossible to beat nlogn complexity.
The haskell 'discrimination' package provides quite general support for linear-time sorting, so it's certainly doable. (I don't recall exactly what the limitations about which value types it can handle, but it's reasonably general IIRC.)
There are references to a few papers in the README.
[0] https://hackage.haskell.org/package/discrimination
There are references to a few papers in the README.
[0] https://hackage.haskell.org/package/discrimination
You can do linear time complexity as long as the keys you are sorting don’t duplicate. The moment they do you can’t bean nlogn. Logn is basically the overhead of the worst case probability when keys overlap.
Just to be clear if you keys don’t duplicate then you are not resolving a sorting problem per se. It’s just a degenerate case of the problem which is obviously easy to resolve.
Just to be clear if you keys don’t duplicate then you are not resolving a sorting problem per se. It’s just a degenerate case of the problem which is obviously easy to resolve.
I don't understand what you mean by duplicate here. Apply a Schwartzian Transform and there you go -- no duplicates.
the decorate sort undecorate is more expensive than the thing you're trying to save
That doesn't make sense. The Schwartzian Transform is linear time and cheap time-wise.
Btw, I'm surprised nobody has objections about constants. The constants for the type of stuff 'discrimination' does are (apparently) really bad. Like really bad.
^ The above was a bit sarcastic. I know you're talking about straight up performance, but the problem there wouldn't be the Schwartzian Transform.
Btw, I'm surprised nobody has objections about constants. The constants for the type of stuff 'discrimination' does are (apparently) really bad. Like really bad.
^ The above was a bit sarcastic. I know you're talking about straight up performance, but the problem there wouldn't be the Schwartzian Transform.
Curious to know more. Any sources?
So, there are a few reasons it isn't fair to compare to std::sort.
The C++ standard requires that std::sort work for "move-only types", so you can't copy the pivot. I suspect this is where quite a bit of the slowdown happens -- as the pivot has to be taken by reference/pointer, the compiler optimises worse.
Could std::sort implementations optimise for when the pivot can be copied? Certainly! Particularly when it is a "small value" like this. I worked on this years ago for libstdc++ (g++'s std::sort), but it turned out to make the code really horrible, so it was never merged in.
std::sort implementations already use an alternative sort (usually insertion sort) for small sized lists.
The C++ standard requires that std::sort work for "move-only types", so you can't copy the pivot. I suspect this is where quite a bit of the slowdown happens -- as the pivot has to be taken by reference/pointer, the compiler optimises worse.
Could std::sort implementations optimise for when the pivot can be copied? Certainly! Particularly when it is a "small value" like this. I worked on this years ago for libstdc++ (g++'s std::sort), but it turned out to make the code really horrible, so it was never merged in.
std::sort implementations already use an alternative sort (usually insertion sort) for small sized lists.
> 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.
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.
As integers are "movable" (moving them in C++ just copies them, but you can call std::move), implementations of algorithms like std::sort tend to assume they are only allowed to move things.
You could in principle write two implementations, one that moves + swaps, and one that moves, swaps and (occasionally if it really wants to) copies, but it's extremely hard (possibly impossible) to decide when it is "safe" to use the std::sort that can copy.
It turns out it is much easier to optimise if you can copy the pivot into a local variable, but that's hard to do in std::sort.
You could in principle write two implementations, one that moves + swaps, and one that moves, swaps and (occasionally if it really wants to) copies, but it's extremely hard (possibly impossible) to decide when it is "safe" to use the std::sort that can copy.
It turns out it is much easier to optimise if you can copy the pivot into a local variable, but that's hard to do in std::sort.
I don’t follow. is_copy_constructible tells you if you can copy the type…
Sometimes it produces the wrong answer, see for example https://devblogs.microsoft.com/oldnewthing/20190926-00/?p=10... (things may have gotten better since C++11, I haven't kept up with the times!)
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.
I agree with the first part -- I implemented the movable std::sort for g++, and I found it very hard to convince the compiler to keep the pivot in a register (although I did write it over 10 years ago, maybe the compiler would do a better job by now!)
https://godbolt.org/z/zPWr73qjc
Here is an implementation. This should work with all types. Unfortunate I had to annotate with restrict, but a small price to pay.
Here is an implementation. This should work with all types. Unfortunate I had to annotate with restrict, but a small price to pay.
I think life gets harder when you have to deal with iterators, and have to use iterator::reference (which might not be a raw C++ reference, although it almost always is in practice).
A while ago I was tinkering with Quicksort and avoiding branch mispredictions.
https://easylang.online/blog/qsort_c.html
My implementation is pretty fast. At a size of 40 or 50, I switch to Insertion sort, and there the branchless bubblesort is significantly slower (I just tried it).
But I have to admit defeat to this Sample sort:
https://github.com/SaschaWitt/ips4o
https://easylang.online/blog/qsort_c.html
My implementation is pretty fast. At a size of 40 or 50, I switch to Insertion sort, and there the branchless bubblesort is significantly slower (I just tried it).
But I have to admit defeat to this Sample sort:
https://github.com/SaschaWitt/ips4o
Bubblesort is usually the worst sorting algorithm, in every conceivable way. Given that in a sorting network, bubble sort is dual to insertion sort [1], why can't the optimisations in the blog post be applied to insertion sort? I believe they can be, and the author was just being facetious.
Stop teaching bubble sort.
[1] - https://en.wikipedia.org/wiki/Sorting_network#Insertion_and_...
Stop teaching bubble sort.
[1] - https://en.wikipedia.org/wiki/Sorting_network#Insertion_and_...
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)
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)
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".
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".
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.
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.
Except I was comparing bubble sort to insertion sort. Read my comment again.
If you compare bubble sort to insertion sort, bubble sort is preferable if you have a very small error (like swapping just one element).
You're wrong again. Insertion sort usually does less swaps than bubble sort.
Question: Does it always do less swaps? Probably yes, I think.
Question: Does it always do less swaps? Probably yes, I think.
Part of the article (and the whole article it references) are about how algorithm A that is guaranteed to perform fewer swaps than B is nevertheless slower in practice on modern machines because of other issues (predictability, data flow).
> Most contemporary implementations of quicksort use Hoare partition, for obvious reasons: it does as many comparisons as the Lomuto partition and fewer swaps.
> Given that Hoare partition clearly does less work than Lomuto partition, the question would be why ever teach or use the latter at all. […] implemented in a branch-free manner, Lomuto partition is a lot faster than Hoare partition on random data.
> Most contemporary implementations of quicksort use Hoare partition, for obvious reasons: it does as many comparisons as the Lomuto partition and fewer swaps.
> Given that Hoare partition clearly does less work than Lomuto partition, the question would be why ever teach or use the latter at all. […] implemented in a branch-free manner, Lomuto partition is a lot faster than Hoare partition on random data.
[deleted]
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.
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.
I still dont know why quicksort is so common given its worst case performance.
Not a surprise, really.
I have battled so many times with smug novice "engineers", fresh from their CS courses, pointing, without even thinking twice, O(n^2) or even O(n^3) algorithms as errors on code reviews. This without taking into account the size of the input or the underlying machine executing the code.
It is my constant source of amazement -- to interview yet another candidate who can write any number of sorting algorithms from memory on a whiteboard but who can't tell whether a linked list or an array list insertion is going to be faster for a given application.
I have battled so many times with smug novice "engineers", fresh from their CS courses, pointing, without even thinking twice, O(n^2) or even O(n^3) algorithms as errors on code reviews. This without taking into account the size of the input or the underlying machine executing the code.
It is my constant source of amazement -- to interview yet another candidate who can write any number of sorting algorithms from memory on a whiteboard but who can't tell whether a linked list or an array list insertion is going to be faster for a given application.
The array is a pretty safe bet in most circumstances, on modern hardware. Without a benchmark showing otherwise, I would always default to arrays.
[deleted]
Perhaps https://tug.org/svn/texlive/trunk/Build/source/texk/dvipsk/a... has value at the Bank of Sans Serriffe.
Anyone interested in the ins and outs of Quicksort should have a look at this PhD thesis: https://www.wild-inter.net/publications/wild-2016.pdf
This didn't need to be a surprise! It was a commonplace bit of wisdom in the microcomputer era, when sorting always came with questions about the application. You can't beat it for locality— but you also can't beat it for mostly-sorted, small collections.
Rather than sorting arrays, the area where bubblesort shines (ok. where bubblesort can still be considered!) is keeping linked lists sorted, especially where the sort order is important rather than critical. So event queues: you want to float the highest priority to the top, but it's ok if occasionally #2 is launched before #1, because events aren't guaranteed an execution order. We're using an intrusive linked list because the scheduler has to take what it's given, it can't lay out memory.
Also, any time spent tinkering with an event queue is wasted time. So every round, walk the event queue and perform one (1) bubble sort. This takes the time it takes to traverse the list, effectively. So if you've placed exactly one event at the end of the queue (head of the list), it ends up precisely where it should be. Two? You leave one of them behind for the next pass.
It's easy to reason out that when the sort starts performing badly, the problem you have is event congestion, not a poor big-O complexity for your queue sort.
Bubblesort is sometimes treated as a pessimal joke like bogosort, it isn't, it's just that the reason it's treated as a basic sort pedagogically has been lost, as the profession's center of gravity moves away from these kinds of system-level constructs.