Vecteur vs les Performances de la baie

Dans un autre thread, j'ai commencé une discussion sur les Vecteurs et les Matrices, dans lequel j'ai été largement jouer l'avocat du diable, pour les boutons-poussoirs. Cependant, au cours de cette, je suis tombé sur un cas de test qui m'a un peu perplexe, et je voudrais avoir une vraie discussion à ce sujet, sur les "abus" je suis la pour jouer l'avocat du diable, de lancer un véritable débat sur ce thread est maintenant impossible. Cependant, l'exemple particulier m'a intrigué, et je ne peux pas l'expliquer à moi-même de manière satisfaisante.

La discussion est sur les performances générales du Vecteur vs Tableaux, en ignorant les éléments dynamiques. Ex: évidemment, l'utilisation constante de la push_back() dans un vecteur va le ralentir. Nous supposons que le vecteur et matrice sont pré-remplis avec les données. L'exemple que j'ai présenté, et modifiée par la suite par un individu dans le fil, est le suivant:

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

Lorsque je l'exécute sur ma machine, j'ai le terminal de sortie. La première manche est avec le vecteur ligne sans commentaire, la seconde est la matrice ligne sans commentaire. J'ai utilisé le plus haut niveau d'optimisation, pour donner le vecteur le plus de chance de succès. Ci-dessous sont mes résultats, les deux premières courses de la gamme ligne sans commentaire, la deuxième à deux avec le vecteur ligne.

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

Que les piles de surpasser les vecteurs ne me surprend pas, cependant, que la différence est de l'ordre de 50% me surprend beaucoup, je m'attends à ce qu'ils seraient négligeables, et je me sens comme la nature de ce test m'être obscurcir la nature des résultats. Lorsque vous exécutez ce test sur le tableau des tailles plus petites, les différences de performances dissiper de façon spectaculaire.

Mon explication:

Supplémentaires de la mise en œuvre des instructions vectorielles sont à l'origine du vecteur instructions pour l'aligner dans la mémoire de mal, peut-être même sur cet exemple, un split à vraiment un mauvais point sur 2 différents "blocs". Ceci est à l'origine de la mémoire de sauter en arrière-et-vient entre les niveaux de cache vs cache de données vs cache d'instructions de plus en plus fréquemment que vous attendez. Je pense aussi que le compilateur LLVM peut-être exagérer les faiblesses, et de l'optimisation de mal, à cause de certains des plus récents de C++11 éléments, mais je n'ai aucune raison pour ces explications en dehors de l'hypothèse et de la conjecture.

Je suis intéressé si Un: que quelqu'un peut reproduire mes résultats et B: si quelqu'un a une meilleure explication de la façon dont l'ordinateur est en cours d'exécution cette référence et pourquoi vecteur est donc considérablement moins performants tableaux dans cette instance.

Mon set up: http://www.newegg.com/Product/Product.aspx?Item=N82E16834100226

OriginalL'auteur ChrisCM | 2013-05-08