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

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.正如这个问题所探讨的那样,传统的方法似乎只是保留存储和使用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_ts,

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

我得到以下时间(使用gcc 4.8和-O3; 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的intel i7芯片,4核,8个超线程):

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.我发现了这个问题,std::vector通过提供一个问题来避免默认初始化uninitialized_allocator.这不再符合标准,但对我的测试用例非常有效(详见下面我自己的答案和这个问题).

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;
}

Answer 2

好的,这是我问自这个问题后我学到的东西.

Q1(有没有合法的方法可以使用标准的库容器来提供后面这些时间？)在某种程度上是肯定的,如Mark和Evgeny的回答所示.std::vector向缺省构造的构造函数提供生成器的方法.

Q2(有没有合法的方法来使用标准的库容器,它会在多线程情况下提供后面这些时间？)不,我不这么认为.原因在于,在构造时,任何符合标准的容器必须初始化其元素,以确保对元素析构函数的调用(在破坏或调整容器大小时)是良好的形式.由于std库容器不支持在构造元素时使用多线程,因此Q1的技巧无法复制,因此我们不能忽略默认构造.

因此,如果我们想要使用C++进行高性能计算,那么在管理大量数据时,我们的选择会受到一些限制.我们可以

1声明一个容器对象,并且在同一个编译单元中,当编译器希望优化构造时的初始化时,立即填充它(并发);

2诉诸new[]和delete[],甚至malloc()和free(),当所有的内存管理,并且在后一种情况下,要素的建设是我们的责任,也是我们的C++标准库非常有限的潜在用途.

3招一个std::vector来使用自定义未初始化其元素unitialised_allocator是elides默认的建设.按照Jared Hoberock的想法,这样的分配器可能看起来像这样(另见这里):

// based on a design by Jared Hoberock
// edited (Walter) 10-May-2013, 23-Apr-2014
template<typename T, typename base_allocator = std::allocator<T> >
struct uninitialised_allocator
  : base_allocator
{
  static_assert(std::is_same<T,typename base_allocator::value_type>::value,
                "allocator::value_type mismatch");

  template<typename U>
  using base_t =
    typename std::allocator_traits<base_allocator>::template rebind_alloc<U>;

  // rebind to base_t<U> for all U!=T: we won't leave other types uninitialised!
  template<typename U>
  struct rebind
  {
    typedef typename
    std::conditional<std::is_same<T,U>::value,
                     uninitialised_allocator, base_t<U> >::type other; 
  }

  // elide trivial default construction of objects of type T only
  template<typename U>
  typename std::enable_if<std::is_same<T,U>::value && 
                          std::is_trivially_default_constructible<U>::value>::type
  construct(U*) {}

  // elide trivial default destruction of objects of type T only
  template<typename U>
  typename std::enable_if<std::is_same<T,U>::value && 
                          std::is_trivially_destructible<U>::value>::type
  destroy(U*) {}

  // forward everything else to the base
  using base_allocator::construct;
  using base_allocator::destroy;
};

然后unitialised_vector<>可以像这样定义模板:

template<typename T, typename base_allocator = std::allocator<T>>
using uninitialised_vector = std::vector<T,uninitialised_allocator<T,base_allocator>>;

我们仍然可以使用几乎所有标准库的功能.虽然必须说明uninitialised_allocator,并且因此暗示unitialised_vector它们不符合标准,因为它的元素不是默认构造的(例如,构造后vector<int>不会全部0构造).

当我使用这个工具来解决我的小问题时,我得到了很好的结果:

timing vector::vector(n) + set_v0();
n=10000 time: 3.7e-05 sec
n=100000 time: 0.000334 sec
n=1000000 time: 0.002926 sec
n=10000000 time: 0.028649 sec
n=100000000 time: 0.293433 sec

timing vector::vector() + vector::reserve() + set_v1();
n=10000 time: 2e-05 sec
n=100000 time: 0.000178 sec
n=1000000 time: 0.001781 sec
n=10000000 time: 0.020922 sec
n=100000000 time: 0.428243 sec

timing vector::vector() + vector::reserve() + set_v0();
n=10000 time: 9e-06 sec
n=100000 time: 7.3e-05 sec
n=1000000 time: 0.000821 sec
n=10000000 time: 0.011685 sec
n=100000000 time: 0.291055 sec

timing vector::vector(n) + omp parllel set_v0();
n=10000 time: 0.00044 sec
n=100000 time: 0.000183 sec
n=1000000 time: 0.000793 sec
n=10000000 time: 0.00892 sec
n=100000000 time: 0.088051 sec

timing vector::vector() + vector::reserve() + omp parallel set_v0();
n=10000 time: 0.000192 sec
n=100000 time: 0.000202 sec
n=1000000 time: 0.00067 sec
n=10000000 time: 0.008596 sec
n=100000000 time: 0.088045 sec

当作弊和"合法"版本之间没有任何区别时.

Answer 3

boost::transformed

对于单线程版本,您可以使用boost::transformed.它有:

返回范围类别:rng的范围类别.

这意味着,如果你会给Random Access Range到boost::transformed,它会返回Random Access Range,你会允许vector的构造函数预分配所需的内存量.

您可以按如下方式使用它:

const auto &gen = irange(0,1<<10) | transformed([](int x)
{
    return exp(Value{x});
});
vector<Value> v(begin(gen),end(gen));

现场演示

#define BOOST_RESULT_OF_USE_DECLTYPE 
#include <boost/range/adaptor/transformed.hpp>
#include <boost/container/vector.hpp>
#include <boost/range/irange.hpp>
#include <boost/progress.hpp>
#include <boost/range.hpp>
#include <iterator>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
#include <array>


using namespace std;
using namespace boost;
using namespace adaptors;

#define let const auto&

template<typename T>
void dazzle_optimizer(T &t)
{
    auto volatile dummy = &t; (void)dummy;
}

// _______________________________________ //

using Value = array<int,1 << 16>;
using Vector = container::vector<Value>;

let transformer = [](int x)
{
    return Value{{x}};
};
let indicies = irange(0,1<<10);

// _______________________________________ //

void random_access()
{
    let gen = indicies | transformed(transformer);
    Vector v(boost::begin(gen), boost::end(gen));
    dazzle_optimizer(v);
}

template<bool reserve>
void single_pass()
{
    Vector v;
    if(reserve)
        v.reserve(size(indicies));
    for(let i : indicies)
        v.push_back(transformer(i));
    dazzle_optimizer(v);
}

void cheating()
{
    Vector v;
    v.reserve(size(indicies));
    for(let i : indicies)
        v[i]=transformer(i);
    dazzle_optimizer(v);
}

// _______________________________________ //

int main()
{
    struct
    {
        const char *name;
        void (*fun)();
    } const tests [] =
    {
        {"single_pass, no reserve",&single_pass<false>},
        {"single_pass, reserve",&single_pass<true>},
        {"cheating reserve",&cheating},
        {"random_access",&random_access}
    };
    for(let i : irange(0,3))
        for(let test : tests)
            progress_timer(), // LWS does not support auto_cpu_timer
                (void)i,
                test.fun(),
                cout << test.name << endl;

}