Optimisation lors de la mise en boucle de deux vecteurs de longueurs différentes

Question

#include <vector> 
#include <iostream> 
#include <cmath> 
#include <iomanip> 
#include <sys/time.h> 

using namespace std; 

int main() 
{ 
    struct timeval timeStart, 
        timeEnd; 

Créez des vecteurs de 0 et 1 aléatoires. Nous comparerons le temps pour les résumer.

int n1 = 450000000; // size of vector v1 
    int n2 = 500000000; // size of vector v2 
    int i; 
    vector<bool> v1(n1); 
    vector<bool> v2(n2); 

    for (i=0; i < n1 ; i++) 
    { 
    v1[i] = rand() % 2; 
    } 
    for (i=0; i < n2 ; i++) 
    { 
    v2[i] = rand() % 2; 
    } 

Première technique à additionner. Additionner ces vecteurs avec deux boucles (indépendantes) complètes

int sum1 = 0; 
    int sum2 = 0; 
    gettimeofday(&timeStart, NULL); 
    for (i=0; i < n1 ; i++) 
    { 
     sum1 += v1[i]; 
    } 
    for (i=0; i < n2 ; i++) 
    { 
     sum2 += v2[i]; 
    } 
    gettimeofday(&timeEnd, NULL); 
    cout << "Two complete loops took " << ((timeEnd.tv_sec - timeStart.tv_sec) * 1000000 + timeEnd.tv_usec - timeStart.tv_usec) << " us" << endl; 

Deuxième technique. Somme ces vecteurs avec une boucle complète et une boucle partielle

sum1 = 0; 
    sum2 = 0; 
    gettimeofday(&timeStart, NULL); 
    for (i=0; i < n1 ; i++) 
    { 
     sum1 += v1[i]; 
     sum2 += v2[i]; 
    } 
    for (i=n1; i < n2 ; i++) 
    { 
     sum2 += v2[i]; 
    } 
    gettimeofday(&timeEnd, NULL); 
    cout << "With a reduced second loop, it took " << ((timeEnd.tv_sec - timeStart.tv_sec) * 1000000 + timeEnd.tv_usec - timeStart.tv_usec) << " us" << endl; 

return 0; 
} 

je reçois systématiquement une sortie du genre

Two complete loops took 13291126 us 
With a reduced second loop, it took 12758827 us 

Je me serais attendu soit en même temps (si le compilateur optimisé la première solution que Je l'ai excepté) ou je m'attendais à ce que les deux boucles complètes prennent considérablement plus de temps (et pas seulement 5% -10% de plus) que la seconde boucle partielle.

Que fait probablement le compilateur ici? Devrais-je envisager d'utiliser des boucles partielles dans le futur lorsque je fais une boucle entre deux vecteurs de longueurs différentes?

---

Pour votre information, je compilé avec g++ -std=c++11 -o test test.cpp, avec la version

g++ --version 
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 
Apple LLVM version 7.0.2 (clang-700.1.81) 
Target: x86_64-apple-darwin15.3.0 
Thread model: posix 

Answer 1

A essayer d'expliquer les similitudes dans les temps d'exécution:

Lorsque vous faites ceci:

for (i=0; i < n1 ; i++) 
{ 
    sum1 += v1[i]; 
} 
for (i=0; i < n2 ; i++) 
{ 
    sum2 += v2[i]; 
} 

vous effectuez 2 boucles donc plus d'instructions, mais vous lisez la mémoire contiguë dans les deux cas s: les caches fonctionnent de manière optimale (ce qui prend le plus de temps dans les ordinateurs «modernes» est plus d'accès mémoire/échec de cache que l'exécution de code)

BTW Je doute que le compilateur puisse regrouper ces 2 boucles.

Le deuxième cas prend moins de nombre d'instructions de contrôle, mais la mémoire n'est pas lue de manière contiguë.

Egalement: optimiseur utilisé pour "dérouler" les boucles, réduisant ainsi l'effet négatif de l'instruction de contrôle.

Donc ce que vous gagnez d'un côté, vous perdez de l'autre côté. Ces optimisations doivent être étalonnées, et vous pourriez avoir de plus grandes variations en fonction de l'architecture du processeur.