33

Why aren't any std::algorithm methods constexpr? If I understand the new C++14 rules correctly, many of these methods could be constexpr. For example, why can't std::find be constexpr?

static constexpr std::array<char, 4> DnaBases {'A', 'C', 'G', 'T'};

constexpr bool is_dna(char b)
{
    return std::find(std::cbegin(DnaBases), std::cend(DnaBases), b) != std::cend(DnaBases); // why not?
}

Which other std::algorithms could be constexpr?

Daniel
  • 8,179
  • 6
  • 31
  • 56
  • The bottom line is you can not evaluate a function at compile time when you have no idea what data it is going to process. That has to happen at runtime. – Galik Sep 04 '15 at 11:37
  • 1
    @Galik: Not true; the language allows a `constexpr` method to be used with non-`constexpr` data. – Daniel Sep 04 '15 at 11:48
  • But it will only evaluate at compile time if the data passed to it is constexpr. Otherwise it will be compiled as a normal function. – Galik Sep 04 '15 at 11:51
  • 8
    @Galik: yes, that's the point; if you loose nothing from declaring as `constexpr`, then you can only win. – Daniel Sep 04 '15 at 11:53
  • [Related Q&A](http://stackoverflow.com/q/18052208/819272) wrt containers and utilities. – TemplateRex Sep 21 '15 at 12:41

6 Answers6

13

It could be constexpr, but cannot be evaluated as a constant expression, since in this case, for example for compile-time find it is required that: begin/end should be constexpr, the * operator of the iterator should be constexpr, operator == should be constexpr, operator != for the iterator should be constexpr, operator ++ for the iterator should be constexpr. But, if all functions are constexpr, then many algorithms can be implemented with constexpr.

You can look at the SPROUT library for the implementation of constexpr containers/algorithms.

And related talk on the isocpp.org forums

psmears
  • 26,070
  • 4
  • 40
  • 48
ForEveR
  • 55,233
  • 2
  • 119
  • 133
  • 1
    Is there any reason why these operators couldn't in theory be `constexpr` (assuming underlying type can be made `constexpr`)? – Daniel Sep 04 '15 at 10:22
  • 5
    Since `std::find` is a function *template*, it can be marked what has formerly been "conditional constexpr". Function templates do not have to produce functions which are valid constexpr functions for every set of template arguments. However, there should be at least one set of arguments such that an instantiation is a valid constexpr function (so an unconditional `throw` must not appear, for example). – dyp Sep 04 '15 at 10:32
  • 1
    Even in a non-template `constexpr` function, there is still a certain conditionality. The result of a call to such a function is not always a constant expression - instead, it is a constant expression *if and only if* all the arguments are constant expressions. I guess my point here is that it the compiler already is forced to do a very context-specific decision (is this constant or not?) at each call. So why not simply ignore `constexpr` and simply encourage the compiler to make everything "as constant as possible"? – Aaron McDaid Sep 04 '15 at 11:02
  • @AaronMcDaid: I think you'd have to mandate rather than merely encourage, otherwise it'd be up to the quality of the compiler what can be used as an ICE, which wouldn't be much fun. As for why the `constexpr` keyword is needed, as opposed to the language just giving something the semantics of `constexpr` if and only if it would (under the current rules) be valid for `constexpr` to be added to it, I'm not sure. Maybe because if you ODR-use a constexpr object then it needs exactly one definition, so the authors felt it would be useful for this to be explicit in the code? – Steve Jessop Sep 04 '15 at 11:45
11

Functions cannot be overloaded based on constexpr-ness. As a result, any function defined as constexpr needs to be implemented in a form which could be a constexpr. This requirement imposes constraints on all implementations.

The C++14 specification is somewhat relaxed with respect to the constraints compared to C++11. However, when the specification was finalized nobody was confident that all optimizations which can be achieved without the constexpr constraint can be achieved when algorithms are mandated to be constexpr. Without knowing that the non-constexpr functionality is not impeded by mandating constexpr implementations the algorithms won't be defined to be constexpr. The non-constexpr use of algorithms is still assumed to be the primary use of algorithms.

It may be worth having a special set of algorithms which are defined to be constexpr. I'm not aware of a correspnding proposal. I also don't see a lot if demand warranting standardization but my perception may be different from other's.

Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • 1
    I agree any function that would require modification to be `constexpr` should not be. But it seems some could be declared `constexpr` without modification (including `std::find`). The restriction is then only on the parameter types satisfying `constexpr`-ness (which is a separate issue). – Daniel Sep 04 '15 at 10:58
  • 1
    @Daniel: Maybe you have only seen trivial implementations of `std::find()`? Even for something like `std::find()` I can imagine improvements over a naïve implementation, notably dealing with segments, which would be made harder, at least, having to formulate them as `constexpr` (admittedly, I'd be more happy if implementations would implement the segmented optimization). – Dietmar Kühl Sep 04 '15 at 11:01
  • 1
    I don't see what improvements could be made over the naive algorithm (which is the algorithm used in libc++). Unless you are referring to a multi-threaded solution. – Daniel Sep 04 '15 at 11:43
  • 1
    @Daniel: the immediately obvious improvements for `std::find()` are loop-unrolling (which the compiler does for some data structures but not for others), vectorization (again something the compiler may or may not do), and as already mentioned above dealing specifically with segmented sequences like `std::deque` or `std::istreambuf_iterator`. I haven't verified it but I can imagine that the formulation needed for `constexpr` puts off the optimizer in some form, i.e., resulting in less optimized code. – Dietmar Kühl Sep 04 '15 at 12:48
  • 2
    @Daniel `std::find` might, for instance, dispatch to `memchr` (which is highly optimized), given appropriate arguments. MSVC's `find` does that. – T.C. Sep 04 '15 at 21:30
6

The current (C++14) Standard Library is pretty much under-powered w.r.t. to the corresponding Core Language capabilities concerning constexpr.

E.g., MSVC 2015, which only has C++11 language support for constexpr, could almost fully implement the entire C++14 Standard Library usage of constexpr. The only exceptions were std::min, std::max, std::minmax, std::min_element, std::max_element, std::minmax_element for std::initializer_list.

As of C++1z (17?), the std::xxx_element algorithms will become constexpr algorithms for general iterator and comparator inputs to unify the usage for std::initializer_list. Furthermore, there are proposals for constexpr lambda functions for C++1z as well.

With lambdas being upgraded, there are still a few core language limitations left to prevent the entire <algorithm> header from becoming constexpr. (Note that these are not hard-core technological obstacles, most of them could be resolved by allowing the compiler to evaluate them).

  1. Some algorithms can dynamically allocate memory by calling std::get_temporary_buffer (std::inplace_merge, std::stable_sort and std::stable_partition) which is not allowed in constexpr contexts.
  2. Some algorithms can fall back to low-level C routines such as memset (std::fill and std::fill_n) that would prevent library authors from using these algorithms in constexpr contexts.
  3. Some algorithm implementations can benefit from the judicious use of goto (e.g. std::nth_element, std::stable_sort), for which a C++1z proposal was rejected.
  4. Last but not least, constexpr is an interface change, promising that all future implementations will have to deliver this promise. For that reason, implementations are not allowed to add constexpr as a Quality of Implementation feature (in contrast to noexcept).

Especially the 4th issue stalls the experimentation with how much constexpr could be pushed for the Standard Library (algorithms, containers and other utilities). Instead, a separate proposal has to be written and approved for every expansion of constexpr.

Community
  • 1
  • 1
TemplateRex
  • 69,038
  • 19
  • 164
  • 304
3

This is the subject of Antony Polukhin's proposal P0202:

Add Constexpr Modifiers to Functions in and Headers

which I hope would be adopted by the C++ Library Evolution Working Group and make its way into C++20.

einpoklum
  • 118,144
  • 57
  • 340
  • 684
0

std::algorithm algorithms act on iterators. There is a technical reason why making them constexpr would usually either prevent compiling them (in C++11) or do nothing (in C++14 or with conditional-constexpr), but there's also a semantic reason why it wouldn't make sense for them to be constexpr.

The technical reason is that constexpr functions cannot call non-constexpr expressions. ForEveR points out that template constexpr functions can't be evaluated at compile-time if they call non-constexpr expressions.

In the case of std::algorithm, evaluating constexpr functions in std::algorithm would require the functions for accessing container iterators to be constexpr, which in turn would require the iterators themselves to be constexpr types. But this is impossible almost by definition; containers are typically designed as lightweight access to heap-allocated memory, but heap memory cannot be allocated at compile time (of course). In the comments below, dyp points out that iterators don't always point to containers, but even these iterators are unlikely to be useable at compile-time; for instance, streams objects are of course not readable or writeable at compile time, since IO cannot be done at compile time.

This leads to the semantic problem: constexpr semantically means that a function is intended to be possible to evaluate at compile time. Declaring functions conditionally-constexpr when it is impossible to evaluate them at compile time would make the API confusing and misleading.

Now, I think the language would be improved if there were a way to create and use containers at compile time; this would make constexpr that much more similar to Lisp's macro capabilities. This may eventually be added, but currently it's not really supported by existing standard library code. The most flexible approach, of allowing some objects to live on the heap during compile time, is, as mentioned above, not supported at all by the core language, and it would create some serious complications. For instance, what would it be legal to do with such objects? Either their lifetimes would need to be limited to compile-time only, or they would need to be included as static const memory in the final program (like a string literal), or...what?

Kyle Strand
  • 15,941
  • 8
  • 72
  • 167
  • The `` algorithms act on *iterators*, or *iterator-ranges*, not Containers. Additionally, function *templates* marked as `constexpr` may produce instantiations that are no valid `constexpr` functions (formerly, they were *conditionally `constexpr`*). – dyp Sep 04 '15 at 21:35
  • @dyp What exactly is an iterator or iterator-range without a corresponding container? – Kyle Strand Sep 04 '15 at 21:36
  • Ranges generating values, for example boost's `counting_range`; other iterators such as `istream_iterator` refer to a stream, not a Container. There are filter ranges which refer to other ranges etc. – dyp Sep 04 '15 at 21:38
  • @dyp Streams, of course, also can't exist at compile time, but point taken. – Kyle Strand Sep 04 '15 at 21:39
  • [Here's an example of the "conditional `constexpr`"](http://melpon.org/wandbox/permlink/Zhwl6HBchLc5udg9): While `foo(4.2)` is a constant expression, `foo(42)` is not a constant expression. – dyp Sep 04 '15 at 21:42
0

Add the latest status for GCC for reference, since GCC 10.1, we finally have the full support for constexpr algorithm!

Add constexpr modifiers to functions in and Headers P0202R3 10.1 __cpp_lib_constexpr_algorithms >= 201703L

prehistoricpenguin
  • 6,130
  • 3
  • 25
  • 42