Gli algoritmi STL sono ottimizzati per la velocità?

Question

Stavo testando la velocità del loop di diversi modi su un vettore std ::. Nel seguente codice, ritengo 5 modi per calcolare la somma di tutti gli elementi di un vettore di N = 10000000 elementi:

1. utilizzando iteratori
2. usando indici interi
3. usando indici interi, svolgimento di un fattore 2
4. usando indici interi, srotolando di un fattore 4
5. utilizzando std :: accumulare

Il co de è compilato con g ++ per Windows, la riga di comando utilizzato per compilare è:

g++ -std=c++11 -O3 loop.cpp -o loop.exe 

Ho eseguito il codice di 4 volte, misurando il tempo di ciascun metodo, ottengo i seguenti risultati (tempo in microsecondi, max e min sono indicati):

• iteratori: 8002 - 8007
• indici Int: 8004 - 9003
• srotolare 2: 6004 - 7005
• unroll 4: 4001 - 5004
• accumulano: 8005 - 9007

Quello che questi esperimenti sembrano indicare è:

1. Looping con iteratori vs indici interi non fa molta differenza, almeno con piena ottimizzazione.

2. apertolo il ciclo paga off

3. Sorprendentemente, lo STL :: accumulano dà la performance peggiore.

Mentre le conclusioni 1 e 2 erano previste, il numero 3 è piuttosto sorprendente. Non tutti i libri dicono di usare gli algoritmi STL invece di scrivere loop da solo?

Sto commettendo errori nel modo in cui sto misurando il tempo o nel modo in cui interpreto i risultati? Avete uno scenario diverso nel caso in cui proviate il codice indicato di seguito?

#include <iostream> 
#include <chrono> 
#include <vector> 
#include <numeric> 

using namespace std; 
using namespace std::chrono; 



int main() 
{ 
    const int N = 10000000; 
    vector<int> v(N); 
    for (int i = 0; i<N; ++i) 
     v[i] = i; 

    //looping with iterators 
    { 
     high_resolution_clock::time_point t1 = high_resolution_clock::now(); 

     long long int sum = 0; 
     for (auto it = v.begin(); it != v.end(); ++it) 
      sum+=*it; 

     high_resolution_clock::time_point t2 = high_resolution_clock::now(); 

     auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count(); 

     cout << duration << "microseconds output = " << sum << " (Iterators)\n"; 
    } 

    //looping with integers 
    { 
     high_resolution_clock::time_point t1 = high_resolution_clock::now(); 

     long long int sum = 0; 
     for (int i = 0; i<N; ++i) 
      sum+=v[i]; 

     high_resolution_clock::time_point t2 = high_resolution_clock::now(); 

     auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count(); 

     cout << duration << "microseconds output = " << sum << " (integer index)\n"; 
    } 

    //looping with integers (UNROLL 2) 
    { 
     high_resolution_clock::time_point t1 = high_resolution_clock::now(); 

     long long int sum = 0; 
     for (int i = 0; i<N; i+=2) 
      sum+=v[i]+v[i+1]; 

     high_resolution_clock::time_point t2 = high_resolution_clock::now(); 

     auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count(); 

     cout << duration << "microseconds output = " << sum << " (integer index, UNROLL 2)\n"; 
    } 

    //looping with integers (UNROLL 4) 
    { 
     high_resolution_clock::time_point t1 = high_resolution_clock::now(); 

     long long int sum = 0; 
     for (int i = 0; i<N; i+=4) 
      sum+=v[i]+v[i+1]+v[i+2]+v[i+3]; 

     high_resolution_clock::time_point t2 = high_resolution_clock::now(); 

     auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count(); 

     cout << duration << "microseconds output = " << sum << " (integer index, UNROLL 4)\n"; 
    } 

    //using std::accumulate 
    { 
     high_resolution_clock::time_point t1 = high_resolution_clock::now(); 

     long long int sum = accumulate(v.begin(), v.end(), static_cast<long long int>(0)); 

     high_resolution_clock::time_point t2 = high_resolution_clock::now(); 

     auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count(); 

     cout << duration << "microseconds output = " << sum << " (std::accumulate)\n"; 
    } 
    return 0; 
} 

Answer 1

La ragione per usare gli algoritmi della libreria standard è non per ottenere una migliore efficienza, è quello di permettere di pensare ad un più alto livello di astrazione.

Mentre potrebbero esserci alcuni casi in cui l'algoritmo sarà più veloce del proprio codice laminato a mano, non è quello per cui sono lì. Uno dei grandi vantaggi del C++ è che ti permette di ignorare le librerie integrate quando hai esigenze specifiche. Se il tuo benchmarking ha dimostrato che la libreria standard sta causando un rallentamento critico, sei libero di esplorare alternative classiche come lo srotolamento del loop. Per la maggior parte degli scopi non sarà mai necessario.

Con ciò detto, un algoritmo di libreria standard ben scritto non sarà mai più orribilmente lento dell'implementazione diretta, a meno che non si stia approfittando della conoscenza delle specifiche dei dati.

Answer 2

Oltre a Mar, penso che lo STL non sia più veloce della propria implementazione nella maggior parte dei casi, poiché è una soluzione generale per una serie di domande correlate ma non per una specifica, quindi è probabile che STL richieda più fattori presi in considerazione rispetto a quelli di cui hai realmente bisogno, quindi meno efficienti. Ma c'è un'eccezione: stl :: sort utilizza l'ottimizzazione sottile (forse un misto di algoritmo di ordinamento diverso) in modo che funzioni più rapidamente delle normali implementazioni.