对于先前分配的向量，为什么 push_back 比 operator[] 慢
我刚刚读了这个博客 http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/ 比较 operator[] 分配和 push_back 在预先保留的内存 std::vector 上，我决定自己尝试一下.操作很简单:
I just read this blog http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/ comparing performance of operator[] assignment and push_back on memory pre-reserved std::vector and I decided to try it myself. The operation is simple:
// for vector
bigarray.reserve(N);
// START TIME TRACK
for(int k = 0; k < 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);
结果如下:
~/t/benchmark> icc 1.cpp -O3 -std=c++11
~/t/benchmark> ./a.out
[ 1.cpp: 52] 0.789123s --> C++ new
[ 1.cpp: 52] 0.774049s --> C++ new
[ 1.cpp: 66] 0.351176s --> vector
[ 1.cpp: 80] 1.801294s --> reserve + push_back
[ 1.cpp: 94] 1.753786s --> reserve + emplace_back
[ 1.cpp: 107] 2.815756s --> no reserve + push_back
~/t/benchmark> clang++ 1.cpp -std=c++11 -O3
~/t/benchmark> ./a.out
[ 1.cpp: 52] 0.592318s --> C++ new
[ 1.cpp: 52] 0.566979s --> C++ new
[ 1.cpp: 66] 0.270363s --> vector
[ 1.cpp: 80] 1.763784s --> reserve + push_back
[ 1.cpp: 94] 1.761879s --> reserve + emplace_back
[ 1.cpp: 107] 2.815596s --> no reserve + push_back
~/t/benchmark> g++ 1.cpp -O3 -std=c++11
~/t/benchmark> ./a.out
[ 1.cpp: 52] 0.617995s --> C++ new
[ 1.cpp: 52] 0.601746s --> C++ new
[ 1.cpp: 66] 0.270533s --> vector
[ 1.cpp: 80] 1.766538s --> reserve + push_back
[ 1.cpp: 94] 1.998792s --> reserve + emplace_back
[ 1.cpp: 107] 2.815617s --> no reserve + push_back
对于所有的编译器，带有 operator[] 的 vector 比带有 operator[] 的原始指针快得多.这就引出了第一个问题:为什么?第二个问题，我已经预留"了内存，为什么opeator[]更快?
For all the compilers, vector with operator[] is much faster than raw pointer with operator[]. This led to the first question: why? The second question is, I have already "reserved" the memory, so why opeator[] is faster?
下一个问题是，既然已经分配了内存，为什么push_back比operator[]慢?
The next question is, since the memory is already allocated, why push_back is times slower than operator[]?
下面附上测试代码:
#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__);
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;
const int N = (1 << 29);
int routine1()
{
int sum;
int* bigarray = new 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;
}
int routine2()
{
int sum;
vector<int> bigarray (N);
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray[k] = k;
}, "vector");
sum = std::accumulate (begin (bigarray), end (bigarray), 0);
return sum;
}
int routine3()
{
int sum;
vector<int> bigarray;
bigarray.reserve (N);
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;
}
int routine4()
{
int sum;
vector<int> bigarray;
bigarray.reserve (N);
PROFILE (
{
for (unsigned int k = 0; k < N; ++k)
bigarray.emplace_back(k);
}, "reserve + emplace_back");
sum = std::accumulate (begin (bigarray), end (bigarray), 0);
return sum;
}
int routine5()
{
int sum;
vector<int> bigarray;
PROFILE (
{
for (unsigned int k = 0; k < 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);
}
推荐答案
push_back 进行边界检查.operator[] 没有.因此，即使您保留了空间，push_back 也会进行额外的条件检查，而 operator[] 将不会有.此外，它会增加 size 值(reserve 只设置 capacity)，所以它每次都会更新.
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.
简而言之，push_back 做的比 operator[] 做的更多 - 这就是为什么它更慢(也更准确).
In short, push_back is doing more than what operator[] is doing - which is why it is slower (and more accurate).
相关文章