title: Dynamic allocation and random access: Raw, Smart, Deque, Vector. Why raw so fast, and deque so slow?
body: <p>I created a little performance test comparing the setup and access times of three popular techniques for dynamic allocation: raw pointer, std::unique_ptr, and a std::deque.</p>
  
  <p>EDIT: per @NathanOliver's, added <code>std::vector</code>:
  EDIT 2: per latedeveloper's, allocated with std::vector(n) and std::deque(n) constructors
  EDIT 3: per @BaummitAugen, moved allocation inside timing loop, and compiled an optimized version.
  EDIT 4: per @PaulMcKenzie's comments, set runs to 2000.</p>
  
  <p>Results: These changes have tightened things up a lot. Deque and Vector are still slower on allocation and assignment, while deque is much slower on access:</p>
  
  <p>pickledEgg$ g++ -std=c++11 -o sp2 -O2 sp2.cpp</p>
  
  <pre><code>Average of 2000 runs:
  Method  Assign          Access
  ======  ======          ======
  Raw:    0.0000085643    0.0000000724
  Smart:  0.0000085281    0.0000000732
  Deque:  0.0000205775    0.0000076908
  Vector: 0.0000163492    0.0000000760
  </code></pre>
  
  <p>Just for fun, here are -Ofast results:<br>
  pickledEgg$ g++ -std=c++11 -o sp2 -Ofast sp2.cpp</p>
  
  <pre><code>Average of 2000 runs:
  Method  Assign          Access
  ======  ======          ======
  Raw:    0.0000045316    0.0000000893
  Smart:  0.0000038308    0.0000000730
  Deque:  0.0000165620    0.0000076475
  Vector: 0.0000063442    0.0000000699
  </code></pre>
  
  <p>ORIGINAL: For posterity; note lack of optimizer -O2 flag:</p>
  
  <p>pickledEgg$ g++ -std=c++11 -o sp2 sp2.cpp</p>
  
  <pre><code>Average of 100 runs:
  Method  Assign      Access
  ======  ======      ======
  Raw:    0.0000466522    0.0000468586
  Smart:  0.0004391623    0.0004406758
  Deque:  0.0003144142    0.0021758729
  Vector: 0.0004715145    0.0003829193
  </code></pre>
  
  <p>Updated Code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;iomanip&gt;
  #include &lt;vector&gt;
  #include &lt;deque&gt;
  #include &lt;chrono&gt;
  #include &lt;memory&gt;
  
  const int NUM_RUNS(2000);
  
  int main() {
      std::chrono::high_resolution_clock::time_point b, e;
      std::chrono::duration&lt;double&gt; t, raw_assign(0), raw_access(0), smart_assign(0), smart_access(0), deque_assign(0), deque_access(0), vector_assign(0), vector_access(0);
      int k, tmp, n(32768);
  
      std::cout &lt;&lt; "Average of " &lt;&lt; NUM_RUNS &lt;&lt; " runs:" &lt;&lt; std::endl; 
      std::cout &lt;&lt; "Method " &lt;&lt; '\t' &lt;&lt; "Assign" &lt;&lt; "\t\t" &lt;&lt; "Access" &lt;&lt; std::endl;
      std::cout &lt;&lt; "====== " &lt;&lt; '\t' &lt;&lt; "======" &lt;&lt; "\t\t" &lt;&lt; "======" &lt;&lt; std::endl;
  
      // Raw
      for (k=0; k&lt;NUM_RUNS; ++k) {
          b = std::chrono::high_resolution_clock::now();
          int* raw_p = new int[n]; // run-time allocation
          for (int i=0; i&lt;n; ++i) { //assign
              raw_p[i] = i;
          }
          e = std::chrono::high_resolution_clock::now();
          t = std::chrono::duration_cast&lt;std::chrono::duration&lt;double&gt; &gt;(e - b);
          raw_assign+=t;
          b = std::chrono::high_resolution_clock::now();
          for (int i=0; i&lt;n; ++i) { //access
              tmp = raw_p[i];
          }
          e = std::chrono::high_resolution_clock::now();
          t = std::chrono::duration_cast&lt;std::chrono::duration&lt;double&gt; &gt;(e - b);
          raw_access+=t;
          delete [] raw_p; // :^)
      }
      raw_assign /= NUM_RUNS;
      raw_access /= NUM_RUNS;
      std::cout &lt;&lt; "Raw:   " &lt;&lt; '\t' &lt;&lt; std::setprecision(10) &lt;&lt; std::fixed &lt;&lt; raw_assign.count() &lt;&lt; '\t' &lt;&lt; raw_access.count() &lt;&lt; std::endl;
  
      // Smart
      for (k=0; k&lt;NUM_RUNS; ++k) {
          b = std::chrono::high_resolution_clock::now();
          std::unique_ptr&lt;int []&gt; smart_p(new int[n]); // run-time allocation
          for (int i=0; i&lt;n; ++i) { //assign
              smart_p[i] = i;
          }
          e = std::chrono::high_resolution_clock::now();
          t = std::chrono::duration_cast&lt;std::chrono::duration&lt;double&gt; &gt;(e - b);
          smart_assign+=t;
          b = std::chrono::high_resolution_clock::now();
          for (int i=0; i&lt;n; ++i) { //access
              tmp = smart_p[i];
          }
          e = std::chrono::high_resolution_clock::now();
          t = std::chrono::duration_cast&lt;std::chrono::duration&lt;double&gt; &gt;(e - b);
          smart_access+=t;
      }
      smart_assign /= NUM_RUNS;
      smart_access /= NUM_RUNS;
      std::cout &lt;&lt; "Smart: " &lt;&lt; '\t' &lt;&lt; std::setprecision(10) &lt;&lt; std::fixed &lt;&lt; smart_assign.count() &lt;&lt; '\t' &lt;&lt; smart_access.count() &lt;&lt; std::endl;
  
      // Deque
      for (k=0; k&lt;NUM_RUNS; ++k) {
          b = std::chrono::high_resolution_clock::now();
          std::deque&lt;int&gt; myDeque(n);
          for (int i=0; i&lt;n; ++i) { //assign
              myDeque[n] = i;
  //          myDeque.push_back(i);
          }
          e = std::chrono::high_resolution_clock::now();
          t = std::chrono::duration_cast&lt;std::chrono::duration&lt;double&gt; &gt;(e - b);
          deque_assign+=t;
          b = std::chrono::high_resolution_clock::now();
          for (int i=0; i&lt;n; ++i) { //access
              tmp = myDeque[n];
          }
          e = std::chrono::high_resolution_clock::now();
          t = std::chrono::duration_cast&lt;std::chrono::duration&lt;double&gt; &gt;(e - b);
          deque_access+=t;
      }
      deque_assign /= NUM_RUNS;
      deque_access /= NUM_RUNS;
      std::cout &lt;&lt; "Deque: " &lt;&lt; '\t' &lt;&lt; std::setprecision(10) &lt;&lt; std::fixed &lt;&lt; deque_assign.count() &lt;&lt; '\t' &lt;&lt; deque_access.count() &lt;&lt; std::endl;
  
      // vector
      for (k=0; k&lt;NUM_RUNS; ++k) {
          b = std::chrono::high_resolution_clock::now();
          std::vector&lt;int&gt; myVector(n);
          for (int i=0; i&lt;n; ++i) { //assign
              myVector[i] = i;
  //          .push_back(i);
          }
          e = std::chrono::high_resolution_clock::now();
          t = std::chrono::duration_cast&lt;std::chrono::duration&lt;double&gt; &gt;(e - b);
          vector_assign+=t;
          b = std::chrono::high_resolution_clock::now();
          for (int i=0; i&lt;n; ++i) { //access
              tmp = myVector[i];
  //          tmp = *(myVector.begin() + i);
          }
          e = std::chrono::high_resolution_clock::now();
          t = std::chrono::duration_cast&lt;std::chrono::duration&lt;double&gt; &gt;(e - b);
          vector_access+=t;
      }
      vector_assign /= NUM_RUNS;
      vector_access /= NUM_RUNS;
      std::cout &lt;&lt; "Vector:" &lt;&lt; '\t' &lt;&lt; std::setprecision(10) &lt;&lt; std::fixed &lt;&lt; vector_assign.count() &lt;&lt; '\t' &lt;&lt; vector_access.count() &lt;&lt; std::endl;
  
      std::cout &lt;&lt; std::endl;
      return 0;
  }
  </code></pre>