Stack overflow on std::array class

Question

I used to do some C# and Java, but lately I wanted to learn c++ as well as I found out many large company prefer c++ for its efficiency.

Trying to get used to the syntax and behaviour of C++, I started to translate the test I done in Java to C++ code, and the following is one of them:

#include "stdafx.h"
#include <iostream>
#include <array>
#include <string>
#include <cstring>
#include <chrono>
using namespace std;
using namespace std::chrono;

typedef array<array<int, 1000>, 1000> aArray;

aArray hasLocality(aArray, aArray);
aArray noLocality(aArray, aArray);

static aArray a = aArray();
static aArray b = aArray();

int main() {

    for (size_t i = 0; i < 100; i++)
    {
        for (size_t j = 0; j < 100; j++)
        {
            a[i][j] = i + j;
            b[i][j] = i + j;
        }
    }
    hasLocality(a, b);
    noLocality(a, b);
    system("pause");
    return 0;
}

aArray hasLocality(aArray a, aArray b) {
    milliseconds startTime = duration_cast<milliseconds>(
        system_clock::now().time_since_epoch()
        );
    aArray ans = aArray();
    for (size_t i = 0; i < ans.size(); i++)
    {
        for (size_t k = 0; k < ans[0].size(); k++)
        {
            for (size_t j = 0; j < ans[0].size(); j++)
            {
                ans[i][j] = ans[i][j] + a[i][k] * b[k][j];
            }
        }
    }

    milliseconds endTime = duration_cast<milliseconds>(
        system_clock::now().time_since_epoch()
        );
    string time = std::to_string((endTime - startTime).count()) + "\n";
    cout.write(time.c_str(), (unsigned)strlen(time.c_str()));
    return ans;
}

aArray noLocality(aArray a, aArray b) {
    milliseconds startTime = duration_cast<milliseconds>(
        system_clock::now().time_since_epoch()
        );
    aArray ans = aArray();
    for (size_t i = 0; i < ans.size(); i++)
    {
        for (size_t j = 0; j < ans[0].size(); j++)
        {
            for (size_t k = 0; k < ans[0].size(); k++)
            {
                ans[i][j] = ans[i][j] + a[i][k] * b[k][j];
            }
        }
    }
    milliseconds endTime = duration_cast<milliseconds>(
        system_clock::now().time_since_epoch()
        );
    string time = std::to_string((endTime - startTime).count()) + "\n";
    cout.write(time.c_str(), (unsigned)strlen(time.c_str()));
    return ans;
}

This is one of my test on locality by doing simple matrix multiplication, however I can't get rid of stack overflow exception because of the excessive large array size, which I think is essential for the test.

I also thought the array would be placed on heap instead of stack as I put it as static.

At last, I found that the noLocality is more efficient than hasLocality when given a smaller array size (100, 100), was that abnormal or just insufficient amount of data for locality to take place?

Thanks in advance

Answer 1

In Java, all object arguments are passed by reference. In C++, the default is that they are passed by value (ie a copy is placed on the stack). So when you call:

aArray hasLocality(aArray a, aArray b)

You end up with a copy of a on the stack followed by a copy of b, and you also have space allocated for the return value, another copy of an aArray. You have 3 massive arrays allocated on the stack. This is different from Java.

In C++ you can avoid passing by value by using references or pointers. Java does not have pointers. Java references are not quite the same as C++ references, but there are similarities.

So if you have:

aArray hasLocality(aArray &a, aArray &b)

then you end up with something similar to Java, the arrays are passed by reference, same as in Java. Calls to hasLocality are no different. So just change hasLocality and noLocality in this way. You still have the return value copy. To avoid that, one thing you can do is pass in the return value as well:

void hasLocality(aArray &a, aArray &b, aArray &ans)

and then move

aArray ans = aArray();

outside the function.

At that point you'd have no array copying going on, just like Java. But do keep in mind references in C++ are a bit different, once a reference refers to an object, it cannot refer to any other object. Since you're new to C++ this might confuse you right now, but you'll learn. Note that C++ is more complicated than Java overall.