¿Hay alguna ventaja en la manipulación de bits estilo C sobre std :: bitset?

14

Trabajo casi exclusivamente en C ++ 11/14, y generalmente me estremezco cuando veo un código como este:

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

Esto es solo un ejemplo; Estoy hablando de manipulación de bits en general. En C ++, ¿hay realmente algún punto? Lo anterior es alucinante y propenso a errores, mientras que usar std::bitset le permite:

  1. modifique más fácilmente el tamaño de std::bitset según sea necesario ajustando un parámetro de plantilla y dejando que la implementación se encargue del resto, y
  2. dedique menos tiempo a descubrir qué está pasando (y posiblemente cometer errores) y escriba std::bitset de una manera similar a std::array u otros contenedores de datos.

Mi pregunta es; ¿hay alguna razón no para usar std::bitset sobre los tipos primitivos, excepto para compatibilidad con versiones anteriores?

    
pregunta quant 18.05.2015 - 02:42

2 respuestas

10

Desde un punto de vista lógico (no técnico), no hay ninguna ventaja.

Cualquier código plano de C / C ++ puede incluirse en una "construcción de biblioteca" adecuada. Después de tal ajuste, la cuestión de "si esto es más ventajoso que eso" se convierte en una cuestión discutible.

Desde un punto de vista de velocidad, C / C ++ debería permitir que la construcción de la biblioteca genere código que sea tan eficiente como el código simple que envuelve. Sin embargo, esto está sujeto a:

  • función en línea
  • Verificación en tiempo de compilación y eliminación de la verificación innecesaria en tiempo de ejecución
  • Eliminación de código muerto
  • Muchas otras optimizaciones de código ...

Al usar este tipo de argumento no técnico, cualquier "función faltante" puede ser agregada por cualquier persona y, por lo tanto, no se considera una desventaja.

Sin embargo, los requisitos y limitaciones incorporados no se pueden superar con un código adicional. A continuación, sostengo que el tamaño de std::bitset es una constante de tiempo de compilación y, por lo tanto, aunque no se considera una desventaja, sigue siendo algo que afecta la elección del usuario.

Desde un punto de vista estético (legibilidad, facilidad de mantenimiento, etc.), hay una diferencia.

Sin embargo, no es aparente que el código std::bitset gane inmediatamente sobre el código C simple. Uno tiene que mirar piezas de código más grandes (y no una muestra de juguete) para decir si el uso de std::bitset ha mejorado la calidad humana del código fuente.

La velocidad de la manipulación de bits depende del estilo de codificación. El estilo de codificación afecta tanto a la manipulación de bits C / C ++, y es igualmente aplicable a std::bitset como se explica a continuación.

Si uno escribe un código que usa el operator [] para leer y escribir un bit a la vez, uno tendrá que hacer esto varias veces si hay más de un bit a manipular. Lo mismo se puede decir del código de estilo C.

Sin embargo, bitset también tiene otros operadores, como operator &= , operator <<= , etc., que opera en todo el ancho del conjunto de bits. Debido a que la maquinaria subyacente a menudo puede operar con 32 bits, 64 bits y, a veces, 128 bits (con SIMD) a la vez (en el mismo número de ciclos de CPU), código diseñado para aprovechar tales operaciones de múltiples bits. puede ser más rápido que el código de manipulación de bits "flojo".

La idea general se llama SWAR (SIMD dentro de un registro) , y es un subtema bajo manipulación de bits.

Algunos proveedores de C ++ pueden implementar bitset entre 64 bits y 128 bits con SIMD. Algunos proveedores podrían no (pero eventualmente podrían hacerlo). Si hay una necesidad de saber qué está haciendo la biblioteca del proveedor de C ++, la única forma es mirar el desensamblaje.

En cuanto a si std::bitset tiene limitaciones, puedo dar dos ejemplos.

  1. El tamaño de std::bitset debe ser conocido en el momento de la compilación. Para hacer una matriz de bits con el tamaño elegido dinámicamente, uno tendrá que usar std::vector<bool> .
  2. La especificación actual de C ++ para std::bitset no proporciona una manera de extraer una porción consecutiva de N bits de un bitset más de M bits.

El primero es fundamental, lo que significa que para las personas que necesitan conjuntos de bits de tamaño dinámico, deben elegir otras opciones.

El segundo se puede superar, porque se puede escribir algún tipo de adaptadores para realizar la tarea, incluso si el estándar bitset no es extensible.

Hay ciertos tipos de operaciones SWAR avanzadas que no se proporcionan de manera inmediata desde std::bitset . Se podría leer acerca de estas operaciones en este sitio web sobre permutaciones de bits . Como es habitual, se pueden implementar por su cuenta, operando sobre std::bitset .

Con respecto a la discusión sobre el rendimiento.

Una advertencia: muchas personas preguntan por qué (algo) de la biblioteca estándar es mucho más lento que un código de C simple. No repetiría el conocimiento previo de microbenchmarking aquí, pero solo tengo este consejo: asegúrese de realizar una prueba en "modo de lanzamiento" (con optimizaciones habilitadas), y asegúrese de que el código no sea eliminated (eliminación del código muerto) o siendo sacado de un bucle (movimiento de código invariante de bucle) .

Ya que en general no podemos saber si alguien (en Internet) estaba haciendo las microbiogramas correctamente, la única forma en que podemos obtener una conclusión confiable es hacer nuestras propias microbiogramas y documentar los detalles, y enviarlos a revisión y crítica públicas. . No está de más volver a hacer marcas de microbado que otros han hecho antes.

    
respondido por el rwong 18.05.2015 - 06:54
2

Esto ciertamente no se aplica en todos los casos, pero en ocasiones un algoritmo puede depender de la eficiencia de la manipulación de bits al estilo C para proporcionar ganancias significativas de rendimiento. El primer ejemplo que me viene a la mente es el uso de bitboards , codificaciones enteras inteligentes de las posiciones de juego de mesa, para acelerar el ajedrez Motores y similares. Aquí, el tamaño fijo de los tipos de enteros no es un problema, ya que los tableros de ajedrez son siempre 8 * 8 de todos modos.

Para un ejemplo simple, considere la siguiente función (tomada de esta respuesta de Ben Jackson ) que prueba un Connect Four posición para la victoria:

// 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 |
}
    
respondido por el David Zhang 18.05.2015 - 06:03

Lea otras preguntas en las etiquetas