Memory error at lower limit than expected when implementing Sieve of Eratosthenes in C++

Question

My question is related to a problem described here. I have written a C++ implementation of the Sieve of Eratosthenes that hits a memory overflow if I set the target value too high. As suggested in that question, I am able to fix the problem by using a boolean <vector> instead of a normal array.

However, I am hitting the memory overflow at a much lower value than expected, around n = 1 200 000. The discussion in the thread linked above suggests that the normal C++ boolean array uses a byte for each entry, so with 2 GB of RAM, I expect to be able to get to somewhere on the order of n = 2 000 000 000. Why is the practical memory limit so much smaller?

And why does using <vector>, which encodes the booleans as bits instead of bytes, yield more than an eightfold increase in the computable limit?

Here is a working example of my code, with n set to a small value.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main() {
    // Count and sum of primes below target

    const int target = 100000;

    // Code I want to use:
    bool is_idx_prime[target];

    for (unsigned int i = 0; i < target; i++) {
        // initialize by assuming prime
        is_idx_prime[i] = true;
    }
    // But doesn't work for target larger than ~1200000

    // Have to use this instead
    // vector <bool> is_idx_prime(target, true);

    for (unsigned int i = 2; i < sqrt(target); i++) {
        // All multiples of i * i are nonprime
        // If i itself is nonprime, no need to check
        if (is_idx_prime[i]) {
            for (int j = i; i * j < target; j++) {
                is_idx_prime[i * j] = 0;
            }
        }
    }

    // 0 and 1 are nonprime by definition
    is_idx_prime[0] = 0; is_idx_prime[1] = 0;

    unsigned long long int total = 0;
    unsigned int count = 0;
    for (int i = 0; i < target; i++) {
        // cout << "\n" << i << ": " << is_idx_prime[i];
        if (is_idx_prime[i]) {
            total += i;
            count++;
        }
    }
    cout << "\nCount: " << count;
    cout << "\nTotal: " << total;
    return 0;
}

outputs

Count: 9592
Total: 454396537
C:\Users\[...].exe (process 1004) exited with code 0.
Press any key to close this window . . .

Or, changing n = 1 200 000 yields

C:\Users\[...].exe (process 3144) exited with code -1073741571.
Press any key to close this window . . .

I am using the Microsoft Visual Studio interpreter on Windows with the default settings.

Answer 1

Turning the comment into a full answer:

Your operating system reserves a special section in the memory to represent the call stack of your program. Each function call pushes a new stack frame onto the stack. If the function returns, the stack frame is removed from the stack. The stack frame includes the memory for the parameters to your function and the local variables of the function. The remaining memory is referred to as the heap. On the heap, arbitrary memory allocations can be made, whereas the structure of the stack is governed by the control flow of your program. A limited amount of memory is reserved for the stack, when it gets full (e.g. due to too many nested function calls or due to too large local objects), you get a stack overflow. For this reason, large objects should be allocated on the heap.

General references on stack/heap: Link, Link

To allocate memory on the heap in C++, you can:

• Use vector<bool> is_idx_prime(target);, which internally does a heap allocation and deallocates the memory for you when the vector goes out of scope. This is the most convenient way.

• Use a smart pointer to manage the allocation: auto is_idx_prime = std::make_unique<bool[]>(target); This will also automatically deallocate the memory when the array goes out of scope.

• Allocate the memory manually. I am mentioning this only for educational purposes. As mentioned by Paul in the comments, doing a manual memory allocation is generally not advisable, because you have to manually deallocate the memory again. If you have a large program with many memory allocations, inevitably you will forget to free some allocation, creating a memory leak. When you have a long-running program, such as a system service, creating repeated memory leaks will eventually fill up the entire memory (and speaking from personal experience, this absolutely does happen in practice). But in theory, if you would want to make a manual memory allocation, you would use bool *is_idx_prime = new bool[target]; and then later deallocate again with delete [] is_idx_prime.