Std :: vector est-il beaucoup plus lent que les tableaux simples?

212

J'ai toujours pensé que c'est la sagesse générale qui std::vectorest "implémentée comme un tableau", bla bla bla. Aujourd'hui, je suis descendu et l'ai testé, et il semble que ce ne soit pas le cas:

Voici quelques résultats de 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 environ 3 à 4 fois plus lent! Ne justifie pas vraiment les vectorcommentaires " peut être plus lent pour quelques nanosecs".

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 en train de faire mal ou quelque chose? Ou ai-je juste brisé ce mythe de la performance?

J'utilise le mode Release dans Visual Studio 2005 .


Dans Visual C ++ , #define _SECURE_SCL 0réduit UseVectorde moitié (le ramenant à 4 secondes). C'est vraiment énorme, OMI.

kizzx2
la source
23
Certaines versions de vector lorsque vous êtes en mode débogage ajoutent des instructions supplémentaires pour vérifier que vous n'accédez pas au-delà de la fin du tableau et des trucs comme ça. Pour obtenir des temps réels, vous devez créer en mode de libération et activer les optimisations.
Martin York
40
C'est bien que vous ayez mesuré au lieu de croire les affirmations que vous avez entendues sur Internet.
P Shved
51
le vecteur est implémenté sous forme de tableau. Ce n'est pas de la «sagesse conventionnelle», c'est la vérité. Vous avez découvert qu'il vectors'agit d'un tableau redimensionnable à usage général. Toutes nos félicitations. Comme avec tous les outils à usage général, il est possible de trouver des situations spécialisées où il est sous-optimal. C'est pourquoi la sagesse conventionnelle est de commencer par un vectoret d'envisager des alternatives si nécessaire.
Dennis Zickefoose
37
lol, quelle est la différence de vitesse entre "jeter des plats sales dans un évier" et "jeter des plats sales dans un évier et vérifier s'ils ne se cassent pas"?
Imre L
9
Sur VC2010 au moins, il semble que la principale différence est que malloc () est plus rapide que resize (). Supprimez l'allocation de mémoire de la synchronisation, compilez avec _ITERATOR_DEBUG_LEVEL == 0 et les résultats sont les mêmes.
Andreas Magnusson

Réponses:

260

En utilisant ce qui suit:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray terminé en 2.196 secondes
UseVector terminé en 4.412 secondes
UseVectorPushBack terminé en 8.017 secondes
Le tout terminé en 14.626 secondes

Le tableau est donc deux fois plus rapide que le vecteur.

Mais après avoir examiné le code plus en détail, cela est attendu; lorsque vous parcourez le vecteur deux fois et le tableau une seule fois. Remarque: lorsque vous êtes resize()le vecteur, vous allouez non seulement la mémoire, mais vous parcourez également le vecteur et appelez le constructeur sur chaque membre.

Réorganiser légèrement le code pour que le vecteur n'initialise chaque objet qu'une seule fois:

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

Maintenant, refaites le même timing:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector terminé en 2,216 secondes

Les performances du vecteur ne sont désormais que légèrement inférieures à celles du tableau. OMI, cette différence est insignifiante et pourrait être causée par tout un tas de choses non associées au test.

Je tiens également compte du fait que vous n'initialisez / ne détruisez pas correctement l'objet Pixel dans la UseArrray()méthode car aucun constructeur / destructeur n'est 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 des pointeurs) causera des problèmes.

Loki Astari
la source
48
@ kizzx2: Vous devez utiliser à la reserve()place de resize(). Cela alloue de l'espace aux objets (c'est-à-dire qu'il modifie la capacité du vecteur) mais ne crée pas les objets (c'est-à-dire que la taille du vecteur reste inchangée).
James McNellis
25
Vous effectuez 1 000 000 000 d'accès aux baies. Le décalage horaire est de 0,333 seconde. Ou une différence de 0,00000000000333 par accès à la baie. En supposant un processeur 2,33 GHz comme le mien, c'est 0,7 étage de pipeline d'instructions par accès à la baie. Le vecteur semble donc utiliser une instruction supplémentaire par accès.
Martin York
3
@James McNellis: Vous ne pouvez pas simplement remplacer resize()par reserve(), car cela n'ajuste pas l'idée interne du vecteur de sa propre taille, donc les écritures suivantes sur ses éléments sont techniquement "écrivant après la fin" et produiront UB. Bien que, dans la pratique, chaque implémentation STL "se comporte" à cet égard, comment resynchronisez-vous la taille du vecteur? Si vous essayez d'appeler resize() après avoir rempli le vecteur, cela écrasera très probablement tous ces éléments avec des valeurs construites par défaut!
j_random_hacker
8
@j_random_hacker: N'est-ce pas exactement ce que j'ai dit? Je pensais être très clair que cela reservene change que la capacité d'un vecteur, pas sa taille.
James McNellis
7
D'accord, allez comprendre. Il y avait beaucoup de problèmes liés aux exceptions dans les méthodes vectorielles. L'ajout /EHscaux commutateurs de compilation a nettoyé cela et assign()bat réellement le tableau maintenant. Yay.
Pavel Minaev, le
55

Grande question. Je suis venu ici en espérant trouver une solution simple qui accélérerait les tests vectoriels. Cela n'a pas fonctionné comme je m'y attendais!

L'optimisation aide, mais ce n'est pas suffisant. Avec l'optimisation activée, je constate toujours une différence de performances 2X entre UseArray et UseVector. Fait intéressant, UseVector était beaucoup plus lent 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 n ° 1 - Utilisez new [] au lieu de malloc

J'ai essayé de passer malloc()à new[]UseArray pour que les objets soient construits. Et passer de l'affectation de champ individuel à l'attribution d'une instance Pixel. Oh, et renommer la variable de boucle interne en 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 n'a fait la moindre différence. Pas même le changement new[]auquel par défaut construira tous les pixels. Il semble que gcc puisse optimiser les appels du constructeur par défaut lors de l'utilisation new[], mais pas lors de l'utilisation vector.

Idée n ° 2 - Supprimer les appels répétés de l'opérateur []

J'ai également tenté de me débarrasser de la triple operator[]recherche et de mettre en cache la référence pixels[j]. Cela a en 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 n ° 3 - Supprimer les constructeurs

