4 ms·

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 p

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
      Sometimes it produces the wrong answer, see for example https://devblogs.microsoft.com/oldnewthing/20190926-00/?p=102924 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!)
gerbenst 5y ago
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.
- CJefferson 5y ago
  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!)
  - gerbenst 5y ago
    https://godbolt.org/z/zPWr73qjc 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.
    - CJefferson 5y ago
      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).

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
    Sometimes it produces the wrong answer, see for example https://devblogs.microsoft.com/oldnewthing/20190926-00/?p=102924 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!)

gerbenst 5y ago

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.

CJefferson 5y ago
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!)
- gerbenst 5y ago
  https://godbolt.org/z/zPWr73qjc 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.
  - CJefferson 5y ago
    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).