Why push_back is slower than operator[] for a previously allocated vector
As Yakk and me have found out, there might be another interesting factor that contributes to the apparent slowness of push_back.
The first interesting observation is that in the original test, using new and operating on a raw array is slower than using vector<int> bigarray(N); and operator[] -- more than a factor 2. Even more interesting is that you can get the same performance for both by inserting an additional memset for the raw array variant:
int routine1_modified()
{
int sum;
int* bigarray = new int[N];
memset(bigarray, 0, sizeof(int)*N);
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray[k] = k;
}, "C++ new");
sum = std::accumulate (bigarray, bigarray + N, 0);
delete [] bigarray;
return sum;
}
The conclusion of course is, that PROFILE measures something different than expected. Yakk and me guess it has something to do with memory management; from Yakk's comment to the OP:
resizewill touch the entire block of memory.reservewill allocate without touching. If you have a lazy allocator that doesn't fetch or assign physical memory pages until accessed,reserveon an empty vector can be nearly free (doesn't even have to find physical memory for the pages!) until you write to the pages (at which point, they have to be found).
I thought of something similar, so tried a small test for this hypothesis by touching certain pages with a "strided memset" (a profiling tool might get more reliable results):
int routine1_modified2()
{
int sum;
int* bigarray = new int[N];
for(int k = 0; k < N; k += PAGESIZE*2/sizeof(int))
bigarray[k] = 0;
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray[k] = k;
}, "C++ new");
sum = std::accumulate (bigarray, bigarray + N, 0);
delete [] bigarray;
return sum;
}
By changing the stride from every page half to every 4th page to leaving it out completely, we get a nice transition of the timings from the vector<int> bigarray(N); case to the new int[N] case where no memset has been used.
In my opinion, that's a strong hint that memory management is a major contributor to the measurement results.
Another issue is the branching in push_back. It is claimed in many answers that this is a / the major reason why push_back is much slower as compared to using operator[]. Indeed, comparing the raw-pointer w/o memset to using reserve + push_back, the former is two times faster.
Similarly, if we add a bit of UB (but check the results later):
int routine3_modified()
{
int sum;
vector<int> bigarray;
bigarray.reserve (N);
memset(bigarray.data(), 0, sizeof(int)*N); // technically, it's UB
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray.push_back (k);
}, "reserve + push_back");
sum = std::accumulate (begin (bigarray), end (bigarray), 0);
return sum;
}
this modified version is about 2 times slower than using new + a full memset. So it seems whatever the invocation of push_back does, it results in a factor 2 slowdown when compared to just setting the element (via operator[] in both the vector and raw array case).
But is it the branching required in push_back, or the additional operation?
// pseudo-code
void push_back(T const& p)
{
if(size() == capacity())
{
resize( size() < 10 ? 10 : size()*2 );
}
(*this)[size()] = p; // actually using the allocator
++m_end;
}
It is indeed that simple, see e.g. libstdc++'s implementation.
I've tested it by using the vector<int> bigarray(N); + operator[] variant, and inserting a function call that mimics the behaviour of push_back:
unsigned x = 0;
void silly_branch(int k)
{
if(k == x)
{
x = x < 10 ? 10 : x*2;
}
}
int routine2_modified()
{
int sum;
vector<int> bigarray (N);
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
{
silly_branch(k);
bigarray[k] = k;
}
}, "vector");
sum = std::accumulate (begin (bigarray), end (bigarray), 0);
return sum;
}
Even when declaring x as volatile, this only has 1 % influence on the measurement. Of course, you had to verify that the branch is actually in the opcode, but my assembler knowledge doesn't allow me to verify that (at -O3).
The interesting point now is what happens when I add an increment to silly_branch:
unsigned x = 0;
void silly_branch(int k)
{
if(k == x)
{
x = x < 10 ? 10 : x*2;
}
++x;
}
Now, the modified routine2_modified runs 2 times slower than the original routine2, being on par with the proposed routine3_modified above that includes UB to commit the memory pages. I don't find that particularly surprising, as it adds another write to every write in the loop, so we have two times the work and two times the duration.
Conclusion
Well you had to carefully look at the assembly and profiling tools to verify the hypotheses of memory management and the additional write is a good hypothesis ("correct"). But I think the hints are strong enough to claim that there's something more complicated going on than just a branch which makes push_back slower.
Here's the full test code:
#include <iostream>
#include <iomanip>
#include <vector>
#include <numeric>
#include <chrono>
#include <string>
#include <cstring>
#define PROFILE(BLOCK, ROUTNAME) ProfilerRun([&](){do {BLOCK;} while(0);}, \
ROUTNAME, __FILE__, __LINE__);
//#define PROFILE(BLOCK, ROUTNAME) BLOCK
template <typename T>
void ProfilerRun (T&& func, const std::string& 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 << "[" << std::setw (20)
<< (std::strrchr (file, '/') ?
std::strrchr (file, '/') + 1 : file)
<< ":" << std::setw (5) << line << "] "
<< std::setw (10) << std::setprecision (6) << std::fixed
<< static_cast<float> (duration_cast<microseconds>
(t_end - t_begin).count()) / 1e6
<< "s --> " << routine_name << endl;
cerr.unsetf (std::ios_base::floatfield);
}
using namespace std;
constexpr int N = (1 << 28);
constexpr int PAGESIZE = 4096;
uint64_t __attribute__((noinline)) routine1()
{
uint64_t sum;
int* bigarray = new int[N];
PROFILE (
{
for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
*p = k;
}, "new (routine1)");
sum = std::accumulate (bigarray, bigarray + N, 0ULL);
delete [] bigarray;
return sum;
}
uint64_t __attribute__((noinline)) routine2()
{
uint64_t sum;
int* bigarray = new int[N];
memset(bigarray, 0, sizeof(int)*N);
PROFILE (
{
for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
*p = k;
}, "new + full memset (routine2)");
sum = std::accumulate (bigarray, bigarray + N, 0ULL);
delete [] bigarray;
return sum;
}
uint64_t __attribute__((noinline)) routine3()
{
uint64_t sum;
int* bigarray = new int[N];
for(int k = 0; k < N; k += PAGESIZE/2/sizeof(int))
bigarray[k] = 0;
PROFILE (
{
for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
*p = k;
}, "new + strided memset (every page half) (routine3)");
sum = std::accumulate (bigarray, bigarray + N, 0ULL);
delete [] bigarray;
return sum;
}
uint64_t __attribute__((noinline)) routine4()
{
uint64_t sum;
int* bigarray = new int[N];
for(int k = 0; k < N; k += PAGESIZE/1/sizeof(int))
bigarray[k] = 0;
PROFILE (
{
for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
*p = k;
}, "new + strided memset (every page) (routine4)");
sum = std::accumulate (bigarray, bigarray + N, 0ULL);
delete [] bigarray;
return sum;
}
uint64_t __attribute__((noinline)) routine5()
{
uint64_t sum;
int* bigarray = new int[N];
for(int k = 0; k < N; k += PAGESIZE*2/sizeof(int))
bigarray[k] = 0;
PROFILE (
{
for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
*p = k;
}, "new + strided memset (every other page) (routine5)");
sum = std::accumulate (bigarray, bigarray + N, 0ULL);
delete [] bigarray;
return sum;
}
uint64_t __attribute__((noinline)) routine6()
{
uint64_t sum;
int* bigarray = new int[N];
for(int k = 0; k < N; k += PAGESIZE*4/sizeof(int))
bigarray[k] = 0;
PROFILE (
{
for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
*p = k;
}, "new + strided memset (every 4th page) (routine6)");
sum = std::accumulate (bigarray, bigarray + N, 0ULL);
delete [] bigarray;
return sum;
}
uint64_t __attribute__((noinline)) routine7()
{
uint64_t sum;
vector<int> bigarray (N);
PROFILE (
{
for (int k = 0; k < N; ++k)
bigarray[k] = k;
}, "vector, using ctor to initialize (routine7)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
uint64_t __attribute__((noinline)) routine8()
{
uint64_t sum;
vector<int> bigarray;
PROFILE (
{
for (int k = 0; k < N; ++k)
bigarray.push_back (k);
}, "vector (+ no reserve) + push_back (routine8)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
uint64_t __attribute__((noinline)) routine9()
{
uint64_t sum;
vector<int> bigarray;
bigarray.reserve (N);
PROFILE (
{
for (int k = 0; k < N; ++k)
bigarray.push_back (k);
}, "vector + reserve + push_back (routine9)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
uint64_t __attribute__((noinline)) routine10()
{
uint64_t sum;
vector<int> bigarray;
bigarray.reserve (N);
memset(bigarray.data(), 0, sizeof(int)*N);
PROFILE (
{
for (int k = 0; k < N; ++k)
bigarray.push_back (k);
}, "vector + reserve + memset (UB) + push_back (routine10)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
template<class T>
void __attribute__((noinline)) adjust_size(std::vector<T>& v, int k, double factor)
{
if(k >= v.size())
{
v.resize(v.size() < 10 ? 10 : k*factor);
}
}
uint64_t __attribute__((noinline)) routine11()
{
uint64_t sum;
vector<int> bigarray;
PROFILE (
{
for (int k = 0; k < N; ++k)
{
adjust_size(bigarray, k, 1.5);
bigarray[k] = k;
}
}, "vector + custom emplace_back @ factor 1.5 (routine11)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
uint64_t __attribute__((noinline)) routine12()
{
uint64_t sum;
vector<int> bigarray;
PROFILE (
{
for (int k = 0; k < N; ++k)
{
adjust_size(bigarray, k, 2);
bigarray[k] = k;
}
}, "vector + custom emplace_back @ factor 2 (routine12)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
uint64_t __attribute__((noinline)) routine13()
{
uint64_t sum;
vector<int> bigarray;
PROFILE (
{
for (int k = 0; k < N; ++k)
{
adjust_size(bigarray, k, 3);
bigarray[k] = k;
}
}, "vector + custom emplace_back @ factor 3 (routine13)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
uint64_t __attribute__((noinline)) routine14()
{
uint64_t sum;
vector<int> bigarray;
PROFILE (
{
for (int k = 0; k < N; ++k)
bigarray.emplace_back (k);
}, "vector (+ no reserve) + emplace_back (routine14)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
uint64_t __attribute__((noinline)) routine15()
{
uint64_t sum;
vector<int> bigarray;
bigarray.reserve (N);
PROFILE (
{
for (int k = 0; k < N; ++k)
bigarray.emplace_back (k);
}, "vector + reserve + emplace_back (routine15)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
uint64_t __attribute__((noinline)) routine16()
{
uint64_t sum;
vector<int> bigarray;
bigarray.reserve (N);
memset(bigarray.data(), 0, sizeof(bigarray[0])*N);
PROFILE (
{
for (int k = 0; k < N; ++k)
bigarray.emplace_back (k);
}, "vector + reserve + memset (UB) + emplace_back (routine16)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
unsigned x = 0;
template<class T>
void /*__attribute__((noinline))*/ silly_branch(std::vector<T>& v, int k)
{
if(k == x)
{
x = x < 10 ? 10 : x*2;
}
//++x;
}
uint64_t __attribute__((noinline)) routine17()
{
uint64_t sum;
vector<int> bigarray(N);
PROFILE (
{
for (int k = 0; k < N; ++k)
{
silly_branch(bigarray, k);
bigarray[k] = k;
}
}, "vector, using ctor to initialize + silly branch (routine17)");
sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
return sum;
}
template<class T, int N>
constexpr int get_extent(T(&)[N])
{ return N; }
int main()
{
uint64_t results[] = {routine2(),
routine1(),
routine2(),
routine3(),
routine4(),
routine5(),
routine6(),
routine7(),
routine8(),
routine9(),
routine10(),
routine11(),
routine12(),
routine13(),
routine14(),
routine15(),
routine16(),
routine17()};
std::cout << std::boolalpha;
for(int i = 1; i < get_extent(results); ++i)
{
std::cout << i << ": " << (results[0] == results[i]) << "\n";
}
std::cout << x << "\n";
}
A sample run, on an old & slow computer; note:
N == 2<<28, not2<<29as in the OP- compiled with g++4.9 20131022 with
-std=c++11 -O3 -march=native
[ temp.cpp: 71] 0.654927s --> new + full memset (routine2) [ temp.cpp: 54] 1.042405s --> new (routine1) [ temp.cpp: 71] 0.605061s --> new + full memset (routine2) [ temp.cpp: 89] 0.597487s --> new + strided memset (every page half) (routine3) [ temp.cpp: 107] 0.601271s --> new + strided memset (every page) (routine4) [ temp.cpp: 125] 0.783610s --> new + strided memset (every other page) (routine5) [ temp.cpp: 143] 0.903038s --> new + strided memset (every 4th page) (routine6) [ temp.cpp: 157] 0.602401s --> vector, using ctor to initialize (routine7) [ temp.cpp: 170] 3.811291s --> vector (+ no reserve) + push_back (routine8) [ temp.cpp: 184] 2.091391s --> vector + reserve + push_back (routine9) [ temp.cpp: 199] 1.375837s --> vector + reserve + memset (UB) + push_back (routine10) [ temp.cpp: 224] 8.738293s --> vector + custom emplace_back @ factor 1.5 (routine11) [ temp.cpp: 240] 5.513803s --> vector + custom emplace_back @ factor 2 (routine12) [ temp.cpp: 256] 5.150388s --> vector + custom emplace_back @ factor 3 (routine13) [ temp.cpp: 269] 3.789820s --> vector (+ no reserve) + emplace_back (routine14) [ temp.cpp: 283] 2.090259s --> vector + reserve + emplace_back (routine15) [ temp.cpp: 298] 1.288740s --> vector + reserve + memset (UB) + emplace_back (routine16) [ temp.cpp: 325] 0.611168s --> vector, using ctor to initialize + silly branch (routine17) 1: true 2: true 3: true 4: true 5: true 6: true 7: true 8: true 9: true 10: true 11: true 12: true 13: true 14: true 15: true 16: true 17: true 335544320
push_back does a bounds check. operator[] does not. So even if you've reserved the space, push_back is going to have an extra conditional check that operator[] will not have. Additionally, it will increase the size value (reserve only sets the capacity), so it will update that every time.
In short, push_back is doing more than what operator[] is doing - which is why it is slower (and more accurate).
I can answer your second question. Although the vector is preallocated, push_back still needs to check the available space everytime you call push_back. On the other hand operator[] performs no checks and simply assumes the space is available.
When you allocate the array in the constructor, the compiler/library can basically memset() the original fill and then just set each individual value. When you use push_back(), the std::vector<T> class will need to:
- Check if there is enough space.
- Change the end pointer to be a new location.
- Set the actual value.
The last step is the only thing that needs to be done when the memory is allocated in one go.