Vektor vs Array Leistung

Question

In einem anderen Thread begann ich eine Diskussion über Vektoren und Arrays, in denen ich weitgehend Teufel Advocatus, Tasten zu drücken spielte. Ich bin dabei jedoch auf einen Testfall gestoßen, der mich ein wenig perplex macht, und ich würde gerne eine echte Diskussion darüber führen, über den "Missbrauch", den ich bekomme, um den Advokaten des Teufels zu spielen und einen echten zu beginnen Diskussion über diesen Thread ist jetzt unmöglich. Das besondere Beispiel hat mich jedoch fasziniert, und ich kann es mir nicht befriedigend erklären.

In der Diskussion geht es um die allgemeine Leistung von Vector vs Arrays, wobei dynamische Elemente ignoriert werden. Bsp .: Offensichtlich wird die kontinuierliche Verwendung von push_back() in einem Vektor es verlangsamen. Wir nehmen an, dass der Vektor und das Array bereits mit Daten gefüllt sind. Das Beispiel, das ich vorgelegt und anschließend von einer Person im Thread geändert, war der folgende:

#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]; 
    } 
} 

Wenn ich laufe dies auf meiner Maschine, bekomme ich folgende Terminal-Ausgabe. Der erste Lauf ist mit der Vektorlinie unkommentiert, der zweite ist mit der Arraylinie unkommentiert. Ich habe die höchste Optimierungsebene verwendet, um dem Vektor die besten Erfolgschancen zu geben. Im Folgenden sind meine Ergebnisse, die ersten beiden läuft mit der Array-Zeile unkommentiert, die beiden anderen mit der Vektorlinie.

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

dass Arrays Vektoren übertreffen überrascht mich nicht, jedoch, dass der Unterschied in der Größenordnung von 50% überrascht mich sehr, ich würde erwarten, dass sie vernachlässigbar sein würde, und ich fühle mich wie die Natur dieser Testfall mich die Natur der Ergebnisse verdunkeln. Wenn Sie diesen Test für kleinere Array-Größen ausführen, werden die Leistungsunterschiede drastisch reduziert.

Meine Erklärung:

Die zusätzlichen Durchführungsanweisungen für Vektor verursachen die Vektorbefehle schlecht in Erinnerung auszurichten, vielleicht sogar auf diesem Beispiel eine Spaltung zu einem wirklich schlechten Punkt auf 2 verschiedenen „Blöcke“. Dies führt dazu, dass der Speicher häufiger zwischen den Ebenen von Cache und Datencache/Befehlscache hin und her springt als erwartet. Ich vermute auch, dass der LLVM-Compiler aufgrund einiger der neueren C++ 11-Elemente Schwächen übertreibt und schlecht optimiert, obwohl ich neben Hypothese und Vermutung keinen Grund für eine dieser Erklärungen habe.

Ich bin interessiert, wenn A: dass jemand meine Ergebnisse replizieren kann und B: wenn jemand eine bessere Erklärung dafür hat, wie der Computer diesen bestimmten Benchmark ausführt und warum Vektor in diesem Fall Arrays so dramatisch unterfordert.

Mein einrichten: http://www.newegg.com/Product/Product.aspx?Item=N82E16834100226

Answer 1

Ich kann garantieren, dass LLVM tut InFact misoptimize std :: vector (wenn Sie in der Tat überhaupt zu optimieren), zumindest im Augenblick von. Viele der beteiligten Funktionsaufrufe werden nicht korrekt eingebunden. Sie erhalten eine bessere Leistung mit GCC.

Answer 2

Eine einfachere Erklärung: Sie bauen mit deaktivierten Optimierungen. Sie möchten -O3, nicht -o3.

Ich habe nicht klappern zur Verfügung genau Ihre Tests zu reproduzieren, aber meine Ergebnisse sind wie folgt:

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