Too many array elements?

[Elliander]

Hi, I am having an odd problem with my arrays. At present, I am creating the arrays in main and then passing them to other functions to do work on them and then returning their pointers so I can read them. In effect, this test works:

#include <iostream>
#include <array>
using namespace std;


//constants
const int _100k = 100000;
const int _200k = 200000;
const int _300k = 300000;
const int _400k = 400000;
const int _500k = 500000;
 
int* sequentialFillArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        arr[i] = i + 1;
    }

    return arr;
}


int main()
{
   
 // Initialize the 10 arrays:

    int arr100k_random[_100k];
    int arr100k_sequential[_100k];
    int arr200k_random[_200k];
    int arr200k_sequential[_200k];
    int arr300k_random[_300k];
    int arr300k_sequential[_300k];
    int arr400k_random[_400k];
    int arr400k_sequential[_400k];
    int arr500k_random[_500k];
    int arr500k_sequential[_500k];

    // sequentially fill the 5 sequential arrays:

    sequentialFillArray(arr100k_sequential, _100k);
    //sequentialFillArray(arr200k_sequential, _200k);
    //sequentialFillArray(arr300k_sequential, _300k);
    //sequentialFillArray(arr400k_sequential, _400k);
    //sequentialFillArray(arr500k_sequential, _500k);

// testing:
    for (int i = 0; i < _100k; i++)
    {
        cout << arr100k_sequential[i] << endl;
    }

    cout << "I get here!" << endl;

    system("pause");


return 0;
}

The output of the test prints out 1 - 100,000 exactly as I need it to. If I uncomment the 200k array it still works, but once I uncomment the 300k the program crashes on load. No errors, it just doesn't work. I thought it might be a limitation of CODE::BLOCKS so I tried running the built application, but I run into the same problem.

Now, if I reduce the array elements by a factor of 10 in the constants, everything works so I know there isn't otherwise a problem with my code. Even here I run into a problem though.

The following code runs just fine:

[code]
#include <iostream>
#include <array>
using namespace std;

//constants
const int _100k = 10;
const int _200k = 20;
const int _300k = 30;
const int _400k = 40;
const int _500k = 50;


int* sequentialFillArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        arr[i] = i + 1;
    }

    return arr;
}

int* randomFillArray(int arr[], int size)
{
    // Need to fill the array sequentially before it can be shuffled
    sequentialFillArray(arr, size);

    // Now we shuffle the array elements at random
    for (int i = 0; i < size; i++)
    {
        //int j = rand()%i;
        //int temp = arr[j];
        //arr[i] = arr[j];
        //arr[j] = temp;
    }


    return arr;
}

int main()
{
    // Initialize the 10 arrays:

    int arr100k_random[_100k];
    int arr100k_sequential[_100k];
    int arr200k_random[_200k];
    int arr200k_sequential[_200k];
    int arr300k_random[_300k];
    int arr300k_sequential[_300k];
    int arr400k_random[_400k];
    int arr400k_sequential[_400k];
    int arr500k_random[_500k];
    int arr500k_sequential[_500k];

    // sequentially fill the 5 sequential arrays:

    sequentialFillArray(arr100k_sequential, _100k);
    sequentialFillArray(arr200k_sequential, _200k);
    sequentialFillArray(arr300k_sequential, _300k);
    sequentialFillArray(arr400k_sequential, _400k);
    sequentialFillArray(arr500k_sequential, _500k);

     // randomly fill the 5 random arrays:

    randomFillArray(arr100k_random, _100k);
    randomFillArray(arr200k_random, _200k);
    randomFillArray(arr300k_random, _300k);
    randomFillArray(arr400k_random, _400k);
    randomFillArray(arr500k_random, _500k);


    // testing:
    for (int i = 0; i < _500k; i++)
    {
        cout << arr500k_sequential[i] << endl;
    }

    cout << "I get here!" << endl;

    system("pause");


	return 0;
}

But as soon as I uncomment the for loop within:

