8 ms·

Hoare’s Rebuttal and Bubble Sort’s Comeback

103 points by blopeur 5y ago

gnufx 5y ago
Perhaps https://tug.org/svn/texlive/trunk/Build/source/texk/dvipsk/afm2tfm.c?revision=61654&view=markup#l974 https://tug.org/svn/texlive/trunk/Build/source/texk/dvipsk/a... has value at the Bank of Sans Serriffe.
chkas 5y ago
A while ago I was tinkering with Quicksort and avoiding branch mispredictions. https://easylang.online/blog/qsort_c.html 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://github.com/SaschaWitt/ips4o
FrozenVoid 5y ago
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://en.wikipedia.org/wiki/Comb_sort https://www.geeksforgeeks.org/comb-sort/ https://www.geeksforgeeks.org/comb-sort/
joosters 5y ago
...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 p += (*it < pivot) Does that really guarantee that it is branchless? Surely a compiler is free to turn that into a comparison and jump? 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.
- haberman 5y ago
  > 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;
- masklinn 5y ago
  And IIRC compilers have been somewhat chilly about cmov because (iirc) it can’t be speculatively executed.
  - ncmncm 5y ago
    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.
JohnHaugeland 5y ago
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
- Radim 5y ago
  Pierre Terdiman's "Radix sort revisited" for O(N) sorting (linear worst case!), from the same era: http://www.codercorner.com/RadixSortRevisited.htm 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.
  - heavenlyblue 5y ago
    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.
    - cassepipe 5y ago
      Curious to know more. Any sources?
    - Quekid5 5y ago
      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 https://hackage.haskell.org/package/discrimination
ogogmad 5y ago
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_Bubble_networks https://en.wikipedia.org/wiki/Sorting_network#Insertion_and_...
- yxhuvud 5y ago
  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.
- moffkalast 5y ago
  Absolutely right, if I had any students to teach I'd start with bogosort. It's arguably the best one.
- bhaak 5y ago
  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.
  - deleted 5y ago
    [deleted]
  - ogogmad 5y ago
    Except I was comparing bubble sort to insertion sort. Read my comment again.
    - bhaak 5y ago
      If you compare bubble sort to insertion sort, bubble sort is preferable if you have a very small error (like swapping just one element).
kleiba 5y ago
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 https://www.wild-inter.net/publications/wild-2016.pdf
- nnoitra 5y ago
  I find this very informal and lacking much rigor.
  - alar44 5y ago
    Mm, I agree. Shallow and pedantic.
samatman 5y ago
> the final surprise is that Bubble Sort takes the crown for small arrays 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.
- thechao 5y ago
  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.
lmilcin 5y ago
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.
- Thiez 5y ago
  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 5y ago
    [deleted]
CJefferson 5y ago
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.
- vlovich123 5y ago
  > 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.
  - CJefferson 5y ago
    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.
    - vlovich123 5y ago
      I don’t follow. is_copy_constructible tells you if you can copy the type…
      - CJefferson 5y ago

103 points by blopeur 5y ago

Perhaps https://tug.org/svn/texlive/trunk/Build/source/texk/dvipsk/afm2tfm.c?revision=61654&view=markup#l974 https://tug.org/svn/texlive/trunk/Build/source/texk/dvipsk/a... has value at the Bank of Sans Serriffe.

chkas 5y ago

A while ago I was tinkering with Quicksort and avoiding branch mispredictions. https://easylang.online/blog/qsort_c.html 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://github.com/SaschaWitt/ips4o

FrozenVoid 5y ago

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://en.wikipedia.org/wiki/Comb_sort https://www.geeksforgeeks.org/comb-sort/ https://www.geeksforgeeks.org/comb-sort/

joosters 5y ago

...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 p += (*it < pivot) Does that really guarantee that it is branchless? Surely a compiler is free to turn that into a comparison and jump? 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.

haberman 5y ago
> 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;
masklinn 5y ago
And IIRC compilers have been somewhat chilly about cmov because (iirc) it can’t be speculatively executed.
- ncmncm 5y ago
  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.

JohnHaugeland 5y ago

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

Radim 5y ago
Pierre Terdiman's "Radix sort revisited" for O(N) sorting (linear worst case!), from the same era: http://www.codercorner.com/RadixSortRevisited.htm 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.
- heavenlyblue 5y ago
  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.
  - cassepipe 5y ago
    Curious to know more. Any sources?
  - Quekid5 5y ago
    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 https://hackage.haskell.org/package/discrimination

ogogmad 5y ago

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_Bubble_networks https://en.wikipedia.org/wiki/Sorting_network#Insertion_and_...

yxhuvud 5y ago
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.
moffkalast 5y ago
Absolutely right, if I had any students to teach I'd start with bogosort. It's arguably the best one.
bhaak 5y ago
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.
- deleted 5y ago
  [deleted]
- ogogmad 5y ago
  Except I was comparing bubble sort to insertion sort. Read my comment again.
  - bhaak 5y ago
    If you compare bubble sort to insertion sort, bubble sort is preferable if you have a very small error (like swapping just one element).

kleiba 5y ago

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 https://www.wild-inter.net/publications/wild-2016.pdf

nnoitra 5y ago
I find this very informal and lacking much rigor.
- alar44 5y ago
  Mm, I agree. Shallow and pedantic.

samatman 5y ago

> the final surprise is that Bubble Sort takes the crown for small arrays 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.

thechao 5y ago
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.

lmilcin 5y ago

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.

Thiez 5y ago
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 5y ago
  [deleted]

CJefferson 5y ago

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.

vlovich123 5y ago
> 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.
- CJefferson 5y ago
  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.
  - vlovich123 5y ago
    I don’t follow. is_copy_constructible tells you if you can copy the type…
    - CJefferson 5y ago