Qu'en est-il de la suppression complète des constructeurs? Alors peut-être que gcc peut optimiser la construction de tous les objets lorsque les vecteurs sont créés. Que se passe-t-il si nous changeons Pixel en:

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 au lieu de l'index de boucle

Que diriez-vous d'utiliser un vector<Pixel>::iteratorau lieu d'un index 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

Non, pas différent. Au moins, ce n'est pas plus lent. Je pensais que cela aurait des performances similaires à # 2 où j'ai utilisé une Pixel&référence.

Conclusion

Même si certains cookies intelligents comprennent comment rendre la boucle vectorielle aussi rapide que celle du tableau, cela ne parle pas bien du comportement par défaut de std::vector. Tant pis pour que le compilateur soit suffisamment intelligent pour optimiser toutes les fonctionnalités C ++ et rendre les conteneurs STL aussi rapides que les tableaux bruts.

L'essentiel est que le compilateur est incapable d'optimiser les appels du constructeur par défaut sans opération lors de l'utilisation std::vector. Si vous utilisez de la plaine, new[]il les optimise très bien. Mais pas avec std::vector. Même si vous pouvez réécrire votre code pour éliminer les appels du constructeur qui vont à l'encontre du mantra ici: "Le compilateur est plus intelligent que vous. La STL est aussi rapide que le simple C. Ne vous en faites pas."

John Kugelman
la source
2
Encore une fois, merci d'avoir exécuté le code. Il est parfois facile de se faire dénigrer sans raison lorsque quelqu'un tente de contester les opinions populaires.
kizzx2
3
"Tant pis pour que le compilateur soit suffisamment intelligent pour optimiser tous les aspects C ++ et rendre les conteneurs STL aussi rapides que les tableaux bruts." Jolis commentaires. J'ai une théorie selon laquelle ce «compilateur est intelligent» n'est qu'un mythe - l'analyse C ++ est extrêmement difficile et le compilateur n'est qu'une machine.
kizzx2
3
Je ne sais pas. Bien sûr, il a pu ralentir le test de la matrice, mais il n'a pas accéléré le vecteur. J'ai édité ci-dessus où j'ai supprimé les constructeurs de Pixel et en ai fait une structure simple, et c'était toujours lent. C'est une mauvaise nouvelle pour quiconque utilise des types simples comme vector<int>.
John Kugelman
2
Je souhaite vraiment pouvoir voter contre votre réponse deux fois. Des idées intelligentes à essayer (même si aucune n'a vraiment fonctionné) auxquelles je ne pouvais même pas penser!
kizzx2
9
Je voulais juste noter que la complexité de l' analyse du C ++ (qui est incroyablement complexe, oui) n'a rien à voir avec la qualité de l'optimisation. Ce dernier se produit généralement sur des scènes où le résultat d'analyse est déjà transformé de nombreuses fois en une représentation beaucoup plus faible.
Pavel Minaev, le
44

C'est une question ancienne mais populaire.

À ce stade, de nombreux programmeurs travailleront en C ++ 11. Et en C ++ 11, le code de l'OP tel qu'il est écrit s'exécute aussi rapidement pour UseArrayou UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

Le problème fondamental était que pendant que votre Pixelstructure n'était pas initialisée, elle std::vector<T>::resize( size_t, T const&=T() )prend une construction par défaut Pixelet la copie . Le compilateur n'a pas remarqué qu'on lui demandait de copier des données non initialisées, il a donc effectué la copie.

En C ++ 11, std::vector<T>::resizea deux surcharges. Le premier est std::vector<T>::resize(size_t), l'autre l'est std::vector<T>::resize(size_t, T const&). Cela signifie que lorsque vous invoquez resizesans second argument, il s'agit simplement de constructions par défaut et le compilateur est suffisamment intelligent pour réaliser que la construction par défaut ne fait rien, il saute donc le passage sur le tampon.

(Les deux surcharges ont été ajoutées pour gérer les types mobiles, constructibles et non copiables - l'amélioration des performances lors du travail sur des données non initialisées est un bonus).

La push_backsolution effectue également la vérification de la clôture, ce qui la ralentit, elle reste donc plus lente que la mallocversion.

exemple en direct (j'ai également remplacé la minuterie par chrono::high_resolution_clock).

Notez que si vous avez une structure qui nécessite généralement une initialisation, mais que vous souhaitez la gérer après avoir augmenté votre tampon, vous pouvez le faire avec un std::vectorallocateur personnalisé . Si vous voulez ensuite le déplacer dans un environnement plus normal std::vector, je pense qu'une utilisation prudente allocator_traitset un remplacement de cela ==pourraient réussir, mais je ne suis pas sûr.

Yakk - Adam Nevraumont
la source
Serait également intéressant de voir comment emplace_backfonctionne vs push_backici.
Daniel
1
Je ne peux pas reproduire vos résultats. Compiler votre code clang++ -std=c++11 -O3a UseArray completed in 2.02e-07 secondset UseVector completed in 1.3026 seconds. J'ai également ajouté une UseVectorEmplaceBackversion qui fait env. 2,5 fois plus vite UseVectorPushBack.
Daniel
1
Les chances de @daniel sont que l'optimiseur a tout supprimé de la version du tableau. Toujours un risque avec des micro-repères.
Yakk - Adam Nevraumont
4
oui vous avez raison, il suffit de regarder le montage (ou son absence) .. J'aurais probablement du penser à ça vu la différence ~ 6448514x! Je me demande pourquoi la version vectorielle ne peut pas faire la même optimisation. Elle le fait si elle est construite avec les dimensions plutôt que redimensionnée.
Daniel
34

Pour être honnête, vous ne pouvez pas comparer une implémentation C ++ à une implémentation C, comme j'appellerais votre version malloc. malloc ne crée pas d'objets - il alloue uniquement de la mémoire brute. Que vous traitez ensuite cette mémoire comme des objets sans appeler le constructeur est un mauvais C ++ (peut-être invalide - je laisse cela aux juristes du langage).

Cela dit, changer simplement le malloc en new Pixel[dimensions*dimensions]et gratuit delete [] pixelsne fait pas beaucoup de différence avec la simple implémentation de Pixel que vous avez. Voici les résultats sur ma box (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 tableaux tournent:

Pixel.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

on obtient 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 constructeur non intégré pour Pixel, std :: vector bat désormais un tableau brut.

Il semblerait que la complexité de l'allocation via std :: vector et std: allocator soit trop importante pour être optimisée aussi efficacement qu'un simple new Pixel[n]. Cependant, nous pouvons voir que le problème est simplement lié à l'allocation et non à l'accès vectoriel en modifiant quelques fonctions de test pour créer le vecteur / tableau une fois en le déplaçant hors 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 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 ceci est que std :: vector est comparable à un tableau brut pour l'accès, mais si vous devez créer et supprimer le vecteur / tableau plusieurs fois, la création d'un objet complexe prendra plus de temps que la création d'un tableau simple lorsque le constructeur de l'élément n'est pas inséré. Je ne pense pas que cela soit très surprenant.

camh
la source
3
Vous avez toujours un constructeur en ligne - le constructeur de copie.
Ben Voigt
26

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));
    }
}

