为什么对于先前分配的向量，push_back比operator []慢 [英] Why push_back is slower than operator[] for a previously allocated vector
问题描述
我刚刚阅读了此博客 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
对于所有编译器， vector operator [] 的c>比使用 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 的值（仅设置 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).
这篇关于为什么对于先前分配的向量，push_back比operator []慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
