Max array size using #define

Question

Possible Duplicate:
stack overflow c++

I have the following program for generating prime numbers:

#include<iostream> 
#include<cmath>
#include<algorithm>

#define MAX 10000000
using namespace std;

int main(int argc, const char *argv[])
{
    bool prime[MAX+1];
    fill_n(prime,MAX+1,true);
    int baseSqrt,i,j;
    baseSqrt = int(sqrt(MAX+1));
    for(i=2;i<=baseSqrt;i++){
        if(prime[i]){
            for(j=i+i;j<=MAX;j+=i){
                    prime[j]=false;
            }   
        }   
    }   
    return 0;
}

The program works fine for MAX value = 1000000. But when I increase the value to 10000000 the program gives segfault. I tried using gdb but it stops on main giving segfault there. I am using a 64 bit OS. Even if I remove MAX and write 10000000 rather than MAX, I get the same error. Where am I going wrong? Please help.

The stack's size is usually very limited compared to the total amount of memory you can use. — chris, Jan 06 '13 at 12:40

Oliver Charlesworth · Answer 1 · 2013-01-06T12:48:07.050

5

You shouldn't declare very large arrays as local variables (i.e. on the stack), as the stack size is usually quite limited. Instead, dynamically allocate them with new[] and delete[]. Or for idiomatic C++, use a container class like std::deque.

edited Jan 06 '13 at 12:48

answered Jan 06 '13 at 12:41

Oliver Charlesworth

267,707
33
569
680

Whats the max size that i can use? Is it around 1MB? because with #define MAX 7000000 program works fine – Shehbaz Jaffer Jan 06 '13 at 12:43
1

Why `new[]` and `delete[]`? Why not `std::vector`? – Nawaz Jan 06 '13 at 12:43
@Nawaz: Why `std::vector`? Why not `std::deque`? – IInspectable Jan 06 '13 at 12:44
@Tim: That would also work. The point however is: avoid `new` and `delete`. – Nawaz Jan 06 '13 at 12:46
@Nawaz: Argh, except in this case, the type in question is `bool`, and [`std::vector` is a mess](http://stackoverflow.com/questions/670308/alternative-to-vectorbool)! – Oliver Charlesworth Jan 06 '13 at 12:47
doesnt vector slow down the program? I dont know. Just asking. what is faster between the two - dynamic array (new, delete) or vector ? – Shehbaz Jaffer Jan 06 '13 at 12:47
@OliCharlesworth: You can use `std::vector` instead of the messy `std::vector`. – Nawaz Jan 06 '13 at 12:48
@ShehbazJaffer: It shouldn't really slow anything down. – Oliver Charlesworth Jan 06 '13 at 12:48
2

@ShehbazJaffer, You can't absolutely know for sure in each case until you measure, and you shouldn't measure until you have to. Worry about working code before premature optimizations. – chris Jan 06 '13 at 12:48

Mats Petersson · Answer 2 · 2013-01-06T14:09:26.027

In this particular case, would it not be a reasonable idea to make "prime" a global variable. I do understand that global variables aren't always a good solution, but for this particular case, it would be a fairly obvious solution. It's not like MAX isn't a constant, so using new/delete or vector as a solution seems a little unnecessary.

And to answer the question of "is if slower to use 'new' vs global variable', then I can say that it's probably irrelevant. I used #define MAX 1000000000 in the above code, moved prime to be a global, and ran it using time, then altered the code to use new/delete, and it took around 0.5s longer - but the overall runtime is 20.4 or 20.9 seconds, so it's about 2% of the total runtime, and I'm pretty sure more than 2% can be gained by doing other things.

Max array size using #define

2 Answers2