爲什麼積累比一個簡單的循環更快？

Question

我正在測試算法，並遇到這種奇怪的行爲，當std::accumulate比簡單的for週期更快。

看着生成的彙編程序我並不太聰明:-)看起來for循環是針對MMX指令進行優化的，而累加則擴展成循環。

這是代碼。該行爲與-O3優化級別，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

當您通過0積累，你這是它積累使用的int，而不是很長很長。

如果你的代碼你手動循環就是這樣，這將是相同的：

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

，或者您可以撥打積累這樣的：

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

Answer 2

我使用Visual Studio的一些不同的結果，2012

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

請注意，原來的std::accumulate代碼不等於t到for循環，因爲std::accumulate的第三個參數是一個int 0值。它使用int執行求和，僅在最後將結果存儲在long long中。將第三個參數更改爲0LL將強制算法使用累加器long long，並在以下時間生成結果。

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

由於最終導致int適合我改變suma和std::accumulate回只用int值。此更改後，MSVC 2012編譯器能夠自動矢量化for循環，並導致以下時間。

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

Answer 3

固定累積問題後，別人指出我既Visual Studio 2008中& 2010年和累積測試確實比手動更快地循環。

看着反彙編，我看到一些額外的迭代器檢查正在手動循環中完成，所以我切換到只是一個原始數組，以消除它。

這裏是我結束了測試：

#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 

使用此代碼，手動環輕鬆擊敗累加。最大的區別是編譯器將手動循環展開4次，否則生成的代碼幾乎完全相同。