large arrays, std::vector and stack overflow

Question

I have a program that is reading data from large arrays, I initially divided the program in two separate projects in Visual Studio and each one separately worked fine, but when I tried to put them together the program acted funny skipping some steps while debugging. I'm very new on C++ so I started doing some research and I found that maybe I was filling the stack with those huge arrays and that I should try to put them on the heap instead.

I decided to change each of the arrays for a std::vector and initialize them this way:

std::vector<double> meanTimeAO = { 0.4437, 0.441, 0.44206, 0.44632, 0.4508, 0.45425,...}

But after changing all of the arrays now when I try to compile the compiler crashes with a stack overflow, I thought I was liberating memory space from the stack by changing the arrays as a vector but it seems I had the opposite results, why is that??

and how should I deal with these big arrays? (they are fixed never changing values or size)

Answer 1

As @Ajay's answer and @Cornstalks comment correctly point out you can avoid the stack and the heap entirely by using a static or constexpr qualifier on your array

const static std::array<float, 1000000> a1 = {}; // OK
constexpr    std::array<float, 1000000> a2 = {}; // OK in C++11 onwards

This stores the array in the data initialized section of your memory (good explanation here). The const serves only to disallow modification of a1, and is not needed to avoid stack overflow. Variables declared as constexpr are also automatically const and hence do not need the qualifier.

Note: You can also achieve the effects of static by making your array(s) global variables, although I would not recommend this.

Program Stack Overflow

If your data is non-static you should use std::vector (or other kinds of heap allocated memory) when the number of elements is very large.

std::array<float, 1000000> a = {};   // Causes stack-overflow on 32-bit MSVS 2015
std::vector<float> v(1000000);       // OK

This is because the default stack size is ~1MB, and 1 million floats requires ~4MB. The size of the heap is limited by your system's available memory (RAM). More on the stack and heap here.

The downsides of std::vector are that it's a little slower than std::array(heap memory allocation, deallocation and access is all slower than that of the stack), and that it's not a fixed size. However you can declare your std::vector as const to prevent yourself (or someone else) from accidentally altering its size or elements.

const std::vector<float> v = {...}; 

Now as to why your std::vectors are causing stack overflows is a bit of a mystery. However while std::vector allocates its elements on the heap, it also allocates a pointer (4 Bytes on 32-bit and 8-Bytes on 64-bit) on the stack. So if you have over ~250,000 std::vectors all in scope at once, this will also cause a stack-overflow (or ~125,000 on 64-bit systems).

Compiler Stack Overflow

The compiler, like any program, allocates memory - some of which will be on the stack. The official error for a compiler stack overflow on MSVC is Fatal Error C1063.

Given that your debugger is behaving oddly, my advice would be to try and isolate the problematic code by manually splitting your code up into modular units and compiling them individually. It's possible that a small amount of code could be responsible for the error, by eating up lots of stack e.g. by recursively generating a large number of functions.

Alternatively, it may be that your code is so inherently complicated that it naturally requires more memory than the stack has. In which case, splitting your code up will still be of benefit but you could also try increasing the default stack size of MSVC.

Improving Your Code

To improve your code you could try splitting your data up into chunks. For example you could: read in ~256 KB worth of the array, process it, write the array back to file, then move onto to the next 256 KB. You could further choose the size of the chunk to be less than the size of your L1 cache (so it could all be stored at once) which would improve performance by minimizing cache misses.

Notes

1. MSVS 2015 (update 2) produces an internal compiler error when compiling

   #include "stdafx.h"
   #include <array>
   int main()
   {
        constexpr std::array<int, 1000000> a = {};
        return 0;
   }
   

   The static const variant works fine, and if I move a outside main (making it a global variable) then it also works fine.

2. Not having a chkstk.asm is unusual. Mine is located at C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\crt\src\i386\chkstk.asm. If you're missing it, then maybe try reinstalling MS Visual Studio.

Answer 2

If the array is of fixed size, and its elements don't change, there is no real need to use vector. You could use std::array, array of const or constexpr instead.

constexpr float meanTimeAO[] = { 0.4437f, 0.441f, 0.44206f, 0.44632f, 0.4508f, 0.45425f,...}

Answer 3

Pointing out maybe a couple things overlooked in the above answers:

1. "program acted funny skipping some steps while debugging". OP, can you provide some more details on what you mean? Perhaps, you were debugging a release build, and as you step through the code you observe that the line of code being executed is not the one you expect to execute next (which is perfectly correct behaviour for a release build with compiler optimisations).

2. The question stated that the compiler crashed with a stack overflow. Not the executed program. So the problem is a compiler problem. Sure, changing the code might make the compiler not crash, but the comment above about allocating std::vector on the stack is unrelated to what might cause the compiler to crash.

Suggestions: you could try seeing if there are any known bugs in the version of compiler you are using (i.e. see if your compiler vendor has released a more recent version which might address the compiler crashing).

Also, specifically picking up on your "they are never changing in value or size" comment, try putting your data into static const double arrays, rather than std::vectors (or even linked lists). An unchanging statically-allocated readonly linked list is sortof a waste of time when you probably should just use double[] . static const data is initialized at compile/link time rather than runtime, and exists in its own memory area (neither stack nor heap, strictly speaking).