Come può std :: bitset essere più veloce di std :: vector ?

Secondo questa risposta, il poster si aspetta che uno std::bitset di dimensione 100k bit sia più veloce di un file std::vector quando si interrogano singoli bit. Come può essere ansible?

Come potrebbero anche differire in modo significativo nella loro implementazione, se std::bitset apparenza consente dimensioni arbitrarie proprio come std::vector ?

Le misurazioni su Visual Studio 2010 mostrano che std::bitset non è generalmente più veloce di std::vector . Qual è la ragione esatta per questo non posso dire – solo che il bitset è implementato in modo significativamente diverso dalla specializzazione completa di std :: vector.

std :: bitset memorizza il suo contenuto completo nell’object tramite a

 template class bitset ..... _Ty _Array[_Words + 1]; // the set of bits }; 

array e che rende il set di bit grande inadatto per essere messo in pila – che non è un argomento di prestazioni di per sé.

vector non soffre del problema dello stack, e testando con una dimensione di 1e6 e 1e7 sembra che sulla mia scatola qui interrogare i valori in un ciclo sia in realtà 2x più veloce con un vettore.

Bene. Immagino che i soliti avvertimenti sui tempi si applichino e YMMV, ma qui è il codice di prova che ho usato se qualcuno si preoccupasse di provare se stesso:

L’output sulla mia scatola è:

 1 vector loop with a size of 10000000 and 10 iterations*n: 11187 ms bitset<10000000> loop with 10 iterations*n: 22719 ms 101250010 Press any key to continue . . . 

BitMap.cpp

 #include "stdafx.h" #include "BitMap.h" using namespace std; // Global var to prevent optimizer from messing things up volatile size_t ext; volatile clock_t t1; volatile clock_t t2; double delta1; double delta2; int main(int argc, _TCHAR* argv[]) { ext = 1; printf("%d\n", ext); vb_t *const vec = new vb_t(bssz); bs_t *const bits = new bs_t(); // must put large bitset on heap const int iter = 10; delta1=0; delta2=0; for(int o=0; o<5; ++o) { t1 = clock(); for(int i=0; i!=5; ++i) bs_loop(iter, *vec); t2 = clock(); delta1 += t2-t1; t1 = clock(); for(int i=0; i!=5; ++i) bs_loop(iter, *bits); t2 = clock(); delta2 += t2-t1; } delta1 /= CLOCKS_PER_SEC; delta2 /= CLOCKS_PER_SEC; delta1 *= 1000; delta2 *= 1000; cout << "vector loop with a size of " << bssz << " and " << iter << " iterations*n: " << delta1 << " ms\n"; cout << "bitset<" << bssz << "> loop with " << iter << " iterations*n: " << delta2 << " ms\n"; printf("%d\n", ext); delete vec; delete bits; return 0; } 

BitMap.h

 #pragma once #include  #include  extern volatile size_t ext; const size_t bssz = size_t(1e7); // 1e7 ca 10m using namespace std; // Test code, using here is OK. typedef vector vb_t; typedef bitset bs_t; template void bs_loop(const int iterations, COLL const& v); 

bs_loop.cpp

 #include "stdafx.h" #include "BitMap.h" template void bs_loop(const int iterations, COLL const& v) { ext = sizeof(COLL); for(size_t i=0; i!=iterations; ++i) { ++ext; for(size_t j=0, e=v.size(); j!=e; ++j) { if(v[j]) { --ext; } else { ++ext; } } } } template void bs_loop(const int iterations, vb_t const& v); template void bs_loop(const int iterations, bs_t const& v); 

Riga di comando del compilatore:

 /Zi /nologo /W3 /WX- /O2 /Oi /Oy- /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Gm- /EHsc /GS /Gy /fp:precise /Zc:wchar_t /Zc:forScope /Yu"StdAfx.h" /Fp"Release\BitMap.pch" /Fa"Release\" /Fo"Release\" /Fd"Release\vc100.pdb" /Gd /analyze- /errorReport:queue 

annota / O2 e mancante / GL (non intero prg opt).

Beh, visto che sono il ragazzo su cui stai basando questa domanda, ecco da dove ho preso l’idea :

“… impacchetta i bool e li memorizza come bit individuali (all’interno, diciamo, chars) nella sua rappresentazione interna.Una conseguenza è che non può semplicemente restituire un bool normale e dal suo operatore [] o dai suoi iteratori dereferenziati [2 ], invece, deve giocare con una class di “proxy” helper che è simile a bool ma non è sicuramente un bool. Sfortunatamente, ciò significa anche che l’accesso a un vector è più lento, perché dobbiamo occuparci di proxy invece di puntatori e riferimenti diretti.

