std::vector今日は、との gcc 最適化可能性のいくつかの違いをベンチマークして比較することにしましたstd::array。一般的に、私が期待していたことがわかりました。短い配列のコレクションのそれぞれに対してタスクを実行すると、コレクションと同等のベクトルに対してタスクを実行するよりもはるかに高速です。
ただし、予期しないstd::vectorstd::arrayことがわかりました。配列のコレクションを格納するためにを使用する方が、 を使用するよりも高速です。スタック上の大量のデータのアーティファクトの結果である場合に備えて、ヒープ上の配列として、およびヒープ上の C スタイルの配列として割り当ててみました (ただし、結果は依然として配列のように見えます)。スタック上の配列と配列のベクトル)。
なぜパフォーマンスが向上するのか（コンパイラがコンパイル時の情報をより多く持っている）について何かstd::vector考えはありますか？std::array
を使用してコンパイルしましたgcc-4.7 -std=c++11 -O3（gcc-4.6 -std=c++0x -O3この難問も発生するはずです）。bash実行時間は、 -nativetimeコマンド (ユーザー時間)を使用して計算されました。
コード：
#include <array>
#include <vector>
#include <iostream>
#include <assert.h>
#include <algorithm>
template <typename VEC>
double fast_sq_dist(const VEC & lhs, const VEC & rhs) {
assert(lhs.size() == rhs.size());
double result = 0.0;
for (int k=0; k<lhs.size(); ++k) {
double tmp = lhs[k] - rhs[k];
result += tmp * tmp;
}
return result;
}
int main() {
const std::size_t K = 20000;
const std::size_t N = 4;
// declare the data structure for the collection
// (uncomment exactly one of these to time it)
// array of arrays
// runtime: 1.32s
std::array<std::array<double, N>, K > mat;
// array of arrays (allocated on the heap)
// runtime: 1.33s
// std::array<std::array<double, N>, K > & mat = *new std::array<std::array<double, N>, K >;
// C-style heap array of arrays
// runtime: 0.93s
// std::array<double, N> * mat = new std::array<double, N>[K];
// vector of arrays
// runtime: 0.93
// std::vector<std::array<double, N> > mat(K);
// vector of vectors
// runtime: 2.16s
// std::vector<std::vector<double> > mat(K, std::vector<double>(N));
// fill the collection with some arbitrary values
for (std::size_t k=0; k<K; ++k) {
for (std::size_t j=0; j<N; ++j)
mat[k][j] = k*N+j;
}
std::cerr << "constructed" << std::endl;
// compute the sum of all pairwise distances in the collection
double tot = 0.0;
for (std::size_t j=0; j<K; ++j) {
for (std::size_t k=0; k<K; ++k)
tot += fast_sq_dist(mat[j], mat[k]);
}
std::cout << tot << std::endl;
return 0;
}
注意 1:すべてのバージョンで同じ結果が出力されます。
NB 2:std::array<std::array<double, N>, K>、std::vector<std::array<double, N> >、およびの間の実行時間の違いが、std::vector<std::vector<double> >単に割り当て時の割り当て/初期化によるものではないことを示すために、単にコレクションを割り当てた場合 (つまり、 の計算と出力をコメントアウトしたtot場合) の実行時間は 0.000 秒、0.000 秒、それぞれ0.004秒。
注意 3:キャッシングの不公平な違いを防ぐために、各メソッドは個別にコンパイルされて実行されます (同じ実行可能ファイル内で連続して実行されるわけではありません)。
注意 4:
配列の配列のアセンブリ: http://ideone.com/SM8dB
配列のベクトルのアセンブリ: http://ideone.com/vhpJv
ベクトルのベクトルのアセンブリ: http://ideone.com/RZTNE
NB 5:はっきりさせておきたいのですが、私は決して STL を批判するつもりはありません。STL が大好きで、頻繁に使用するだけでなく、効果的な使用方法の詳細から、C++ の巧妙で優れた機能の多くを学ぶことができました。代わりに、これは知的な追求です。効率的な C++ 設計の原則を学ぶタイミングを計っていただけです。
さらに、ランタイム差の原因をデコンボリューションするのは難しいため、STL のせいにするのは適切ではありません。最適化をオフにすると、不必要なコピー操作 (最適化されて実稼働コードでは実行されない) から発生する可能性があり、他のデータ型よりも特定のデータ型に偏る可能性があります。
あなたが私のように興味があるなら、これを理解するためにあなたの助けが欲しい.