Warum akkumuliert sich schneller als ein einfacher Zyklus?

Question

Ich habe Algorithmen getestet und in dieses seltsame Verhalten geraten, wenn std::accumulate schneller ist als ein einfacher for Zyklus.

Blick auf den generierten Assembler Ich bin nicht viel klüger :-) Es scheint, dass der for Zyklus in MMX-Anweisungen optimiert ist, während akkumuliert in eine Schleife erweitert.

Dies ist der Code. Das Verhalten manifestiert sich mit -O3 Optimierungsstufe, 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

Wenn Sie die 0 zu akkumulieren passieren, Sie machen es sich ansammeln, anstatt eine lange lange ein int verwenden.

Wenn Sie Ihre Hand-Schleife wie dieser Code, wird es äquivalent sein:

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

oder rufen Sie wie folgt ansammeln kann:

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

Answer 2

Ich habe einige unterschiedliche Ergebnisse von Visual Studio 2012 mit

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

Beachten Sie, dass der ursprüngliche Code std::accumulate nicht äquivalent ist t an die for Schleife, weil der dritte Parameter std::accumulate ist ein int 0 Wert. Es führt die Summierung unter Verwendung eines int durch und speichert das Ergebnis erst am Ende in einem long long. Das Ändern des dritten Parameters auf 0LL zwingt den Algorithmus, einen Akkumulator long long zu verwenden, und führt zu den folgenden Zeiten.

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

Da das Endergebnis in einem int passt änderte ich suma und std::accumulate wieder nur int Werte zu verwenden. Nach dieser Änderung konnte der MSVC 2012-Compiler diefor-Schleife automatisch vektorisieren und führte in den folgenden Zeiten.

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

Answer 3

Nach der accumulate Ausgabe anderen Festsetzung bemerkte mich mit Visual Studio 2008 & 2010 und accumulate war in der Tat schneller als die manuelle Schleife getestet.

Mit Blick auf die Disassembly sah ich einige zusätzliche Iterator Überprüfung in der manuellen Schleife getan, so dass ich nur zu einem rohen Array um es zu beseitigen.

Hier ist, was ich am Ende Prüfung mit:

#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 

diesen Code verwenden, die manuelle Schleife schlägt leicht akkumulieren. Der große Unterschied ist, dass der Compiler die manuelle Schleife 4 mal entrollt, ansonsten ist der generierte Code fast identisch.