What about constexpr?

[Morwenn]

Standard constexpr algorithms

P0202 proposes to add constepxr to many functions from <cstring> and to basically every algorithm from <algorithm>. Apparently, the proposal was rather well-received and we might have constexpr algorithms in the standard at some point in the future.

So, what about cpp-sort? Since we're already using C++14, we can use the improved constexpr but I feel that it won't solve every problem:

• std::swap and a few other utility functions are not constexpr, but we could probably reimplement a few of them. Update: actually, some parts of <functional> such as std::mem_fn and a good part of <iterator> would have to be reimplemented too in order to handle everything, and some parts are rather huge.
• The standard algorithms are not constexpr either, but since we ship altered versions of many of them, adding constexpr shouldn't be a problem.
• Some algorithms allocate dynamic memory. There is currently no way I know of to solve this problem. Projects reimplementing a constexpr version of the standard algorithms such as Bolero Murakami's Sprout don't use algorithms that allocate heap memory; these projects are generally only meant to be used at compile-time.

I would be trivial to change some algorithms to be constexpr but it's probably not the case for most of them. A partial constexpr support could be a starting point.

---

The first revision of P0202 takes several design choices into consideration and gives the following set of rules to make standard algorithms constexpr (<cstring> has been disqualified from constexpr enhancements):

• For some of them, most notably the non-mutating ones, just adding constexpr should be enough.
• Some of them rely on std::memcpy and friends, so compilers are encouraged to use their own equivalent constexpr intrinsics of these functions instead. It concerns everything that relies on the std::copy and std::move family of algorithms.
• Algorithms that might allocate heap memory such as std::stable_partition and std::stable_sort are not marked constexpr.

Basically, we will wait for a constexpr-ified standard library (at least for std::copy and std::move), then we can start to constexpr-ify cpp-sort. The whole iter_move thing might make things harder to do though. Anyway, this is definitely a future issue.

Use cases

I often wondered whether there were use cases for constexpr sorting algorithms. Here is a list of situations where sorting at compile-time might be useful:

• Compile-time std::set which sorts its input and performs a binary search on lookup, which is more performant than the tree implementation (e.g. Frozen).
• It can be used to reorder struct fields by size to make tighter structs.
• Other ideas?

[Morwenn]

