Hoare’s Rebuttal and Bubble Sort’s Comeback

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by CJefferson on Sunday January 30, 2022 @11:16AM (#30138417)

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.

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by vlovich123 on Sunday January 30, 2022 @12:03PM (#30138828)

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

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by CJefferson on Sunday January 30, 2022 @12:29PM (#30139078)

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.

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by vlovich123 on Sunday January 30, 2022 @12:44PM (#30139254)

I don’t follow. is_copy_constructible tells you if you can copy the type…

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by CJefferson on Sunday January 30, 2022 @02:41PM (#30140379)

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!)

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by gerbenst on Sunday January 30, 2022 @12:14PM (#30138922)

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.

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by CJefferson on Sunday January 30, 2022 @12:29PM (#30139084)

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!)

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by gerbenst on Sunday January 30, 2022 @12:55PM (#30139367)

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.

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by CJefferson on Sunday January 30, 2022 @02:38PM (#30140346)

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

[ Parent | on HN ]