(はい、ほとんど同じタイトルの質問があることは知っていますが、回答は満足のいくものではありませんでした。以下を参照してください)
編集申し訳ありませんが、元の質問ではコンパイラの最適化を使用していませんでした。これは修正されましたが、些細な最適化を避け、実際のユースケースに近づけるために、テストは 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::vector
たuninitialized_allocator
。これはもはや標準に準拠していませんが、私のテスト ケースでは非常にうまく機能します (詳細については、以下の私自身の回答とこの質問を参照してください)。