title: Understanding the amount of memory c++ is allocating
body: <p>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.</p>
  
  <p>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).</p>
  
  <p>c++ memory profiling test program:</p>
  
  <pre><code>/**
   * g++ -std=c++11 test.cpp -o test.o
   */
  
  #include &lt;string&gt;
  #include &lt;vector&gt;
  #include &lt;iostream&gt;
  
  using namespace std;
  
  int main(int argc, char **arg) {
      int n = stoi(arg[1]);
      vector&lt;vector&lt;int&gt; &gt; matrix1(n);
      vector&lt;vector&lt;int&gt; &gt; matrix2(n);
      vector&lt;vector&lt;int&gt; &gt; matrix3(n);
      vector&lt;vector&lt;int&gt; &gt; matrix4(n);
      vector&lt;vector&lt;int&gt; &gt; matrix5(n);
      vector&lt;vector&lt;int&gt; &gt; matrix6(n);
      vector&lt;vector&lt;int&gt; &gt; matrix7(n);
      vector&lt;vector&lt;int&gt; &gt; matrix8(n);
  
      for (int i=0; i&lt;n; ++i) {
          for (int j=0; j&lt;n; ++j) {
              matrix1[i].push_back(j);
          }
      }
  
      for (int i=0; i&lt;n; ++i) {
          for (int j=0; j&lt;n; ++j) {
              matrix2[i].push_back(j);
          }
      }
  
      for (int i=0; i&lt;n; ++i) {
          for (int j=0; j&lt;n; ++j) {
              matrix3[i].push_back(j);
          }
      }
  
      for (int i=0; i&lt;n; ++i) {
          for (int j=0; j&lt;n; ++j) {
              matrix4[i].push_back(j);
          }
      }
  
      for (int i=0; i&lt;n; ++i) {
          for (int j=0; j&lt;n; ++j) {
              matrix5[i].push_back(j);
          }
      }
  
      for (int i=0; i&lt;n; ++i) {
          for (int j=0; j&lt;n; ++j) {
              matrix6[i].push_back(j);
          }
      }
  
      for (int i=0; i&lt;n; ++i) {
          for (int j=0; j&lt;n; ++j) {
              matrix7[i].push_back(j);
          }
      }
  
      for (int i=0; i&lt;n; ++i) {
          for (int j=0; j&lt;n; ++j) {
              matrix8[i].push_back(j);
          }
      }
  }
  </code></pre>
  
  <p>I run the following bash script in order to extract memory profiles at different values of <code>n</code> (test.o is the program above, compiled with g++ -std=c++11, g++ is version 5.3.0)</p>
  
  <pre><code>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
  </code></pre>
  
  <p>This gives me the following results:</p>
  
  <pre><code>|--------------------------------|
  | 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                |
  |--------------------------------|
  </code></pre>
  
  <p>Each matrix will be n^2 in size, I have a total of 8 matrices, hence I expected a memory usage to be around <code>f(n) = 8 * n^2</code>.</p>
  
  <p><strong>Question 1</strong> From n=250 to n=8000, why is the memory usage more or less multiplied by 4 at n*=2 ?</p>
  
  <p>From n=16000 to n=32000 something very strange is happening because valgrind actually reports a memory decrease. </p>
  
  <p><strong>Question 2</strong> 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?</p>
  
  <p>See below the massif-visualizer output for n=16000 and n=32000.</p>
  
  <p><a href="https://i.stack.imgur.com/igGPn.png" rel="noreferrer"><img src="https://i.stack.imgur.com/igGPn.png" alt="n=16000"></a>
  <a href="https://i.stack.imgur.com/0xeVm.png" rel="noreferrer"><img src="https://i.stack.imgur.com/0xeVm.png" alt="n=32000"></a></p>