Le vecteur s’initialisant plus lentement que le tableau… pourquoi?

Question

J'ai essayé 2 choses: (pseudo-code ci-dessous)

int arr[10000];
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

et

vector<int> arr(10000);
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

J'ai exécuté les deux programmes et les ai chronométrés à l'aide du "temps". commande shell. Le programme 1 s'exécute en 5 secondes, le programme 2 en 30 secondes. J'ai exécuté les deux programmes avec l'optimisation du compilateur activé, et les deux programmes ont fonctionné à peu près au même moment (0,38 s). Je suis confus par ces résultats. Quelqu'un peut-il m'expliquer pourquoi cela se produit?

Merci!

Answer 1

Pour le modèle, l'indexation est effectuée avec l'opérateur []. Lorsque l'optimisation est désactivée, elle est généralement générée sous la forme d'un véritable appel de fonction, ce qui ajoute beaucoup de charge à quelque chose d'aussi simple que d'indiquer dans un tableau. Lorsque vous activez l'optimisation, elle est générée en ligne, ce qui supprime cette surcharge.

Answer 2

En mode de débogage, les implémentations de std :: vector fournissent beaucoup de vérifications à l'exécution pour faciliter leur utilisation. Cette vérification n'est pas disponible pour les tableaux natifs. Par exemple, dans VC2008, si vous compilez votre exemple vectoriel en mode débogage, il y aura vérification de plage même dans le cas de opérateur [] .

Answer 3

Si votre implémentation vectorielle non optimisée effectue une vérification des limites, cela rendrait compte de la différence.

Answer 4

Ce sont de bonnes réponses, mais il existe un moyen rapide de le découvrir vous-même.

Vous constatez une différence de performances de 6 à 1, n'est-ce pas? Il suffit de lancer le lent et de cliquer sur le bouton "pause". bouton. Ensuite, regardez la pile d'appels. La probabilité est de 5 sur 6 (83%) que vous verrez exactement comment vous dépensez ces 25 secondes supplémentaires. Faites-le plusieurs fois pour obtenir autant d'informations que vous le souhaitez.

Pour le cas optimisé, faites de même avec le programme 1. Puisqu'il est 13 fois plus lent que le programme optimisé, vous verrez la raison pour laquelle à chaque "pause", avec une probabilité de 12/13 = 92%.

C’est une application de cette technique .

Answer 5

parce que lorsque vous écrivez le vecteur arr (10000); vous créez un objet, appelez ses fonctions ... quand et ce sera plus lent que lorsque vous créez int arr [10000];

Answer 6

Dans vos exemples, le tableau se trouve sur la pile. L'accès aux données du tableau implique l'accès aux données de la pile. C'est rapide.

D'autre part, tant que le vector est sur la pile, les données d'un std :: vector sont allouées ailleurs (par défaut, elles sont allouées sur le tas). via std :: allocator ). L'accès aux données du vecteur implique l'accès aux données du segment de mémoire. C'est beaucoup plus lent que d'accéder aux données de la pile.

Vous obtenez quelque chose pour la pénalité de performance, cependant. std :: vector peut être développé, contrairement à un tableau standard. En outre, la taille d'un std :: vector ne doit pas nécessairement être une constante de temps de compilation, contrairement à la taille d'un tableau de la pile. Un tableau alloué par tas (via opérateur new [] ) ne doit pas nécessairement être une constante à la compilation. Si vous comparez un tableau alloué à un tas avec un std :: vector , vous constaterez que les performances sont beaucoup plus proches.

int* arr = new int[10000];
for (int i = 0; i < 10000; i++)
{
   for (int j = 0; j < 10000; j++)
   {
       arr[j] = j;
   }
}

delete[] arr; // std::vector does this for you