En utilisant des tableaux ou std :: vectors en C ++, quelle est l’écart de performance?

L’utilisation de tableaux C ++ avec new (c’est-à-dire en utilisant des tableaux dynamics) doit être évitée. Il y a le problème que vous devez garder de la taille, et vous devez les supprimer manuellement, et faire toutes sortes de ménage.

L’utilisation de tableaux sur la stack est également déconseillée car vous n’avez pas de vérification de plage et la transmission du tableau perd toute information sur sa taille (conversion de tableau en pointeur). Vous devez utiliser boost::array dans ce cas, qui encapsule un tableau C ++ dans une petite classe et fournit une fonction de size et des iterators pour la parcourir.

Maintenant, les tableaux std :: vector vs. C ++ natifs (extraits d’Internet):

 // Comparison of assembly code generated for basic indexing, dereferencing, // and increment operations on vectors and arrays/pointers. // Assembly code was generated by gcc 4.1.0 invoked with g++ -O3 -S on a // x86_64-suse-linux machine. #include  struct S { int padding; std::vector v; int * p; std::vector::iterator i; }; int pointer_index (S & s) { return sp[3]; } // movq 32(%rdi), %rax // movl 12(%rax), %eax // ret int vector_index (S & s) { return sv[3]; } // movq 8(%rdi), %rax // movl 12(%rax), %eax // ret // Conclusion: Indexing a vector is the same damn thing as indexing a pointer. int pointer_deref (S & s) { return *sp; } // movq 32(%rdi), %rax // movl (%rax), %eax // ret int iterator_deref (S & s) { return *si; } // movq 40(%rdi), %rax // movl (%rax), %eax // ret // Conclusion: Dereferencing a vector iterator is the same damn thing // as dereferencing a pointer. void pointer_increment (S & s) { ++sp; } // addq $4, 32(%rdi) // ret void iterator_increment (S & s) { ++si; } // addq $4, 40(%rdi) // ret // Conclusion: Incrementing a vector iterator is the same damn thing as // incrementing a pointer. 

Remarque: Si vous allouez des tableaux avec des objects non-class new et alloués (comme plain int ) ou des classes sans constructeur défini par l’utilisateur et que vous ne voulez pas initialiser vos éléments, l’utilisation de new tableaux alloués peut présenter des avantages std::vector initialise tous les éléments aux valeurs par défaut (0 pour int, par exemple) lors de la construction (crédits à @bernie pour se souvenir de moi).

Préambule pour les micro-optimiseurs

Rappelles toi:

«Les programmeurs perdent énormément de temps à réfléchir ou à se soucier de la rapidité des parties non critiques de leurs programmes, et ces tentatives d’efficacité ont un impact négatif important lorsque le débogage et la maintenance sont pris en compte. 97% du temps: l’ optimisation prématurée est la racine de tous les maux. Pourtant, nous ne devrions pas laisser passer nos opportunités dans ces 3% critiques.

(Merci à la métamorphose pour le devis complet)

N’utilisez pas un tableau C au lieu d’un vecteur (ou autre) simplement parce que vous pensez qu’il est plus rapide car il est supposé être de niveau inférieur. Vous auriez tort

Utilisez par défaut vector (ou le conteneur sécurisé adapté à vos besoins), et si votre profileur dit que c’est un problème, voyez si vous pouvez l’optimiser, en utilisant un meilleur algorithme ou en changeant de conteneur.

Cela dit, nous pouvons revenir à la question initiale.

Statique / Dynamic Array?

Les classes de tableau C ++ se comportent mieux que le tableau C de bas niveau car elles en savent beaucoup sur elles-mêmes et peuvent répondre aux questions que les tableaux C ne peuvent pas. Ils sont capables de se nettoyer eux-mêmes. Et plus important encore, ils sont généralement écrits en utilisant des templates et / ou des inlining, ce qui signifie que ce qui semble beaucoup de code dans debug se résume à peu ou pas de code produit dans cette version.

