# correcting code for larger 2D arrays help

Discussion in 'C Programming' started by Dr Dav, May 30, 2007.

1. ### Dr DavGuest

Hello all, I'm a physicist whose rewriting a numerical simulation,
previously written in IDL, in C with the goal reducing runtime. As you
may imagine, my C programming skills are quite poor but I am learning.
My problem is this. I had sucessfully written a C code that worked
( with considerable speedup over the IDL version ) using an array size
of 100x100. However, I am working towards making the array size closer
to 300x300. Since I had defined 2D arrays in my code as

double array[nCols][nRows];

upon increasing nRows above approximately 250 with nCols = 100 the
program was segfaulting. After some reading I came to the conclusion
that I was creating arrays that were too big for the stack and should
instead be allocated memory on the heap? It's quite possible that i'm
very wrong here so please point out my mistakes. To allocate space on
the heap for the arrays, and for conveniance in array indexing, I
chose to replace the static array creation lines with a malloc call
like (found in the cfaq)

double **array = malloc ( nCols * sizeof ( *array ) );
array[0] = malloc ( nCols * nRows * sizeof ( **array ) );
for ( ii = 1; ii < nCols; ++ii )
array[ii] = array[0] + ii * nRows;

such that indexing the array may be done according to

for ( ii = 0; ii < nCols; ++ii )
{
for ( jj = 0; jj < nRows; ++jj)
{
array[ii][jj] = 0.0;
}
}

Now this also appeared to work. Upon altering the code to use the
malloc statement instead of the static [][] approach I tested the
outputs of the simultaion. They were fine up to a point where I had
converted most of the static array creation lines to the malloc method
above. However, trying to convert more caused a problem. Irrelevant of
which additional array I tried to allocate space for on the heap, the
simulation results would become rubbish. It does not appear to be a
problem with the simulation itself, since the problem occurs with
small array sizes as well which work fine using a static array
declaration, but rather with my poor attempt at memory management in
C. So my questions are:

1. Are arrays of size 300x300 large enough to overwhelm the space
available on the stack (if relevant my machine is an Intel Core 2 Duo
running linux)?

2. What is the standard approach to creating large 2D arrays, i.e., is
the approach I have chosen appropriate?

3. Is it possible I have allocated too many 2D arrays (perhaps 30 in
all) using the above malloc approach and that is the cause of my
simulation woes?

Any help would be great as my brain is slowly melting away.
Dav.

Dr Dav, May 30, 2007

2. ### Richard HeathfieldGuest

Dr Dav said:

<snip>
>
> 1. Are arrays of size 300x300 large enough to overwhelm the space
> available on the stack (if relevant my machine is an Intel Core 2 Duo
> running linux)?

Typical double on a modern desktop system, is 8 bytes. 8 * 300 * 300 is
a mere 720,000 bytes. Nowadays, that's peanuts for *dynamic*
allocation, but could easily cause problems with static allocation,
yes.

> 2. What is the standard approach to creating large 2D arrays, i.e., is
> the approach I have chosen appropriate?

If you got it from the FAQ, it should be fine (although I must admit
it's not how I'd have done it myself). I note, however, that your
example code doesn't ascertain whether the memory allocation succeeded.
Allocation requests can and *do* fail, so you should check to see
whether malloc gave you a null pointer rather than hope it didn't.

> 3. Is it possible I have allocated too many 2D arrays (perhaps 30 in
> all) using the above malloc approach and that is the cause of my
> simulation woes?

You may get more joy out of allocating smaller blocks, and allocating
more of them to compensate. Consider:

struct array_double_2d
{
size_t y;
size_t x;
double **data;
};

int ok = 1;
array_double_2d arr = { 300, 300 };
arr.data = malloc(arr.y * sizeof *arr.data);
if(arr.data != NULL)
{
size_t i = 0;
while(ok && i < arr.y)
{
arr.data = malloc(arr.x * sizeof *arr.data);
if(arr.data == NULL)
{
ok = 0;
}
}
}
else
{
ok = 0;
}

This allocates 300 blocks of (in your case) 2400 bytes, rather than one
great big block of 720000 bytes. *One* 720,000 byte block is no big
deal, but lots of them could become a problem. By splitting your
allocation request down into lots of much smaller requests, you make it
easier for the memory manager to satisfy those requests.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

Richard Heathfield, May 30, 2007

3. ### Keith ThompsonGuest

Richard Heathfield <> writes:
> Dr Dav said:
>
> <snip>
>>
>> 1. Are arrays of size 300x300 large enough to overwhelm the space
>> available on the stack (if relevant my machine is an Intel Core 2 Duo
>> running linux)?

>
> Typical double on a modern desktop system, is 8 bytes. 8 * 300 * 300 is
> a mere 720,000 bytes. Nowadays, that's peanuts for *dynamic*
> allocation, but could easily cause problems with static allocation,
> yes.

[big snip]

There are three storage durations, automatic, static, and allocated.

Automatic storage duration refers to objects declared locally within a
function or block (sometimes referred to as "stack"). Static storage
duration refers to objects that exist throughout the lifetime of the
program; they're declared with the keyword "static" or outside any
function. Allocated storage duration refers to objects allocated by
calls to malloc (or calloc, or realloc) (sometimes referred to as
"heap"),

An implementation is likely to place different limits on these three
kinds of storage duration; automatic duration often has the lowest
limit. As long as you can deal with the differing semantics,
switching from automatic to static storage duration *might* solve your
problem.

Some systems also provide ways to change memory allocation limits,
either system-wide or for a single process. <OT>On Unix-like systems,
see "limit" or "ulimit">,<OT>

Also, if the bounds of your arrays are constant and you choose to use
dynamic allocation (malloc), that can simplify your code. Many
examples of dynamic allocation of two-dimensional arrays are designed
to allow for both dimensions being determined at execution time. If
you know in advance that you want your arrays to be exactly 300 x 300,
you can use a single allocation. For example:

#include <stdio.h>
#include <stdlib.h>

#define MATRIX_SIZE 300
typedef double matrix[MATRIX_SIZE][MATRIX_SIZE];

int main(void)
{
matrix *m;
int i, j;
m = malloc(sizeof *m);
if (m) {
printf("Allocated %lu bytes\n", (unsigned long)sizeof *m);
}
else {
fprintf(stderr, "Allocation failed\n");
exit(EXIT_FAILURE);
}
for (i = 0; i < MATRIX_SIZE; i ++) {
for (j = 0; j < MATRIX_SIZE; j ++) {
(*m)[j] = i + j;
}
}
printf("(*m)[123][234] = %g\n", (*m)[123][234]);
return 0;
}

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson, May 30, 2007