Why can g++ 5.4 not compile this compile-time prime number code?

Question

#include<iostream>
using namespace std;

template<int N> class Prime
{ // generate N prime numbers at compile time
public:
    unsigned int arr[N]{};
    constexpr Prime() {
        int k=0;
        for(unsigned int i=2; k<N; i++) {
            bool isPrime = true;
            for(int j=0; j<k; j++) {
                if(arr[j] > i/2) break;
                if(i % arr[j] == 0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) arr[k++] = i;
        }
    }
};
int main()
{
    Prime<50000> prime; // if 50000->5000, ok
    for(auto& a : prime.arr) cout << a << ' ';
}

G++ fails to compile this code. It spends ages trying to compile, uses lots of memory, and finally just crashes.

If I make the number 50000 smaller, or get rid of constexpr, it compiles. But I want to use bigger arrays to save time.

Any ideas will be appreciated.

Answer 1

This is a Quality of Implemention (QoI) matter. From the draft Standard

Annex B (informative) Implementation quantities [implimits]

1 Because computers are finite, C++ implementations are inevitably limited in the size of the programs they can successfully process. Every implementation shall document those limitations where known. This documentation may cite fixed limits where they exist, say how to compute variable limits as a function of available resources, or say that fixed limits do not exist or are unknown.

2 The limits may constrain quantities that include those described below or others. The bracketed number following each quantity is recommended as the minimum for that quantity. However, these quantities are only guidelines and do not determine compliance.

(2.38) — Recursive constexpr function invocations [512].

(2.39) — Full-expressions evaluated within a core constant expression [1 048 576].

Your algorithm exceeds the limit of full-expressions evaluated within a core constant expression. Note that gcc does exceed the minimum requirement since your loop scales as 1/2 * N^2 and gcc compiles it for N = 5,000. I haven't been able to find the documented hard limit for gcc. Unfortunately, and unlike clang which has -fconstexpr-steps, you cannot override the number of constexpr evaluations for gcc.

Conclusion: submit a performance report to gcc or use clang (for which your example does compile).