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

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.

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.

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

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.

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.

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.

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.

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.

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

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.

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.

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:

3. Le vecteur réalloue la quantité d'espace kX dans un 2e tableau.
4. Il copie les entrées du premier tableau sur le second.
5. Ignore le premier tableau.
6. 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.

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.

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.

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

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.

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.

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.

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 ()).

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.

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.

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.

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[][].