Dans l’ensemble, il appartient à deux catégories:

Tableaux dynamics

Utiliser un pointeur sur un tableau malloc-ed / new-ed sera au mieux aussi rapide que la version std :: vector, et beaucoup moins sûr (voir le post de litb ).

Donc, utilisez un std :: vector.

Tableaux statiques

Utiliser un tableau statique sera au mieux:

• aussi vite que la version std :: array
• et beaucoup moins sûr.

Donc, utilisez un std :: array .

Mémoire non initialisée

Parfois, l’utilisation d’un vector au lieu d’un tampon brut entraîne un coût visible car le vector initialise le tampon lors de la construction, tandis que le code qu’il remplace ne le fait pas, comme l’a remarqué bernie dans sa réponse .

Si c’est le cas, vous pouvez le gérer en utilisant un unique_ptr au lieu d’un vector ou, si le cas n’est pas exceptionnel dans votre codeline, écrivez réellement une classe buffer_owner qui possédera cette mémoire et vous donnera un access facile et sûr à y compris les bonus comme le redimensionner (en utilisant realloc ?), ou tout ce dont vous avez besoin.

Les vecteurs sont des tableaux sous le capot. La performance est la même.

L’un des endroits où vous pouvez rencontrer un problème de performances n’est pas de dimensionner correctement le vecteur pour commencer.

Au fur et à mesure qu’un vecteur se remplit, il se redimensionne, ce qui peut impliquer une nouvelle allocation de tableau, suivie de n constructeurs de copie, suivis par environ n appels de destructeurs, suivis d’une suppression de tableau.

Si votre construction / destruction est coûteuse, il est préférable de commencer avec le vecteur.

Il existe un moyen simple de le démontrer. Créez une classe simple qui indique quand elle est construite / détruite / copiée / assignée. Créez un vecteur de ces choses et commencez à les pousser à l’arrière du vecteur. Lorsque le vecteur se remplit, il y aura une cascade d’activités à mesure que le vecteur se redimensionne. Puis réessayez avec le vecteur dimensionné au nombre d’éléments attendu. Vous verrez la différence.

Pour répondre à quelque chose que Mehrdad a dit:

Cependant, il peut y avoir des cas où vous avez encore besoin de tableaux. Lors de l’interfaçage avec du code de bas niveau (c’est-à-dire un assemblage) ou d’anciennes bibliothèques nécessitant des baies, vous ne pourrez peut-être pas utiliser de vecteurs.

Pas du tout. Les vecteurs se dégradent bien en tableaux / pointeurs si vous utilisez:

 vector vector; vector.push_back(42); double *array = &(*vector.begin()); // pass the array to whatever low-level code you have 

Cela fonctionne pour toutes les principales implémentations STL. Dans le prochain standard, il faudra travailler (même si cela fonctionne très bien aujourd’hui).

Vous avez encore moins de raisons d’utiliser des tableaux simples dans C ++ 11.

Il existe trois types de baies dans la nature, du plus rapide au plus lent, en fonction des fonctionnalités dont elles disposent (bien sûr, la qualité de l’implémentation peut accélérer les choses, même dans le cas 3 de la liste):

1. Statique avec la taille connue au moment de la compilation. — std::array
2. Dynamique avec la taille connue à l’exécution et jamais redimensionnée. L’optimisation typique est que, si le tableau peut être alloué directement dans la stack. – Non disponible Peut-être dynarray en C ++ TS après C ++ 14. En C il y a des VLA
3. Dynamique et redimensionnable à l’exécution. — std::vector

Pour 1. les tableaux statiques simples avec un nombre fixe d’éléments, utilisez std::array dans C ++ 11.

Pour les tableaux 2. de taille fixe spécifiés lors de l’exécution, mais qui ne changeront pas leur taille, il y a une discussion dans C ++ 14, mais celle-ci a été déplacée vers une spécification technique et issue de C ++ 14.

