title: Using 2-dimensional or 1-dimensional, which is fastest?
body: <p>I've been searching the web (and stackoverflow) for opinions on whether or not 1-dimensional arrays (or vectors) are faster than their 2-dimensional counterparts. And the general conclusion seems to be that 1-dimensional are the fastest. However, I wrote a short test program to see for myself, and it shows that 2-dimensional are the best. Can anyone find a bug in my test, or at least explain why I get this result?</p>
  
  <p><strong>I use it for storing matrices, and thus need to index the 1-dimensional arrays with both row and column.</strong></p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;chrono&gt;
  #include &lt;vector&gt;
  
  uint64_t timestamp()
  {
      namespace sc = std::chrono;
      static auto start = sc::high_resolution_clock::now();
      return sc::duration_cast&lt;sc::duration&lt;uint64_t, std::micro&gt;&gt;(sc::high_resolution_clock::now() - start).count();
  }
  
  int main(int argc, char** argv)
  {
      if (argc &lt; 3)
          return 0;
      size_t size = atoi(argv[1]);
      size_t repeat = atoi(argv[2]);
  
      int** d2 = (int**)malloc(size*sizeof(int*));
      for (size_t i = 0; i &lt; size; ++i)
          d2[i] = (int*)malloc(size*sizeof(int));
  
      int* d1 = (int*)malloc(size*size*sizeof(int));
  
      std::vector&lt;std::vector&lt;int&gt; &gt; d2v(size);
      for (auto&amp; i : d2v)
          i.resize(size);
  
      std::vector&lt;int&gt; d1v(size*size);
  
      uint64_t start, end;
      timestamp();
  
      start = timestamp();
      for (size_t n = 0; n &lt; repeat; ++n)
      {
          for (size_t r = 0; r &lt; size; ++r)
          {
              for (size_t c = 0; c &lt; size; ++c)
              {
                  if (r == 0)
                      d2[r][c] = 0;
                  else
                      d2[r][c] = d2[r-1][c] + 1;
              }
          }
      }
      end = timestamp();
      std::cout &lt;&lt; "2D array\t" &lt;&lt; size &lt;&lt; "\t" &lt;&lt; end - start &lt;&lt; std::endl;
  
      start = timestamp();
      for (size_t n = 0; n &lt; repeat; ++n)
      {
          for (size_t c = 0; c &lt; size; ++c)
          {
              for (size_t r = 0; r &lt; size; ++r)
              {
                  if (r == 0)
                      d2[r][c] = 0;
                  else
                      d2[r][c] = d2[r-1][c] + 1;
              }
          }
      }
      end = timestamp();
      std::cout &lt;&lt; "2D array C\t" &lt;&lt; size &lt;&lt; "\t" &lt;&lt; end - start &lt;&lt; std::endl;
  
      start = timestamp();
      for (size_t n = 0; n &lt; repeat; ++n)
      {
          for (size_t r = 0; r &lt; size; ++r)
          {
              for (size_t c = 0; c &lt; size; ++c)
              {
                  if (r == 0)
                      d1[r + c*size] = 0;
                  else
                      d1[r + c*size] = d1[r-1 + c*size] + 1;
              }
          }
      }
      end = timestamp();
      std::cout &lt;&lt; "1D array\t" &lt;&lt; size &lt;&lt; "\t" &lt;&lt; end - start &lt;&lt; std::endl;
  
      start = timestamp();
      for (size_t n = 0; n &lt; repeat; ++n)
      {
          for (size_t c = 0; c &lt; size; ++c)
          {
              for (size_t r = 0; r &lt; size; ++r)
              {
                  if (r == 0)
                      d1[r + c*size] = 0;
                  else
                      d1[r + c*size] = d1[r-1 + c*size] + 1;
              }
          }
      }
      end = timestamp();
      std::cout &lt;&lt; "1D array C\t" &lt;&lt; size &lt;&lt; "\t" &lt;&lt; end - start &lt;&lt; std::endl;
  
      start = timestamp();
      for (size_t n = 0; n &lt; repeat; ++n)
      {
          for (size_t r = 0; r &lt; size; ++r)
          {
              for (size_t c = 0; c &lt; size; ++c)
              {
                  if (r == 0)
                      d2v[r][c] = 0;
                  else
                      d2v[r][c] = d2v[r-1][c] + 1;
              }
          }
      }
      end = timestamp();
      std::cout &lt;&lt; "2D vector\t" &lt;&lt; size &lt;&lt; "\t" &lt;&lt; end - start &lt;&lt; std::endl;
  
      start = timestamp();
      for (size_t n = 0; n &lt; repeat; ++n)
      {
          for (size_t c = 0; c &lt; size; ++c)
          {
              for (size_t r = 0; r &lt; size; ++r)
              {
                  if (r == 0)
                      d2v[r][c] = 0;
                  else
                      d2v[r][c] = d2v[r-1][c] + 1;
              }
          }
      }
      end = timestamp();
      std::cout &lt;&lt; "2D vector C\t" &lt;&lt; size &lt;&lt; "\t" &lt;&lt; end - start &lt;&lt; std::endl;
  
      start = timestamp();
      for (size_t n = 0; n &lt; repeat; ++n)
      {
          for (size_t r = 0; r &lt; size; ++r)
          {
              for (size_t c = 0; c &lt; size; ++c)
              {
                  if (r == 0)
                      d1v[r + c*size] = 0;
                  else
                      d1v[r + c*size] = d1v[r-1 + c*size] + 1;
              }
          }
      }
      end = timestamp();
      std::cout &lt;&lt; "1D vector\t" &lt;&lt; size &lt;&lt; "\t" &lt;&lt; end - start &lt;&lt; std::endl;
  
      start = timestamp();
      for (size_t n = 0; n &lt; repeat; ++n)
      {
          for (size_t c = 0; c &lt; size; ++c)
          {
              for (size_t r = 0; r &lt; size; ++r)
              {
                  if (r == 0)
                      d1v[r + c*size] = 0;
                  else
                      d1v[r + c*size] = d1v[r-1 + c*size] + 1;
              }
          }
      }
      end = timestamp();
      std::cout &lt;&lt; "1D vector C\t" &lt;&lt; size &lt;&lt; "\t" &lt;&lt; end - start &lt;&lt; std::endl;
  
      return 0;
  }
  </code></pre>
  
  <p>I get the following output:</p>
  
  <pre><code>user@user-debian64:~/matrix$ ./build/test/index_test 1000 100
  2D array    1000    79593
  2D array C  1000    326695
  1D array    1000    440695
  1D array C  1000    262251
  2D vector   1000    73648
  2D vector C 1000    418287
  1D vector   1000    371433
  1D vector C 1000    269355
  user@user-debian64:~/matrix$ ./build/test/index_test 10000 1
  2D array    10000   149748
  2D array C  10000   3507346
  1D array    10000   2754570
  1D array C  10000   257997
  2D vector   10000   92041
  2D vector C 10000   3791745
  1D vector   10000   3384403
  1D vector C 10000   266811
  </code></pre>