Understanding the amount of memory c++ is allocating

Question

I'm trying to develop a better understanding of the amount of memory that is allocated on the heap in c++. I've written a small test program which basically does nothing else than fill a number of 2D vectors. I'm running this on a linux 64bit VM and use valgrind's massif tool in order to profile the memory.

The environment I'm running this test on: Linux VM running in VirtualBox on Win10. VM configuration: Base memory: 5248MB, 4CPU's, cap At 100%, disk-type VDI (dynamically alocated storage).

c++ memory profiling test program:

/**
 * g++ -std=c++11 test.cpp -o test.o
 */

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int main(int argc, char **arg) {
    int n = stoi(arg[1]);
    vector<vector<int> > matrix1(n);
    vector<vector<int> > matrix2(n);
    vector<vector<int> > matrix3(n);
    vector<vector<int> > matrix4(n);
    vector<vector<int> > matrix5(n);
    vector<vector<int> > matrix6(n);
    vector<vector<int> > matrix7(n);
    vector<vector<int> > matrix8(n);

    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            matrix1[i].push_back(j);
        }
    }

    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            matrix2[i].push_back(j);
        }
    }

    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            matrix3[i].push_back(j);
        }
    }

    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            matrix4[i].push_back(j);
        }
    }

    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            matrix5[i].push_back(j);
        }
    }

    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            matrix6[i].push_back(j);
        }
    }

    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            matrix7[i].push_back(j);
        }
    }

    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            matrix8[i].push_back(j);
        }
    }
}

I run the following bash script in order to extract memory profiles at different values of n (test.o is the program above, compiled with g++ -std=c++11, g++ is version 5.3.0)

valgrind --tool=massif --massif-out-file=massif-n1000.txt ./test.o 250
valgrind --tool=massif --massif-out-file=massif-n1000.txt ./test.o 500
valgrind --tool=massif --massif-out-file=massif-n1000.txt ./test.o 1000
valgrind --tool=massif --massif-out-file=massif-n2000.txt ./test.o 2000
valgrind --tool=massif --massif-out-file=massif-n4000.txt ./test.o 4000
valgrind --tool=massif --massif-out-file=massif-n8000.txt ./test.o 8000
valgrind --tool=massif --massif-out-file=massif-n16000.txt ./test.o 16000
valgrind --tool=massif --massif-out-file=massif-n32000.txt ./test.o 32000

This gives me the following results:

|--------------------------------|
| n     | peak heap memory usage |
|-------|------------------------|
| 250   | 2.1 MiB                |         
| 500   | 7.9 MiB                |
| 1000  | 31.2 MiB               |
| 2000  | 124.8 MiB              |
| 4000  | 496.5 MiB              |
| 8000  | 1.9  GiB               |
| 16000 | 6.2 GiB                |
| 32000 | 6.1 GiB                |
|--------------------------------|

Each matrix will be n^2 in size, I have a total of 8 matrices, hence I expected a memory usage to be around f(n) = 8 * n^2.

Question 1 From n=250 to n=8000, why is the memory usage more or less multiplied by 4 at n*=2 ?

From n=16000 to n=32000 something very strange is happening because valgrind actually reports a memory decrease.

Question 2 What is happening between n=16000 and n=32000, how can it be possible that heap memory is less, while in theory more data should be allocated?

See below the massif-visualizer output for n=16000 and n=32000.

Answer 1

1) Because the sizes of your matrix vectors (and thus their memory footprint) grow as n², so doubling n leads to quadrupling of memory usage. Any deviations from the exact relationship (as opposed to asymptotic) are due to different factors (e.g. metadata used by malloc / std::allocator, block size doubling method used by vector)

2) You are beginning to run out of memory, so Linux is starting to page some; use --pages-as-heap=yes if you want to see the total (active + paged) memory usage. (Source: http://valgrind.org/docs/manual/ms-manual.html)