ベクトルと配列のパフォーマンス

Question

別のスレッドでは、私は大部分が悪魔の主張者であるボタンを押すために使っていたベクトルと配列に関する議論を始めました。しかし、この過程で、私はちょっと困惑したテストケースに遭遇しました。私は悪魔の主唱者を演じるために得ている「虐待」について、本当の議論をしたいと思いますそのスレッドに関する議論は現在不可能です。しかし、特定の例は興味をそそられており、私はそれを満足に説明することはできません。

ダイナミックエレメントを無視して、Vector vs Arraysの一般的なパフォーマンスについて説明します。例：明らかに、ベクトル内で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番目のシーケンスはベクターラインで実行します。配列はベクターには差が50％程度であること、しかし、私は驚かないん凌駕

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

は非常に私を驚き、私は彼らが無視できるだろうと期待する、と私はこの自然のように感じますテストケース私は結果の性質を不明瞭にしています。小さいサイズのアレイでこのテストを実行すると、パフォーマンスの差異は劇的に減少します。

私の説明：ベクトルの

追加の実装手順は、おそらくこの例では、2つの異なる「ブロック」には本当に悪い点でスプリットに、ベクトル命令が悪いメモリに整列する原因となっています。これは、メモリとキャッシュのレベル間で、データキャッシュと命令キャッシュの間で予想以上に頻繁にジャンプする原因となります。私はまた、LLVMコンパイラが、新しいC++ 11要素のいくつかのために、弱点を誇張して最適化していないと推測していますが、これらの説明のいずれかに仮説と推測以外の理由もありません。

A：誰かが私の結果を複製することができ、B：コンピュータがこの特定のベンチマークをどのように実行しているかについてのより良い説明があり、ベクトルがこのインスタンスでは非常にパフォーマンスの低いアレイである理由について興味があります。

私が設定：http://www.newegg.com/Product/Product.aspx?Item=N82E16834100226

Answer 1

（あなたがすべてで最適化することであるならば）私はLLVMはInfactはmisoptimizeのはstd ::ベクトルをしていることを保証することができ、少なくとも今のように。それは関係する関数呼び出しの多くを正しくインライン化しません。あなたはGCCでより良いパフォーマンスを得るでしょう。

Answer 2

簡単な説明：最適化を無効にしてビルドしています。 -O3が必要です。-o3ではありません。

私は正確にテストを再現するために利用できる打ち鳴らすはありませんが、次のように私の結果は以下のとおりです。

//Array run # 1 
$ g++ -std=c++11 -O3 test.cpp -o b.out && time ./b.out 

real 0m25.323s 
user 0m25.162s 
sys 0m0.148s 

//Vector run #1 
$ g++ -std=c++11 -O3 test.cpp -o b.out && time ./b.out 

real 0m25.634s 
user 0m25.486s 
sys 0m0.136s