En utilisant des tableaux ou des vecteurs std :: en C ++, quel est l'écart de performances?

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 de tableaux. Mais y a-t-il des différences de performances importantes?

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

L'utilisation de tableaux sur la pile est également déconseillée car vous n'avez pas de vérification de plage, et le passage du tableau perdra toutes les informations sur sa taille (conversion de tableau en pointeur). Tu devrais utiliserboost::array dans ce cas, qui encapsule un tableau C ++ dans une petite classe et fournit une sizefonction et des itérateurs pour itérer dessus.

Maintenant, les tableaux std :: vector vs natifs C ++ (tirés 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 <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    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // 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 newet allouez des objets non-classe (comme plain int) ou des classes sans constructeur défini par l'utilisateur et que vous ne voulez pas que vos éléments soient initialisés initialement, l'utilisation de newtableaux alloués peut présenter des avantages en termes de performances car il std::vectorinitialise tous les éléments à valeurs par défaut (0 pour int, par exemple) sur la construction (crédit à @bernie pour me le rappeler).

Préambule pour les micro-optimiseurs

Rappelles toi:

"Les programmeurs perdent énormément de temps à penser 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 le débogage et la maintenance sont envisagés. Nous devons oublier les petites économies, par exemple 97% du temps: l' optimisation prématurée est la racine de tous les maux. Pourtant, nous ne devons 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 censé être de niveau inférieur. Tu aurais tort.

Utilisez le vecteur par défaut (ou le conteneur sécurisé adapté à vos besoins), puis si votre profileur indique qu'il s'agit d'un problème, voyez si vous pouvez l'optimiser, soit en utilisant un meilleur algorithme, soit en changeant de conteneur.

Cela dit, nous pouvons revenir à la question d'origine.

Tableau statique / dynamique?

Les classes de tableaux C ++ se comportent mieux que les tableaux 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 nettoyer après eux-mêmes. Et plus important encore, ils sont généralement écrits à l'aide de modèles et / ou d'inlining, ce qui signifie que ce qui apparaît à beaucoup de code dans le débogage se résout à peu ou pas de code produit dans la version Release, ce qui signifie aucune différence avec leur concurrence intégrée moins sûre.

Dans l'ensemble, il se divise en deux catégories:

Tableaux dynamiques

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

Utilisez donc un std :: vector.

Tableaux statiques

L'utilisation d'un tableau statique sera au mieux:

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

Utilisez donc un std :: array .

Mémoire non initialisée

Parfois, utiliser un vectorau lieu d'un tampon brut entraîne un coût visible car l' vectorinitialisation du tampon lors de la construction, alors que le code qu'il remplace ne l'a pas fait, comme l'a remarqué bernie by dans sa réponse .

Si tel est le cas, vous pouvez le gérer en utilisant un unique_ptrau lieu d'un vectorou, si le cas n'est pas exceptionnel dans votre ligne de code, écrivez en fait une classe buffer_ownerqui possédera cette mémoire et vous donnera un accès facile et sûr, y compris des 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.

Un endroit 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 lui-même, ce qui peut impliquer une nouvelle allocation de tableau, suivie de n constructeurs de copie, suivie d'environ n appels de destructeur, suivie d'une suppression de tableau.

Si votre construction / destruction est coûteuse, vous feriez mieux de faire du vecteur la bonne taille pour commencer.

Il existe un moyen simple de le démontrer. Créez une classe simple qui montre quand elle est construite / détruite / copiée / affecté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é lorsque le vecteur se redimensionne. Réessayez ensuite 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 qui nécessitent des tableaux, vous ne pourrez peut-être pas utiliser de 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

Cela fonctionne pour toutes les implémentations STL principales. Dans la prochaine norme, il devra fonctionner (même s'il fonctionne très bien aujourd'hui).

Vous avez encore moins de raisons d'utiliser des tableaux simples en C ++ 11.

Il existe 3 types de tableaux dans la nature, du plus rapide au plus lent, en fonction des fonctionnalités dont ils disposent (bien sûr, la qualité de la mise en œuvre peut rendre les choses très rapides même pour le cas 3 de la liste):

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

Pour 1. tableaux statiques simples avec un nombre fixe d'éléments, utilisezstd::array<T, N> en C ++ 11.

Pour 2. des tableaux de taille fixe spécifié lors de l' exécution, mais cela ne changera pas leur taille, il y a discussion en C ++ 14 mais il a été déplacé à un cahier des charges technique et fabriqués à partir de C ++ 14 enfin.

Pour 3. std::vector<T> demandera généralement de la mémoire dans le tas . Cela peut avoir des conséquences sur les performances, mais vous pouvez 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 pouvez le redimensionner et qu'il ne se décomposera 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écomposent en pointeurs . Vous économiserez du temps de débogage et les performances sont exactement les mêmes qu'avec des tableaux simples si vous utilisez le même ensemble de fonctionnalités.

Allez avec STL. Il n'y a aucune pénalité de performance. Les algorithmes sont très efficaces et ils font un bon travail pour gérer les types de détails auxquels la plupart d'entre nous ne penseraient 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 à la même vitesse pour les données plus complexes / non alignées.

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 peuvent être nécessaires. Les tableaux sont trop sujets aux erreurs pour être utilisés 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 les performances nécessaires. Par exemple, en initialisant les vecteurs à la taille requise (si vous le savez depuis le début), vous pouvez essentiellement obtenir 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 qui nécessitent des tableaux, vous ne pourrez peut-être pas utiliser de vecteurs.

Si vous compilez le logiciel en mode débogage, de nombreux compilateurs n'intégreront pas les fonctions d'accesseur du vecteur. Cela rendra l'implémentation du vecteur stl beaucoup plus lente dans les circonstances où les performances sont un 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 s'approche de l'efficacité d'un tableau. En effet, de nombreuses méthodes vectorielles sont désormais intégrées.

Il y a certainement un impact sur les performances à utiliser un std::vectorvs un tableau brut lorsque vous voulez un tampon non initialisé (par exemple à utiliser comme destination pour memcpy()). An std::vectorinitialisera tous ses éléments à l'aide du constructeur par défaut. Un tableau brut ne le sera pas.

La spécification c ++ pour le std:vectorconstructeur prenant un countargument (c'est la troisième forme) indique:

`Construit un nouveau conteneur à partir d'une variété de sources de données, en utilisant éventuellement un allocateur fourni par l'utilisateur alloc.

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

Complexité

2-3) Linéaire en nombre

Un tableau brut n'encourt pas ce coût d'initialisation.

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

La différence de performances entre les deux dépend beaucoup de l'implémentation - si vous comparez un vecteur std :: mal implémenté à une implémentation de tableau optimale, le tableau gagnerait, mais le retournerait 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, soit les deux sont redimensionnés dynamiquement), je pense que la différence de performances est négligeable tant que vous suivez la pratique du codage STL. N'oubliez pas que l'utilisation de conteneurs C ++ standard vous permet également d'utiliser les algorithmes pré-roll qui font partie de la bibliothèque C ++ standard et la plupart d'entre eux sont susceptibles d'être plus performants que la mise en œuvre moyenne du même algorithme que vous construisez vous-même .

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

Oh, et n'oubliez pas que le tableau et le vecteur partagent la même disposition de mémoire afin que vous puissiez 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 vous avez à nouveau affaire à de la mémoire brute.

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

Il peut y avoir un cas limite où vous avez un accès vectoriel à l'intérieur d'une fonction inline à l'intérieur d'une fonction inline, où vous êtes allé au-delà de ce que le compilateur va inline et cela forcera un appel de fonction. Ce serait si rare qu'il ne vaut pas la peine de s'inquiéter - en général, je suis d'accord avec litb .

Je suis surpris que personne n'ait encore mentionné cela - ne vous inquiétez pas des performances jusqu'à ce qu'il soit prouvé qu'elles posent problème, puis comparez.

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.

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 avoir de l'importance si vous travaillez avec un système intégré. Bien que la plupart des endroits où ces différences comptent sont des endroits où vous utiliseriez C plutôt que C ++.

Le test simple suivant:

Explication du test de performances du tableau C ++ vs du vecteur

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

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

Parfois, les tableaux sont en effet meilleurs que les vecteurs. Si vous manipulez toujours un ensemble d'objets de longueur fixe, les tableaux sont meilleurs. Tenez compte des 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<int> vec;
public:
X(const vector<int>& v) {vec = v;}
int first() { return vec[0];}
};

et la version 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é publié par comp.lang.c ++ par moi).

Si vous utilisez des vecteurs pour représenter un comportement multidimensionnel, il y a un impact sur les performances.

Les vecteurs 2D + provoquent-ils un impact sur les performances?

L'essentiel est qu'il y a une petite quantité de surcharge avec chaque sous-vecteur ayant des informations de taille, et il n'y aura pas nécessairement de sérialisation des données (comme c'est le cas avec les tableaux c multidimensionnels). Ce manque de sérialisation peut offrir des opportunités supérieures à la micro-optimisation. Si vous faites des tableaux multidimensionnels, il peut être préférable d'étendre simplement std :: vector et de lancer votre propre fonction get / set / resize bits.

En supposant un tableau de longueur fixe (par exemple, int* v = new int[1000];vs std::vector<int> v(1000);, avec une taille vfixée à 1000), la seule considération de performance qui compte vraiment (ou du moins qui m'importait lorsque j'étais dans un dilemme similaire) est la vitesse d'accès à un élément. J'ai recherché le code vectoriel de la STL, et voici ce que j'ai trouvé:

const_reference
operator[](size_type __n) const
{ return *(this->_M_impl._M_start + __n); }

Cette fonction sera très certainement intégrée par le compilateur. Donc, tant que la seule chose avec laquelle vous prévoyez de faire vest d'accéder à ses éléments operator[], il semble qu'il ne devrait pas y avoir vraiment de différence de performances.