int* randomFillArray(int arr[], int size)

it crashes again. Even with those few elements!

My computer is fairly powerful, so it should be able to handle what I am doing. I just don't understand why it can't seem to. Looking at the task manager, it's not like my CPU goes above 14% and my RAM remains at 40% with most of the system resources going to web browsers so I don't see how the program is breaing anything. I am running in Windows 10 if it helps.

What can I do to have all the array elements I need?

[Ganado]

The stack is not very large. You're allocating too much with all your arrays. Use the heap instead, either by making your arrays global (defined outside main()), or by using a std::vector or new[]/delete[]. I recommend a std::vector.

PS: You technically should not start variables with an underscore at the global scope; it's reserved.

[jonnin]

you can change the stack size to hold quite a bit. I don't know the limits, but maybe, maybe not on this program. Generally bad idea to run so much on the stack, and you also don't want to dance on the edge of full since function calls etc need some. Its in your compiler options somewhere, not a code thing.

[Elliander]

There appear to be similar issues running on your web based compiler. The following code will run on http://cpp.sh/ (but not my computer)

#include <iostream>
#include <array>
using namespace std;


//constants
const int _100k = 100000;
const int _200k = 200000;
const int _300k = 300000;
const int _400k = 400000;
const int _500k = 500000;
 
int* sequentialFillArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        arr[i] = i + 1;
    }

    return arr;
}

int* randomFillArray(int arr[], int size)
{
    // Need to fill the array sequentially before it can be shuffled
    sequentialFillArray(arr, size);

    // Now we shuffle the array elements at random
    for (int i = 0; i < size; i++)
    {
        //int j = rand()%i;
        //int temp = arr[j];
        //arr[i] = arr[j];
        //arr[j] = temp;
    }


    return arr;
}


int main()
{
   
 // Initialize the 10 arrays:

    int arr100k_random[_100k];
    int arr100k_sequential[_100k];
    int arr200k_random[_200k];
    int arr200k_sequential[_200k];
    int arr300k_random[_300k];
    int arr300k_sequential[_300k];
    int arr400k_random[_400k];
    int arr400k_sequential[_400k];
    int arr500k_random[_500k];
    int arr500k_sequential[_500k];

    // sequentially fill the 5 sequential arrays:

    sequentialFillArray(arr100k_sequential, _100k);
    sequentialFillArray(arr200k_sequential, _200k);
    sequentialFillArray(arr300k_sequential, _300k);
    sequentialFillArray(arr400k_sequential, _400k);
    sequentialFillArray(arr500k_sequential, _500k);
    
    // randomly fill the 5 random arrays:

    randomFillArray(arr100k_random, _100k);
    randomFillArray(arr200k_random, _200k);
    //randomFillArray(arr300k_random, _300k);
    //andomFillArray(arr400k_random, _400k);
    //randomFillArray(arr500k_random, _500k);

// testing:
    for (int i = 0; i < _100k; i++)
    {
        cout << arr100k_sequential[i] << endl;
    }

    cout << "I get here!" << endl;

    system("pause");


return 0;
}

Now, if I reduce the size of the constants by a factor of 10 the following code will run on your web based compiler (and it will also run on my computer)

#include <iostream>
#include <array>
using namespace std;


//constants
const int _100k = 10000;
const int _200k = 20000;
const int _300k = 30000;
const int _400k = 40000;
const int _500k = 50000;
 
int* sequentialFillArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        arr[i] = i + 1;
    }

    return arr;
}

int* randomFillArray(int arr[], int size)
{
    // Need to fill the array sequentially before it can be shuffled
    sequentialFillArray(arr, size);

    // Now we shuffle the array elements at random
    for (int i = 0; i < size; i++)
    {
        //int j = rand()%i;
        //int temp = arr[j];
        //arr[i] = arr[j];
        //arr[j] = temp;
    }


    return arr;
}


