c++ - vector 和原始c样式数组之间的性能比较

我已经介绍了c++ vector 和c样式数组之间的性能。结果有点出乎意料，因为文献称 vector 的性能应该非常接近原始数组，但事实并非如此。我的配置文件中做错了什么吗？

void getVector1(int n)
{
    if (n < 0)
    {
        throw std::invalid_argument(std::string("negative argument n:") + std::to_string(n));
    }

    auto tp1 = std::chrono::steady_clock::now();
    std::vector<int> ivec(n);
    int i = 0;
    for (auto& x : ivec)
    {
        x = ++i;
    }

    auto tp2 = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::micro> dd = tp2 - tp1;

    printf("spend %6.2f us time to create: %d elements vector inside %s() at %s:%d \n", dd.count(), n, __func__, __FILE__, __LINE__);
}


void getVector2(int n)
{
    if (n < 0)
    {
        throw std::invalid_argument(std::string("negative argument n:") + std::to_string(n));
    }

    auto tp1 = std::chrono::steady_clock::now();
    auto pvec = new int[n];

    for (int i = 0; i < n; ++i)
    {
        pvec[i] = i;
    }

    auto tp2 = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::micro> dd = tp2 - tp1;

    delete[] pvec;
    printf("spend %6.2f us time to create: %d elements vector inside %s() at %s:%d \n", dd.count(), n, __func__, __FILE__, __LINE__);
}



int main()
{
    int n = 10000000;
    getVector1(n);
    getVector2(n);

    return 0;
}

该代码是使用带有-O3选项的g++编译的。

花费11946.38美国时间创建:10000000个元素 vector 在testVectorSpeed.cpp的getVector1()中

花费7296.66美国时间创建:10000000个元素 vector 在testVectorSpeed.cpp的getVector2()中

最佳答案

该成本归结为 vector 通过其分配器将内存清零的情况。

首先，最好使用google benchmark之类的基准测试库，而不要滚动自己的基准测试。我们可以使用quick-bench.com快速使用该库。重写代码以使用此代码:

// Just the benchmark code:
void getVector1(benchmark::State& state)
{
    int n = state.range(0);

    for (auto _ : state) {
      std::vector<int> ivec(n);

      // This is the same operation that you are doing
      std::iota(ivec.begin(), ivec.end(), 1);

      // We don't want the compiler to see that we aren't
      // using `ivec` and thus optimize away the entire
      // loop body
      benchmark::DoNotOptimize(ivec);
    }
}

void getArray1(benchmark::State& state)
{
    int n = state.range(0);

    for (auto _ : state) {
      auto pvec = new int[n];

      std::iota(pvec, pvec + n, 1);

      benchmark::DoNotOptimize(pvec);

      delete[] pvec;
    }
}

// Smaller number still reproduces it
BENCHMARK(getVector1)->Arg(10000);
BENCHMARK(getArray1)->Arg(10000);

Click on image for quick-bench link

通过一些试验，我们可以发现成本差异仅仅是使用 std::uninitialized_fill (on quick-bench)将内存清零的成本。

确实，如果我们改为使用an allocator that leaves the memory uninitialized，则两者之间没有可测量的差异:

// Allocator from https://stackoverflow.com/a/41049640
template <typename T, typename A = std::allocator<T>>
class default_init_allocator : public A {
    typedef std::allocator_traits<A> a_t;
public:
    // http://en.cppreference.com/w/cpp/language/using_declaration
    using A::A; // Inherit constructors from A

    template <typename U> struct rebind {
        using other =
            default_init_allocator
            <  U, typename a_t::template rebind_alloc<U>  >;
    };

    template <typename U>
    void construct(U* ptr)
        noexcept(std::is_nothrow_default_constructible<U>::value) {
        ::new(static_cast<void*>(ptr)) U;
    }

    template <typename U, typename...Args>
    void construct(U* ptr, Args&&... args) {
        a_t::construct(static_cast<A&>(*this),
            ptr, std::forward<Args>(args)...);
    }
};

void getVector1(benchmark::State& state)
{
    int n = state.range(0);

    for (auto _ : state) {
      std::vector<int, default_init_allocator<int>> ivec(n);

      std::iota(ivec.begin(), ivec.end(), 1);

      benchmark::DoNotOptimize(ivec);
    }
}

void getArray1(benchmark::State& state)
{
    int n = state.range(0);

    for (auto _ : state) {
      auto pvec = new int[n];

      std::iota(pvec, pvec + n, 1);

      benchmark::DoNotOptimize(pvec);

      delete[] pvec;
    }
}

BENCHMARK(getVector1)->Arg(10000);
BENCHMARK(getArray1)->Arg(10000);

Click on image for quick-bench link