c++: array size limit?

bigfatdud · 01-26-2005, 12:49 PM

Hello:

I'm just trying to make a 2 dimensional integer array with the following code but keep getting a segmentation fault... I'm running on mandrake 10.1 and gcc 3.4.1.

=============================
#include <iostream.h>

int main()
{
int i[2000][2000];
int j,k;

for (j=0; j<2000; j++) {
for (k=0; k<2000; k++) {
i[j][k] = j+k;
}
}

return 0;
}
=============================

Works okay with smaller arrays (e.g. 1000x1000)... So is there a size limit on the size of arrays? If so, how can I change it? If not, any suggestions on how I should approach?

Thank you very much...

dud

Matir · 01-26-2005, 12:58 PM

My guess is that the maximum size of an array is 4.2 billion (2^32) bytes, as an array position (for 1-d array) is calculated in the processor by:

Code:

base+index*size

where base is the base address of the array, index is the array index, and size is the size of a single element. for a two dimensional array, it is probably:

Code:

base+rowindex*colsize+colindex*size

So, for this all to fit in 32 bits, the maximum size of a two dimensional array must be:

Code:

numrows*numcols*sizeof(element)<(2^32)

Edit:
Your 2000x2000 is only hitting 16,000,000 (2000*2000*4 bytes). The only other thing I can imagine is some sort of limitation I am not thinking of... such as declaring it statically.

orgcandman · 01-26-2005, 12:59 PM

first off, I'd use a dynamically allocated array. The static array will make your binary bloated like crazy (if an int is defined as 32 bits, you have 128000000 bits allocated by the compiler, meaning 16,000,000 bytes. That's a BIG binary for such small code)

int **i = new int[2000][2000];

