LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (http://www.linuxquestions.org/questions/programming-9/)
-   -   Array size in C++ (http://www.linuxquestions.org/questions/programming-9/array-size-in-c-673742/)

Mr Tummyfluff 10-02-2008 09:11 AM

Array size in C++
 
I'm writing an algorithm to do a bit of signal processing. Nothing particularly complicated, just need to be able to handle a large volume of data and funny input file format.

Gist of it is, the huge amount of input is sytematically read a bit at a time a remapped into an array in memory, defined as:

Code:

float modl[nz][nx1][nx2];
All was working fine until I tried to read in a real world sized data set. Then I get a Segmentation Fault when I try to define an array greater than [3001]*[1047]*[1]. And it's definately faulting at the point of the array definition because I have a printf statement straight after which doesn't get run. I find this somewhat confusing, for two reasons:

1.If it was a memory allocation error I'd expect to recieve a malloc error rather than a Segmentation Fault.

2.Estimating the amount memory the array should require as sizeof(float)*[3001]*[1047]*[1], I find it to be in the 3 Mb ball park. Since I'm running on a machine with 4 Gb of memory this really shouldn't be a problem!

Yet, if I decrease the size of the array being defined, it works fine! :(

Anyone any ideas? All help appeciated greatly!

David1357 10-02-2008 10:23 AM

Quote:

Originally Posted by Mr Tummyfluff (Post 3298020)
1.If it was a memory allocation error I'd expect to recieve a malloc error rather than a Segmentation Fault.

You will receive a segmentation fault if you allocate the memory on the stack. See this poor guy's post for an example of the same problem.

Quote:

Originally Posted by Mr Tummyfluff (Post 3298020)
2.Estimating the amount memory the array should require as sizeof(float)*[3001]*[1047]*[1], I find it to be in the 3 Mb ball park. Since I'm running on a machine with 4 Gb of memory this really shouldn't be a problem!

Your estimate is wrong. sizeof(float) is usually 4, so you would get

4 x 3001 x 1047 x 1 = 12,568,188 = 12M (in Microsoft math)

As you will see from the post mentioned above, the default stack limit is 8M.

Mr Tummyfluff 10-02-2008 12:36 PM

Thanks David you're a star..but can I beg one more question!

I hadn't realised there was a memory limit on how big an array you can define on the stack, so I'm now using calloc() to assign the memory and fill it with zeroes. When I want to write to that bit of memory, I shouldn't I just do as below?

Code:

float *modl = calloc ((nz*nx1*nx2),sizeof(float));

for(ix1=0; ix1<nx1; ix1++){
  for(ix2=0; ix2<nx2; ix2++){
    for(iz=0; iz<nz; iz++){
      modl[iz+nz*(ix1+nx2*ix1)] += data[it];
    }
  }
}

This compiles fine, but again gives a Segementation Fault. Sorry, bit of a C noob! ;)

Mark

PS. Yeah, maybe I forgot to multiply by 4 for sizeof(float). Doh!

David1357 10-02-2008 02:38 PM

Quote:

Originally Posted by Mr Tummyfluff (Post 3298206)
Thanks David you're a star...but can I beg one more question!

I give the glory to God.

I stuck in some suggestions as comments in your code below:

Quote:

Originally Posted by Mr Tummyfluff (Post 3298206)
Code:

float *modl = calloc ((nz*nx1*nx2),sizeof(float));

// Insert a check for a NULL return here, e.g.
if (!modl)
{
    printf("ERROR: Could not allocate memory\n");
    exit(1);
}

for(ix1=0; ix1<nx1; ix1++){
  for(ix2=0; ix2<nx2; ix2++){
    for(iz=0; iz<nz; iz++){
      int index = iz+nz*(ix1+nx2*ix1);
      // Print out your calculated index here to verify your math
      printf("index = %d\n");
      // Comment this out until you have verified your index math
//      modl[iz+nz*(ix1+nx2*ix1)] += data[it];
    }
  }
}

// Add some code here to free your memory, or you will leak 12M
free(modl);


Build it with those changes and check your index math first.

ta0kira 10-02-2008 02:58 PM

Quote:

Originally Posted by Mr Tummyfluff (Post 3298020)
And it's definately faulting at the point of the array definition because I have a printf statement straight after which doesn't get run.

This isn't a reliable indicator unless the buffer gets flushed right after the printf call. In theory, standard output is supposed to be line-buffered (meaning a flush is performed after \n,) but that isn't always the case. Just for future reference! Also, you might consider using an mmaped file to prevent page faults, possibly speeding things up a little.
ta0kira

dmail 10-03-2008 05:21 AM

std::vector anyone?

David1357 10-03-2008 08:16 AM

Quote:

Originally Posted by dmail (Post 3298866)
std::vector anyone?

We had some problems at work using GCC's std::vector class. We could only add 4 elements before it threw an exception.

dmail 10-03-2008 08:22 AM

Quote:

Originally Posted by David1357 (Post 3298964)
We had some problems at work using GCC's std::vector class. We could only add 4 elements before it threw an exception.

Maybe you could give some info (I don't know if you have an NDA), but I would really like to see code that does that. gcc version, element type and its structure (ie copy constructor, assignment operator, default constructor) code sample, what exception etc.

David1357 10-03-2008 08:42 AM

Quote:

Originally Posted by dmail (Post 3298968)
Maybe you could give some info (I don't know if you have an NDA), but I would really like to see code that does that. gcc version, element type and its structure (ie copy constructor, assignment operator, default constructor) code sample, what exception etc.

Sorry, it was std::list, and the method was push_back. When we tried to push_back the fifth element, it threw an exception.

sundialsvcs 10-03-2008 09:07 AM

What I'm wondering about is this... do you really have 12 million equal possibilities? Whenever this program runs for a while, is it really likely that every single one of those "[3001]*[1047]*[1]" buckets will be full?

Or could the actual data-distribution be sparse?

In the latter case, what if you consider the "address" of the input to be a 3-tuple, where the range of values in this particular case is ([0..3001], [0..1047], [0..1]) but might be somewhat smaller or larger the next time the program is run.

So, what you use for the storage in this case is a hash table. The values are stored in the hash-table using a 3-tuple as a hash key.

The advantage of this approach is that, as memory is allocated for the hash-table as it grows, that memory will tend to be fairly contiguous even though the distribution of key-values might not. Let's say for instance that you take-in about a hundred-thousand unique numbers in a particular run. The hash-table will have grown to about a hundred-thousand entries, stored in a few more-or-less contiguous megabytes of virtual storage, and it will have done this no matter how widely scattered the key-values might have been.

This will prevent the problem that would otherwise bring your program to its knees: thrashing. By pre-determining the location in virtual storage where each value is to be placed, you potentially force the application to suffer a page-fault for every hit, if the key-value distribution is widely scattered.

Thrashing can easily destroy your program, causing runs to take many hours or days... that ought to take seconds.

Bright(!) Idea... If you have any opportunity to exercise any sort of control over how the data is presented to you (i.e. if it's in a static file rather than coming in real-time), you can radically improve the situation by sorting the values first. Extract them from the funny input file, dump them into a temporary file in an easy-to-use format, and disk-sort that file.

In doing so, you just might eliminate the need for "random access" altogether: identical data-points are now adjacent in the file. Gaps can be found by comparing "this record" to "the previous one." And sorting is an unexpectedly-fast algorithm. A 12 or even 120-megabyte file is "no big deal."

"That's how they did it with punched cards," and the technique still works today!


All times are GMT -5. The time now is 03:41 AM.