int main()
{
   
 // Initialize the 10 arrays:

    int arr100k_random[_100k];
    int arr100k_sequential[_100k];
    int arr200k_random[_200k];
    int arr200k_sequential[_200k];
    int arr300k_random[_300k];
    int arr300k_sequential[_300k];
    int arr400k_random[_400k];
    int arr400k_sequential[_400k];
    int arr500k_random[_500k];
    int arr500k_sequential[_500k];

    // sequentially fill the 5 sequential arrays:

    sequentialFillArray(arr100k_sequential, _100k);
    sequentialFillArray(arr200k_sequential, _200k);
    sequentialFillArray(arr300k_sequential, _300k);
    sequentialFillArray(arr400k_sequential, _400k);
    sequentialFillArray(arr500k_sequential, _500k);
    
    // randomly fill the 5 random arrays:

    randomFillArray(arr100k_random, _100k);
    randomFillArray(arr200k_random, _200k);
    randomFillArray(arr300k_random, _300k);
    randomFillArray(arr400k_random, _400k);
    randomFillArray(arr500k_random, _500k);

// testing:
    for (int i = 0; i < _100k; i++)
    {
        cout << arr100k_sequential[i] << endl;
    }

    cout << "I get here!" << endl;

    system("pause");


return 0;
}

But if I uncomment the for loop in the above code it won't run on my computer or in a web based compiler even if I also use the following constants:

const int _100k = 1;
const int _200k = 2;
const int _300k = 3;
const int _400k = 4;
const int _500k = 5;

I'm not sure how to get around this.

[Ganado]

