Problème de performance pour vector::size() dans une boucle en C++.

Question

Dans le code suivant :

std::vector<int> var;
for (int i = 0; i < var.size(); i++);

Est-ce que le size() La fonction membre est appelée pour chaque itération de la boucle, ou une seule fois ?

Answer 1

Mais cela pourrait être fait de cette façon (à condition que cette boucle ne vise qu'à lire/écrire sans réellement changer la taille d'un vecteur) :

for(vector<int>::size_type i=0, size = var.size(); i < size; ++i) 
{
//do something
}

Dans la boucle ci-dessus, vous n'avez qu'un seul appel à size, indépendamment du fait que size soit inlined ou non.

Answer 2

Comme d'autres l'ont dit

• la sémantique doit être comme si elle était appelée à chaque fois
• il est probablement inlined, et est probablement une fonction simple

sur lequel

• un optimiseur suffisamment intelligent peut être en mesure de déduire qu'il s'agit d'un invariant de boucle sans effets secondaires et de l'élider entièrement (ceci est plus facile si le code est inlined, mais peut être possible même s'il ne l'est pas). si le compilateur effectue une optimisation globale)

Answer 3

I pensez à que si le compilateur peut déduire de manière concluante que la variable var n'est pas modifié à l'intérieur du "corps de la boucle".

for(int i=0; i< var.size();i++) { 
    // loop body
}

alors ce qui précède peut être transposé en quelque chose d'équivalent à

const size_t var_size = var.size();
for( int i = 0; i < var_size; i++ ) { 
    // loop body
}

Cependant, je n'en suis pas absolument sûr, alors les commentaires sont les bienvenus :)

Aussi,

• Dans la plupart des situations, le size() est inlined, donc le problème ne justifie pas de s'inquiéter.

• Cette préoccupation est peut-être également applicable à la end() qui est toujours utilisé pour les boucles basées sur des itérateurs, c'est-à-dire it != container.end()

• Veuillez envisager d'utiliser size_t o vector<int>::size_type pour le type de i (Voir le commentaire de Steve Jessop ci-dessous).

Answer 4

Comme d'autres l'ont dit, le compilateur décide de ce qu'il faut faire avec le code réellement écrit. Le chiffre clé est qu'il est appelé à chaque fois. Mais si vous voulez obtenir un gain de performance, il est préférable d'écrire votre code en tenant compte de certaines considérations. Votre cas en est un, il y en a d'autres aussi, comme la différence entre ces deux morceaux de code :

for (int i = 0 ; i < n ; ++i)
{
   for ( int j = 0 ; j < n ; ++j)
       printf("%d ", arr[i][j]);
   printf("\n");
}
for (int j = 0 ; j < n ; ++j)
{
   for ( int i = 0 ; i < n ; ++i)
       printf("%d ", arr[i][j]);
   printf("\n");
}

La différence est que la première ne modifiera pas trop la page de RAM par référence, mais l'autre épuisera votre cache, votre TLB et autres.

Aussi en ligne ne sera pas d'une grande aide ! car l'ordre de la fonction appelante restera n(taille du vecteur) fois. Cela peut cependant aider à certains endroits, mais le mieux est de réécrire votre code.

Mais ! si vous voulez laisser un compilateur faire ses optimisations sur votre code, ne mettez JAMAIS de volatile, comme ceci :

for(volatile int i = 0 ; i < 100; ++i)

Il empêche le compilateur d'optimiser. Si vous avez besoin d'un autre indice pour les performances, utilisez register au lieu de volatile.

for(register int i = 0 ; i < 100; ++i)

Le compilateur essaiera de ne pas déplacer i des registres du CPU vers la RAM. Il n'est pas sûr de pouvoir le faire, mais il fera de son mieux ;)

Answer 5

Je l'ai testé pour 900 000 itérations Il prend 43 secondes pour la taille pré-calculée et 42 secondes pour l'utilisation de l'appel size().

Si vous avez la garantie que la taille du vecteur ne change pas dans la boucle, il vaut mieux utiliser la taille pré-calculée, sinon il n'y a pas de choix et il faut utiliser size().

#include <iostream>
#include <vector>

using namespace std;

int main() {
vector<int> v;

for (int i = 0; i < 30000; i++)
        v.push_back(i);

const size_t v_size = v.size();
for(int i = 0; i < v_size; i++)
        for(int j = 0; j < v_size; j++)
                cout << "";

//for(int i = 0; i < v.size(); i++)
//      for(int j = 0; j < v.size(); j++)
//              cout << "";
}