29

(はい、ほとんど同じタイトルの質問があることは知っていますが、回答は満足のいくものではありませんでした。以下を参照してください)

編集申し訳ありませんが、元の質問ではコンパイラの最適化を使用していませんでした。これは修正されましたが、些細な最適化を避け、実際のユースケースに近づけるために、テストは 2 つのコンパイル ユニットに分割されました。

のコンストラクター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()は本質的に遅いため、この 2 番目のアプローチは、 sなどの十分に単純な構築可能なオブジェクトの最初のアプローチよりも実際には遅くなります。size_t

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()と同等のチート方法を次に示します (4 コア、8 ハイパースレッドを備えた私の MacBook の 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 倍高速であることに注意してください。これはほぼ予想どおりですが、標準バージョンはそうではありません。

だから、私の2 番目の質問: マルチスレッドの状況でこれらの後者のタイミングを与える標準ライブラリ コンテナーを使用する合法的な方法はありますか?

PS。私はこの質問を見つけましstd::vectoruninitialized_allocator。これはもはや標準に準拠していませんが、私のテスト ケースでは非常にうまく機能します (詳細については、以下の私自身の回答とこの質問を参照してください)。

4

4 に答える 4

12

g++ 4.5 では、ジェネレーターを使用して直接構築することで、v0 から実行時間を約 20% (1.0 秒から 0.8 秒に) 短縮し、v1 では 0.95 秒から 0.8 秒にわずかに短縮することができました。

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;
}
于 2013-04-11T15:48:08.413 に答える
12

さて、この質問をしてから学んだことは次のとおりです。

Q1 (これらの後者のタイミングを提供する標準ライブラリ コンテナーを使用する合法的な方法はありますか? ) Mark と Evgeny による回答に示されているように、ある程度はい。ジェネレーターを elide のコンストラクターに提供する方法はstd::vector、デフォルトの構成です。

Q2 (マルチスレッドの状況でこれらの後者のタイミングを与える標準ライブラリ コンテナーを使用する合法的な方法はありますか? )いいえ、そうは思いません。その理由は、構築時に、標準準拠のコンテナは要素を初期化する必要があり、(コンテナの破棄またはサイズ変更時に) 要素デストラクタへの呼び出しが整形式であることを確認する必要があるためです。std ライブラリ コンテナーは、要素の構築におけるマルチスレッドの使用をサポートしていないため、Q1のトリックをここで複製することはできません。そのため、デフォルトの構築を省略することはできません。

したがって、ハイ パフォーマンス コンピューティングに C++ を使用したい場合、大量のデータを管理する場合、オプションはいくらか制限されます。私たちはできる

1コンテナー オブジェクトを宣言し、同じコンパイル単位で、すぐに (同時に) 埋めます。

2すべてのメモリ管理と、後者の場合は要素の構築が私たちの責任であり、C++ 標準ライブラリの潜在的な使用が非常に制限されている場合、new[]anddelete[]またはand に頼ることさえmalloc()あります。free()

3デフォルトの構造を無視std::vectorするカスタムを使用して要素を初期化しないようにaをだまします。Jared Hoberockunitialised_allocatorアイデアに従うと、そのようなアロケータは次のようになります (こちらも参照)。

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

標準ライブラリのほぼすべての機能を引き続き使用できます。ただし、要素がデフォルトで構築されていないため (たとえば、 aは構築後にすべてを持たないため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

不正行為と「合法」バージョンの間にもはや違いがないとき。

于 2013-04-12T08:41:31.320 に答える
6

boost::transformed

シングルスレッド バージョンの場合は、 を使用できますboost::transformed。それは持っています:

返される範囲カテゴリ: rng の範囲カテゴリ。

つまり、 に与えるRandom Access Rangeboost::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;

}
于 2013-04-11T20:20:39.637 に答える