À l’aide de tableaux ou std::vectors en C++, ce qui ' s l’écart de performance ?

Question

Dans notre cours de C++ ils suggèrent de ne pas pour utiliser de tableaux C++ sur de nouveaux projets plus. Autant que je sache Stroustroup lui-même suggère ne pas d’employer des tableaux. Mais y a-t-il des différences de performances significatives ?

Answer 1

À l'aide de C++ tableaux avec des new (qui est, à l'aide de tableaux dynamiques) doit être évitée. 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.

À l'aide de tableaux sur la pile est également découragé parce que vous n'avez pas le contrôle de la portée, et en passant le tableau autour perdrez toutes les informations au sujet de sa taille (tableau de pointeur de conversion). Vous devez utiliser boost::array dans ce cas, qui encapsule un C++ tableau dans une petite classe et fournit un size de la fonction et des itérateurs pour itérer sur elle.

Maintenant, le std::vector vs C++ natif de tableaux (pris sans vergogne à partir d'ici: http://www.xs4all.nl/~weegen/eelis/vector-speed.cpp):

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

Answer 2

Préambule pour les micro-optimiseur de personnes

Rappelez-vous "l'optimisation Prématurée est la racine de tout mal".

N'utilisez pas de C tableau au lieu d'un vecteur (ou autre) juste parce que vous croyez que c'est plus rapide car il est censé être de niveau inférieur. Vous auriez tort.

L'utilisation par défaut du vecteur (ou le coffre contenant adapté à votre besoin), et ensuite, si votre profiler dit que c'est un problème, voir si vous pouvez l'optimiser, soit par le biais d'un meilleur algorithme, ou de changer de récipient.

Cela dit, nous pouvons revenir à la question initiale.

Statique/Dynamique De Tableau?

Le C++ tableau des classes sont mieux comportés que le faible niveau C tableau car ils savent beaucoup de choses sur eux-mêmes, et peut répondre à des questions C les tableaux peuvent pas. Ils sont capables de nettoyer après eux-mêmes. Et plus important encore, ils sont généralement écrites à l'aide de modèles et/ou l'in-lining, ce qui signifie que ce qui apparaît à beaucoup de code dans le debug résout à peu ou pas de code de produit en version release, ce qui signifie pas de différence avec ses construit en moins sûr de la concurrence.

Dans l'ensemble, il tombe sur deux catégories:

Les tableaux dynamiques

À l'aide d'un pointeur vers un malloc-ed/nouvelle-ed tableau sera, au mieux, aussi rapide que le std::vector version, et beaucoup moins en sécurité (voir litb du post).

Il faut donc utiliser un std::vector.

Les tableaux statiques

À l'aide d'un tableau statique sera au mieux:

• aussi rapide que le boost::array version
• et beaucoup moins sûr.

Il faut donc utiliser un boost::array.

Answer 3

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

Un endroit où vous pouvez rencontrer un problème de performance, n'est pas de la taille du vecteur correctement pour commencer.

En tant que vecteur de remplissage, il sera redimensionné lui-même, et qui peuvent se traduire, un nouveau tableau de répartition, suivi de n copie constructeurs, suivis par environ n destructeur des appels, suivi par un tableau de supprimer.

Si votre construction/destruction est cher, vous êtes beaucoup mieux de faire le vecteur de la bonne taille pour commencer.

Il existe un moyen simple de le démontrer. Créer une classe simple qui permet de savoir quand il est construit/détruit/copié/affecté. Créer un vecteur de ces choses, et de commencer à pousser sur l'extrémité arrière du vecteur. Lorsque le vecteur de remplissage, il y aura une cascade d'activité comme le vecteur redimensionne. Puis essayez à nouveau avec le vecteur de taille moyenne pour le nombre d'éléments. Vous verrez la différence.

Answer 4

Pour répondre à quelque chose de Mehrdad dit:

Toutefois, il pourrait y avoir des cas où vous avez encore besoin de tableaux. Lorsque l'interfaçage avec le code bas-niveau (c'est à dire assemblée) ou les anciennes bibliothèques qui exiger des tableaux, vous pourriez ne pas être en mesure d'utiliser des vecteurs.

Pas vrai du tout. Vecteurs de se dégrader bien des 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 grandes STL implémentations. Dans le prochain standard, il sera nécessaire de travailler (même si il ne fonctionne tout simplement beau aujourd'hui).

Answer 5

Vous avez encore moins de raisons de l'utilisation de la plaine des tableaux en C++11.

Il existe 3 types de tableaux dans la nature du plus rapide au plus lent, selon les caractéristiques qu'ils ont (bien sûr, la qualité de la mise en œuvre peut faire des choses vraiment rapide, même pour les cas 3 dans la liste):

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

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

Pour 2. les matrices de taille fixe spécifié lors de l'exécution, mais ça ne changera pas leur taille, il y a des discussions en C++14, mais il a été déplacé à une spécification technique, le fait de C++14, enfin.

Pour 3. std::vector<T> demandera généralement de la mémoire dans le tas. Cela pourrait avoir des performances des conséquences, mais vous pouvez utiliser std::vector<T, MyAlloc<T>> afin d'améliorer la situation avec un allocateur personnalisé. L'avantage par rapport à l' T mytype[] = new MyType[n]; , c'est que vous pouvez la redimensionner et qu'il ne sera pas endommagé à un pointeur, comme de simples tableaux de faire.

Utilisation de la bibliothèque standard types mentionnés pour éviter les matrices de décomposition de pointeurs. Vous permettra d'économiser du temps de débogage et de la performance est exactement le même que la plaine des tableaux si vous utilisez le même ensemble de fonctionnalités.