In conclusione: se ti preoccupi di più della velocità rispetto alle dimensioni, non dovresti usare std::vector . Invece, dovresti modificare questa ottimizzazione usando invece un file std::vector o simili, il che è sfortunato ma è comunque il meglio che puoi fare. ”

Oppure, come ho raccomandato, se conosci la dimensione più grande che otterrà il tuo set, usa std::bitset .

Onestamente penso che bitset sia meglio usare nello stack e non sullo heap. inoltre i due non sono in conflitto tra loro perché una soluzione elegante può essere qualcosa del genere:

 vector< bitset<64> > v(100000) //or whatever... 

può essere interessante un test rispetto a questo due invece:

 vector v1(1000000) //8 bits to manage them manually vector< bitset<8> > v2(1000000) //8 bits managed by bitset 

Inoltre, solo per aggiungere alle risposte qui e ricordare come il compilatore dipenda anche MOLTO nelle prestazioni, ecco un semplice test fatto con:

  • VS2012
  • mingw / g ++ 4.7.0
  • g ++ 4.8.2 su Ubuntu

(ma tutti questi test sono un po ‘complicati e forse ci danno solo l’idea generale approssimativa per un confronto diretto. Profilare il progetto è l’unica cosa alla fine da fare.)

  • VS2012 compilato in Release (versione predefinita fornita).
  • g ++ compilato con -O2
  • g ++ codificato con -O2 -std = c ++ 11

NOTA:

con taglia 10 ^ 7:

  • VS2012 arresto anomalo in fase di esecuzione. (Quindi posso presumere di avere una gestione della memoria diversa da g ++)
  • g ++ va bene
  • g ++ 11 ha un problema con test2 () tempo di reporting = 0, ho stampato alcuni valori solo per triggersre l’esecuzione del codice. (Suppongo che sia un ottimizzazione del compilatore).

Ho incluso anche il tempo di overhead del costruttore e del distruttore degli oggetti.

qui il semplice codice di prova:

 #include  #include  #include  #include  using namespace std; #define SIZE1 1000000000 //10e9 //#define SIZE2 10000000 //10e7 VS2012 crash at runtime, g++ OK #define SIZE2 1000000 //10e6 void test1() { register bool j; clock_t t1,t2; cout.precision(10); t1=clock(); vector *v = new vector(SIZE1); for(register long int i=0; i *b = new bitset(); for(register long int i=0; i v(SIZE2); for(register int k=0; k b; for(register int k=0; k 

Uscita VS2012:

 vector speed = 3.105000019 (3105,0) bitset speed = 10.44400024 (13551,3107) vector speed = 3.987999916 (17542,13554) v[1], v[2] 0, 1 bitset speed = 9.772999763 (27318,17545) b[1], b[2] 0, 1 

uscita mingw / g ++ -O2:

 vector speed = 1.519 (1520,1) bitset speed = 1.647 (3168,1521) vector speed = 1.383999944 (4554,3170) v[1], v[2] 0, 1 bitset speed = 1.610000014 (6166,4556) b[1], b[2] 0, 1 

output mingw / g ++ -O2 -std = c ++ 11:

 vector speed = 1.528 (1529,1) bitset speed = 1.685 (3215,1530) vector speed = 1.409999967 (4626,3216) v[1], v[2] 0, 1 bitset speed = 1.763000011 (6392,4629) b[1], b[2] 0, 1 

g ++ 4.8.2 output -O2:

 vector speed = 1.561391 (1564139,2748) bitset speed = 1.681818 (3246051,1564233) vector speed = 1.487877011 (4733975,3246098) v[1], v[2] 0, 1 bitset speed = 1.685297012 (6419328,4734031) b[1], b[2] 0, 1 

g ++ 4.8.2 output -O2 -std = c ++ 11:

 vector speed = 1.561391 (1564139,2748) bitset speed = 1.681818 (3246051,1564233) vector speed = 1.487877011 (4733975,3246098) v[1], v[2] 0, 1 bitset speed = 1.685297012 (6419328,4734031) b[1], b[2] 0, 1 

CONCLUSIONE:

Come un vettore idea approssimativa sembra più veloce per questi casi d'uso.

Non eseguo istanze multiple e media i risultati, ma più o meno i valori sono sempre gli stessi.