Marking this as a future issue for now. Apparently not everyone thinks P0202 is a good idea as is (can't remember where I read that, but I definitely did), and too many existing parts of the standard library would have to be implemented again in order to be usable at compile-time. Some of them even rely on constexpr versions of std::memcpy and friends, which means that it will be hard to get a portable implementation without an officially constexpr standard library.

[Morwenn]

C++20 is approaching with plenty of extended constexpr and compile-time utilities, most notably:

• constexpr std::swap and std::invoke, which are fundamental building blocks for many things
• constexpr <algorithm>
• More constexpr here and there in the library
• constexpr new and delete might solve the problem of allocating algorithms
• consteval functions
• std::is_constant_evaluated, which might help for the cases where std::memcpy is not usable
• constexpr std::bit_cast, which avoids having to use std::memcpy in some places
• constexpr std::string, which is the first step to make string-specific algorithms constexpr
• constexpr std::vector, which helps having to reinvent it in the places where we use vectors
• constexpr union and trivial default initialization, which are required to make fixed_size_list nodes constexpr
• constexpr try/catch, dynamic_cast and virtual, which might help to complete the remaining gaps
• constexpr unevaluated asm statements, which we most likely don't use

All those improvements should make C++20 the suitable candidate for making most of the library constexpr. However there are caveats to take into account: we're supposed to use std::construct_at and std::destruct_at instead of placement new and [pseudo-]destructor calls to construct and destruct objects. Moreover objects created at compile time must be explicitly destroyed, we can't elide the destructor call at compile time even if it is trivial, so we need to check std::is_constant_evaluated to decide whether to call the trivial destructors or not (ignoring them at runtime still helps with debug mode performance).

[Morwenn]

Another advantage I hadn't thought of is that undefined behaviour isn't allowed when invoking constexpr functions, so it would be something valuable in the testsuite. Once many functions are marked constexpr, on interesting way to test them would be to use Catch2's STATIC_REQUIRE when possible.

Both compile-time checks and runtime checks are interesting though (just to make sure that all the tests are run even when there are failures at compile time), so I would most likely just add another CI job per compiler for compile-time tests, and define CATCH_CONFIG_RUNTIME_STATIC_REQUIRE for the ones that already exist. That would warrant another option in the testsuite CMake file.

[Morwenn]

Instead of completely waiting for C++20, I decided to start rolling out some constexpr support in version 1.10.0: the idea is that even if we don't provide constexpr sorters ourselves, the library components such as sorter_facade can still be used to create constexpr sorters. This is still fairly limited since passing ranges to a sorter in a constexpr context won't work before C++17, but this is somewhat enabling without having to change many things.

[Morwenn]

In the spirit of a few messages above, 1.13.0 ships with a new CMake option called CPPSORT_STATIC_TESTS which controls CATCH_CONFIG_RUNTIME_STATIC_REQUIRE. I changed tests to use STATIC_CHECK instead of CHECK when it was trivial to do so. By default all tests are deferred to runtime, but setting that new option to ON allows the changed ones to run at compile time instead.

The constexpr support is rolling out slowly, but those are all good first steps.

[Morwenn]

Changing the whole test suite would be quite the task and I still don't have a master plan for it, so for now I decided to go with the simplest approach: have a new test where constexpr sorters are called at compile time on a small array. This is quite limited for a bunch of reasons (for example it only tests algorithms that work on random-access iterators) but will already allow to see which sorters can be made trivially constexpr and which ones require additional work. We need to start somewhere and that's a good place to start if any, iterations to increase the coverage can happen later.

List of sorters to try to make constexpr:

• [ ] adaptive_shivers_sorter
• [ ] cartesian_tree_sorter
• [x] counting_sorter
• [ ] float_spread_sorter
• [ ] grail_sorter
• [x] heap_sorter
• [x] heap_sorter<4>
• [x] insertion_sorter
• [ ] integer_spread_sorter
• [ ] mel_sorter
• [ ] merge_insertion_sorter
• [ ] merge_sorter
• [x] pdq_sorter (FIXED: reinterpret_cast for MinGW)
• [x] poplar_sorter
• [x] quick_merge_sorter (FIXED: goto in adaptive quickselect)
• [x] quick_sorter
• [x] selection_sorter
• [ ] ska_sorter
• [ ] slab_sorter
• [ ] smooth_sorter (issue: std::bitset)
• [ ] spin_sorter
• [ ] spread_sorter
• [ ] std_sorter
• [ ] string_spread_sorter
• [ ] tim_sorter
• [ ] wiki_sorter

Adapters:

• [ ] container_aware_adapter
• [x] counting_adapter
• [ ] drop_merge_adapter
• [x] hybrid_adapter
• [ ] indirect_adapter
• [ ] out_of_place_adapter
• [ ] schwartz_adapter
• [ ] self_sort_adapter
• [ ] small_array_adapter
• [ ] split_adapter
• [ ] stable_adapter, make_stable, stable_t
• [ ] verge_adapter

Measures of presortedness:

• [ ] block
• [ ] dis
• [ ] enc
• [ ] exc
• [ ] ham
• [ ] inv
• [ ] max
• [x] mono
• [ ] osc
• [ ] rem
• [x] runs
• [ ] sus

Other actions:

• [x] Create test template
• [ ] Update documentation on a sorter-per-sorter basis

I will first perform tests on the 2.x.y branch, but might also backport the ones that can trivially be made constexpr to the 1.x.y branch, guarded with a macro only enabling the feature in C++20 mode.

[Morwenn]

Components that can reasonably be marked constexpr without too much additional work in 1.x.y:

• [ ] heap_sorter
• [ ] insertion_sorter
• [ ] quick_merge_sorter
• [ ] quick_sorter
• [ ] selection_sorter
• [x] hybrid_adapter (even in C++14 mode)
• [ ] probe::mono
• [ ] probe::runs