or something like that ( I'm somewhat hazy on how to do a multi-dimensional array in C++)

Also, I think that you're trying to addres a memory region that's way to large (think of 2000 * 2000, you get 4000000 byte address. This is more than most systems can address if my math is correct, which it probably isn't as I'm doing this back-of-the-envelope.)

Therefore, yes there's a limitation, but it's hardware related not software related.

-Aaron

Hivemind · 01-26-2005, 02:13 PM

The size of an array does nothing to the size of the executable. However, an array that large is simply too big to be allocated on the stack on most systems. Allocate it dynamically or, probably better, use a container from the C++ standard library that handles the dynamic allocation for you. A std::vector for example.
And btw, don't include iostream.h, include iostream. iostream.h is not part of standard C++.

jlliagre · 01-26-2005, 02:22 PM

Put your array in the static area by prefixing it with the static keyword:

Code:

static int i[2000][2000];

Without doing it, it goes to the heap, which is limited in size by the linker (can be something like 1 megabyte) and is not suitable for storing large variables.

Be aware that your function is no more reentrant after that.

Matir · 01-26-2005, 02:26 PM

Best of all, do:

Code:

int **array=malloc(2000*2000*sizeof(int));

or something similar. or use the fancy "new" keyword in C++.

(for those who say malloc is not C++ enough, that may be true, but it's still functional)

Hivemind · 01-26-2005, 02:43 PM

Don't use malloc()/free() in C++, it doesn't know about constructors and destructors. For more details, read Meyers.

Matir · 01-26-2005, 03:20 PM

malloc/free is fine if you're not doing it to objects. and what is Meyers?

Hivemind · 01-26-2005, 04:50 PM

malloc and free is fine in C, in C++ use new and delete.
Scott Meyers has written very goo C++ books, the "Effective C++"-series.

bigfatdud · 01-26-2005, 05:07 PM

Thanks a bunch for all the help.

Cheers to all.
Dud

thadeu · 01-26-2005, 05:39 PM

I learn recently an way to create/destroy dynamic array using new/delete, as example:

// creating an int NxN array
int N = 1000;
int **p;
p = new int*[N];
for( int i = 0; i < N; i++ )
{
p[i] = new int[N];
for( int j = 0; j < N; j++ )
p[i][j] = 0;
}

...

// destoying the array
for( int i = 0; i < N; i++ )
delete [] p[i];
delete [] p;

Matir · 01-26-2005, 08:11 PM

Does:

Code:

int **array=new int[1000][1000];

work as expected?

kees-jan · 01-27-2005, 03:57 AM

Short answer: Probably no (depends on what you expect, though).

the problem is that with this code, array[x][y] cannot be properly computed, because int** has insufficient information about array sizes.

What happens under water is that to find the proper memory address of array[x][y], the compiler computes something like

Code:

x*sizeof(array[0]) + y*sizeof(array[0][0])

In order to work as expected, sizeof(array[0]) should equal 1000*sizeof(int), which is 4000. However, since array is of type int**, sizeof(array[0]) equals sizeof (int*), which is 4. Hence the wrong array element will be accessed.

Groetjes,

Kees-Jan

deiussum · 01-27-2005, 08:09 AM

Not only that, you will also get a compiler error.

error: cannot convert `int (*)[1000]' to `int**' in initialization

To create a multidimensional array dynamically, you have to first initialize the pointer array, then initialize memory for each pointer in that array. This isn't quite the same as a static multidemensional array because it is not likely to be a contiguous block of memory.

Another option is to just initialize a contiguous block of memory for a single dimension array and index it appropriately. (e.g. index = x + y*width; )

jim mcnamara · 01-27-2005, 11:19 AM

There are probably stack size limits enforced. SIGSEGV is sent when those limits are turned on and you blow past them. You can check to see with something like this:

Code:

#include <sys/time.h>
#include <sys/resource.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

/* macro - check return codes for (-1) */
#define ckEOF(z)\
if( (z)==EOF)\
{ \
    perror("Fatal error"); \
    exit(EXIT_FAILURE); \
}
void print_limit(rlim_t  value)
{
    if(value==RLIM_INFINITY)
    {
    	fprintf(stdout,"%s\n","Infinite");
    }
    else
    {
    	fprintf(stdout,"%u\n",value);
    }
}

/* show the current hard & soft limits, current usage for a resource */
void showlimit(int resource)
{
    struct rlimit lim;
    struct rusage r_usage;
    long usage=0;
    char what_limit[32]={0x0};
    char tmp[24]={0x0};
    
    ckEOF(getrlimit(resource, &lim));
    ckEOF(getrusage(RUSAGE_SELF, &r_usage));

    switch(resource)
    {
      case RLIMIT_STACK:
           strcpy(what_limit,"Stack size -");
           usage+=r_usage.ru_isrss;               /* integral unshared stack " */
           break;
      case RLIMIT_AS:
           usage+=r_usage.ru_ixrss;               /* integral shared memory size */
           usage+=r_usage.ru_idrss;               /* integral unshared data " */
           usage+=r_usage.ru_isrss;               /* integral unshared stack " */      
           strcpy(what_limit,"All memory segments -");
           break;
      case RLIMIT_DATA:   
           usage+=r_usage.ru_idrss;               /* integral unshared data " */   
           strcpy(what_limit,"Data segment size -"); 
           break;
      default:
           break;
    
    }   	
    fprintf(stdout,"%22s hard limit    ",what_limit);
    print_limit(lim.rlim_max);
    fprintf(stdout,"%22s soft limit    ",what_limit);
    print_limit(lim.rlim_cur);
    if(usage==0)
    {
        strcpy(tmp,"not implemented");
    }
    else
    {
      	sprintf(tmp,"%-12d",usage);
    }       

    fprintf(stdout,"%22s Current usage %s\n"," ", tmp);    
}
       
int main(int argc, char *argv[])
{
    showlimit(RLIMIT_STACK);
    showlimit(RLIMIT_DATA);
    showlimit(RLIMIT_AS);
    return 0;
}