Quale implementazione di bitset dovrei usare per le massime prestazioni?

Question

Attualmente sto cercando di implementare vari algoritmi in un compilatore Just In Time (JIT). Molti degli algoritmi operano su bitmap, più comunemente noti come bitset.

In C++ esistono vari modi per implementare un set di bit. Come vero sviluppatore C++, preferirei usare qualcosa da STL. L'aspetto più importante è la performance. Non ho necessariamente bisogno di un set di bit ridimensionabile in modo dinamico.

Come vedo, ci sono tre opzioni possibili.

I. Un'opzione sarebbe quella di utilizzare std::vector<bool>, che è stato ottimizzato per lo spazio. Ciò indicherebbe anche che i dati non devono essere contigui in memoria. Immagino che questo potrebbe ridurre le prestazioni. D'altra parte, avere un bit per ogni valore bool potrebbe migliorare la velocità dato che è molto cache friendly.

II. Un'altra opzione sarebbe quella di utilizzare invece un std::vector<char>. Garantisce che i dati siano contigui in memoria ed è più facile accedere ai singoli elementi. Tuttavia, sembra strano usare questa opzione poiché non è destinata a essere un bitset.

III. La terza opzione sarebbe quella di utilizzare l'attuale std::bitset. Il fatto che non sia ridimensionabile dinamicamente non ha importanza.

Quale scegliere per le massime prestazioni?

Answer 1

Il modo migliore è limitarlo, perché ogni situazione è diversa.

Non vorrei usare std::vector<bool>. L'ho provato una volta e l'esibizione è stata orribile. Potrei migliorare le prestazioni della mia applicazione semplicemente usando std::vector<char>.

non ho davvero confrontare con std::bitsetstd::vector<char>, ma se lo spazio non è un problema nel tuo caso, vorrei andare per std::vector<char>. Usa 8 volte più spazio di un set di bit, ma dal momento che non deve fare operazioni di bit per ottenere o impostare i dati, dovrebbe essere più veloce.

Ovviamente se è necessario memorizzare molti dati nel bitset/vettore, potrebbe essere utile utilizzare il set di bit, poiché ciò si adatterebbe nella cache del processore.

Il modo più semplice è utilizzare un typedef e nascondere l'implementazione. Sia bitset che vector supportano l'operatore [], quindi dovrebbe essere facile passare da un'implementazione all'altra.

Answer 2

Potreste anche essere interessato a questo documento (un po 'datato): http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

Answer 3

ho risposto a una domanda simile di recente in questo forum. Raccomando il mio BITSCAN library. Ho appena rilasciato la versione 1.0. BITSCAN è specificamente progettato per operazioni di scansione veloce bit.

classe A bitboard avvolge diverse implementazioni per le operazioni tipiche come BsF, BSR o popcount di parole a 64 bit (alias bitboard). Classi BitBoardN, BBIntrin e BBSentinel estendono la scansione dei bit alle stringhe di bit. Una stringa di bit in BITSCAN è una matrice di bitboard. La classe base wrapper per una stringa di bit è BitBoardN. BBIntrin estende BitBoardN utilizzando l'intrinseco del compilatore Windows su 64 bit.BBIntrin è reso portatile a POSIX utilizzando le funzioni equivalenti di asm appropriate.

Ho usato BITSCAN per implementare un numero di solutori efficienti per problemi combinatori NP nel dominio del grafico. In genere la matrice di adiacenza del grafico e gli insiemi di vertici sono codificati come stringhe di bit e i calcoli tipici vengono eseguiti utilizzando le maschere di bit. Il codice per oggetti grafici bitencoded semplici è disponibile in GRAPH. Sono inoltre disponibili esempi su come utilizzare BITSCAN e GRAPH.

Un confronto tra BITSCAN e le implementazioni tipiche in STL (BitSet) e BOOST (dynamic_bitset) si possono trovare qui: http://blog.biicode.com/bitscan-efficiency-at-glance/