c++ - 对于先前分配的 vector ，为什么 push_back 比 operator[] 慢

Question

我刚读了这篇博客 http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/比较 operator[] 分配和 push_back 在内存预保留 std::vector 上的性能，我决定自己尝试一下。操作很简单:

// 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[] 的原始指针快得多。这就引出了第一个问题:为什么？第二个问题是，我已经“预留”了内存，那为什么operator[]更快？

下一个问题是，既然内存已经分配了，为什么push_back比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);
}

Answer 1

push_back 进行边界检查。 operator[] 没有。因此，即使您保留了空间，push_back 也会有一个额外的条件检查，而 operator[] 不会有。此外，它会增加 size 的值(reserve 只设置 capacity)，所以每次都会更新。

简而言之，push_back 所做的比 operator[] 所做的要多 - 这就是它更慢(且更准确)的原因。