的性能，因爲在標準容器元素的默認初始化降解

Question

（是的，我知道有一個question幾乎相同的標題，但得到的答覆是不能令人滿意的，見下文）

編輯抱歉，原來的問題沒有使用編譯器優化。現在這個問題已經解決了，但爲了避免微不足道的優化，並且更接近我的實際使用案例，測試已經被分成了兩個編譯單元。

事實上，std::vector<>的構造函數具有線性複雜度，這對於性能關鍵型應用程序來說是一件令人討厭的事情。當時間顯著量是通過構造x浪費考慮這個簡單的代碼

// 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 

。解決這個問題的傳統方式，通過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()是固有的緩慢，使得第二種方法比第一種用於充分簡單地constructible對象實際上較慢，如size_t S，用於

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

我得到以下定時（使用gcc 4.8與-O3時;鐺3.2產生〜10％的SL奧爾代碼）

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 

的加速實際上是可能的，如果能的Elid元素的默認構造可以通過下面的欺騙版本

// 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，排除鐺的時刻）

// 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 

現在的事實，所有元素的默認初始化是沒有多線程的，從而導致潛在的嚴重性能受損降解。這裏是（有4個核，8個超線程用我的MacBook的英特爾酷睿i7芯片）爲set_omp_v0()時序和等效作弊方法：

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來避免默認初始化。 這不再符合標準，但對我的測試用例非常有用（請參閱我自己的答案，詳見this question）。

Answer 1

好了，這是因爲提出這個問題，我學到的東西。

Q1（有沒有使用標準庫的容器，這將使後者時序任何合法的方式？）是到一定程度，如由馬克和葉夫根的答案中。向std::vector的構造函數提供一個發電機的方法消除了默認構造。

Q2（有沒有使用標準庫容器，這將在多線程的情況下，給後者時序任何法律途徑？）沒有，我不這麼認爲。原因在於，在構建任何符合標準的容器都必須初始化其元素，已經確保調用元素析構函數（銷燬或調整容器大小時）是格式良好的。由於標準庫容器不支持在構建元素時使用多線程，因此Q1的技巧無法在此複製，所以我們不能忽略默認構造。

因此，如果我們想要使用C++進行高性能計算我們的選擇在管理大量數據方面有所限制。我們可以

聲明一個容器對象，並在相同的編譯單元，立即填充（同時），當編譯器優化希望在施工遠初始化;

訴諸new[]和delete[]甚至malloc()和free()，當所有的內存管理，並且在後一種情況下，要素的建設是我們的責任，也是我們的C++標準庫的潛在用途非常有限。

把戲std::vector使用自定義unitialised_allocator是elides默認建構不初始化它的元素。繼Jared Hoberock這樣的分配器的ideas看起來是這樣的（見here）：

// 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 2

隨着克++ 4.5我能夠實現在運行系統中的近似20％的減少，從V 0（1.0秒到0.8秒），並通過使用生成器來直接構造略微從0.95s至少爲0.8秒V1：

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

LIVE DEMO

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

} 

Answer 4

我確實要在這種情況下，建議推出自己的容器或尋找，因爲與我看到的方式替代，你的內在問題是不是與標準集裝箱默認構造元素。試圖使用容量可以在施工時確定的可變容量容器。

沒有實例，其中標準庫不必要的默認構造元素。 vector只有這樣做爲它的填充構造和resize，這兩者都是概念性地所需的通用容器，因爲這些點是調整所述容器包含有效的元素。同時它足夠簡單的做到這一點：

T* mem = static_cast<T*>(malloc(num * sizeof(T))); 
for (int j=0; j < num; ++j) 
    new (mem + j) T(...); // meaningfully construct T 
... 
for (int j=0; j < num; ++j) 
    mem[j].~T();   // destroy T 
free(mem); 

...然後建立一個異常安全RAII符合要求的容器上面的代碼。而這正是我建議你的情況，因爲如果默認的建設是一種浪費，足以在填充構造背景下的代替reserve和push_back或emplace_back同樣不足點不可忽略的，然後有機會，即使是集裝箱處理的能力作爲一個變量的大小是一個不可忽略的開銷，在這一點上，你更有理由去尋找其他的東西，包括從上面的概念中滾動你自己的東西。

標準庫對於它在蘋果和蘋果比較中難以置信地難以匹配的方式是非常有效的，但在這種情況下，您的需求需要橙子而不是蘋果。在這種情況下，通常開始變得更容易直接達到橙色，而不是試圖將蘋果變成橙色。