c++ - programacion - ¿Cuál es la forma más eficiente de contar bits establecidos en una posición o menos?

manual de programacion android pdf (5)

Given std::bitset<64> bits con cualquier cantidad de bits configurados y una posición de bit X (0-63)

¿Cuál es la forma más eficiente de contar bits en la posición X o inferior o devolver 0 si el bit en X no está configurado?

Nota: Si el bit está configurado, el retorno siempre será al menos 1

La fuerza bruta es muy lenta:

int countupto(std::bitset<64> bits, int X) { if (!bits[X]) return 0; int total=1; for (int i=0; i < X; ++i) { total+=bits[i]; } return total; }

El count() methof de bitset le dará la popcount de todos los bits, pero el conjunto de bits no admite rangos

Nota: Este no es un duplicado de ¿Cómo contar la cantidad de bits configurados en un entero de 32 bits? como eso pregunta sobre todos los bits, no el rango de 0 a X

Es fácil convertir entre un bit y una máscara para los bits debajo de él, así que algo así debería funcionar:

int popcnt(bitset<64> bs, int x) { // Early out when bit not set if (!bs[x]) return 0; // Otherwise, make mask from `x`, mask and count bits return (bs & bitset<64>((1UL << x) - 1)).count() + 1; }

La suposición aquí es que bitset::count se implementa de manera eficiente (usando los intrínsecos popcnt o una alternativa eficiente); esto no está garantizado, pero la gente de STL tiende a optimizar este tipo de cosas.

Este C ++ obtiene g ++ para emitir un ASM x86 muy bueno (explorador del compilador Godbolt) . También espero que se compile eficientemente en otras arquitecturas de 64 bits (si hay una cuenta de HW para std::bitset::count para usar, de lo contrario esa será siempre la parte lenta):

#include <bitset> int popcount_subset(std::bitset<64> A, int pos) { int high_bits_to_eliminate = 63 - pos; A <<= (high_bits_to_eliminate & 63); // puts A[pos] at A[63]. return (A[63]? ~0ULL : 0) & A.count(); // most efficient way: great code with gcc and clang // see the godbolt link for some #ifdefs with other ways to do the check, like // return A[BSET_SIZE-1] ? A.count() : 0; }

Esto probablemente no sea óptimo en las arquitecturas de 32 bits, así que compare otras alternativas si necesita hacer una compilación de 32 bits.

Esto funcionará para otros tamaños de conjuntos de bits , siempre que haga algo sobre los 63 s codificados y cambie la máscara & 63 para el recuento de cambios en una verificación de rango más general. Para un rendimiento óptimo con bitsets de tamaño extraño, realice una función de plantilla con una especialización para size <= register width de size <= register width de la máquina de destino. En ese caso, extraiga el conjunto de bits a un tipo unsigned del ancho apropiado, y cambie a la parte superior del registro en lugar de la parte superior del conjunto de bits.

Es de esperar que esto también genere código ideal para bitset<32> , pero no lo hace del todo. gcc / clang aún usa registros de 64 bits en x86-64.

Para bitsets grandes, cambiar todo será más lento que simplemente contar las palabras debajo de la que contiene pos , y usar esto en esa palabra. (Aquí es donde realmente brilla una cuenta vectorizada en x86 si puede asumir SSSE3 pero no el popcnt hardware popcnt insn, o para objetivos de 32 bits. AVX2 256bit pshufb es la forma más rápida de hacer popcounts masivos, pero sin AVX2 creo que popcnt 64 popcnt es bastante cerca de una implementación de pshufb 128 bits. Consulte los comentarios para obtener más información).

Si tiene una matriz de elementos de 64 bits y desea contar bits por debajo de una determinada posición en cada uno por separado, entonces definitivamente debe usar SIMD . Las partes de desplazamiento de este algoritmo se vectorizan, no solo la parte popcnt. Utilice psadbw contra un registro con cero todos los bytes de suma horizontal en fragmentos de 64 bits después de un pshufb basado en pshufb que produce recuentos para los bits en cada byte por separado. SSE / AVX no tiene desplazamiento aritmético a la derecha de 64 bits, pero puede usar una técnica diferente para combinar el bit alto de cada elemento.

Cómo se me ocurrió esto:

Las instrucciones de asm que quiere que el compilador muestre:

eliminar los bits no deseados del valor de 64 bits
prueba el más alto de los bits deseados.
recuento.
return 0 o popcount, dependiendo del resultado de la prueba. (Las implementaciones sin sucursales o de ramificación tienen ambas ventajas. Si la rama es predecible, una implementación sin sucursales tiende a ser más lenta).

La forma más obvia de hacer 1 es generar una máscara ( (1<<(pos+1)) -1 ) y & it. Una forma más eficiente es desplazar hacia la izquierda en 63-pos , Dejando los bits que desea empaquetar en la parte superior de un registro.

Esto también tiene el interesante efecto secundario de poner el bit que desea probar como el bit superior en el registro. Probar el bit de signo, en lugar de cualquier otro bit arbitrario, requiere un poco menos de instrucciones. Un desplazamiento aritmético a la derecha puede transmitir el bit de signo al resto del registro, lo que permite un código sin sucursales más eficiente que el habitual.

Hacer el popcount es un problema muy discutido, pero en realidad es la parte más complicada del rompecabezas. En x86, hay soporte de hardware extremadamente eficiente para él, pero solo en hardware lo suficientemente reciente. En las CPU Intel, la instrucción popcnt solo está disponible en Nehalem y más reciente. Me olvido cuando AMD agregó soporte.

Entonces, para usarlo de manera segura, necesita hacer un despacho de CPU con un respaldo que no use popcnt . O bien, crea binarios separados que no dependen de algunas características de la CPU.

popcount sin la instrucción popcnt se puede hacer de varias maneras. Uno usa SSSE3 pshufb para implementar una LUT de 4 bits. Sin embargo, esto es más efectivo cuando se usa en una matriz completa, en lugar de solo 64b a la vez. Los bithacks escalares podrían ser mejores aquí, y no requerirían SSSE3 (por lo que serían compatibles con CPU antiguas de AMD que tienen 64 bits pero no pshufb).

El Bitbroadcast:

(A[63]? ~0ULL : 0) le pide al compilador que transmita el bit alto a todas las demás posiciones de bit, lo que permite que se use como máscara AND hasta cero (o no) el resultado popcount. Tenga en cuenta que incluso para tamaños de bits grandes, solo está enmascarando la salida de popcnt , no el conjunto de bits en sí, así que ~0ULL está bien. ~0ULL ULL para asegurarme de que nunca le pedí al compilador que transmitiera el bit solo al bajo 32b de un registro (con UL en Windows, por ejemplo).

Esta transmisión se puede hacer con un desplazamiento aritmético a la derecha en 63, que cambia en copias del bit alto.

clang generó este código a partir de la versión original. Después de algunas insistencias de Glenn sobre diferentes implementaciones para 4 , me di cuenta de que podía dirigir gcc hacia la solución óptima de clang escribiendo la fuente más como el ASM que quiero. Lo obvio ((int64_t)something) >> 63 para solicitar más directamente un desplazamiento aritmético a la derecha no sería estrictamente portátil, porque los cambios a la derecha firmados se definen en la implementación como aritméticos o lógicos . El estándar no proporciona ningún operador aritmético de desplazamiento a la derecha. (Sin embargo, no es un comportamiento indefinido ). De todos modos, afortunadamente, los compiladores son lo suficientemente inteligentes: gcc ve la mejor manera una vez que le das suficiente pista.

Esta fuente hace un gran código en x86-64 y ARM64 con gcc y clang. Ambos simplemente usan un desplazamiento aritmético a la derecha en la entrada a popcnt (para que el cambio pueda ejecutarse en paralelo con el popcnt). También se compila muy bien en 32bit x86 con gcc, porque la máscara solo pasa a una variable de 32 bits (después de que se agreguen múltiples resultados popcnt). Es el resto de la función que es desagradable en 32 bits (cuando el conjunto de bits es más grande que un registro).

Versión original de operador ternario con gcc

Compilado con gcc 5.3.0 -O3 -O3 -march=nehalem -mtune=haswell (gcc antiguo, como 4.9.2, también sigue emitiendo esto):

; the original ternary-operator version. See below for the optimal version we can coax gcc into emitting. popcount_subset(std::bitset<64ul>, int): ; input bitset in rdi, input count in esi (SysV ABI) mov ecx, esi ; x86 variable-count shift requires the count in cl xor edx, edx ; edx=0 xor eax, eax ; gcc''s workaround for popcnt''s false dependency on the old value of dest, on Intel not ecx ; two''s complement bithack for 63-pos (in the low bits of the register) sal rdi, cl ; rdi << ((63-pos) & 63); same insn as shl (arithmetic == logical left shift) popcnt rdx, rdi test rdi, rdi ; sets SF if the high bit is set. cmovs rax, rdx ; conditional-move on the sign flag ret

Ver ¿Cómo probar que la afirmación C -x, ~ x + 1 y ~ (x-1) produce los mismos resultados? para el fondo en el uso de gcc de -x == ~x + 1 identidad de complemento de dos. ( ¿ Y qué operaciones enteras complementarias de 2 se pueden usar sin poner a cero bits altos en las entradas, si solo se quiere la parte baja del resultado? Lo que tangencialmente menciona que shl enmascara el recuento de turnos, entonces solo necesitamos los 6 bits bajos de ecx para Mantengo 63 - pos . Principalmente vinculando eso porque lo escribí recientemente y cualquiera que siga leyendo este párrafo puede encontrarlo interesante.

Algunas de esas instrucciones desaparecerán cuando esté en línea. (por ejemplo, gcc generaría el recuento en ecx en primer lugar).

Con la idea de Glenn de multiplicar en lugar de ternario (habilitada por USE_mul ), gcc sí

shr rdi, 63 imul eax, edi

al final en lugar de xor / test / cmovs .

Análisis de perfusión Haswell , utilizando datos de microarchivo de Agner Fog (versión Multiply):

mov r,r : 1 dominio fusionado uop, 0 latencia, sin unidad de ejecución
xor zero: 1 uop de dominio fusionado, sin unidad de ejecución
not : 1 uop para p0 / p1 / p5 / p6, 1c latencia, 1 por 0.25c de rendimiento
shl (aka sal ) con count in cl : 3 uops para p0 / p6: 2c latencia, 1 por 2c de rendimiento. (Los datos de Agner Fog indican que IvyBridge solo toma 2 uops para esto, extrañamente).
popcnt : 1 uop para p1, 3c latencia, 1 por 1c de rendimiento
shr r,imm : 1 uop para p0 / p6, 1c latencia. 1 por 0.5c de rendimiento.
imul r,r : 1uop para latencia p1, 3c.
sin contar el ret

Totales:

9 uops de dominio fusionado, pueden emitirse en 2.25 ciclos (en teoría, los efectos de la línea de caché uop generalmente embotan levemente el frontend).
4 uops (turnos) para p0 / p6. 2 uops para p1. 1 any-ALU-port uop. Se puede ejecutar a una por 2c (saturando los puertos de cambio), por lo que la interfaz es el peor cuello de botella.

Latencia: ruta crítica desde cuando el conjunto de bits está listo para cuando el resultado es: shl (2) -> popcnt (3) -> imul (3). Total 8 ciclos . O 9c desde cuando pos está listo, porque el not es una latencia 1c extra para él.

La versión de bitbroadcast óptima reemplaza a shr con sar (mismo perf), e imul con and (1c latencia en lugar de 3c, se ejecuta en cualquier puerto). Entonces, el único cambio de rendimiento es reducir la latencia del camino crítico a 6 ciclos . El rendimiento todavía está embotellado en la interfaz. and poder ejecutar en cualquier puerto no hace la diferencia, a menos que esté mezclando esto con un código que embotella en el puerto 1 (en lugar de mirar el rendimiento para ejecutar solo este código en un ciclo cerrado).

Versión cmov (operador ternario) : 11 uops de dominio fusionado (frontend: uno por 2.75c ). unidades de ejecución: todavía embotellado en los puertos de cambio (p0 / p6) a una por 2c. Latencia : 7c desde el conjunto de bits hasta el resultado, 8c desde la posición hasta el resultado. ( cmov es 2 latencia, 2 uops para cualquiera de p0 / p1 / p5 / p6).

Clang tiene algunos trucos diferentes bajo su manga: en lugar de test / cmovs , genera una máscara de todos o de uno con ceros usando un desplazamiento aritmético hacia la derecha para transmitir el bit de signo a todas las posiciones de un registro. Me encanta: Usar and lugar de cmov es más eficiente en Intel. Todavía tiene la dependencia de datos y funciona para ambos lados de la rama (que es la principal desventaja de cmov en general). Actualización: con el código fuente correcto, gcc también usará este método.

clang 3.7 -O3 -Wall -march=nehalem -mtune=haswell

popcount_subset(std::bitset<64ul>, int): mov ecx, 63 sub ecx, esi ; larger code size, but faster on CPUs without mov-elimination shl rdi, cl ; rdi << ((63-pos) & 63) popcnt rax, rdi ; doesn''t start a fresh dep chain before this, like gcc does sar rdi, 63 ; broadcast the sign bit and eax, edi ; eax = 0 or its previous value ret

sar / and reemplaza xor / test / cmov , y cmov es una instrucción 2-uop en las CPU de Intel, así que eso es realmente bueno. (Para la versión de operador ternario).

Clang sigue haciendo el sar / and truco en lugar de un imul real al usar la versión fuente múltiple, o la versión fuente "bitbroadcast". Entonces, esos ayudan a GCC sin lastimar clang. ( sar/and es definitivamente mejor que shr/imul : 2c menos latencia en la ruta crítica.) La versión pow_of_two_sub lastima clang (vea el primer enlace godbolt: omitido de esta respuesta para evitar el desorden con ideas que no funcionó) .

El mov ecx, 63 / sub ecx, esi es realmente más rápido en las CPU sin eliminación de mov para reg, reg movimientos (latencia cero y no puerto de ejecución, manejado por el cambio de nombre de registro). Esto incluye Intel pre-IvyBridge, pero no las CPU Intel y AMD más recientes.

El método mov imm / sub Clang pone solo un ciclo de latencia para pos en la ruta crítica (más allá de la latencia bitset-> resultado), en lugar de dos para una mov ecx, esi / not ecx en CPU donde mov r,r tiene latencia 1c .

Con BMI2 (Haswell y posterior), una versión ASM óptima puede guardar un mov a ecx . Todo lo demás funciona igual, porque shlx enmascara su registro de entrada de recuento de cambios hasta el tamaño del operando, al igual que shl .

Las instrucciones de cambio x86 tienen una semántica de CISC loca, donde si el recuento de turnos es cero, las banderas no se ven afectadas. Por lo tanto, las instrucciones de cambio de conteo variable tienen una dependencia (potencial) en el valor anterior de los indicadores. "Normal" x86 shl r, cl decodifica a 3 uops en Haswell, pero BMI2 shlx r, r, r es solo 1. Así que es una lástima que gcc todavía emita sal con -march=haswell , en lugar de usar shlx (lo cual hace uso en algunos otros casos).

// hand-tuned BMI2 version using the NOT trick and the bitbroadcast popcount_subset(std::bitset<64ul>, int): not esi ; The low 6 bits hold 63-pos. gcc''s two-s complement trick xor eax, eax ; break false dependency on Intel. maybe not needed when inlined. shlx rdi, rdi, rsi ; rdi << ((63-pos) & 63) popcnt rax, rdi sar rdi, 63 ; broadcast the sign bit: rdi=0 or -1 and eax, edi ; eax = 0 or its previous value ret

Análisis de rendimiento para Intel Haswell: 6 uops de dominio fusionado ( frontend: uno por 1.5c ). Unidades de ejecución: 2 p0 / p6 shift uops. 1 p1 uop. 2 uops de puerto: (uno por 1.25c de los límites del puerto de ejecución total). Latencia de ruta crítica: shlx (1) -> popcnt (3) -> and (1) = 5c bitset-> result. (o 6c de pos -> resultado).

Tenga en cuenta que al enlining, un humano (o compilador inteligente) podría evitar la necesidad del xor eax, eax . Está solo allí debido a la falsa dependencia de popcnt en el registro de salida (en Intel) , y necesitamos la salida en eax (que la persona que llama pudo haber usado recientemente para una larga cadena de depósito). Con -mtune=bdver2 o algo así, gcc no pondrá a cero el registro que usará para la salida popcnt .

Cuando estamos en línea, podríamos usar un registro de salida que ya debe estar listo al menos tan pronto como el popcnt de origen de popcnt para evitar el problema. Los compiladores realizarán un popcnt rdi,rdi - popcnt rdi,rdi in popcnt rdi,rdi cuando la fuente no se necesite más tarde, pero ese no es el caso aquí. En cambio, podemos elegir otro registro que ya debe estar listo antes de la fuente. La entrada de popcnt depende de 63-pos , y podemos popcnt rsi,rdi , así que la popcnt rsi,rdi rdi en rsi no puede retrasarlo. O si tuviéramos 63 en un registro, podríamos popcnt rsi,rdi / sarx rax, rsi, reg_63 / and eax, esi . O las instrucciones de cambio de BMI2 de 3 operandos tampoco nos permitirían interceptar las entradas en caso de que sean necesarias después.

Esto es tan liviano que la sobrecarga del bucle y la configuración de los operandos de entrada / almacenamiento de los resultados serán factores importantes. (Y el 63-pos puede optimizar lejos con una constante de tiempo de compilación, o en cualquier parte del conteo de variables).

El compilador de Intel se dispara divertido en el pie y no aprovecha el hecho de que A [63] es el bit de signo. shl / bt rdi, 63 / jc . Incluso establece las ramas de una manera realmente tonta. Podría cero eax, y luego saltar sobre popcnt o no según el indicador de señal establecido por shl .

Una implementación de bifurcación óptima , a partir de la salida ICC13 de -O3 -O3 -march=corei7 en godbolt:

// hand-tuned, not compiler output mov ecx, esi ; ICC uses neg/add/mov :/ not ecx xor eax, eax ; breaks the false dep, or is the return value in the taken-branch case shl rdi, cl jns .bit_not_set popcnt rax, rdi .bit_not_set: ret

Eso es bastante óptimo: el caso A[pos] == true tiene una rama no tomada. Sin embargo, no ahorra mucho en el método sin sucursales.

Si el caso A[pos] == false es más común: salta sobre una instrucción ret , a un popcnt / ret . (O después de la alineación: saltar a un bloque al final que hace el popcnt y salta hacia atrás).

He editado un problema que he visto antes que verifica si un número impar o par de bits se establece en un número. Es para C, pero no debería ser demasiado difícil darle masajes a C ++. El quid de la solución es lo que está en el ciclo while. Pruébelo en papel para comprender cómo selecciona el LSB y luego lo elimina de x. El resto del código es directo. El código se ejecuta en O (n), donde n es el número de bits establecidos en x. Eso es mucho mejor que el tiempo lineal, el cual también pensé que solo era posible cuando primero miraba este problema.

#include <stdio.h> int count(long x, int pos) { /* if bit at location pos is not set, return 0 */ if (!((x >> pos) & 1)) { return 0; } /* prepare x by removing set bits after position pos */ long tmp = x; tmp = tmp >> (pos + 1); tmp = tmp << (pos + 1); x ^= tmp; /* increment count every time the first set bit of x is removed (from the right) */ int y; int count = 0; while (x != 0) { y = x & ~(x - 1); x ^= y; count++; } return count; } int main(void) { /* run tests */ long num = 0b1010111; printf("%d/n", count(num, 0)); /* prints: 1 */ printf("%d/n", count(num, 1)); /* prints: 2 */ printf("%d/n", count(num, 2)); /* prints: 3 */ printf("%d/n", count(num, 3)); /* prints: 0 */ printf("%d/n", count(num, 4)); /* prints: 4 */ printf("%d/n", count(num, 5)); /* prints: 0 */ printf("%d/n", count(num, 6)); /* prints: 5 */ }

Mi reacción inmediata sería probar el bit especificado, e inmediatamente devolver 0 de eso está claro.

Si supera eso, cree una máscara de bits con ese bit (y los menos significativos) establecidos, and eso con la entrada original. Luego use la función miembro count() para obtener el recuento de bits establecidos en el resultado.

En cuanto a la creación de la máscara: puede desplazar 1 lugar N izquierdo, luego restar 1.

Suponiendo que un unsigned long o unsigned long unsigned long long es lo suficientemente grande como para contener 64 bits, puede llamar a bits.to_unlong() (o bits.to_ullong() ) para obtener los datos del conjunto de bits como un entero, enmascarar los bits por encima de X ( (1 << X) - 1 ) luego cuente esos bits como se dan en la respuesta a la pregunta que enlaza.