C'è qualche vantaggio nella manipolazione dei bit in stile c rispetto a std :: bitset?

Question

C'è qualche vantaggio nella manipolazione dei bit in stile c rispetto a std :: bitset?

#1 da (10 voti)
#2 da (2 voti)

14

Lavoro quasi esclusivamente in C ++ 11/14 e di solito rabbrividisco quando vedo un codice come questo:

std::int64_t mArray;
mArray |= someMask << 1;

Questo è solo un esempio; Sto parlando di manipolazione bit-in generale. In C ++, c'è davvero qualche punto? Quanto sopra è distorto dalla mente e soggetto a errori, mentre l'utilizzo di std::bitset ti consente di:

più facilmente modifica la dimensione della std::bitset secondo necessità regolando un parametro del modello e lasciando che l'implementazione si occupi del resto, e
dedica meno tempo a capire cosa sta succedendo (e probabilmente commettendo errori) e scrivi std::bitset in modo simile a std::array o ad altri contenitori di dati.

La mia domanda è; c'è qualche ragione non per usare std::bitset su tipi primitivi, se non per retrocompatibilità?

c++ c++11 bitwise-operators

posta quant 18.05.2015 - 02:42

fonte

2 risposte

2

Questo di certo non si applica in tutti i casi, ma a volte un algoritmo potrebbe dipendere dall'efficienza del bit-twing in stile C per fornire miglioramenti significativi delle prestazioni. Il primo esempio che mi viene in mente è l'uso di bitboard , codifiche di numeri intelligenti di posizioni di gioco da tavolo, per accelerare gli scacchi motori e simili. Qui, la dimensione fissa dei tipi interi non è un problema, dal momento che le scacchiere sono sempre 8 * 8 comunque.

Per un semplice esempio, considera la seguente funzione (tratta da questa risposta di Ben Jackson ) che verifica un Connect Four posizione per la vittoria:

// return whether newboard includes a win
bool haswon2(uint64_t newboard)
{
    uint64_t y = newboard & (newboard >> 6);
    uint64_t z = newboard & (newboard >> 7);
    uint64_t w = newboard & (newboard >> 8);
    uint64_t x = newboard & (newboard >> 1);
    return (y & (y >> 2 * 6)) | // check \ diagonal
           (z & (z >> 2 * 7)) | // check horizontal -
           (w & (w >> 2 * 8)) | // check / diagonal
           (x & (x >> 2));      // check vertical |
}

risposta data 18.05.2015 - 06:03

fonte

Leggi altre domande sui tag c++ c++11 bitwise-operators

Quanto sono efficaci le sfide di programmazione nel processo di reclutamento? [chiuso] Dove si inserisce jQuery con framework come JavaScriptMVC, BackboneJS, SproutCore e Knockout?

score 10 · Accepted Answer

Da un punto di vista logico (non tecnico), non c'è alcun vantaggio.

Qualsiasi semplice codice C / C ++ può essere inserito all'interno di un "costrutto di libreria" adatto. Dopo tale involucro, la questione di "se questo è più vantaggioso di quello" diventa una questione discutibile.

Da un punto di vista della velocità, C / C ++ dovrebbe consentire al costrutto della libreria di generare codice che sia efficiente quanto il codice semplice che avvolge. Questo è tuttavia soggetto a:

Inlining della funzione
Controllo in fase di compilazione ed eliminazione del controllo runtime non necessario
Eliminazione del codice morto
Molte altre ottimizzazioni del codice ...

Usando questo tipo di argomento non tecnico, qualsiasi "funzione mancante" potrebbe essere aggiunta da chiunque, e quindi non viene considerata come uno svantaggio.

Tuttavia, i requisiti e le limitazioni incorporati non possono essere superati con codice aggiuntivo. Sotto, sostengo che la dimensione di std::bitset è una costante in fase di compilazione, e quindi, sebbene non venga considerata come uno svantaggio, è comunque qualcosa che influenza la scelta dell'utente.

Da un punto di vista estetico (leggibilità, facilità di manutenzione, ecc.), c'è una differenza.

Tuttavia, non è evidente che il codice std::bitset vince immediatamente sul codice C semplice. Bisogna guardare pezzi di codice più grandi (e non alcuni esempi di giocattoli) per dire se l'uso di std::bitset ha migliorato la qualità umana del codice sorgente.

La velocità di manipolazione dei bit dipende dallo stile di codifica. Lo stile di codifica influisce sulla manipolazione del bit C / C ++ ed è ugualmente applicabile anche a std::bitset , come spiegato di seguito.

Se si scrive codice che usa operator [] per leggere e scrivere un bit alla volta, si dovrà farlo più volte se ci sono più di un bit da manipolare. Lo stesso si può dire del codice in stile C.

Tuttavia, bitset ha anche altri operatori, come operator &= , operator <<= , ecc., che opera sull'intera larghezza del set di bit. Poiché i macchinari sottostanti possono spesso operare su 32 bit, 64 bit e talvolta 128 bit (con SIMD) alla volta (nello stesso numero di cicli della CPU), codice progettato per sfruttare le operazioni multi-bit può essere più veloce del codice di manipolazione di bit "loopy".

L'idea generale è chiamata SWAR (SIMD in un registro) , ed è un sottoargomento con manipolazioni di bit.

Alcuni produttori di C ++ potrebbero implementare bitset tra 64-bit e 128-bit con SIMD. Alcuni venditori potrebbero non farlo (ma potrebbero eventualmente farlo). Se è necessario sapere che cosa sta facendo la libreria del fornitore C ++, l'unico modo è osservare il disassemblaggio.

Per quanto riguarda se std::bitset ha limitazioni, posso dare due esempi.

La dimensione di std::bitset deve essere nota al momento della compilazione. Per creare una serie di bit con dimensioni scelte dinamicamente, sarà necessario utilizzare std::vector<bool> .
L'attuale specifica C ++ per std::bitset non fornisce un modo per estrarre una porzione consecutiva di N bit da una più grande bitset di M bit.

Il primo è fondamentale, il che significa che per le persone che necessitano di bitset di dimensioni dinamiche, devono scegliere altre opzioni.

Il secondo può essere superato, perché si può scrivere alcuni tipi di adattatori per eseguire l'attività, anche se lo standard bitset non è estensibile.

Esistono alcuni tipi di operazioni SWAR avanzate che non vengono fornite out-of-the-box da std::bitset . Si può leggere su queste operazioni su questo sito web su permutazioni di bit . Come al solito, è possibile implementarli da soli, operando sopra std::bitset .

Per quanto riguarda la discussione sul rendimento.

Una ammonizione: molte persone chiedono perché (qualcosa) dalla libreria standard è molto più lento di un semplice codice in stile C. Non vorrei ripetere la conoscenza prerequisita di microbenchmarking qui, ma ho solo questo consiglio: assicurati di fare benchmark in "modalità di rilascio" (con le ottimizzazioni abilitate) e assicurati che il codice non sia elimina (eliminazione del codice morto) o essere issato da un loop (motion code invariante ciclo) .

Poiché in generale non possiamo dire se qualcuno (su internet) stia facendo correttamente i microbenchmark, l'unico modo per ottenere una conclusione attendibile è fare i nostri microbenchmark e documentare i dettagli, e sottoporli a revisione e critica pubblica . Non fa male ri-fare microbenchmarks che altri hanno fatto prima.