C++ 11 vector <bool> problema di prestazioni (con esempio di codice)

Question

Ho notato che il vettore è molto più lento dell'array bool quando esegue il codice seguente.

int main() 
{ 
    int count = 0; 
    int n = 1500000; 
    // slower with c++ vector<bool> 
    /*vector<bool> isPrime; 
    isPrime.reserve(n); 
    isPrime.assign(n, true); 
    */ 
    // faster with bool array 
    bool* isPrime = new bool[n]; 

    for (int i = 0; i < n; ++i) 
     isPrime[i] = true; 


    for (int i = 2; i< n; ++i) { 
     if (isPrime[i]) 
      count++; 
     for (int j =2; i*j < n; ++j) 
      isPrime[i*j] = false; 
    } 

    cout << count << endl; 
    return 0; 
} 

C'è qualche modo che io possa fare per rendere vector<bool> più veloce? Btw, entrambi std::vector::push_back e std::vector::emplace_back sono anche più lenti di std::vector::assign.

Answer 1

vector<bool> può avere una specializzazione di modello e può essere implementato utilizzando l'array di bit per risparmiare spazio. Estrarre e salvare un bit e convertirlo da/a bool potrebbe causare il calo delle prestazioni che si sta osservando. Se si utilizza std::vector::push_back, si ridimensiona il vettore che causerà prestazioni ancora peggiori. Il prossimo killer delle prestazioni potrebbe essere assign (Peggiore complessità: lineare del primo argomento), utilizzare invece operator [] (Complessità: costante).

D'altra parte, bool [] è garantito come array di bool.

E si dovrebbe ridimensionare a n anziché n-1 per evitare un comportamento non definito.

Answer 2

std::vector<bool> può avere vari problemi di prestazioni (ad esempio, dare un'occhiata a https://isocpp.org/blog/2012/11/on-vectorbool).

In generale è possibile:

• uso std::vector<std::uint8_t> invece di std::vector<bool> (dare una prova di std::valarray<bool> anche).

  Ciò richiede più memoria ed è meno cache-friendly ma non c'è un sovraccarico (sotto forma di manipolazione dei bit) per accedere a un singolo valore, quindi ci sono situazioni in cui funziona meglio (dopotutto è proprio come la matrice di bool ma senza il fastidio di gestione della memoria)

• uso std::bitset se si sa al momento della compilazione quanto sia grande l'array booleano sta per essere (o se si può almeno stabilire un ragionevole limite superiore)
• se Boost è un'opzione prova boost::dynamic_bitset (la dimensione può essere specificata in fase di esecuzione)

---

Ma per ottimizzazioni di velocità si deve mettere alla prova ...

Con il vostro esempio specifico posso confermare una differenza di prestazioni solo quando le ottimizzazioni sono disattivati ​​(naturalmente questo non è la strada da percorrere).

Alcuni test con g v4.8.3 ++ e clangore v3.4.5 ++ su un sistema Intel Xeon (-O3 livello di ottimizzazione) danno un quadro diverso:

    time (ms) 
       G++  CLANG++ 
array of bool 3103  3010 
vector<bool>  2835  2420 // not bad! 
vector<char>  3136  3031 // same as array of bool 
bitset   2742  2388 // marginally better 

(tempo trascorso per 100 corse del codice nella risposta)

std::vector<bool> non sembra così male (codice sorgente here).

Answer 3

vector<bool>can può essere ad alte prestazioni, ma non è necessario essere. Per vector<bool> per essere efficiente, ha bisogno di operare su molti bool alla volta (ad esempio isPrime.assign(n, true)), e l'implementatore ha dovuto mettere amorevole cura in esso. L'indicizzazione di singoli bool in un vector<bool> è lenta.

Ecco un cercatore di primo che ho scritto un po 'indietro con vector<bool> e clang + libC++ (la libC++ parte è importante):

#include <algorithm> 
#include <chrono> 
#include <iostream> 
#include <vector> 

std::vector<bool> 
init_primes() 
{ 
    std::vector<bool> primes(0x80000000, true); 
    primes[0] = false; 
    primes[1] = false; 
    const auto pb = primes.begin(); 
    const auto pe = primes.end(); 
    const auto sz = primes.size(); 
    size_t i = 2; 
    while (true) 
    { 
     size_t j = i*i; 
     if (j >= sz) 
      break; 
     do 
     { 
      primes[j] = false; 
      j += i; 
     } while (j < sz); 
     i = std::find(pb + (i+1), pe, true) - pb; 
    } 
    return primes; 
} 

int 
main() 
{ 
    using namespace std::chrono; 
    using dsec = duration<double>; 
    auto t0 = steady_clock::now(); 
    auto p = init_primes(); 
    auto t1 = steady_clock::now(); 
    std::cout << dsec(t1-t0).count() << "\n"; 
} 

Esegue per me in circa 28s (-O3). Quando lo cambio per restituire un vector<char>, invece, il tempo di esecuzione sale a a circa 44 secondi.

Se si esegue questo utilizzando un altro std :: lib, probabilmente non si vedrà questa tendenza. Sugli algoritmi libC++ come std::find sono stati ottimizzati per cercare una parola di bit alla volta, anziché bit alla volta.

Vedere http://howardhinnant.github.io/onvectorbool.html per ulteriori dettagli su quali algoritmi std potrebbero essere ottimizzati dal fornitore.