c++ - 由于标准容器中元素的默认初始化导致性能下降

Question

(是的，我知道有一个 question 的标题几乎相同，但答案并不令人满意，见下文)

编辑对不起，原来的问题没有使用编译器优化。现在已修复此问题，但为了避免琐碎的优化并更接近我的实际用例，测试已分为两个编译单元。

std::vector<> 的构造函数当涉及到性能关键的应用程序时，具有线性复杂性是一个麻烦。考虑这个简单的代码

// compilation unit 1:
void set_v0(type*x, size_t n)
{
  for(size_t i=0; i<n; ++i)
    x[i] = simple_function(i);
}

// compilation unit 2:
std::vector<type> x(n);                     // default initialisation is wasteful
set_v0(x.data(),n);                         // over-writes initial values

当大量时间浪费在构造 x 上时.正如 this question 所探讨的，解决此问题的传统方法，似乎只是保留存储和使用push_back()填写数据:

// compilation unit 1:
void set_v1(std::vector<type>&x, size_t n)
{
  x.reserve(n);
  for(size_t i=0; i<n; ++i)
    x.push_back(simple_function(i));
}

// compilation unit 2:
std::vector<type> x(); x.reserve(n);        // no initialisation
set_v1(x,n);                                // using push_back()

但是，正如我的评论所指出的，push_back()本质上很慢，对于足够简单的可构造对象，例如 size_t，第二种方法实际上比第一种方法慢 s，当为

simple_function = [](size_t i) { return i; };

我得到以下时间(使用带有 -O3 的 gcc 4.8；clang 3.2 产生的代码慢了约 10%)

timing vector::vector(n) + set_v0();
n=10000 time: 3.9e-05 sec
n=100000 time: 0.00037 sec
n=1000000 time: 0.003678 sec
n=10000000 time: 0.03565 sec
n=100000000 time: 0.373275 sec

timing vector::vector() + vector::reserve(n) + set_v1();
n=10000 time: 1.9e-05 sec
n=100000 time: 0.00018 sec
n=1000000 time: 0.00177 sec
n=10000000 time: 0.020829 sec
n=100000000 time: 0.435393 sec

如果可以省略元素的默认构造，实际上可能的加速可以通过以下作弊版本来估计

// compilation unit 2
std::vector<type> x; x.reserve(n);          // no initialisation
set_v0(x,n);                                // error: write beyond end of vector
                                            // note: vector::size() == 0

当我们得到

timing vector::vector + vector::reserve(n) + set_v0();          (CHEATING)
n=10000 time: 8e-06 sec
n=100000 time: 7.2e-05 sec
n=1000000 time: 0.000776 sec
n=10000000 time: 0.01119 sec
n=100000000 time: 0.298024 sec

那么，我的第一个问题:是否有任何合法的方式来使用标准库容器来提供这些后一个时间？还是我必须自己管理内存？

现在，我真正想要的是使用多线程来填充容器。幼稚的代码(为了简单起见，本例中使用了 openMP，暂时不包括 clang)

// compilation unit 1
void set_v0(type*x, size_t n)
{
#pragma omp for                       // only difference to set_v0() from above 
  for(size_t i=0; i<n; ++i)
    x[i] = simple_function(i);
}

// compilation unit 2:
std::vector<type> x(n);               // default initialisation not mutli-threaded
#pragma omp parallel
set_v0(x,n);                          // over-writes initial values in parallel

现在所有元素的默认初始化都不是多线程的，这会导致潜在的严重性能下降。以下是 set_omp_v0() 的时间安排和一个等效的作弊方法(使用我的macbook 4核8超线程的intel i7芯片):

timing std::vector::vector(n) + omp parallel set_v0()
n=10000 time: 0.000389 sec
n=100000 time: 0.000226 sec
n=1000000 time: 0.001406 sec
n=10000000 time: 0.019833 sec
n=100000000 time: 0.35531 sec

timing vector::vector + vector::reserve(n) + omp parallel set_v0(); (CHEATING)
n=10000 time: 0.000222 sec
n=100000 time: 0.000243 sec
n=1000000 time: 0.000793 sec
n=10000000 time: 0.008952 sec
n=100000000 time: 0.089619 sec

请注意，作弊版比串行作弊版快约 3.3 倍，大致符合预期，但标准版则不然。

那么，我的第二个问题:是否有任何合法的方法可以使用标准库容器，从而在多线程情况下提供后面的计时？

PS。我找到了 this question , 其中 std::vector通过提供 uninitialized_allocator 来欺骗它以避免默认初始化. 这不再符合标准，但非常适合我的测试用例(请参阅下面我自己的答案和 this question 了解详细信息)。

Answer 1

使用 g++ 4.5，通过使用生成器直接构建，我能够实现从 v0(1.0s 到 0.8s)的运行时间减少大约 20% 并且从 v1 的 0.95s 到 0.8s 稍微减少:

struct Generator : public std::iterator<std::forward_iterator_tag, int>
{
    explicit Generator(int start) : value_(start) { }
    void operator++() { ++value_; }
    int operator*() const { return value_; }

    bool operator!=(Generator other) const { return value_ != other.value_; }

    int value_;
};

int main()
{
    const int n = 100000000;
    std::vector<int> v(Generator(0), Generator(n));

    return 0;
}