std :: vector est tellement plus lent que les tableaux simples?

Question

J'ai toujours pensé que c'est la sagesse générale qu' std::vector est "mis en œuvre comme un tableau," blah blah blah. Aujourd'hui je suis allé vers le bas et l'a testé, ne semble pas être si:

Voici quelques résultats du test:

UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds

C'est au sujet de 3 - 4 fois plus lent! N'a pas vraiment justifier pour le "vector peut être plus lente pour quelques nanosecs" des commentaires.

Et le code que j'ai utilisé:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
public:
    TestTimer(const std::string & name) : name(name),
        start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
    {
    }

    ~TestTimer()
    {
        using namespace std;
        using namespace boost;

        posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
        posix_time::time_duration d = now - start;

        cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
            " seconds" << endl;
    }

private:
    std::string name;
    boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector()
{
    TestTimer t("UseVector");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPushBack");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        free(pixels);
    }
}

int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}

Suis-je le fais mal ou quelque chose? Ou ai-je juste éclaté cette performance mythe?

Edit: je suis en utilisant le mode de Libération dans MSVS2005.

---

Dans MSVC, #define _SECURE_SCL 0 réduit UseVector de moitié (de le ramener à 4 secondes). C'est vraiment énorme de l'OMI.

Answer 1

En utilisant les éléments suivants:

g++ -O3 Time.cpp -je <MyBoost>
./un.hors
UseArray achevé en 2.196 secondes
UseVector achevé en 4.412 secondes
UseVectorPushBack achevé en 8.017 secondes
Le tout complété en 14.626 secondes

Si la matrice est deux fois plus rapide que vecteur.

Mais après avoir regardé le code en détail ce qui est attendu; que vous exécutez à travers le vecteur à deux reprises et le tableau qu'une seule fois. Remarque: lorsque vous redimensionnez() le vecteur vous n'êtes pas seulement l'allocation de la mémoire, mais également en cours d'exécution par le vecteur d'appeler le constructeur de chaque membre.

Ré-Organiser le code légèrement de sorte que le seul vecteur initialise chaque objet une fois:

 std::vector<Pixel>  pixels(dimensions * dimensions, Pixel(255,0,0));

Maintenant le même temps de nouveau:

g++ -O3 Time.cpp -je <MyBoost>
./un.hors
UseVector achevé en 2.216 secondes

Le vecteur maintenant des performances légèrement pire que le tableau. OMI, cette différence est négligeable et pourrait être causé par tout un tas de choses pas associé avec le test.

Je voudrais aussi prendre en compte que vous n'êtes pas correctement initialisation/Détruire le Pixel de l'objet dans le UseArrray() la méthode que ni constructeur/destructeur n'est pas appelé (cela peut ne pas être un problème pour cette classe simple, mais quelque chose de légèrement plus complexe (c'est à dire avec des pointeurs ou des membres avec les pointeurs) va causer des problèmes.

Answer 2

Grande question. Je suis venu ici en attendant de trouver quelque solution simple qui permettrait d'accélérer le vecteur des tests de droite vers le haut. Cela ne fonctionne pas tout à fait comme je l'espérais!

Optimisation de l'aide, mais ça ne suffit pas. Avec l'optimisation, je suis toujours de voir un 2X différence de performances entre UseArray et UseVector. Il est intéressant de noter, UseVector était significativement plus lente que UseVectorPushBack sans optimisation.

# g++ -Wall -Wextra -pedantic -o vector vector.cpp
# ./vector
UseArray completed in 20.68 seconds
UseVector completed in 120.509 seconds
UseVectorPushBack completed in 37.654 seconds
The whole thing completed in 178.845 seconds
# g++ -Wall -Wextra -pedantic -O3 -o vector vector.cpp
# ./vector
UseArray completed in 3.09 seconds
UseVector completed in 6.09 seconds
UseVectorPushBack completed in 9.847 seconds
The whole thing completed in 19.028 seconds

Idée #1 - Utiliser les nouvelles[] à la place de malloc