for (int i = 0; i < size; i++)
{
        int j = rand()%i;

This is dividing by 0 on the first iteration (assuming uncommented).

Sometimes cpp.sh is screwy, so I wouldn't rely on it. It does not crash for me when the sizes are 1 ... 5.

[lastchance]

I can't see it liking rand()%i when i=0

[Elliander]

@Ganado

I'm not experienced with vectors. What makes them different?

The only reason why I started the variables with an underscore is because the compiler wouldn't let them start with a number.

@jonnin How would I increase the stack size in Code::Blocks using GNU CCC Compiler for C++ 11 ?

...

I see the divide by zero issue! But if I use a + 1 here I wouldn't be able to swap the 0th element, right? So the first element would always be 1.

EDIT: Looks like I should be using SIZE instead if i there, like so:

int* randomFillArray(int arr[], int size)
{
    // Need to fill the array sequentially before it can be shuffled
    sequentialFillArray(arr, size);

    // Now we shuffle the array elements at random
    for (int i = 0; i < size; i++)
    {
        int j = rand() % size;
        int temp = arr[j];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    return arr;
}

That results in the correct output when I test it like so:

for (int i = 0; i < _100k; i++)
    {
        cout << arr100k_random[i] << endl;
    }

But I am still limited in how many arrays I can run, so I need to either increase the size of the stack or I guess delete the arrays after I am done with them, one at a time.

[thmm]

A simple demo about std::vector:

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

const int _500k = 500'000;

std::vector<int> sequentialFillVector(size_t size)
{
    std::vector<int> v(size);
    
    for (size_t i = 0; i < size; i++)
    {
        v[i] = i + 1;
    }

    return v;
}

std::vector<int> randomFillVector(size_t size)
{
    std::vector<int> v = sequentialFillVector(size);
    std::random_shuffle(v.begin(), v.end());
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(v.begin(), v.end(), g);

    return v;
}


int main()
{
    std::vector<int> v = randomFillVector(_500k);
    
    for (int i: v)
        std::cout << i << '\n';
} 

Only the amount of RAM limits the size or number of vectors you can have.

[George PlusPlus]

Instead of doing a manual sequential fill of a container, why not use <numeric>'s std::iota?
https://en.cppreference.com/w/cpp/algorithm/iota

Lines 12-15 could be (starting at 1): std::iota(v.begin(), v.end(), 1);

[George PlusPlus]

Interesting example of using unnamed temporaries in std::shuffle at the link for std::iota above:
std::shuffle(v.begin(), v.end(), std::mt19937{std::random_device{}()});

[mbozzi]

Interesting example of using unnamed temporaries in std::shuffle at the link for std::iota above:

I'm only here to offer the obligatory warning about seeding a random number generator with 19937 bits of salient state using only 32 random bits.

[jonnin]

@jonnin How would I increase the stack size in Code::Blocks using GNU CCC Compiler for C++ 11 ?

in the nicest possible way, you start by loading up the google web page.

then you get stuff like
https://stackoverflow.com/questions/2275550/change-stack-size-for-a-c-application-in-linux-during-compilation-with-gnu-com
or
https://codeforces.com/blog/entry/79

which say stuff like:
--stack=268435456
or the risky
ulimit -s unlimited


again, I think you have too much anyway. This is useful on occasion, but the right answer is almost always to move it off the stack.

[George PlusPlus]

mbozzi wrote:

I'm only here to offer the obligatory warning about seeding a random number generator with 19937 bits of salient state using only 32 random bits.

If'n you want to quibble about that go mention it to the folks at cppreference, that is their code snippet.

That snippet is still a hell of a better situation, using <random> vs. srand/rand in new C++ code.

I prefer using std::default_random_engine when I don't need fine granular control the other engines provide. For most purposes it suffices more than adequately. And out-performs the C random generator.

Elliander wrote:

either increase the size of the stack or I guess delete the arrays after I am done with them

Really easy is to use the C++ containers that manage the memory for you. std::vector, for example, is a runtime variable sized array. To do that with a regular array requires manual memory management.
https://en.cppreference.com/w/cpp/container/vector

See also: https://www.learncpp.com/cpp-tutorial/an-introduction-to-stdvector/

[thmm]

George P

Instead of doing a manual sequential fill of a container, why not use <numeric>'s std::iota?

I forgot about std::iota and when I remembered I was too lazy to change the code.

[againtry]

Sounds like memory management is a problem combined with a function that appears not to make much sense. Assuming(?) that's true, and without bothering about delete[]'s, the following runs without a problem.

#include <iostream>

//constants
const int k100 = 100000;
const int k200 = 200000;
const int k300 = 300000;
const int k400 = 400000;
const int k500 = 500000;

void sequentialFillArray(int* arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        arr[i] = i + 1;
    }
}

int main()
{
    
    // Initialize the 10 arrays:
    int* arr100k_random = new int[k100];
    int* arr100k_sequential = new int[k100];

    int* arr200k_random = new int[k200];
    int* arr200k_sequential = new int[k200];

    int* arr300k_random = new int[k300];
    int* arr300k_sequential = new int[k300];

    int* arr400k_random = new int[k400];
    int* arr400k_sequential = new int[k400];
    
    int* arr500k_random = new int[k500];
    int* arr500k_sequential = new int[k500];
    
    // sequentially fill the 5 sequential arrays:
    sequentialFillArray(arr100k_sequential, k100);
    sequentialFillArray(arr200k_sequential, k200);
    sequentialFillArray(arr300k_sequential, k300);
    sequentialFillArray(arr400k_sequential, k400);
    sequentialFillArray(arr500k_sequential, k500);
    
    // testing:
    for (int i = 0; i < k500; i++)
    {
        std::cout << arr500k_sequential[i] << '\n';
    }
    
    std::cout << "I get here!\n";
    
    return 0;
}

[seeplus]

In general, it's not a good idea to try to hold a large amount of data in stack memory. The amount that can be stored here is limited. If you don't want to use a dynamic container (such as a heap), then either make the data global (again not a good idea) or mark the variable as static. This creates the data elsewhere to the stack where the stack limit doesn't apply.

[George PlusPlus]

thmm wrote:

I forgot about...

Welcome to my "world."

I more often than not have a vague idea of some std library construct I used and have to go hunting for it. I remembered I had some saved test of <random> (I do a lot of that) for simulating a deck of cards that used std::iota.

Originally seen here: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3551.pdf (page 10).