Hacker News Reader

Comment by CJefferson | Hacker News Reader

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.

View on HN

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

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.

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.

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

Reply on news.ycombinator.com