Pour 3. std::vector demandera généralement de la mémoire dans le tas . Cela pourrait avoir des conséquences sur les performances, bien que vous puissiez utiliser std::vector> pour améliorer la situation avec un allocateur personnalisé. L’avantage par rapport à T mytype[] = new MyType[n]; est que vous pouvez le redimensionner et qu’il ne se désintègre pas en un pointeur, comme le font les tableaux simples.

Utilisez les types de bibliothèques standard mentionnés pour éviter que les tableaux ne se désintègrent en pointeurs . Vous économiserez du temps de débogage et les performances sont identiques à celles des tableaux simples si vous utilisez le même ensemble de fonctionnalités.

STL est une bibliothèque fortement optimisée. En fait, il est même suggéré d’utiliser STL dans les jeux où des performances élevées pourraient être nécessaires. Les tableaux sont trop sujets aux erreurs pour être utilisés dans les tâches quotidiennes. Les compilateurs actuels sont également très intelligents et peuvent vraiment produire un excellent code avec STL. Si vous savez ce que vous faites, STL peut généralement fournir les performances nécessaires. Par exemple, en initialisant les vecteurs à la taille requirejse (si vous le savez depuis le début), vous pouvez essentiellement atteindre les performances du tableau. Cependant, il peut y avoir des cas où vous avez encore besoin de tableaux. Lors de l’interfaçage avec du code de bas niveau (c’est-à-dire un assemblage) ou d’anciennes bibliothèques nécessitant des baies, vous ne pourrez peut-être pas utiliser de vecteurs.

Aller avec STL. Il n’y a pas de pénalité de performance. Les algorithmes sont très efficaces et ils gèrent bien les types de détails auxquels la plupart d’entre nous ne penseraient pas.

A propos de la consortingbution de duli

La conclusion est que les tableaux d’entiers sont plus rapides que les vecteurs d’entiers (5 fois dans mon exemple). Cependant, les tableaux et les vecteurs suivent la même vitesse pour les données plus complexes / non alignées.

Si vous comstackz le logiciel en mode débogage, de nombreux compilateurs n’incluront pas les fonctions d’accesseur du vecteur. Cela rendra l’implémentation stl vector beaucoup plus lente dans les cas où les performances posent problème. Cela facilitera également le débogage du code, car vous pouvez voir dans le débogueur la quantité de mémoire allouée.

En mode optimisé, je m’attendrais à ce que le vecteur stl approche de l’efficacité d’un tableau. Cela est dû au fait que de nombreuses méthodes vectorielles sont maintenant intégrées.

La différence de performance entre les deux dépend beaucoup de l’implémentation – si vous comparez un std :: vector mal implémenté à une implémentation optimale du tableau, le tableau gagnerait, mais le renverserait et le vecteur gagnerait …

Tant que vous comparez des pommes avec des pommes (que le tableau et le vecteur aient un nombre déterminé d’éléments, ou que les deux soient redimensionnés dynamicment), je pense que la différence de performance est négligeable tant que vous suivez le code STL. N’oubliez pas que l’utilisation de conteneurs C ++ standard vous permet également d’utiliser les algorithmes pré-déployés qui font partie de la bibliothèque C ++ standard et que la plupart d’entre eux sont probablement plus performants que l’implémentation moyenne du même algorithme que vous avez créé. .

Cela dit, à mon humble avis, le vecteur gagne dans un scénario de débogage avec un STL de débogage, car la plupart des implémentations STL avec un mode de débogage approprié peuvent au moins mettre en évidence les erreurs typiques commises avec des conteneurs standard.

Oh, et n’oubliez pas que le tableau et le vecteur partagent la même disposition de mémoire, donc vous pouvez utiliser des vecteurs pour transmettre des données au code C ou C ++ hérité qui attend des tableaux de base. Gardez à l’esprit que la plupart des paris sont désactivés dans ce scénario, et que vous avez à nouveau affaire à de la mémoire brute.