J'obtiens presque exactement les mêmes performances qu'avec la baie.

Le fait vectorest que c'est un outil beaucoup plus général qu'un tableau. Et cela signifie que vous devez considérer comment vous l'utilisez. Il peut être utilisé de différentes manières, offrant des fonctionnalités qu'un tableau n'a même pas. Et si vous l'utilisez «mal» à vos fins, vous encourez beaucoup de frais généraux, mais si vous l'utilisez correctement, il s'agit généralement d'une structure de données sans frais généraux. Dans ce cas, le problème est que vous avez initialisé séparément le vecteur (ce qui fait que tous les éléments ont leur ctor par défaut appelé), puis écrasez chaque élément individuellement avec la valeur correcte. C'est beaucoup plus difficile à optimiser pour le compilateur que lorsque vous faites la même chose avec un tableau. C'est pourquoi le vecteur fournit un constructeur qui vous permet de faire exactement cela:NX.

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

Donc non, vous n'avez pas brisé le mythe de la performance. Mais vous avez montré que ce n'est vrai que si vous utilisez le vecteur de manière optimale, ce qui est également un bon point. :)

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

jalf
la source
1
Je me demande encore s'il s'agit d'une comparaison équitable. Si vous vous débarrassez de la boucle intérieure, l'équivalent du tableau serait de construire un seul objet Pixel, puis de le blit sur l'ensemble du tableau.
John Kugelman
1
L'utilisation new[]exécute les mêmes constructions par défaut que le vector.resize()fait, mais c'est beaucoup plus rapide. new[]La boucle intérieure devrait avoir la même vitesse que vector.resize()la boucle intérieure, mais ce n'est pas le cas, elle est presque deux fois plus rapide.
John Kugelman, le
@John: C'est une comparaison juste. Dans le code d'origine, le tableau est alloué mallocsans initialiser ni construire quoi que ce soit, il s'agit donc en fait d' un algorithme à passage unique, tout comme mon vectorexemple. Et en ce qui concerne new[]la réponse, il est évident que les deux nécessitent deux passes, mais dans le new[]cas, le compilateur est en mesure d'optimiser cette surcharge supplémentaire, ce qu'il ne fait pas dans le vectorcas. Mais je ne vois pas pourquoi il est intéressant de voir ce qui se passe dans les cas sous-optimaux. Si vous vous souciez des performances, vous n'écrivez pas de code comme ça.
jalf
@John: Commentaire intéressant. Si je voulais blit sur l'ensemble du tableau, je suppose que le tableau est à nouveau la solution optimale - car je ne peux pas dire vector::resize()de me donner un morceau de mémoire contingent sans perdre de temps à appeler des constructeurs inutiles.
kizzx2
@ kizzx2: oui et non. Un tableau est normalement également initialisé en C ++. En C, vous utiliseriez mallocce qui n'effectue pas l'initialisation, mais cela ne fonctionnera pas en C ++ avec des types non POD. Donc, dans le cas général, un tableau C ++ serait tout aussi mauvais. Peut-être que la question est, si vous effectuez souvent ce blitting, ne réutilisez-vous pas le même tableau / vecteur? Et si vous faites cela, vous ne payez qu'une seule fois le coût des "constructeurs inutiles", au tout début. Le blitting réel est tout aussi rapide après tout.
jalf
22

Ce n'était pas une comparaison juste quand j'ai regardé votre code pour la première fois; Je pensais vraiment que vous ne compariez pas des pommes avec des pommes. Alors j'ai pensé, faisons appel aux constructeurs et aux destructeurs sur tous les tests; puis 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, qu'avec cette configuration, elles devraient être exactement les mêmes. Il s'avère que j'avais tort.

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

Alors pourquoi cette perte de performances de 30% s'est-elle même produite? La STL a tout dans les en-têtes, donc il aurait dû être possible pour le compilateur de comprendre tout ce qui était requis.

Mes pensées étaient que c'est dans la façon dont la boucle initialise toutes les valeurs au constructeur par défaut. 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 étaient comme je le soupçonnais:

Default Constructed: 1
Copy Constructed: 300

C'est clairement la source du ralentissement, le fait que le vecteur utilise le constructeur de copie pour initialiser les éléments à partir d'un objet construit par défaut.

Cela signifie que l'ordre de pseudo-opération suivant se produit lors de la construction du vecteur:

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

Ce qui, en raison du constructeur de copie implicite créé par le compilateur, est développé comme suit:

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

Ainsi , la valeur par défaut Pixelreste non initialisées, tandis que le reste sont initialisés avec la valeur par défaut Pixelde » un-initialisées valeurs.

Par rapport à la situation alternative 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 laissés à leurs valeurs non initialisées, et sans la double itération sur la séquence.

Armé de ces informations, comment pouvons-nous les tester? Essayons d'écraser le constructeur de copie implicite.

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 vous créez très souvent des centaines de vecteurs: repensez votre algorithme .

Dans tous les cas, l' implémentation STL n'est pas plus lente pour une raison inconnue, elle fait exactement ce que vous demandez; en espérant en savoir plus.