J'ai essayé de changer malloc() de new[] dans UseArray de sorte que les objets obtiendrait construit. Et l'évolution de l'individu cession de terrain à l'affectation d'un Pixel de l'instance. Oh, et le renommage de la boucle interne variable j.

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {   
        int dimension = 999;

        // Same speed as malloc().
        Pixel * pixels = new Pixel[dimension * dimension];

        for(int j = 0 ; j < dimension * dimension; ++j)
            pixels[j] = Pixel(255, 0, 0);

        delete[] pixels;
    }
}

Étonnamment (pour moi), aucun de ces changements fait aucune différence. Pas même le changement d' new[] qui sera, par défaut, de construire tous les Pixels. Il semble que gcc peut optimiser le constructeur par défaut des appels lors de l'utilisation d' new[], mais pas lors de l'utilisation d' vector.

Idée #2 - Supprimer répétée de l'opérateur[] appels

J'ai également essayé de se débarrasser de la triple - operator[] de recherche et de mise en cache de la référence à l' pixels[j]. Que fait ralenti UseVector! Oups.

for(int j = 0; j < dimension * dimension; ++j)
{
    // Slower than accessing pixels[j] three times.
    Pixel &pixel = pixels[j];
    pixel.r = 255;
    pixel.g = 0;
    pixel.b = 0;
}

# ./vector 
UseArray completed in 3.226 seconds
UseVector completed in 7.54 seconds
UseVectorPushBack completed in 9.859 seconds
The whole thing completed in 20.626 seconds

Idée #3 - Supprimer les constructeurs

Qu'en supprimant les constructeurs entièrement? Alors peut-être gcc pouvez optimiser la construction de tous les objets lorsque les vecteurs sont créés. Qu'advient-il si nous changeons de Pixel:

struct Pixel
{
    unsigned char r, g, b;
};

Résultat: environ 10% plus rapide. Encore plus lent qu'un tableau. Hm.

# ./vector 
UseArray completed in 3.239 seconds
UseVector completed in 5.567 seconds

Idée n ° 4 - Utiliser l'itérateur à la place de l'indice de boucle

Comment sur l'utilisation d'un vector<Pixel>::iterator au lieu d'un indice de boucle?

for (std::vector<Pixel>::iterator j = pixels.begin(); j != pixels.end(); ++j)
{
    j->r = 255;
    j->g = 0;
    j->b = 0;
}

Résultat:

# ./vector 
UseArray completed in 3.264 seconds
UseVector completed in 5.443 seconds

Nope, pas différent. Au moins, il n'est pas plus lent. J'ai pensé que ce serait une performance similaire à #2 où j'ai utilisé un Pixel& de référence.

Conclusion

Même si certains futés chiffres comment faire le vecteur en boucle aussi vite que le tableau, cela ne veut pas dire du bien de le comportement par défaut de std::vector. Voilà pour le compilateur assez intelligent pour optimiser toutes les C++ness et de faire des conteneurs STL aussi vite que les matières premières des tableaux.

La ligne de fond est que le compilateur est pas en mesure d'optimiser loin le non-op constructeur par défaut des appels lors de l'utilisation d' std::vector. Si vous utilisez plain new[] il optimise loin l'amende juste. Mais pas avec std::vector. Même si vous pouvez réécrire votre code d'éliminer le constructeur appelle qui vole en face de l'mantra ici: "Le compilateur est plus intelligent que vous. Le TSL est tout aussi rapide que la plaine C. Ne vous inquiétez pas à ce sujet."

Answer 3

Pour être juste, on ne peut pas comparer une implémentation C++ à C de mise en œuvre, que je voudrais appeler votre malloc version. malloc ne pas créer d'objets - il n'alloue de la mémoire brute. Que vous de traiter ce mémoire comme des objets sans appeler le constructeur est de mauvaise C++ (et éventuellement non valide - je vais laisser ça à la langue des avocats).

Cela dit, il suffit de changer le malloc de new Pixel[dimensions*dimensions] et gratuit pour delete [] pixels n'a pas beaucoup de différence avec la simple mise en œuvre de Pixels que vous avez. Voici les résultats sur ma boîte (E6600, 64 bits):