Si vous n’avez pas besoin d’ajuster dynamicment la taille, vous avez une surcharge de mémoire pour enregistrer la capacité (un pointeur / taille_t). C’est tout.

Il pourrait y avoir un cas particulier où vous avez un access vectoriel dans une fonction inline dans une fonction en ligne, où vous êtes allé au-delà de ce que le compilateur va mettre en ligne et forcer un appel de fonction. Ce serait si rare que cela ne vaut pas la peine de s’inquiéter. En général, je suis d’accord avec Litb .

Je suis surpris que personne ne l’ait encore mentionné – ne vous inquiétez pas de la performance tant qu’il n’aura pas été prouvé qu’il s’agit d’un problème, puis d’un benchmark.

Je soutiens que la principale préoccupation n’est pas la performance, mais la sécurité. Vous pouvez faire beaucoup d’erreurs avec les tableaux (pensez à redimensionner, par exemple), où un vecteur vous épargnerait beaucoup de douleur.

Les vecteurs utilisent un peu plus de mémoire que les tableaux car ils contiennent la taille du tableau. Ils augmentent également la taille du disque dur des programmes et probablement l’empreinte mémoire des programmes. Ces augmentations sont minimes, mais peuvent être importantes si vous travaillez avec un système intégré. Bien que la plupart des endroits où ces différences sont importantes sont des endroits où vous utiliseriez C plutôt que C ++.

Le test simple suivant:

Explication du test de performance C ++ Array vs Vector

contredit les conclusions de “Comparaison du code d’assemblage généré pour les opérations d’indexation de base, de déréférencement et d’incrémentation sur les vecteurs et les tableaux / pointeurs”.

Il doit y avoir une différence entre les tableaux et les vecteurs. Le test dit donc … essayez-le, le code est là …

Parfois, les tableaux sont meilleurs que les vecteurs. Si vous manipulez toujours un ensemble d’objects de longueur fixe, les tableaux sont meilleurs. Considérez les extraits de code suivants:

 int main() { int v[3]; v[0]=1; v[1]=2;v[2]=3; int sum; int starttime=time(NULL); cout << starttime << endl; for (int i=0;i<50000;i++) for (int j=0;j<10000;j++) { X x(v); sum+=x.first(); } int endtime=time(NULL); cout << endtime << endl; cout << endtime - starttime << endl; } 

où la version vectorielle de X est

 class X { vector vec; public: X(const vector& v) {vec = v;} int first() { return vec[0];} }; 

et la version de tableau de X est:

 class X { int f[3]; public: X(int a[]) {f[0]=a[0]; f[1]=a[1];f[2]=a[2];} int first() { return f[0];} }; 

La version du tableau de main () sera plus rapide car nous évitons la surcharge de "nouveau" à chaque fois dans la boucle interne.

(Ce code a été posté sur comp.lang.c ++ par moi).

L’utilisation d’un std::vector vs un tableau brut a certainement un impact sur les performances lorsque vous souhaitez utiliser un tampon non initialisé (par exemple, pour l’utiliser comme destination pour memcpy() ). Un std::vector initialisera tous ses éléments en utilisant le constructeur par défaut. Un tableau brut ne sera pas.

La spécification c ++ pour le constructeur std:vector prenant un argument count (c’est la troisième forme) indique:

`Construit un nouveau conteneur à partir de diverses sources de données, en utilisant éventuellement une allocation d’allocateur fournie par l’utilisateur.

3) Construit le conteneur avec le nombre d’instances insérées par défaut de T. Aucune copie n’est faite.

Complexité

2-3) Nombre linéaire

Un tableau brut n’engendre pas ce coût d’initialisation.

Voir aussi Comment puis-je éviter std :: vector <> pour initialiser tous ses éléments?