nota su VS : Penso che usi un diverso meccanismo di gestione della memoria rispetto a gcc e per questi casi d'uso sembra più lento nel codice generato.

il vettore accede ai suoi elementi con iteratori, che non possono essere un semplice typedef per bool *, che lo rende più lento del bitset, che non fornisce iteratori. Un’altra cosa che lo rende veloce è che la sua dimensione è nota in fase di compilazione e quindi non ha alcuna allocazione con la nuova, che è più lenta dell’assegnazione dello stack. Solo pensieri casuali

Ecco il mio punto di riferimento non scientifico di accesso / inserimento di 3 miliardi di elementi da / in bitset<> e vector di dimensioni 100K, 1M e 5M. Il compilatore è GCC 4.8.2 su macchina Linux a 64 bit (Core i7):

Con ottimizzazione (flag del compilatore: -O2 -std=c++11 ):

 [[email protected] bitset_vs_vector]$ ./bitset_vs_vector bitset<100000> (3 billion accesses/inserts): 132.424 ms vector(100000) (3 billion accesses/inserts): 270.577 ms bitset<1000000> (3 billion accesses/inserts): 67.752 ms vector(1000000) (3 billion accesses/inserts): 268.193 ms bitset<5000000> (3 billion accesses/inserts): 67.426 ms vector(5000000) (3 billion accesses/inserts): 267.566 ms 

Senza ottimizzazione (flag del compilatore: -std=c++11 ):

 [[email protected] bitset_vs_vector]$ make g++ -std=c++11 -o bitset_vs_vector *.cpp [[email protected] bitset_vs_vector]$ ./bitset_vs_vector bitset<100000> (3 billion accesses/inserts): 1900.13 ms vector(100000) (3 billion accesses/inserts): 1784.76 ms bitset<1000000> (3 billion accesses/inserts): 1825.09 ms vector(1000000) (3 billion accesses/inserts): 1768.03 ms bitset<5000000> (3 billion accesses/inserts): 1846.73 ms vector(5000000) (3 billion accesses/inserts): 1763.48 ms 

Quindi, in queste condizioni, sembra che il bitset sia più veloce del vettore quando il codice è ottimizzato, mentre il vettore in realtà viene fuori da un margine (molto) piccolo quando non lo è.

Detto questo, se il tuo codice è critico in termini di tempo, dovresti probabilmente eseguire benchmark da solo, poiché sospetto che questi numeri siano altamente compilatori / specifici per l’ambiente.

Codice di riferimento:

 #include  #include  #include  #include  #include  // Performs N access/insert on container. template void access_and_insert(T &container, int N) { const std::size_t size = container.size(); for (int i = 0; i < N; ++i) { bool v = container[i % size]; container[i % size] = true; } } // Measure the time in milliseconds required to call f. double measure(std::function f) { clock_t start = std::clock(); f(); return 1000.0 * (std::clock() - start)/CLOCKS_PER_SEC; } int main (void) { // Benchmark with 100K elements. std::bitset<100000> bitset100K; std::vector vector100K(100000); std::cout << "bitset<100000> (3 billion accesses/inserts): "; std::cout << measure([&]() { access_and_insert(bitset100K, 3E7); }) << " ms " << std::endl; std::cout << "vector(100000) (3 billion accesses/inserts): "; std::cout << measure([&]() { access_and_insert(vector100K, 3E7); }) << " ms" << std::endl; std::cout << std::endl; // Benchmark with 1M elements. std::bitset<1000000> bitset1M; std::vector vector1M(1000000); std::cout << "bitset<1000000> (3 billion accesses/inserts): "; std::cout << measure([&]() { access_and_insert(bitset1M, 3E7); }) << " ms " << std::endl; std::cout << "vector(1000000) (3 billion accesses/inserts): "; std::cout << measure([&]() { access_and_insert(vector1M, 3E7); }) << " ms" << std::endl; std::cout << std::endl; // Benchmark with 5M elements. std::bitset<5000000> bitset5M; std::vector vector5M(5000000); std::cout << "bitset<5000000> (3 billion accesses/inserts): "; std::cout << measure([&]() { access_and_insert(bitset5M, 3E7); }) << " ms " << std::endl; std::cout << "vector(5000000) (3 billion accesses/inserts): "; std::cout << measure([&]() { access_and_insert(vector5M, 3E7); }) << " ms" << std::endl; return 0; } 

Inoltre, si noti che un vector è una specializzazione del modello vettoriale e viene implementato in modo molto diverso da come si potrebbe pensare.