En utilisant des tableaux ou des vecteurs std:: en C++, quelle est la différence de performance?
dans notre cours C++ ils suggèrent de ne plus utiliser de tableaux C++ sur de nouveaux projets. Pour autant que je sache Stroustroup lui-même suggère de ne pas utiliser les tableaux. Mais il y a de différences significatives de performance?
17 réponses
utilisant des matrices C++ avec new (c'est-à-dire utilisant des matrices dynamiques) doit être évité. Là est le problème, vous devez garder une trace de la taille, et vous devez les supprimer manuellement, et faire toute sorte de ménage.
utiliser des tableaux sur la pile est également déconseillé parce que vous n'avez pas de vérification de la portée, et passer le tableau autour perdra toute information sur sa taille (tableau à la conversion de pointeur). Vous devez utiliser boost::array dans ce cas, qui enroule un tableau C++ dans une petite classe et fournit une fonction size et des itérateurs pour itérer dessus.
Maintenant std::vector vs C++ natif de matrices (de l'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 <vector>
struct S
{
int padding;
std::vector<int> v;
int * p;
std::vector<int>::iterator i;
};
int pointer_index (S & s) { return s.p[3]; }
// movq 32(%rdi), %rax
// movl 12(%rax), %eax
// ret
int vector_index (S & s) { return s.v[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 *s.p; }
// movq 32(%rdi), %rax
// movl (%rax), %eax
// ret
int iterator_deref (S & s) { return *s.i; }
// 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) { ++s.p; }
// addq , 32(%rdi)
// ret
void iterator_increment (S & s) { ++s.i; }
// addq , 40(%rdi)
// ret
// Conclusion: Incrementing a vector iterator is the same damn thing as
// incrementing a pointer.
Note: Si vous attribuez des tableaux avec new et des objets hors classe (comme int ) ou des classes sans un constructeur défini par l'utilisateur et , vous ne voulez pas avoir vos éléments initialisé initialement, en utilisant new - tableaux alloués peuvent avoir des avantages de performance parce que std::vector initialise tous les éléments aux valeurs par défaut (0 pour int, par exemple) sur la construction (crédits à @bernie pour se souvenir de moi).
Préambule pour les micro-optimiseur de personnes
Rappelez-vous:
" les programmeurs gaspillent énormément de temps à réfléchir ou à s'inquiéter de la vitesse des parties non critiques de leurs programmes, et ces tentatives d'efficacité ont en fait un fort impact négatif lorsque l'on considère le débogage et la maintenance. Nous devrions oublier les petites efficacités, disons environ 97% du temps: l'optimisation prématurée est la racine de tous les maux. mais nous ne devons pas laisser passer nos chances dans ce 3% critique".
(merci à metamorphosis pour la citation complète)
N'utilisez pas un tableau C à la place d'un vecteur (ou autre) juste parce que vous croyez qu'il est plus rapide comme il est censé être de niveau inférieur. Vous auriez tort.
utilisez par défaut le vecteur (ou le conteneur sûr adapté à votre besoin), et puis si votre profiler dit que c'est un problème, voir si vous pouvez l'optimiser, soit en utilisant un meilleur algorithme, ou en changeant le conteneur.
Cela dit, nous pouvons revenir à la question initiale.
Statique/Dynamique De Tableau?
les classes de tableaux C++ se comportent mieux que les tableaux C de bas niveau parce qu'elles en savent beaucoup sur elles-mêmes, et peuvent répondre à des questions que les tableaux C ne peuvent pas. Ils sont capables de nettoyer après eux-mêmes. Et plus important encore, ils sont généralement écrit en utilisant des gabarits et / ou en ligne, ce qui signifie que ce qui apparaît à beaucoup de code dans le debug se résout à peu ou pas de code produit dans la construction de la version, ce qui signifie aucune différence avec leur concurrence moins sûr intégré.
au total, il se divise en deux catégories:
tableaux Dynamiques
utilisant 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 litb post ).
donc utiliser un std::vecteur.
tableaux statiques
utilisant un tableau statique sera au mieux:
- aussi rapide que le std:: array version
- et beaucoup moins sûr.
utilisez donc 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 parce que le vector initialise le tampon à la construction, tandis que le code qu'il remplace n'a pas, comme le fait remarquer bernie par dans son réponse .
Si c'est le cas, alors vous pouvez le manipuler à l'aide d'un unique_ptr au lieu de vector ou, si le cas n'est pas exceptionnel dans votre version, à l'écriture d'un classe buffer_owner qui possédera cette mémoire, et vous donner un accès facile et sûr à elle, y compris les primes comme le redimensionnement (en utilisant realloc ?), ou tout ce que vous avez besoin.
sont des tableaux sous le capot. La performance est la même.
un endroit où vous pouvez courir dans un problème de performance, n'est pas dimensionnement du vecteur correctement pour commencer.
comme un vecteur remplit, il se redimensionne, et cela peut impliquer, une nouvelle allocation de tableau, suivi par n copy constructors, suivi par environ n appels destructeurs, suivi par un tableau supprimer.
si votre construction / destruction est coûteuse, vous êtes il est préférable de faire du vecteur la taille correcte pour commencer.
il y a une façon simple de le démontrer. Créez une classe simple qui montre 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 de remplissage, il y aura une cascade d'activité comme le vecteur redimensionne. Ensuite, essayez de nouveau avec le vecteur dimensionné au nombre attendu d'éléments. Vous verrez différence.
Pour répondre à quelque chose de Mehrdad , a déclaré:
cependant, il peut y avoir des cas où vous avez encore besoin de tableaux. Lorsque l'interfaçage avec le code bas-niveau (c'est à dire les bibliothèques anciennes qui exiger des tableaux, vous pourriez ne pas être en mesure d'utiliser des vecteurs.
pas vrai du tout. Les vecteurs se dégradent bien en tableaux / pointeurs si vous utilisez:
vector<double> vector;
vector.push_back(42);
double *array = &(*vector.begin());
// pass the array to whatever low-level code you have
ça marche pour tous principales implémentations STL. Dans la prochaine norme, il sera nécessaire de travailler (même si elle fait très bien aujourd'hui).
vous avez encore moins de raisons d'utiliser des tableaux simples en C++11.
il y a 3 types de tableaux dans la nature, du plus rapide au plus lent, en fonction des caractéristiques qu'ils ont (bien sûr la qualité de la mise en œuvre peut rendre les choses vraiment rapide, même pour le cas 3 dans la liste):
- statique avec une taille connue au moment de la compilation. ---
std::array<T, N> - dynamique avec taille connue à l'exécution et jamais redimensionnée. Le typique l'optimisation est ici, que, si le tableau peut être alloué dans la pile directement. -- Non disponible . Peut-être
dynarrayen C++ TS après C++14. En C Il y a VLAs - dynamique et redimensionnable à l'exécution. ---
std::vector<T>
pour 1. tableaux statiques simples avec nombre fixe d'éléments, utilisez std::array<T, N> en C++11.
pour 2. taille fixe les tableaux spécifiés à l'exécution, mais qui ne changeront pas leur taille, il y a une discussion dans C++14 mais il a été déplacé à une spécification technique et fait à partir de C++14 enfin.
pour 3. std::vector<T> demandera généralement la mémoire dans le tas . Cela pourrait avoir des conséquences sur la performance, bien que vous puissiez utiliser std::vector<T, MyAlloc<T>> pour améliorer la situation avec un allocateur personnalisé. L'avantage par rapport à T mytype[] = new MyType[n]; est que vous peut le redimensionner et qu'il ne se décomposera pas en pointeur, comme les tableaux simples le font.
utilisez les types de bibliothèques standards mentionnés pour éviter les tableaux se décomposent en pointeurs . Vous économiserez du temps de débogage et la performance est exactement la même que pour les 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ù la haute performance pourrait être nécessaire. Les matrices sont trop sujettes aux erreurs pour être utilisées dans les tâches quotidiennes. Les compilateurs d'aujourd'hui 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 la performance nécessaire. Par exemple, en initialisant les vecteurs à la taille requise (si vous le savez depuis le début), vous pouvez fondamentalement atteindre la performance du tableau. Cependant, il peut y avoir des cas où vous avez encore besoin de tableaux. Lors de l'interfaçage avec le code de bas niveau (i.e. l'assemblage) ou d'anciennes bibliothèques qui nécessitent des tableaux, vous pourriez ne pas être en mesure d'utiliser des vecteurs.
va avec STL. Il n'y a pas de perte de performances. Les algorithmes sont très efficaces et ils font du bon travail pour gérer le genre de détails que la plupart d'entre nous ne penserait pas.
à propos de la contribution 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 sont à peu près à la même vitesse pour les données plus complexes / non alignées.
si vous compilez le logiciel en mode debug, beaucoup de compilateurs ne vont pas en ligne les fonctions d'accesseur du vecteur. Cela rendra la mise en œuvre du vecteur stl beaucoup plus lente dans les circonstances où la performance est un problème. Il sera également plus facile de déboguer le code puisque vous pouvez voir dans le débogueur combien de mémoire a été allouée.
en mode optimisé, Je m'attendrais à ce que le vecteur stl approche l'efficacité d'un réseau. Ceci est dû au fait que de nombreuses méthodes vectorielles sont maintenant intégrées.
la différence de performance entre les deux est très dépendante de la mise en œuvre - si vous comparez un std mal mis en œuvre::vector à une mise en œuvre optimale du tableau, le tableau gagnerait, mais tournez-le et le vecteur gagnerait...
tant que vous comparez des pommes avec des pommes (soit le tableau et le vecteur ont un nombre fixe d'éléments, ou les deux sont redimensionnés dynamiquement) je pense que la différence de performance est négligeable tant que vous suivez got STL code pratique. N'oubliez pas que l'utilisation de conteneurs standard C++ vous permet également de faire usage des algorithmes pré-roulés qui font partie de la bibliothèque standard C++ et la plupart d'entre eux sont susceptibles d'être plus performants que l'implémentation moyenne du même algorithme que vous construisez vous-même.
cela dit, IMHO le vecteur gagne dans un scénario de débogage avec une STL de débogage comme la plupart des implémentations de STL avec un mode de débogage approprié peut au moins surligner / cathc le type erreurs commises par les gens lorsqu'ils travaillent avec des contenants standard.
OH, et n'oubliez pas que le tableau et le vecteur partagent la même disposition de mémoire de sorte que vous pouvez utiliser des vecteurs pour passer des données au code C ou C++ qui attend des tableaux de base. Gardez à l'esprit que la plupart des paris sont off dans ce scénario, bien que, et vous avez affaire à la mémoire brute à nouveau.
il y a certainement un impact de performance à utiliser un std::vector vs Un tableau brut quand vous voulez un tampon non initialisé (par exemple à utiliser comme destination pour memcpy() ). Un std::vector initialise tous ses éléments en utilisant le constructeur par défaut. Un tableau brut ne le fera pas.
le c++ spec pour le std:vector constructeur prenant un count argument (c'est la troisième forme) déclare:
' construit un nouveau conteneur à partir d'une variété de sources de données, en utilisant éventuellement un allocateur fourni par l'utilisateur.
3) construit le conteneur avec les instances de T insérées par défaut.aucune copie n'est faite.
complexité
2-3) linéaire en nombre
un tableau brut n'entraîne pas ce coût d'initialisation.
Voir aussi Comment puis-je éviter de std::vector<> pour initialiser tous ses éléments?
si vous n'avez pas besoin d'ajuster dynamiquement la taille, vous avez la mémoire au-dessus de sauver la capacité (un pointeur/size_t). C'est tout.
il pourrait y avoir un cas de bord où vous avez un accès vectoriel à l'intérieur d'une fonction en ligne à l'intérieur d'une fonction en ligne, où vous êtes allé au-delà de ce que le compilateur va en ligne et il va forcer un appel de fonction. Ce serait si rare qu'il ne vaudrait pas la peine de s'en inquiéter - en général, je serais d'accord avec litb .
je suis surpris que personne ne l'ait encore mentionné - ne vous inquiétez pas pour la performance jusqu'à ce qu'il ait été prouvé que c'est un problème, puis référence.
je dirais 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.
utilisent un tout petit peu plus de mémoire que les tableaux puisqu'ils contiennent la taille du tableau. Ils augmentent également la taille du disque dur des programmes et probablement l'empreinte de mémoire des programmes. Ces augmentations sont minuscules, mais peut importe si vous travaillez avec un système embarqué. 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:
C++ Tableau vs Vecteur de test de performance explication
est en contradiction avec les conclusions de la "Comparaison de code assembleur généré pour base d'indexation, de déférence, et incrémenter les opérations sur les vecteurs et les tableaux/pointeurs."
Il doit y avoir une différence entre les matrices et des vecteurs. Le test dit de la sorte... il suffit de l'essayer, le code est là...
parfois les tableaux sont en effet meilleurs que les vecteurs. Si vous êtes toujours en train de manipuler une longueur fixe ensemble d'objets, les tableaux sont mieux. Considérons 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 vecteur de X est
class X {
vector<int> vec;
public:
X(const vector<int>& v) {vec = v;}
int first() { return vec[0];}
};
et la version array 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 les les frais généraux de "nouveau" à chaque fois dans la boucle interne.
(ce code a été posté à comp.lang.c++ par moi).