UseArray completed in 0.269 seconds
UseVector completed in 1.665 seconds
UseVectorPushBack completed in 7.309 seconds
The whole thing completed in 9.244 seconds

Mais avec un léger changement, les tables tournent:

Pixels.h

struct Pixel
{
    Pixel();
    Pixel(unsigned char r, unsigned char g, unsigned char b);

    unsigned char r, g, b;
};

Pixel.cc

#include "Pixel.h"

Pixel::Pixel() {}
Pixel::Pixel(unsigned char r, unsigned char g, unsigned char b) 
  : r(r), g(g), b(b) {}

main.cc

#include "Pixel.h"
[rest of test harness without class Pixel]
[UseArray now uses new/delete not malloc/free]

Compilé de cette façon:

$ g++ -O3 -c -o Pixel.o Pixel.cc
$ g++ -O3 -c -o main.o main.cc
$ g++ -o main main.o Pixel.o

nous obtenons des résultats très différents:

UseArray completed in 2.78 seconds
UseVector completed in 1.651 seconds
UseVectorPushBack completed in 7.826 seconds
The whole thing completed in 12.258 seconds

Avec un non-inline constructeur de Pixel, std::vector bat maintenant raw d'un tableau.

Il semblerait que la complexité de l'allocation par des std::vector et std:allocateur est trop pour être optimisé de manière aussi efficace comme un simple new Pixel[n]. Cependant, nous pouvons voir que le problème est simplement de l'allocation de ne pas le vecteur d'accès en modifiant un couple de fonctions de test pour créer le vecteur/matrice, une fois en le déplaçant à l'extérieur de la boucle:

