¿Qué implementación de conjunto de bits debería usar para obtener el máximo rendimiento?

Question

Actualmente estoy tratando de implementar varios algoritmos en un compilador Just In Time (JIT). Muchos de los algoritmos operan en bitmaps, más comúnmente conocidos como bitsets.

En C++ hay varias formas de implementar un conjunto de bits. Como verdadero desarrollador de C++, preferiría usar algo de STL. El aspecto más importante es el rendimiento. No necesariamente necesito un conjunto de bits dinámicamente redimensionable.

Según lo veo, hay tres opciones posibles.

I. Una opción sería usar std::vector<bool>, que ha sido optimizado para el espacio. Esto también indicaría que los datos no tienen que estar contiguos en la memoria. Supongo que esto podría disminuir el rendimiento. Por otro lado, tener un bit por cada valor de bool podría mejorar la velocidad, ya que es muy compatible con la caché.

II. Otra opción sería usar un std::vector<char> en su lugar. Garantiza que los datos estén contiguos en la memoria y que sea más fácil acceder a elementos individuales. Sin embargo, se siente extraño utilizar esta opción, ya que no está destinado a ser un conjunto de bits.

III. La tercera opción sería usar el std::bitset real. El hecho de que no sea redimensionable dinámicamente no importa.

¿Cuál debo elegir para obtener el máximo rendimiento?

Answer 1

La mejor manera es simplemente compararlo, porque cada situación es diferente.

No utilizaría std::vector<bool>. Lo intenté una vez y la actuación fue horrible. Podría mejorar el rendimiento de mi aplicación simplemente usando std::vector<char>.

Realmente no comparé std::bitset con std::vector<char>, pero si el espacio no es un problema en su caso, yo iría por std::vector<char>. Utiliza 8 veces más espacio que un conjunto de bits, pero como no tiene que hacer operaciones de bits para obtener o establecer los datos, debería ser más rápido.

Por supuesto, si necesita almacenar muchos datos en el conjunto de bits/vector, entonces podría ser beneficioso utilizar el conjunto de bits, porque eso cabría en la memoria caché del procesador.

La manera más fácil es usar un typedef y ocultar la implementación. Tanto el conjunto de bits y el vector apoyan al operador [], por lo que debería ser fácil cambiar una implementación por la otra.

Answer 2

Usted también puede estar interesado en este documento (un poco anticuado): http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

Answer 3

Me respondió una pregunta similar hace poco en este foro. Recomiendo mi BITSCAN library. Acabo de lanzar la versión 1.0. BITSCAN está específicamente diseñado para operaciones de escaneo rápido de bits.

clase A BitBoard se ajusta un número de diferentes implementaciones para operaciones típicas tales como BSF, BSR o popcount para las palabras de 64 bits (también conocido como bitboards). Las clases BitBoardN, BBIntrin y BBSentinel amplían el escaneo de bits a cadenas de bits. Una cadena de bits en BITSCAN es una matriz de tablas de bits. La clase de contenedor base para una cadena de bits es BitBoardN. BBIntrin amplía BitBoardN utilizando los intrínsecos del compilador de Windows sobre 64 bitboards.BBIntrin se hace portátil a POSIX utilizando las funciones equivalentes de asm apropiadas.

He utilizado BITSCAN para implementar una cantidad de solucionadores eficientes para problemas combinatorios NP en el dominio del gráfico. Normalmente, la matriz de adyacencia del gráfico, así como los conjuntos de vértices, se codifican como cadenas de bits y los cálculos típicos se realizan usando máscaras de bits. El código para objetos de gráfico bitencoded simples está disponible en GRAPH. Ejemplos de cómo usar BITSCAN y GRAPH también están disponibles.

Una comparación entre BITSCAN y las implementaciones típicas en STL (BitSet) y BOOST (dynamic_bitset) se pueden encontrar aquí: http://blog.biicode.com/bitscan-efficiency-at-glance/