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

En théorie il est appelé à chaque fois, depuis une boucle for :

for(initialization; condition; increment)
    body;

est étendu à quelque chose comme

{
    initialization;
    while(condition)
    {
        body;
        increment;
    }
}

(remarquez les accolades, car l'initialisation est déjà dans une portée interne)

En pratique si le compilateur comprend qu'une partie de votre condition est invariante pendant toute la durée de la boucle et que le compilateur ne peut pas la modifier. il n'a pas d'effets secondaires il peut être assez intelligent pour le déplacer. Cela se fait couramment avec strlen et des choses comme ça (que le compilateur connaît bien) dans des boucles où son argument n'est pas écrit.

Il faut cependant noter que cette dernière condition n'est pas toujours triviale à prouver ; en général, c'est facile si le conteneur est local à la fonction et n'est jamais passé à des fonctions externes ; si le conteneur n'est pas local (par exemple, il est passé par référence - même s'il est const ) et que le corps de la boucle contient des appels à d'autres fonctions, le compilateur doit souvent supposer que ces fonctions peuvent l'altérer, bloquant ainsi la remontée du calcul de la longueur.

Faire cette optimisation à la main est valable si vous savez qu'une partie de votre condition est "coûteuse" à évaluer (et une telle condition ne l'est généralement pas, puisqu'elle se résume habituellement à une soustraction de pointeur, qui est presque sûrement inlined).

---

Edit : comme d'autres l'ont dit, en général avec les conteneurs, il est préférable d'utiliser des itérateurs, mais pour les vector ce n'est pas si important, car l'accès aléatoire aux éléments par l'intermédiaire des operator[] est garanti en O(1) ; en fait, avec les vecteurs, il s'agit généralement d'une somme de pointeurs (base du vecteur + index) et d'une déréférence par rapport au pointeur. incrémenter (élément précédent+1) et déréférencement des itérateurs. Puisque l'adresse cible est toujours la même, je ne pense pas que vous puissiez gagner quelque chose des itérateurs en termes de localité du cache (et même si c'est le cas, si vous ne parcourez pas de grands tableaux dans des boucles serrées, vous ne devriez même pas remarquer ce genre d'améliorations).

Pour les listes et autres conteneurs, en revanche, l'utilisation d'itérateurs au lieu de l'accès aléatoire peut être vraiment important, puisque l'utilisation de l'accès aléatoire peut signifier parcourir chaque fois la liste, alors que l'incrémentation d'un itérateur est juste une déréférence de pointeur.

Answer 2

Le site size() est appelée à chaque fois, mais ce serait une très mauvaise implémentation de ne pas la mettre en ligne, et une implémentation étrange où ce ne serait pas un simple accès à une donnée fixe ou une soustraction de deux pointeurs.
Quoi qu'il en soit, vous ne devriez pas vous préoccuper de telles futilités tant que vous n'avez pas profilé votre application et constaté qu'il s'agit d'un goulot d'étranglement.

Cependant, ce que vous devrait faire attention est :

1. Le type correct pour l'index d'un vecteur est std::vector<T>::size_type .
2. Il existe des types (certains itérateurs, par exemple) pour lesquels l'option i++ pourrait être plus lent que ++i .

Par conséquent, la boucle devrait être :

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

Answer 3

Elle est "appelée" à chaque fois, mais je mets "appelée" entre guillemets parce qu'il s'agit probablement d'un simple appel de méthode en ligne, et vous n'avez donc pas à vous soucier de ses performances.

Pourquoi ne pas utiliser vector<int>::iterator à la place ?

Answer 4

Le problème avec votre question est qu'elle n'a aucun sens. Un compilateur C++ traduit un code source en un programme binaire. L'exigence est que le programme résultant doit préserver effets observables du code selon les règles de la norme C++. Ce code :

for (int i = 0; i < var.size(); i++); 

n'a tout simplement pas d'effet observable. De plus, il n'interagit en aucune façon avec le code environnant, et le compilateur peut l'optimiser complètement, c'est-à-dire ne générer aucun assemblage correspondant.

Pour que votre question ait un sens, vous devez préciser ce qui se passe à l'intérieur de la boucle . Le problème avec

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

est que la réponse dépend beaucoup de ce que ... l'est en réalité. Je crois que @MatteoItalia a fourni une très bonne réponse, je voudrais juste ajouter une description de quelques expériences que j'ai faites. Considérons le code suivant :

int g(std::vector<int>&, size_t);

int f(std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

Premièrement, même si appeler var.size() sera presque à 100% sûr d'être inlined avec des optimisations activées, et cet inlining se traduit typiquement par une soustraction de deux pointeurs, ce qui apporte toujours dans la boucle une certaine surcharge. Si un compilateur n'est pas capable de prouver que la taille du vecteur est préservée (ce qui, en général, est très difficile ou même infaisable, comme dans notre cas), alors vous vous retrouverez avec des charge y sous (et, éventuellement, équipe ) instructions. L'assemblage généré de la boucle avec GCC 9.2, -O3 et x64 était :

.L3:
    mov     rsi, rbx
    mov     rdi, rbp
    add     rbx, 1
    call    g(std::vector<int, std::allocator<int> >&, unsigned long)
    add     r12d, eax
    mov     rax, QWORD PTR [rbp+8] // loads a pointer
    sub     rax, QWORD PTR [rbp+0] // subtracts another poniter
    sar     rax, 2                 // result * sizeof(int) => size()
    cmp     rbx, rax
    jb      .L3

Si nous réécrivons le code comme suit :

int g(std::vector<int>&, size_t);

int f(std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0, e = v.size(); i < e; i++)
      res += g(v, i);
   return res;
}

alors, l'assemblage généré est plus simple (et, par conséquent, plus rapide) :

.L3:
    mov     rsi, rbx
    mov     rdi, r13
    add     rbx, 1
    call    g(std::vector<int, std::allocator<int> >&, unsigned long)
    add     r12d, eax
    cmp     rbx, rbp
    jne     .L3

La valeur de la taille du vecteur est simplement conservée dans un registre ( rbp ).

J'ai même essayé une autre version où le vecteur est marqué comme étant const :

int g(const std::vector<int>&, size_t);

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

Étonnamment, même lorsque v.size() ne peut pas changer ici, l'assemblage généré était le même que dans le premier cas (avec des modifications supplémentaires de l'assemblage). mov , sub y sar instructions).

La démo en direct est ici .

De plus, quand j'ai changé la boucle en :

for (size_t i = 0; i < v.size(); i++)
   res += v[i];

alors, il n'y avait pas d'évaluation de v.size() (soustraction de pointeurs) dans la boucle au niveau de l'assemblage. GCC a pu "voir" ici, que le corps de la boucle ne modifie en rien la taille.

Answer 5

Elle doit être appelée à chaque fois parce que size() peut retourner une valeur différente à chaque fois.

Par conséquent, il n'y a pas de grand choix, il doit simplement en être ainsi.