title: Why push_back is slower than operator[] for a previously allocated vector
body: <p>I just read this blog <a href="http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/" rel="noreferrer">http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/</a> comparing performance of <code>operator[]</code> assignment and <code>push_back</code> on memory pre-reserved <code>std::vector</code> and I decided to try it myself. The operation is simple:</p>
  
  <pre><code>// for vector
  bigarray.reserve(N);
  
  // START TIME TRACK
  for(int k = 0; k &lt; N; ++k)
     // for operator[]:
     // bigarray[k] = k;
     // for push_back
     bigarray.push_back(k);
  // END TIME TRACK
  
  // do some dummy operations to prevent compiler optimize
  long sum = accumulate(begin(bigarray), end(array),0 0);
  </code></pre>
  
  <p>And here is the result:</p>
  
  <pre><code> ~/t/benchmark&gt; icc 1.cpp -O3 -std=c++11
   ~/t/benchmark&gt; ./a.out
  [               1.cpp:   52]     0.789123s  --&gt; C++ new
  [               1.cpp:   52]     0.774049s  --&gt; C++ new
  [               1.cpp:   66]     0.351176s  --&gt; vector
  [               1.cpp:   80]     1.801294s  --&gt; reserve + push_back
  [               1.cpp:   94]     1.753786s  --&gt; reserve + emplace_back
  [               1.cpp:  107]     2.815756s  --&gt; no reserve + push_back
   ~/t/benchmark&gt; clang++ 1.cpp -std=c++11 -O3
   ~/t/benchmark&gt; ./a.out
  [               1.cpp:   52]     0.592318s  --&gt; C++ new
  [               1.cpp:   52]     0.566979s  --&gt; C++ new
  [               1.cpp:   66]     0.270363s  --&gt; vector
  [               1.cpp:   80]     1.763784s  --&gt; reserve + push_back
  [               1.cpp:   94]     1.761879s  --&gt; reserve + emplace_back
  [               1.cpp:  107]     2.815596s  --&gt; no reserve + push_back
   ~/t/benchmark&gt; g++ 1.cpp -O3 -std=c++11
   ~/t/benchmark&gt; ./a.out
  [               1.cpp:   52]     0.617995s  --&gt; C++ new
  [               1.cpp:   52]     0.601746s  --&gt; C++ new
  [               1.cpp:   66]     0.270533s  --&gt; vector
  [               1.cpp:   80]     1.766538s  --&gt; reserve + push_back
  [               1.cpp:   94]     1.998792s  --&gt; reserve + emplace_back
  [               1.cpp:  107]     2.815617s  --&gt; no reserve + push_back
  </code></pre>
  
  <p>For all the compilers, <code>vector</code> with <code>operator[]</code> is much faster than raw pointer with <code>operator[]</code>. This led to the first question: why? The second question is, I have already "reserved" the memory, so why <code>opeator[]</code> is faster?</p>
  
  <p>The next question is, since the memory is already allocated, why <code>push_back</code> is times slower than <code>operator[]</code>? </p>
  
  <p>The test code is attached below:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;iomanip&gt;
  #include &lt;vector&gt;
  #include &lt;numeric&gt;
  #include &lt;chrono&gt;
  #include &lt;string&gt;
  #include &lt;cstring&gt;
  
  #define PROFILE(BLOCK, ROUTNAME) ProfilerRun([&amp;](){do {BLOCK;} while(0);}, \
          ROUTNAME, __FILE__, __LINE__);
  
  template &lt;typename T&gt;
  void ProfilerRun (T&amp;&amp;  func, const std::string&amp; routine_name = "unknown",
                    const char* file = "unknown", unsigned line = 0)
  {
      using std::chrono::duration_cast;
      using std::chrono::microseconds;
      using std::chrono::steady_clock;
      using std::cerr;
      using std::endl;
  
      steady_clock::time_point t_begin = steady_clock::now();
  
      // Call the function
      func();
  
      steady_clock::time_point t_end = steady_clock::now();
      cerr &lt;&lt; "[" &lt;&lt; std::setw (20)
           &lt;&lt; (std::strrchr (file, '/') ?
               std::strrchr (file, '/') + 1 : file)
           &lt;&lt; ":" &lt;&lt; std::setw (5) &lt;&lt; line &lt;&lt; "]   "
           &lt;&lt; std::setw (10) &lt;&lt; std::setprecision (6) &lt;&lt; std::fixed
           &lt;&lt; static_cast&lt;float&gt; (duration_cast&lt;microseconds&gt;
                                  (t_end - t_begin).count()) / 1e6
           &lt;&lt; "s  --&gt; " &lt;&lt; routine_name &lt;&lt; endl;
  
      cerr.unsetf (std::ios_base::floatfield);
  }
  
  using namespace std;
  
  const int N = (1 &lt;&lt; 29);
  
  int routine1()
  {
      int sum;
      int* bigarray = new int[N];
      PROFILE (
      {
          for (unsigned int k = 0; k &lt; N; ++k)
              bigarray[k] = k;
      }, "C++ new");
      sum = std::accumulate (bigarray, bigarray + N, 0);
      delete [] bigarray;
      return sum;
  }
  
  int routine2()
  {
      int sum;
      vector&lt;int&gt; bigarray (N);
      PROFILE (
      {
          for (unsigned int k = 0; k &lt; N; ++k)
              bigarray[k] = k;
      }, "vector");
      sum = std::accumulate (begin (bigarray), end (bigarray), 0);
      return sum;
  }
  
  int routine3()
  {
      int sum;
      vector&lt;int&gt; bigarray;
      bigarray.reserve (N);
      PROFILE (
      {
          for (unsigned int k = 0; k &lt; N; ++k)
              bigarray.push_back (k);
      }, "reserve + push_back");
      sum = std::accumulate (begin (bigarray), end (bigarray), 0);
      return sum;
  }
  
  int routine4()
  {
      int sum;
      vector&lt;int&gt; bigarray;
      bigarray.reserve (N);
      PROFILE (
      {
          for (unsigned int k = 0; k &lt; N; ++k)
              bigarray.emplace_back(k);
      }, "reserve + emplace_back");
      sum = std::accumulate (begin (bigarray), end (bigarray), 0);
      return sum;
  }
  
  int routine5()
  {
      int sum;
      vector&lt;int&gt; bigarray;
      PROFILE (
      {
          for (unsigned int k = 0; k &lt; N; ++k)
              bigarray.push_back (k);
      }, "no reserve + push_back");
      sum = std::accumulate (begin (bigarray), end (bigarray), 0);
      return sum;
  }
  
  
  int main()
  {
      long s0 = routine1();
      long s1 = routine1();
      long s2 = routine2();
      long s3 = routine3();
      long s4 = routine4();
      long s5 = routine5();
      return int (s1 + s2);
  }
  </code></pre>