Neden döngü için basit bir hızdan daha hızlı birikir?

Question

std::accumulate basit bir for döngüsünden daha hızlı olduğunda, algoritmaları test ediyordum ve bu tuhaf davranışla karşılaşıyordum.

Oluşturulan assembler'a bakıyorum çok fazla zeki değilim :-) for döngüsünün MMX yönergelerine göre en iyi duruma getirildiği göründüğünde, birikir bir döngüde genişler.

Bu koddur. davranış -O3 optimizasyon seviyesine, gcc ile tezahür

#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

sen uzun uzun bir yerine bir int kullanarak birikir yapıyoruz birikmeye 0 geçmesi 4.7.1.

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

veya böyle birikir çağırabilirsiniz: Eğer böyle manuel döngü kod varsa

, bu eşdeğer olacak

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

Answer 2

Visual Studio kullanarak bazı farklı sonuçlar var 2012

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

Orijinal std::accumulate kodunun eşdeğer olmadığını unutmayın. t std::accumulate için üçüncü parametre int 0 değeri olduğundan for döngüsüne t. Bir int kullanarak toplama yapar ve sadece sonuçta bir long long sonucunu saklar. Üçüncü parametrenin 0LL'a değiştirilmesi, algoritmayı bir long long akümülatör kullanacak şekilde kuvvetlendirir ve aşağıdaki sürelerle sonuçlanır. Nihai sonuç, bir int sığar yana

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

Sadece int değerleri kullanarak geri suma ve std::accumulate değişti. Bu değişiklikten sonra MSVC 2012 derleyicisi for döngüsünü otomatik hale getirdi ve aşağıdaki zamanlarda sonuçlandı. biriktiği sorunu diğerlerini düzelttikten sonra

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

Answer 3

daha hızlı manuel döngü daha gerçekten de Visual Studio 2008 & 2010 ve biriktiği hem test kaydetti.

Demontajı incelemek Elle döngüde yapılan bazı ek yineleyici kontrollerini gördüm, bu yüzden elimden çıkarmak için ham bir diziye geçtim.

Burada ile test sona erdi budur: Bu kodu kullanarak

#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 

, manuel döngü kolayca birikir yener. Büyük fark, derleyicinin manuel döngüyü 4 kez açmasıdır, aksi halde üretilen kod hemen hemen aynıdır.