c++ - vector 和原始 C 风格数组之间的性能比较

Question

我分析了 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 us 时间创建:在 testVectorSpeed.cpp 中的 getVector1() 中有 10000000 个元素 vector

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

Answer 1

此成本归结为 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}