How to convert template-sized array initialization to constexpr initialization?

Question

Here's the loop. Basically generates a certain number of points along the circumference of the circle. The points array is obviously constant & can be computed at compile-time, but I can't seem to figure out a way to hoist it into a constexpr.

#include <array>
#include <cmath>

template <std::size_t Len>
class Circle {
public:
    Circle() {
        for (int i = 0; i < Len; i++) {
            float x = (float)std::cos(2 * M_PI * i / (Len - 1));
            float y = (float)std::sin(2 * M_PI * i / (Len - 1));
            points[i * 3] = x;
            points[i * 3 + 1] = y;
            points[i * 3 + 2] = 0;
        }
     }
 private:
     std::array<float, Len * 3> points;
 };

I can see absolutely no point hoisting this into a constexpr. How shall your Circle be required in a constant expression? For optimzation it makes no sense at all! Also: accept an answer! — Walter, Dec 02 '12 at 15:09

score 3 · Answer 1 · answered Dec 01 '12 at 08:42

3

They're not guaranteed to be strictly accurate, but they might be good enough for your purposes.

I just used the Taylor-series approximations. Add constexpr and see if they work.

long double sin2r(long double const r, long double const t, long double const tn, unsigned long long k)
{
    return tn == 0 ? r : sin2r(r + ((k / 2) % 2 ? -1 : +1) * tn, t, tn * t * t / ((k + 1) * (k + 2)), k + 2);
}

long double cos2r(long double const r, long double const t, long double const tn, unsigned long long k)
{
    return tn == 0 ? r : cos2r(r + ((k / 2) % 2 ? -1 : +1) * tn, t, tn * t * t / ((k + 1) * (k + 2)), k + 2);
}

long double sin2(long double const t)
{
    return sin2r(0, t, t, 1);
}

long double cos2(long double const t)
{
    return cos2r(0, t, 1, 0);
}

answered Dec 01 '12 at 08:42

user541686

205,094
128
528
886

+1 for the discussion going on in my answer and for interestingness :) – Billy ONeal Dec 01 '12 at 09:03
1

Combining this with the [indices trick](http://stackoverflow.com/questions/7858817/unpacking-a-tuple-to-call-a-matching-function-pointer) should make for a complete answer. – Luc Danton Dec 01 '12 at 09:19
Hmmm... can you clarify? Still trying to figure out how to initialize an array whose size is defined by a template. – Vitali Dec 01 '12 at 09:56
Oh, found a SO post. http://stackoverflow.com/questions/13313980/populate-an-array-using-constexpr-at-compile-time?rq=1 – Vitali Dec 01 '12 at 10:11

score 2 · Answer 2 · answered Dec 01 '12 at 08:03

2

First of all, a constexpr function is not necessarily evaluated at compile time. There are cases where the compiler must do this (e.g. if the thing is used as a compile time constant); but the standard doesn't require such a thing. (In theory, a compiler might want to do this if storing the generation code and running it once at startup was trivial and used less space than storing the calculated value of the constexpr)

Second, your example is not possible to make constexpr. The standard requires any constexpr function to only call other constexpr functions, and be of the form return expression;. Your example meets neither qualification, because you depend on sin and cos (which are not constexpr functions), and you require a loop, which is not of the form return expression;.

constexpr is not designed for optimization; it is designed to allow you to calculate compile time constants (e.g. so that you could use the result as the size of a stack allocated array).

answered Dec 01 '12 at 08:03

Billy ONeal

104,103
58
317
552

*"...and you require a loop, which is not of the form `return expression`"*... there's this thing called recursion... – user541686 Dec 01 '12 at 08:09
*"`constexpr` is not designed for optimization"*... templates weren't designed to be Turing-complete, either. – user541686 Dec 01 '12 at 08:10
@Mehrdad: I don't see a way to write this recursively that wouldn't cause massive stack explosion. Languages that rely on tail recursion to accomplish loops generally speaking use tail optimization to turn a call into a loop. But C++ certainly doesn't require that. (And a stack frame in C++ compiler land probably includes a whole bunch of stuff for symbol tables and things) Templates might be turing complete -- but I don't see anybody using them for such a purpose. – Billy ONeal Dec 01 '12 at 08:29
o.O "massive stack explosion"? How many iterations do you expect you'd need? See my answer... – user541686 Dec 01 '12 at 08:43
Also, regarding templates being Turing-complete... people do take advantage of their Turing-completeness, like with template-based parser generators. And even if you ignore that, they still do a heck of a lot with templates that they weren't originally intended for. – user541686 Dec 01 '12 at 08:54
@Mehrdad: Perhaps I should have qualified that with "for values of `n` where calculating this a compile time is interesting". You used a large number of recursive calls just to calculate `sin` and `cos` in your answer; adding that to the OP's loop turned into a recursive call would use at least that plus `n` stack frames. – Billy ONeal Dec 01 '12 at 08:55
I don't know how big `NSlices` is, but my code uses like 10-20 stack frames, so as long as he can fit the big loop into a recursion, it's fine. Plus, he can always split up the intervals into halves to go a logarithmic depth instead of a linear depth... you don't *have* to do a tail-style recursion when turning a loop into recursion, you know. – user541686 Dec 01 '12 at 08:56
@Mehrdad: Hmm.. didn't consider possible ways to make it `lg n` deep. The standard suggests 512 levels of recursion allowed in Annex B, so this might be okay. I've never seen that myself; though of course that isn't "hoisting" the OP's function into a `constexpr` -- that's significant algorithm change. – Billy ONeal Dec 01 '12 at 08:59
If it's logarithmic then even 20 levels of recursion should be more than enough. – user541686 Dec 01 '12 at 09:01
I was just interested mainly in how to initialize an array whose size is determined by a template parameter. The sin/cos is kind of a misdirect (you can use the clever taylor series approximation in Mehdrad's answer, or realistically a lot of the primitive math functions will be defined constexpr in the future). For instance, if I wanted to initialize a N-array whose index i contains the value i * 2. – Vitali Dec 01 '12 at 09:59
1

@Vitali: I don't see why you would ever define math functions as `constexpr` -- generally speaking, there's little reason to use such things as compile time constants. Calculating this kind of thing once at program start will probably be faster than loading the calculated results from disk anyway. In your `i * 2` case, it will almost always be better to calculate the value on the fly rather than store an array with the answers. Memory is slow these days. – Billy ONeal Dec 01 '12 at 19:37
@Vitali : I don't think floating-point math functions are ever likely to become `constexpr`. – ildjarn Dec 01 '12 at 21:52

How to convert template-sized array initialization to constexpr initialization?

2 Answers2