Czy algorytmy STL są zoptymalizowane pod kątem szybkości?

Question

Testowałem prędkość różnych sposobów pętli na std :: vector. W poniższym kodu, pod 5 sposoby obliczania sumy wszystkich elementów wektora n = 10000000 elementów:

1. wykorzystaniem iteratorami
2. pomocą indeksów całkowite
3. za pomocą indeksów całkowitych, rozwijając poprzez: a czynnik 2
4. pomocą indeksów całkowitych, rozwijając przez współczynnik 4
5. pomocą std :: gromadzić

The Co de jest skompilowany z g ++ dla Windows, wiersz poleceń używany do kompilacji jest:

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

wpadłem kod 4 razy, mierząc czas każdej metody, mam następujące wyniki (czas w mikrosekundach, max i min podano)

• Iterators: 8002 - 8007
• indeksy Int: 8004 - 9003
• odwijać 2: 6004 - 7005
• Unroll 4: 4001 - 5004
• gromadzić: 8005 - 9007

Co te eksperymenty wydają się wskazywać na to:

1. Pętla z iteratorów vs indeksów całkowitych nie robi dużej różnicy, przynajmniej z pełną optymalizacją.

2. rozwinięciem pętli opłaca

3. Niespodziewanie, stl :: Akumuluj daje gorszą wydajność.

Podczas gdy wnioski 1 i 2 były spodziewane, liczba 3 jest dość zaskakująca. Czy nie wszystkie książki mówią, że używają algorytmów STL zamiast pisać pętle sam?

Czy popełniam jakiś błąd w sposobie mierzenia czasu lub sposobu, w jaki interpretuję wyniki? Czy macie inny scenariusz na wypadek wypróbowania kodu podanego poniżej?

#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

Powodem użyciu standardowych algorytmów biblioteki jest nie aby uzyskać lepszą wydajność, jest to, co pozwala myśleć na wyższym poziomie abstrakcji.

Chociaż mogą istnieć przypadki, w których algorytm będzie szybszy niż własny, ręczny kod, nie jest to tym, za co są. Jedną z wielkich zalet języka C++ jest to, że pozwala ominąć wbudowane biblioteki, gdy masz konkretne potrzeby. Jeśli testy porównawcze wykazały, że standardowa biblioteka powoduje krytyczne spowolnienie, możesz swobodnie eksplorować klasyczne alternatywy, takie jak rozwijanie pętli. Do większości celów, które nigdy nie będą konieczne.

Dobrze napisany algorytm biblioteki standardowej nigdy nie będzie strasznie wolniejszy niż twoja prosta implementacja, chyba że korzystasz z wiedzy o specyfice twoich danych.

Answer 2

Oprócz Mar, uważam, że STL nie jest szybszy niż twoja własna implementacja w większości przypadków, ponieważ jest to ogólne rozwiązanie dla serii powiązanych pytań, ale nie dla konkretnego, więc jest prawdopodobne, że STL bierze bierze pod uwagę więcej czynników, niż naprawdę potrzeba, a więc mniej wydajnych. Ale istnieje wyjątek: stl :: sort używa subtelnej optymalizacji (być może algorytmu mieszanego o innym sortowaniu), aby działało szybciej niż zwykle.