caviar décéléré
la source
3
À en juger par le plaisir que nous (vous et moi et d'autres personnes intelligentes ici) avons eu, "l'espoir" de la mise en œuvre de STL est en effet assez exigeant: P Fondamentalement, nous pouvons exagérer et conclure qu'il espère avoir lu et analysé toute sa source code. Quoi qu'il en soit: P
kizzx2
1
Impressionnant! Dans VS 2013, cela a rendu le vecteur plus rapide que les tableaux. Bien qu'il semble que pour les systèmes à performances critiques, vous devez beaucoup tester STL pour pouvoir l'utiliser efficacement.
rozina
7

Essayez de désactiver les itérateurs vérifiés et de créer en mode de publication. Vous ne devriez pas voir beaucoup de différence de performances.

kloffy
la source
1
J'ai essayé #define _SECURE_SCL 0. Cela fait UseVectorenviron 4 secondes (similaire à gccci-dessous) mais c'est toujours deux fois plus lent.
kizzx2
C'est presque certainement la cause. Microsoft nous offre gracieusement le débogage de l'itérateur par défaut pour le débogage et la version. Nous avons trouvé que c'était la cause première d'un ralentissement massif après la mise à niveau de 2003 à 2008. Certainement l'un des accrochages les plus pernicieux de Visual Studio.
Doug T.
2
@ kizzx2 il y a une autre macro à désactiver: HAS_ITERATOR_DEBUGGING ou quelque chose comme ça.
Doug T.
Comme le montrent @Martin et mes réponses, gcc montre le même schéma, même avec une optimisation à -O3.
John Kugelman
1
@Doug: En regardant le document, je pense qu'il _HAS_ITERATOR_DEBUGGINGest désactivé dans la version: msdn.microsoft.com/en-us/library/aa985939(VS.80).aspx
kizzx2
4

La STL de GNU (et d'autres), étant donné vector<T>(n), construit par défaut un objet prototypique T()- le compilateur optimisera le constructeur vide - mais une copie de tout ce qui se trouve être dans les adresses mémoire maintenant réservées à l'objet est prise par les STL __uninitialized_fill_n_aux, qui boucles remplissant des copies de cet objet comme valeurs par défaut dans le vecteur. Donc, "ma" STL n'est pas la construction en boucle, mais la construction puis la boucle / copie. C'est contre-intuitif, mais j'aurais dû m'en souvenir en commentant une récente question de stackoverflow sur ce point: la construction / copie peut être plus efficace pour les objets comptés par référence, etc.

Alors:

vector<T> x(n);

ou

vector<T> x;
x.resize(n);

est - sur de nombreuses implémentations STL - quelque chose comme:

T temp;
for (int i = 0; i < n; ++i)
    x[i] = temp;

Le problème étant que la génération actuelle des optimiseurs de compilateur ne semble pas fonctionner à partir du fait que temp est une ordure non initialisée et ne parvient pas à optimiser la boucle et les appels de constructeur de copie par défaut. Vous pourriez affirmer de manière crédible que les compilateurs ne devraient absolument pas optimiser cela, car un programmeur écrivant ce qui précède a une attente raisonnable que tous les objets seront identiques après la boucle, même si des ordures (mises en garde habituelles sur `` identique '' / opérateur == vs memcmp / operator = etc s'appliquent). On ne peut pas s'attendre à ce que le compilateur ait un aperçu supplémentaire du contexte plus large de std :: vector <> ou de l'utilisation ultérieure des données qui suggérerait cette optimisation en toute sécurité.

Cela peut être mis en contraste avec la mise en œuvre directe la plus évidente:

for (int i = 0; i < n; ++i)
    x[i] = T();

Que nous pouvons attendre d'un compilateur pour optimiser.

Pour être un peu plus explicite sur la justification de cet aspect du comportement du vecteur, considérez:

std::vector<big_reference_counted_object> x(10000);

C'est clairement une différence majeure si nous faisons 10000 objets indépendants contre 10000 référençant les mêmes données. Il y a un argument raisonnable que l'avantage de protéger les utilisateurs C ++ occasionnels de faire accidentellement quelque chose de si cher surpasse le très petit coût réel de la construction de copie difficile à optimiser.

RÉPONSE ORIGINALE (pour référence / donner un sens aux commentaires): Aucune chance. le vecteur est aussi rapide qu'un tableau, du moins si vous réservez judicieusement de l'espace. ...

Tony Delroy
la source
6
Je ne peux vraiment pas justifier que cette réponse soit quelque peu utile à quiconque. J'espère que je pourrais downvoter deux fois.
kizzx2
-1, voilà mon support sur kizzx2. le vecteur ne sera jamais aussi rapide que le tableau en raison de la fonctionnalité supplémentaire qu'il fournit, de la règle de l'univers, tout a un prix!
YeenFei
Vous passez à côté, Tony… c'est un exemple de référence artificielle, mais cela prouve ce à quoi il prétend.
Potatoswatter
Les roses sont vertes, les violettes sont oranges, les votes descendants sont amers, mais la réponse les supplie.
Pavel Minaev
3

La réponse de Martin York me dérange car elle semble être une tentative de balayer le problème d'initialisation sous le tapis. Mais il a raison d'identifier la construction par défaut redondante comme la source de problèmes de performances.

[EDIT: la réponse de Martin ne suggère plus de changer le constructeur par défaut.]

Pour le problème immédiat, vous pouvez certainement appeler la version à 2 paramètres du vector<Pixel>ctor à la place:

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

Cela fonctionne si vous souhaitez initialiser avec une valeur constante, ce qui est un cas courant. Mais le problème le plus général est: comment pouvez-vous initialiser efficacement avec quelque chose de plus compliqué qu'une valeur constante?

Pour cela, vous pouvez utiliser un back_insert_iterator, qui est un adaptateur d'itérateur. Voici un exemple avec un vecteur de ints, bien que l'idée générale fonctionne aussi bien pour Pixels:

#include <iterator>
// Simple functor return a list of squares: 1, 4, 9, 16...
struct squares {
    squares() { i = 0; }
    int operator()() const { ++i; return i * i; }

private:
    int i;
};

...

std::vector<int> v;
v.reserve(someSize);     // To make insertions efficient
std::generate_n(std::back_inserter(v), someSize, squares());

Vous pouvez également utiliser copy()ou à la transform()place de generate_n().

L'inconvénient est que la logique de construction des valeurs initiales doit être déplacée dans une classe distincte, ce qui est moins pratique que de l'avoir en place (bien que les lambdas en C ++ 1x rendent cela beaucoup plus agréable). De plus, je m'attends à ce que ce ne soit toujours pas aussi rapide qu'une malloc()version non STL basée sur des bases, mais je m'attends à ce qu'elle soit proche, car elle ne fait qu'une seule construction pour chaque élément.

j_random_hacker
la source
2

Les vecteurs appellent également des constructeurs Pixel.

Chacun provoque près d'un million de cycles de calcul que vous chronométrez.

edit: puis il y a la boucle externe 1 ... 1000, alors faites qu'un milliard de ctor appelle!

edit 2: il serait intéressant de voir le démontage du cas UseArray. Un optimiseur pourrait optimiser le tout, car il n'a aucun effet autre que la gravure du processeur.

Graham Perks
la source
Vous avez raison, mais la question est: comment désactiver ces appels inutiles au processeur? C'est facile pour l'approche non STL, mais difficile / moche pour la manière STL.
j_random_hacker
1

Voici comment fonctionne la push_backméthode dans le vecteur:

  1. Le vecteur alloue X espace lors de son initialisation.
  2. Comme indiqué ci-dessous, il vérifie s'il y a de la place dans le tableau sous-jacent actuel pour l'élément.
  3. Il fait une copie de l'élément dans l'appel push_back.

Après avoir appelé push_backX éléments:

  1. Le vecteur réalloue la quantité d'espace kX dans un 2e tableau.
  2. Il copie les entrées du premier tableau sur le second.
  3. Ignore le premier tableau.
  4. Utilise maintenant le deuxième tableau comme stockage jusqu'à ce qu'il atteigne les entrées kX.

Répéter. Si vous n'êtes pas dans l' reservingespace, cela va certainement être plus lent. Plus que cela, s'il est cher de copier l'élément, alors 'push_back' comme ça va vous manger vivant.

En ce qui concerne le vectortableau versus, je vais devoir être d'accord avec les autres personnes. Exécutez la version, activez les optimisations et placez quelques indicateurs supplémentaires pour que les sympathiques de Microsoft ne le # @% $ ^ fassent pas pour vous.

Encore une chose, si vous n'avez pas besoin de redimensionner, utilisez Boost.Array.

blés
la source
Je comprends que les gens n'aiment pas lire un tas de code lorsqu'il est affiché mot pour mot. Mais je l'ai utilisé reservecomme je le devrais.
kizzx2
Désolé de l'avoir manqué. Est-ce que rien d'autre que j'ai mis là-bas n'a été utile du tout?
Wheaties
push_backa amorti le temps constant. On dirait que vous décrivez un processus O (N). (Les étapes 1 et 3 semblent complètement hors de propos.) Ce qui push_backralentit pour OP est la vérification de la plage pour voir si la réallocation doit avoir lieu, la mise à jour des pointeurs, la vérification par rapport à NULL à l'intérieur du placement newet d'autres petites choses qui sont normalement noyées par le travail réel du programme.
Potatoswatter
Cela va être plus lent, même reserves'il doit encore effectuer cette vérification (s'il doit être réaffecté) à chaque fois push_back.
Pavel Minaev, le
Tous les bons points. Ce que je décris ressemble à un processus O (N) mais ce n'est pas, enfin pas tout à fait. La plupart des gens que je connais ne comprennent pas comment fonctionne une vectorfonctionnalité de redimensionnement, c'est juste "magique". Ici, permettez-moi de clarifier un peu plus.
Wheaties
1

Certaines données du profileur (le pixel est aligné sur 32 bits):

g++ -msse3 -O3 -ftree-vectorize -g test.cpp -DNDEBUG && ./a.out
UseVector completed in 3.123 seconds
UseArray completed in 1.847 seconds
UseVectorPushBack completed in 9.186 seconds
The whole thing completed in 14.159 seconds

Blabla

andrey@nv:~$ opannotate --source libcchem/src/a.out  | grep "Total samples for file" -A3
Overflow stats not available
 * Total samples for file : "/usr/include/c++/4.4/ext/new_allocator.h"
 *
 * 141008 52.5367
 */
--
 * Total samples for file : "/home/andrey/libcchem/src/test.cpp"
 *
 *  61556 22.9345
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_vector.h"
 *
 *  41956 15.6320
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_uninitialized.h"
 *
 *  20956  7.8078
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_construct.h"
 *
 *   2923  1.0891
 */

Dans allocator:

               :      // _GLIBCXX_RESOLVE_LIB_DEFECTS
               :      // 402. wrong new expression in [some_] allocator::construct
               :      void
               :      construct(pointer __p, const _Tp& __val)
141008 52.5367 :      { ::new((void *)__p) _Tp(__val); }

vector:

               :void UseVector()
               :{ /* UseVector() total:  60121 22.3999 */
...
               :
               :
 10790  4.0201 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
   495  0.1844 :            pixels[i].r = 255;
               :
 12618  4.7012 :            pixels[i].g = 0;
               :
  2253  0.8394 :            pixels[i].b = 0;
               :
               :        }

tableau

               :void UseArray()
               :{ /* UseArray() total:  35191 13.1114 */
               :
...
               :
   136  0.0507 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
  9897  3.6874 :            pixels[i].r = 255;
               :
  3511  1.3081 :            pixels[i].g = 0;
               :
 21647  8.0652 :            pixels[i].b = 0;

La plupart des frais généraux se trouvent dans le constructeur de copie. Par exemple,

    std::vector < Pixel > pixels;//(dimension * dimension, Pixel());

    pixels.reserve(dimension * dimension);

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

        pixels[i].r = 255;

        pixels[i].g = 0;

        pixels[i].b = 0;
    }

Il a les mêmes performances qu'un tableau.

Anycorn
la source
2
Malheureusement, après la "solution" que vous avez donnée, pixels.size()sera rompue.
kizzx2
1
c'est faux, vous ne pouvez pas appeler reserve puis utiliser les éléments, vous devez toujours utiliser push_back pour ajouter des éléments
paulm
1

Mon ordinateur portable est Lenova G770 (4 Go de RAM).

Le système d'exploitation est Windows 7 64 bits (celui avec ordinateur portable)

Le compilateur est MinGW 4.6.1.

L'IDE est Code :: Blocks .

Je teste les codes sources du premier post.

Les resultats

Optimisation d'O2

UseArray terminé en 2,841 secondes

UseVector terminé en 2,548 secondes

UseVectorPushBack terminé en 11,95 secondes

Le tout terminé en 17.342 secondes

pause système

Optimisation O3

UseArray terminé en 1,452 secondes

UseVector terminé en 2,514 secondes

UseVectorPushBack terminé en 12,967 secondes

Le tout terminé en 16.937 secondes

Il semble que les performances du vecteur soient pires sous l'optimisation O3.

Si vous changez la boucle en

    pixels[i].r = i;
    pixels[i].g = i;
    pixels[i].b = i;

La vitesse du réseau et du vecteur sous O2 et O3 sont presque les mêmes.

StereoMatching
la source
Même si je change malloc en new, dans le premier cas de test sous O3, les performances du vecteur sont toujours plus lentes que array.Mais lorsque vous changez la valeur assignée de (255, 0, 0) à (i, i, i), les performances de le vecteur et le tableau sont presque les mêmes sous O2 et O3, c'est assez bizarre
StereoMatching
Désolé, j'ai oublié de changer gratuitement pour supprimer.Après avoir changé gratuitement pour supprimer, les performances sous O3 du vecteur et du tableau sont les mêmes maintenant, il semble que l'allocateur soit la principale raison?
StereoMatching
1

Un meilleur benchmark (je pense ...), le compilateur dû aux optimisations peut changer le code, car les résultats des vecteurs / tableaux alloués ne sont utilisés nulle part. Résultats:

$ g++ test.cpp -o test -O3 -march=native
$ ./test 
UseArray inner completed in 0.652 seconds
UseArray completed in 0.773 seconds
UseVector inner completed in 0.638 seconds
UseVector completed in 0.757 seconds
UseVectorPushBack inner completed in 6.732 seconds
UseVectorPush completed in 6.856 seconds
The whole thing completed in 8.387 seconds

Compilateur:

gcc version 6.2.0 20161019 (Debian 6.2.0-9)

CPU:

model name  : Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz

Et le code:

#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(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVector inner");

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

        std::vector<Pixel>& pixels = results.at(i);
        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(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVectorPushBack inner");

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

        std::vector<Pixel>& pixels = results.at(i);
            pixels.reserve(dimension * dimension);

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

void UseArray(Pixel** results)
{
    TestTimer t("UseArray inner");

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

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

        results[i] = pixels;

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

        // free(pixels);
    }
}

void UseArray()
{
    TestTimer t("UseArray");
    Pixel** array = (Pixel**)malloc(sizeof(Pixel*)* 1000);
    UseArray(array);
    for(int i=0;i<1000;++i)
        free(array[i]);
    free(array);
}

void UseVector()
{
    TestTimer t("UseVector");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVector(vector);
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPush");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVectorPushBack(vector);
    }
}


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

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

    return 0;
}
Michał Szczepaniak
la source
1

