別のスレッドで、私はベクトルと配列についての議論を開始しました。そこでは、主にボタンを押すための悪魔の代弁者を演じていました。しかし、この過程で、私は少し戸惑うテストケースに出くわしました.悪魔の擁護者を演じることで得られる「虐待」について、本当の議論をしたいと思います。そのスレッドでの議論は現在不可能です。しかし、その特定の例に興味をそそられ、自分自身に十分に説明することはできません.
議論は、動的要素を無視して、ベクトルと配列の一般的なパフォーマンスについてです。例: ベクトルで push_back() を継続的に使用すると、明らかに速度が低下します。ベクトルと配列にはデータが事前に入力されていると想定しています。私が提示し、その後スレッド内の個人によって変更された例は次のとおりです。
#include <iostream>
#include <vector>
#include <type_traits>
using namespace std;
const int ARRAY_SIZE = 500000000;
// http://stackoverflow.com/a/15975738/500104
template <class T>
class no_init_allocator
{
public:
typedef T value_type;
no_init_allocator() noexcept {}
template <class U>
no_init_allocator(const no_init_allocator<U>&) noexcept {}
T* allocate(std::size_t n)
{return static_cast<T*>(::operator new(n * sizeof(T)));}
void deallocate(T* p, std::size_t) noexcept
{::operator delete(static_cast<void*>(p));}
template <class U>
void construct(U*) noexcept
{
// libstdc++ doesn't know 'is_trivially_default_constructible', still has the old names
static_assert(is_trivially_default_constructible<U>::value,
"This allocator can only be used with trivally default constructible types");
}
template <class U, class A0, class... Args>
void construct(U* up, A0&& a0, Args&&... args) noexcept
{
::new(up) U(std::forward<A0>(a0), std::forward<Args>(args)...);
}
};
int main() {
srand(5); //I use the same seed, we just need the random distribution.
vector<char, no_init_allocator<char>> charArray(ARRAY_SIZE);
//char* charArray = new char[ARRAY_SIZE];
for(int i = 0; i < ARRAY_SIZE; i++) {
charArray[i] = (char)((i%26) + 48) ;
}
for(int i = 0; i < ARRAY_SIZE; i++) {
charArray[i] = charArray[rand() % ARRAY_SIZE];
}
}
これを自分のマシンで実行すると、次の端末出力が得られます。最初の実行はベクトル行のコメントを外したもので、2 回目は配列行のコメントを外したものです。ベクトルに最高の成功のチャンスを与えるために、最高レベルの最適化を使用しました。以下は私の結果です。最初の 2 回は配列行のコメントを外して実行し、次の 2 回はベクトル行を使用して実行しました。
//Array run # 1
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out
real 0m20.287s
user 0m20.068s
sys 0m0.175s
//Array run # 2
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out
real 0m21.504s
user 0m21.267s
sys 0m0.192s
//Vector run # 1
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out
real 0m28.513s
user 0m28.292s
sys 0m0.178s
//Vector run # 2
clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out
real 0m28.607s
user 0m28.391s
sys 0m0.178s
配列がベクトルよりも優れていることは驚くことではありませんが、その差が 50% 程度であることには非常に驚かされます。結果の。より小さな配列サイズでこのテストを実行すると、パフォーマンスの違いは劇的に解消されます。
私の説明：
ベクトルの追加の実装命令により、ベクトル命令のメモリ内での整列が不十分になり、おそらくこの例でも、2 つの異なる「ブロック」の非常に悪いポイントで分割されています。これにより、メモリがキャッシュ、データ キャッシュ、命令キャッシュのレベル間を予想よりも頻繁に行き来します。また、新しい C++11 要素の一部が原因で、LLVM コンパイラが弱点を誇張し、最適化が不十分である可能性もあると思いますが、仮説と推測以外にこれらの説明のいずれにも理由はありません。
A: 誰かが私の結果を再現できるかどうか、B: コンピューターがこの特定のベンチマークをどのように実行しているか、およびこのインスタンスでベクトルが配列のパフォーマンスを大幅に下回っている理由について、誰かがより良い説明を持っているかどうかに興味があります。
私のセットアップ: http://www.newegg.com/Product/Product.aspx?Item=N82E16834100226