void UseVector()
{
    TestTimer t("UseVector");

    int dimension = 999;
    std::vector<Pixel> pixels;
    pixels.resize(dimension * dimension);

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

et

void UseArray()
{
    TestTimer t("UseArray");

    int dimension = 999;
    Pixel * pixels = new Pixel[dimension * dimension];

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
    delete [] pixels;
}

Nous obtenons ces résultats sont maintenant:

UseArray completed in 0.254 seconds
UseVector completed in 0.249 seconds
UseVectorPushBack completed in 7.298 seconds
The whole thing completed in 7.802 seconds

Ce que nous pouvons apprendre de cela, c'est que std::vector est comparable à un raw tableau pour l'accès, mais si vous avez besoin de créer et de supprimer le vecteur/matrice à de nombreuses reprises, la création d'un objet complexe prendront plus de temps que la création d'un tableau simple lorsque l'élément du constructeur n'est pas insérée. Je ne pense pas que c'est très surprenant.

Answer 4

Essayez avec ceci:

void UseVectorCtor()
{
    TestTimer t("UseConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
    }
}

Je reçois presque exactement les mêmes performances qu'avec le tableau.

La chose à propos de vector c'est qu'il est beaucoup plus général que d'un tableau. Et cela signifie que vous devez tenir compte de la façon dont vous l'utilisez. Il peut être utilisé dans un grand nombre de façons différentes, qui fournit les fonctionnalités qu'un tableau n'a pas même. Et si vous l'utilisez "mauvais" pour votre but, vous engager beaucoup de frais généraux, mais si vous l'utilisez correctement, il est généralement fondamentalement un zéro frais généraux de la structure de données. Dans ce cas, le problème est que vous initialisées séparément le vecteur (l'origine de tous les éléments ont leur défaut ctor appelé), et puis l'écrasement de chaque élément individuellement avec la valeur correcte. C'est beaucoup plus difficile pour le compilateur d'optimiser loin que lorsque vous faites la même chose avec un tableau. C'est pourquoi le vecteur fournit un constructeur qui permet de faire exactement cela: initialiser N les éléments dont la valeur X.

Et lorsque vous l'utilisez, le vecteur est tout aussi rapide comme un tableau.

Donc non, vous n'avez pas cassé le mythe de la performance. Mais vous ont montré que c'est seulement vrai si vous utilisez le vecteur de manière optimale, ce qui est un très bon point aussi. :)

Sur le côté positif, c'est vraiment le plus simple d'utilisation qui s'avère être le plus rapide. Si vous comparez mon extrait de code (une seule ligne) avec Jean Kugelman réponse, contenant des tas et des tas de réglages et optimisations, ce qui n'est pas toujours tout à fait d'éliminer la différence de performances, il est assez clair que l' vector est assez intelligemment conçus, après tout. Vous n'avez pas à sauter à travers des cerceaux pour obtenir la vitesse égale à un tableau. Au contraire, vous devez utiliser la plus simple solution possible.

Answer 5

Son était à peine à une comparaison équitable quand j'ai regardé ton code, j'ai vraiment pensé que vous n'étiez pas comparer des pommes avec des pommes. Alors j'ai pensé, permet d'obtenir les constructeurs et le destructeur est appelé sur tous les tests; puis de les comparer.

const size_t dimension = 1000;

void UseArray() {
    TestTimer t("UseArray");
    for(size_t j = 0; j < dimension; ++j) {
        Pixel* pixels = new Pixel[dimension * dimension];
        for(size_t i = 0 ; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
        delete[] pixels;
    }
}

void UseVector() {
    TestTimer t("UseVector");
    for(size_t j = 0; j < dimension; ++j) {
        std::vector<Pixel> pixels(dimension * dimension);
        for(size_t i = 0; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
    }
}

int main() {
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();

    return 0;
}

Mes pensées étaient, avec cette mise en place, ils devraient être exactement les mêmes. S'avère, j'ai eu tort.

UseArray completed in 3.06 seconds
UseVector completed in 4.087 seconds
The whole thing completed in 10.14 seconds

Alors, pourquoi cette 30% de perte de performance encore se produire? Le TSL a tout dans les en-têtes, de sorte qu'il aurait été possible pour le compilateur de comprendre tout ce qui était nécessaire.

Mes pensées ont été que c'est dans la façon dont la boucle initialise toutes les valeurs par défaut du constructeur. J'ai donc effectué un test:

class Tester {
public:
    static int count;
    static int count2;
    Tester() { count++; }
    Tester(const Tester&) { count2++; }
};
int Tester::count = 0;
int Tester::count2 = 0;

int main() {
    std::vector<Tester> myvec(300);
    printf("Default Constructed: %i\nCopy Constructed: %i\n", Tester::count, Tester::count2);

    return 0;
}

Les résultats ont été comme je le soupçonnais:

Default Constructed: 1
Copy Constructed: 300

C'est clairement la source de la ralentir, le fait que le vecteur utilise le constructeur de copie d'initialiser les éléments de défaut d'un objet construit.

Cela signifie, que le pseudo-ordre d'opération se passe lors de la construction du vecteur:

Pixel pixel;
for (auto i = 0; i < N; ++i) vector[i] = pixel;

Qui, en raison de l'implicite constructeur de copie faite par le compilateur, est remplacée par la suivante:

Pixel pixel;
for (auto i = 0; i < N; ++i) {
    vector[i].r = pixel.r; 
    vector[i].g = pixel.g; 
    vector[i].b = pixel.b;
}

Donc la valeur par défaut Pixel non initialisé, alors que le reste sont initialisées avec la valeur par défaut Pixels' onu-initialisées à des valeurs.

Par rapport à l'alternative de la situation avec New[]/Delete[]:

int main() {
    Tester* myvec = new Tester[300];

    printf("Default Constructed: %i\nCopy Constructed:%i\n", Tester::count, Tester::count2);

    delete[] myvec;    

    return 0;
}

Default Constructed: 300
Copy Constructed: 0

Ils sont tous de gauche à l'onu-initialisées à des valeurs, et sans le double itération au cours de la séquence. Armé avec cette information, comment peut-on le tester? Que diriez-vous de la sur-écriture de l'implicite du constructeur de copie.

Pixel(const Pixel&) {}

Et les résultats?

UseArray completed in 2.617 seconds
UseVector completed in 2.682 seconds
The whole thing completed in 5.301 seconds

Donc en résumé, si votre réalisation de centaines de vecteurs très souvent: repenser votre algorithme.

Dans tous les cas, la STL mise en œuvre n'est pas plus lent pour une raison inconnue, il n'a tout simplement exactement ce que vous demandez; en espérant que vous connaissez mieux.