On Sun, Oct 13, 2019 at 9:58 PM Jeremy Ong via Std-Discussion <std-discussion@lists.isocpp.org> wrote:
I wanted to write to seek broader feedback and relay my experience trying to leverage constexpr in a real-world situation where compile-time computation is a requirement for performance. By way of a brief background, I am working on an library that computes expressions over higher-dimensional data types. The math itself isn't important for the purposes of this discussion, but compile-time techniques allow me to "collapse" higher dimensional data into sparse representations without needing runtime annotation. When working with expressions, authors of ETLs know that expressions can explode dramatically.

For example, if I encode a polynomial using templates (variables, monomials, and degrees) via parameter packs as some type P and later try to do a 4th order taylor expansion (just as an example), the number of terms will increase as O(N^4). I quickly found that templates were untenable due to memory and processing constraints (instantiating too many types, etc). This is *despite* aggressive usage of folds and ensuring that parameter packs had an imposed total order to minimize instantiations. Under this approach, is was astonishingly easy to completely cripple the compiler even for cases I would consider easy (clang profiling was tried, as well as general profiling tools). Again, this is code that runs perfectly fine at runtime, but the cost could easily be moved to compile time.

Thus, the next option is to leverage constexpr, encoding expressions as actual member data, and using templates solely to encode the size of the data. Folds become loops, and in principle, compilation time and memory usage should go down. Here are the things I encountered along the way:

1. The compiler is "dumb" in the sense that data that is entirely compile time deterministic is not usable as such. Going back to the example of polynomials. Suppose the number of addends in each is N1 and N2. Upon addition, the sum is at most N1 + N2, however, it is possible that some of the monomials combine. Trying to express this using any form of constexpr is extremely difficult. Common strategies include traversing the data twice (once to compute the size, a second time to actually compute it). In this case, the data itself is not encoded in types, and so this is not possible (despite, again, all the data being compile-time deterministic).

2. I have found that constexpr can ironically decrease performance in a number of situations. Once code was restructured as constexpr, the compiler often fails to inline code that should be entirely inlineable. Suppose we want to actually attach data to what is now a compiled expression template. All early attempts to do so failed because the compiler was unable to infer that the instantiation of the function could only possibly be invoked in one place (and thus should be inlined no questions asked). Part of the issue here is that constexpr as a keyword conveys very little information regarding what will ultimately happen when invoked. By the time I restructured the code to peel away the non-constexpr argument that had snuck in, the compile times became untenable again (once again, more data needed to be pushed to types) and it was back to the drawing board.

3. The proper usage of `if constexpr` feels a bit lackluster. The operand must be fully determined to be a constant expression, but this immediately qualifies "data" that is, again, static at compile time. Constant expression arguments proposed for C++2b is an option, but it should seem that an if block gated by the `is_constant_evaluated` should preclude that (it doesn't). Another issue is that in more complicated functions, it can be very difficult to reason about the branches when constexpr and non-constexpr branches must intermingle.

4. Allowing allocations which do not leave the constexpr context via constexpr new is not actually helpful in several situations I can think of. At the end of the data, often, the data needs to be variably sized, and in this scenario, you cannot use auto return type deduction to read off the size as a constant expression and create the appropriately sized type that I need.

Are there situations and workarounds to the above? Yes, but only after extensive rewrite and fighting the compiler every step of the way. Even at the end, I'm not sure if I will be getting the performance I could have gotten with just straight C-style procedural code for each operation I need to support. Granted, I think my application was perhaps a bit more extreme in its requirements, but I think it was a decent "sniff"-test for what I see as problems and headaches ahead. As it is, I'm doing things like rounding up capacities to the nearest size of two (and other such nonsense) to reduce the combinatorial explosion of type instantiations.

The idea I would like to float around is the following:

- Proposal: introduce a new function signature decorator called `consteval` (in the spirit of the variable consteval decorator) which is an input into overload resolution.
- All other overload resolution decorators are evaluated first (const, ref qualifier, ADL), and then `consteval` is considered. If the invocation occurs at compile time, the `consteval` overload is given precedence.
- All arguments passed to the consteval function are implicitly constexpr by definition

The only way to do this is to make that function a template and treat all the arguments as non-type template parameters. See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0992r0.pdf for why this is a problem.
 
- All if statements and control statements are similarly implicitly constexpr (even if the notion for such a construct doesn't exist now, i.e. there is no `for constexpr` as of yet).
- Functions that are `consteval` can call non-consteval functions without any issue (it is a weaker qualification).
- All allocations are also permitted applying the rules with the currently proposed `constexpr new`, except they may leave the constexpr context and reside in the data segment (analogous to static variable initialization). Initially, I would imagine that only trivial destructors are permitted (but still this would unlock a lot of capability).

We almost got this for C++20, but there are some significant issues to solve here.

- Michael Spencer
 
- All data mutated in the consteval context are also considered "constant expressions" when referenced later.
- Ergo, consteval produces an easy-to-reason about "frontier" of constant expressions. In conjunction with consteval as a variable decorator, there is no guesswork as to what will happen at compile time and what won't
- We dramatically simplify code and no longer need specific constexpr variants of various control structures and littered code with conditionals to activate "compile-time-only" code.
- If we want to share functionality, we can introduce a common entry point that does not have the `consteval` qualifier.

The theme of the idea is simple. Code that is C++ should just be C++, and how it behaves at compile time and runtime should differ by at most a keyword. I think such a feature is far easier to reason about (and to teach, just piggy-backing off general overload resolution principles), without overcrowding the API (at our current rate, we'll have a constexpr-paper variant for every language feature in C++). I would not propose deprecating any existing functionality immediately, but tbh, if I had something like `consteval` today, I would outright ban constexpr in my codebase.

Important: I don't (even remotely) claim that the above has worked out all the details, or that there aren't issues I haven't thought of. These are just thoughts that I kept coming back to now that I've had much more extensive experience working with constexpr (compared to just dotted isolated cases in the wild before). My standardese is weak, having never written a paper, so consider this primarily as a perspective from the lens of a practitioner.

Thoughts/feedback appreciated,
Jeremy

--
Std-Discussion mailing list
Std-Discussion@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-discussion