Perché si accumula più velocemente di un semplice ciclo?

Question

Stavo testando gli algoritmi e mi sono imbattuto in questo strano comportamento, quando std::accumulate è più veloce di un semplice ciclo for.

Guardando l'assemblatore generato non sono molto più saggio :-) Sembra che il ciclo for sia ottimizzato in istruzioni MMX, mentre si accumula si espande in un ciclo.

Questo è il codice. Il comportamento si manifesta con -O3 livello di ottimizzazione, gcc 4.7.1

#include <vector>                                                                
#include <chrono>                                                                
#include <iostream>                                                                
#include <random>                                                                
#include <algorithm>                                                               
using namespace std;                                                               

int main()                                                                  
{                                                                    
    const size_t vsize = 100*1000*1000;                                                           

    vector<int> x; 
    x.reserve(vsize); 

    mt19937 rng; 
    rng.seed(chrono::system_clock::to_time_t(chrono::system_clock::now())); 

    uniform_int_distribution<uint32_t> dist(0,10); 

    for (size_t i = 0; i < vsize; i++) 
    { 
     x.push_back(dist(rng)); 
    } 

    long long tmp = 0; 
    for (size_t i = 0; i < vsize; i++) 
    { 
     tmp += x[i]; 
    } 

    cout << "dry run " << tmp << endl; 

    auto start = chrono::high_resolution_clock::now(); 
    long long suma = accumulate(x.begin(),x.end(),0); 
    auto end = chrono::high_resolution_clock::now(); 

    cout << "Accumulate runtime " << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << " - " << suma << endl; 

    start = chrono::high_resolution_clock::now(); 
    suma = 0; 
    for (size_t i = 0; i < vsize; i++) 
    { 
     suma += x[i]; 
    } 
    end = chrono::high_resolution_clock::now(); 

    cout << "Manual sum runtime " << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << " - " << suma << endl; 

    return 0; 
} 

Answer 1

Quando si passa il 0 ad accumularsi, si stanno facendo che si accumulano con un int invece di un long long.

Se si codifica il ciclo manuale come questo, sarà equivalente:

int sumb = 0; 
for (size_t i = 0; i < vsize; i++) 
{ 
    sumb += x[i]; 
} 
suma = sumb; 

o si può chiamare accumulare in questo modo:

long long suma = accumulate(x.begin(),x.end(),0LL); 

Answer 2

Ho alcuni risultati diversi che utilizzano Visual Studio 2012

// original code 
Accumulate runtime 93600 ms 
Manual sum runtime 140400 ms 

Si noti che il codice originale std::accumulate non è equivalente t al ciclo for poiché il terzo parametro su std::accumulate è un valore 0 int. Esegue la somma utilizzando uno int e solo alla fine memorizza il risultato in un long long. La modifica del terzo parametro su 0LL impone all'algoritmo di utilizzare un accumulatore long long e genera i seguenti orari.

// change std::accumulate initial value -> 0LL 
Accumulate runtime 265200 ms 
Manual sum runtime 140400 ms 

Poiché il risultato finale si inserisce in un int I cambiato suma e std::accumulate ritorna utilizzando solo int valori. Dopo questa modifica, il compilatore MSVC 2012 è stato in grado di creare automaticamente il ciclo il ciclo for e ha generato i seguenti orari.

// change suma from long long to int 
Accumulate runtime 93600 ms 
Manual sum runtime 46800 ms 

Answer 3

Dopo fissare il problema si accumulano altri notato ho provato sia con Visual Studio 2008 & 2010 e si accumulano era effettivamente più veloce del ciclo manuale.

Guardando allo smontaggio ho visto alcuni controlli iteratori aggiuntivi eseguiti nel ciclo manuale, quindi sono passato a un array raw per eliminarlo.

Ecco quello che ho finito il test con:

#include <Windows.h> 
#include <iostream> 
#include <numeric> 
#include <stdlib.h> 

int main() 
{ 
    const size_t vsize = 100*1000*1000;                                                           
    int* x = new int[vsize]; 

    for (size_t i = 0; i < vsize; i++) x[i] = rand() % 1000; 

    LARGE_INTEGER start,stop; 
    long long suma = 0, sumb = 0, timea = 0, timeb = 0; 

    QueryPerformanceCounter(&start); 
    suma = std::accumulate(x, x + vsize, 0LL); 
    QueryPerformanceCounter(&stop); 
    timea = stop.QuadPart - start.QuadPart; 

    QueryPerformanceCounter(&start); 
    for (size_t i = 0; i < vsize; ++i) sumb += x[i]; 
    QueryPerformanceCounter(&stop); 
    timeb = stop.QuadPart - start.QuadPart; 

    std::cout << "Accumulate: " << timea << " - " << suma << std::endl; 
    std::cout << "  Loop: " << timeb << " - " << sumb << std::endl; 

    delete [] x; 
    return 0; 
} 

Accumulate: 633942 - 49678806711 
     Loop: 292642 - 49678806711 

Utilizzando questo codice, il ciclo manuale batte facilmente accumularsi. La grande differenza è che il compilatore ha srotolato il ciclo manuale 4 volte, altrimenti il ​​codice generato è quasi identico.