J'ai fait quelques tests approfondis que je voulais depuis un moment maintenant. Autant partager cela.

Il s'agit de ma machine à double démarrage i7-3770, 16 Go de RAM, x86_64, sur Windows 8.1 et sur Ubuntu 16.04. Plus d'informations et conclusions, remarques ci-dessous. Testé à la fois MSVS 2017 et g ++ (à la fois sur Windows et sur Linux).

Programme de test

#include <iostream>
#include <chrono>
//#include <algorithm>
#include <array>
#include <locale>
#include <vector>
#include <queue>
#include <deque>

// Note: total size of array must not exceed 0x7fffffff B = 2,147,483,647B
//  which means that largest int array size is 536,870,911
// Also image size cannot be larger than 80,000,000B
constexpr int long g_size = 100000;
int g_A[g_size];


int main()
{
    std::locale loc("");
    std::cout.imbue(loc);
    constexpr int long size = 100000;  // largest array stack size

    // stack allocated c array
    std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
    int A[size];
    for (int i = 0; i < size; i++)
        A[i] = i;

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style stack array size=" << sizeof(A) << "B\n\n";

    // global stack c array
    start = std::chrono::steady_clock::now();
    for (int i = 0; i < g_size; i++)
        g_A[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "global c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "global c-style stack array size=" << sizeof(g_A) << "B\n\n";

    // raw c array heap array
    start = std::chrono::steady_clock::now();
    int* AA = new int[size];    // bad_alloc() if it goes higher than 1,000,000,000
    for (int i = 0; i < size; i++)
        AA[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style heap array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style heap array size=" << sizeof(AA) << "B\n\n";
    delete[] AA;

    // std::array<>
    start = std::chrono::steady_clock::now();
    std::array<int, size> AAA;
    for (int i = 0; i < size; i++)
        AAA[i] = i;
    //std::sort(AAA.begin(), AAA.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::array size=" << sizeof(AAA) << "B\n\n";

    // std::vector<>
    start = std::chrono::steady_clock::now();
    std::vector<int> v;
    for (int i = 0; i < size; i++)
        v.push_back(i);
    //std::sort(v.begin(), v.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::vector duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::vector size=" << v.size() * sizeof(v.back()) << "B\n\n";

    // std::deque<>
    start = std::chrono::steady_clock::now();
    std::deque<int> dq;
    for (int i = 0; i < size; i++)
        dq.push_back(i);
    //std::sort(dq.begin(), dq.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::deque duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::deque size=" << dq.size() * sizeof(dq.back()) << "B\n\n";

    // std::queue<>
    start = std::chrono::steady_clock::now();
    std::queue<int> q;
    for (int i = 0; i < size; i++)
        q.push(i);

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::queue duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::queue size=" << q.size() * sizeof(q.front()) << "B\n\n";
}

Résultats

//////////////////////////////////////////////////////////////////////////////////////////
// with MSVS 2017:
// >> cl /std:c++14 /Wall -O2 array_bench.cpp
//
// c-style stack array duration=0.15ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.130ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.90ms
// c-style heap array size=4B
//
// std::array duration=0.20ms
// std::array size=400,000B
//
// std::vector duration=0.544ms
// std::vector size=400,000B
//
// std::deque duration=1.375ms
// std::deque size=400,000B
//
// std::queue duration=1.491ms
// std::queue size=400,000B
//
//////////////////////////////////////////////////////////////////////////////////////////
//
// with g++ version:
//      - (tdm64-1) 5.1.0 on Windows
//      - (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609 on Ubuntu 16.04
// >> g++ -std=c++14 -Wall -march=native -O2 array_bench.cpp -o array_bench
//
// c-style stack array duration=0ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.124ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.648ms
// c-style heap array size=8B
//
// std::array duration=1ms
// std::array size=400,000B
//
// std::vector duration=0.402ms
// std::vector size=400,000B
//
// std::deque duration=0.234ms
// std::deque size=400,000B
//
// std::queue duration=0.304ms
// std::queue size=400,000
//
//////////////////////////////////////////////////////////////////////////////////////////

Remarques

  • Assemblé par une moyenne de 10 pistes.
  • J'ai d'abord effectué des tests avec std::sort()trop (vous pouvez le voir commenté) mais les ai supprimés plus tard car il n'y avait pas de différences relatives significatives.

Mes conclusions et remarques

  • remarquez comment le tableau de style c global prend presque autant de temps que le tableau de style c tas
  • De tous les tests, j'ai remarqué une stabilité remarquable dans std::arrayles variations de temps entre des exécutions consécutives, tandis que d'autres, en particulier les structures std :: data, variaient énormément en comparaison
  • L'optimisation O3 n'a montré aucune différence de temps notable
  • La suppression de l'optimisation sous Windows cl (no -O2) et g ++ (Win / Linux no -O2, no -march = native) augmente considérablement les temps. Particulièrement pour les structures std :: data. Temps globalement plus élevés sur MSVS que sur g ++, mais les std::arraytableaux de style c sont plus rapides sur Windows sans optimisation
  • g ++ produit un code plus rapide que le compilateur de microsoft (apparemment, il s'exécute plus rapidement même sous Windows).

Verdict

Bien sûr, c'est du code pour une construction optimisée. Et puisque la question portait sur std::vectoralors oui c'est bien! plus lent que les tableaux simples (optimisé / non optimisé). Mais lorsque vous faites un benchmark, vous voulez naturellement produire du code optimisé.

La star du spectacle pour moi a cependant été std::array.

Nikos
la source
0

Avec les bonnes options, les vecteurs et les tableaux peuvent générer un asm identique . Dans ces cas, ils ont bien sûr la même vitesse, car vous obtenez le même fichier exécutable de toute façon.


la source
1
Dans ce cas, ils ne semblent pas générer le même assemblage. En particulier, il semble qu'il n'y ait aucun moyen de supprimer l'appel aux constructeurs utilisant des vecteurs. Vous pouvez vous référer aux réponses ici pour ce problème (c'est une longue lecture mais cela explique pourquoi il y a une différence de performances dans des cas autres que le cas de test simple dans le lien que vous avez provoqué.) (En fait, il semble y avoir un moyen - - écrire un allocateur STL personnalisé, comme suggéré. Personnellement, je trouve cela inutilement plus de travail que d'utiliser malloc)
kizzx2
1
@ kizzx2: Que vous devez aller aussi loin pour utiliser des objets non construits est une bonne chose, car c'est une erreur de 99% (je suis peut-être largement sous-estimée) du temps. J'ai lu les autres réponses et je me rends compte que je ne traite pas de votre situation spécifique (pas besoin, les autres réponses sont correctes), mais je voulais quand même vous donner cet exemple de la façon dont les vecteurs et les tableaux peuvent se comporter exactement de la même manière.
@Roger: c'est génial! Merci pour le lien
kizzx2
0

Par ailleurs, le ralentissement de votre vision dans les classes utilisant vector se produit également avec des types standard comme int. Voici un code multithread:

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <typeinfo>
#include <vector>
#include <pthread.h>
#include <sstream>
#include <fstream>
using namespace std;

//pthread_mutex_t map_mutex=PTHREAD_MUTEX_INITIALIZER;

long long num=500000000;
int procs=1;

struct iterate
{
    int id;
    int num;
    void * member;
    iterate(int a, int b, void *c) : id(a), num(b), member(c) {}
};

//fill out viterate and piterate
void * viterate(void * input)
{
    printf("am in viterate\n");
    iterate * info=static_cast<iterate *> (input);
    // reproduce member type
    vector<int> test= *static_cast<vector<int>*> (info->member);
    for (int i=info->id; i<test.size(); i+=info->num)
    {
        //printf("am in viterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

void * piterate(void * input)
{
    printf("am in piterate\n");
    iterate * info=static_cast<iterate *> (input);;
    int * test=static_cast<int *> (info->member);
    for (int i=info->id; i<num; i+=info->num) {
        //printf("am in piterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

int main()
{
    cout<<"producing vector of size "<<num<<endl;
    vector<int> vtest(num);
    cout<<"produced  a vector of size "<<vtest.size()<<endl;
    pthread_t thread[procs];

    iterate** it=new iterate*[procs];
    int ans;
    void *status;

    cout<<"begining to thread through the vector\n";
    for (int i=0; i<procs; i++) {
        it[i]=new iterate(i, procs, (void *) &vtest);
    //  ans=pthread_create(&thread[i],NULL,viterate, (void *) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the vector";
    //reuse the iterate structures

    cout<<"producing a pointer with size "<<num<<endl;
    int * pint=new int[num];
    cout<<"produced a pointer with size "<<num<<endl;

    cout<<"begining to thread through the pointer\n";
    for (int i=0; i<procs; i++) {
        it[i]->member=&pint;
        ans=pthread_create(&thread[i], NULL, piterate, (void*) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the pointer\n";

    //delete structure array for iterate
    for (int i=0; i<procs; i++) {
        delete it[i];
    }
    delete [] it;

    //delete pointer
    delete [] pint;

    cout<<"end of the program"<<endl;
    return 0;
}

Le comportement du code montre que l'instanciation du vecteur est la partie la plus longue du code. Une fois que vous avez traversé le goulot de la bouteille. Le reste du code s'exécute extrêmement rapidement. Cela est vrai quel que soit le nombre de threads que vous exécutez.

Soit dit en passant, ignorez le nombre absolument insensé d'includes. J'utilise ce code pour tester des choses pour un projet, donc le nombre d'inclusions continue de croître.

Zachary Kraus
la source
0

Je veux juste mentionner que le vecteur (et smart_ptr) n'est qu'une couche mince ajoutée au-dessus des tableaux bruts (et des pointeurs bruts). Et en fait, le temps d'accès d'un vecteur en mémoire continue est plus rapide que le tableau. Le code suivant montre le résultat de l'initialisation et de l'accès au vecteur et au tableau.

#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <vector>
#define SIZE 20000
int main() {
    srand (time(NULL));
    vector<vector<int>> vector2d;
    vector2d.reserve(SIZE);
    int index(0);
    boost::posix_time::ptime start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        vector2d.push_back(vector<int>(SIZE));
    }
    boost::posix_time::ptime start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            vector2d[index][index]++;
        }
    }
    boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time();
    boost::posix_time::time_duration msdiff = end - start_total;
    cout << "Vector total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Vector access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 


    int index(0);
    int** raw2d = nullptr;
    raw2d = new int*[SIZE];
    start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        raw2d[i] = new int[SIZE];
    }
    start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            raw2d[index][index]++;
        }
    }
    end = boost::posix_time::microsec_clock::local_time();
    msdiff = end - start_total;
    cout << "Array total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Array access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 
    for (int i = 0; i < SIZE; i++) {
        delete [] raw2d[i];
    }
    return 0;
}

La sortie est:

    Vector total time: 925milliseconds.
    Vector access time: 4milliseconds.
    Array total time: 30milliseconds.
    Array access time: 21milliseconds.

Ainsi, la vitesse sera presque la même si vous l'utilisez correctement. (comme d'autres l'ont mentionné en utilisant reserve () ou resize ()).

Charles Chow
la source
0

Eh bien, parce que vector :: resize () fait beaucoup plus de traitement que l'allocation de mémoire ordinaire (par malloc).

Essayez de mettre un point d'arrêt dans votre constructeur de copie (définissez-le afin que vous puissiez faire un point d'arrêt!) Et le temps de traitement supplémentaire augmente.

YeenFei
la source
0

Je dois dire que je ne suis pas un expert en C ++. Mais pour ajouter quelques résultats d'expériences:

compiler: gcc-6.2.0 / bin / g ++ -O3 -std = c ++ 14 vector.cpp

machine:

Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz 

OS:

2.6.32-642.13.1.el6.x86_64

Production:

UseArray completed in 0.167821 seconds
UseVector completed in 0.134402 seconds
UseConstructor completed in 0.134806 seconds
UseFillConstructor completed in 1.00279 seconds
UseVectorPushBack completed in 6.6887 seconds
The whole thing completed in 8.12888 seconds

Ici, la seule chose qui me semble étrange est la performance de "UseFillConstructor" par rapport à "UseConstructor".

Le code:

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

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

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


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

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

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

Ainsi, la "valeur" supplémentaire fournie ralentit beaucoup les performances, ce qui, je pense, est dû à plusieurs appels au constructeur de copie. Mais...

Compiler:

gcc-6.2.0/bin/g++ -std=c++14 -O vector.cpp

Production:

UseArray completed in 1.02464 seconds
UseVector completed in 1.31056 seconds
UseConstructor completed in 1.47413 seconds
UseFillConstructor completed in 1.01555 seconds
UseVectorPushBack completed in 6.9597 seconds
The whole thing completed in 11.7851 seconds

Donc dans ce cas, l'optimisation gcc est très importante mais elle ne peut pas vous aider beaucoup quand une valeur est fournie par défaut. C'est contre mes frais de scolarité en fait. Espérons que cela aide le nouveau programmeur à choisir le format d'initialisation du vecteur.

user2189731
la source
0

Cela semble dépendre des drapeaux du compilateur. Voici un code de référence:

#include <chrono>
#include <cmath>
#include <ctime>
#include <iostream>
#include <vector>


int main(){

    int size = 1000000; // reduce this number in case your program crashes
    int L = 10;

    std::cout << "size=" << size << " L=" << L << std::endl;
    {
        srand( time(0) );
        double * data = new double[size];
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C style heap array:    " << duration << "ms\n";
        delete data;
    }

    {
        srand( 1 + time(0) );
        double data[size]; // technically, non-compliant with C++ standard.
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C99 style stack array: " << duration << "ms\n";
    }

    {
        srand( 2 + time(0) );
        std::vector<double> data( size );
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of std::vector array:     " << duration << "ms\n";
    }

    return 0;
}

Différents indicateurs d'optimisation donnent des réponses différentes:

$ g++ -O0 benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181182
Duration of C style heap array:    118441ms
Calculation result is 181240
Duration of C99 style stack array: 104920ms
Calculation result is 181210
Duration of std::vector array:     124477ms
$g++ -O3 benchmark.cpp
$ ./a.out 
size=1000000 L=10
Calculation result is 181213
Duration of C style heap array:    107803ms
Calculation result is 181198
Duration of C99 style stack array: 87247ms
Calculation result is 181204
Duration of std::vector array:     89083ms
$ g++ -Ofast benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181164
Duration of C style heap array:    93530ms
Calculation result is 181179
Duration of C99 style stack array: 80620ms
Calculation result is 181191
Duration of std::vector array:     78830ms

Vos résultats exacts varieront mais c'est assez typique sur ma machine.

shuhalo
la source
0

D'après mon expérience, parfois, juste parfois, vector<int>peut être beaucoup plus lent que int[]. Une chose à garder à l'esprit est que les vecteurs de vecteurs sont très différents int[][]. Comme les éléments ne sont probablement pas contigus en mémoire. Cela signifie que vous pouvez redimensionner différents vecteurs à l'intérieur du vecteur principal, mais le processeur peut ne pas être en mesure de mettre en cache les éléments aussi bien que dans le cas de int[][].

Íhor Mé
la source