popcount Bit para buffer de gran tamaño, con Core 2 CPU (SSSE3)

Question

Estoy buscando la manera más rápida popcount en gran buffer de 512 o más bytes. Puedo garantizar cualquier alineamiento necesario, y el tamaño del búfer es siempre una potencia de 2. Los corresponde tampón para bloquear las asignaciones, por lo general los bits son o bien todos conjunto, ninguno conjunto, o mayormente establecer favoreciendo la "izquierda" de la memoria intermedia, con agujeros ocasionales.

Algunas de las soluciones que he consideradas son:

• __builtin_popcount
• BitSlice popcount_24words
• Contando conjunto de bits de, manera de Brian Kernighan

Estoy interesado en la solución más rápida, tiene que trabajar en 32 bits x86 chipset perteneciente al Core 2 o más reciente. SSE y SIMD son de gran interés. Voy a estar poniendo a prueba en el siguiente CPU de cuatro núcleos:

matt@stanley:~/anacrolix/public/stackoverflow$ cat /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz
stepping        : 11
cpu MHz         : 1600.000
cache size      : 4096 KB
physical id     : 0
siblings        : 4
core id         : 0
cpu cores       : 4
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 10
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm tpr_shadow vnmi flexpriority
bogomips        : 4800.21
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Answer 1

Me delinear el mejor C / montaje de las funciones que he encontrado para recuento de la población / peso de Hamming de gran tampones abajo.

La función más rápido montaje es ssse3_popcount3 , descrito aquí . Requiere SSSE3 , disponible en Intel Core 2 y más tarde, y conjuntos de chips AMD llega en 2011. Utiliza SIMD instrucciones a popcount en 16 trozos byte y desenrolla 4 iteraciones del bucle a la vez.

La función más rápido C es popcount_24words , descrito aquí . Se utiliza el algoritmo de bits de corte. Es de destacar que me encontré con que sonido metálico realidad podría generar instrucciones de montaje de vectores apropiados, lo que dio un impresionante aumento de rendimiento. Aparte de esto, el algoritmo sigue siendo extremadamente rápido.

Answer 2

Vea una versión de 32 bits en el href="http://support.amd.com/us/Embedded_TechDocs/25112.PDF" rel="nofollow noreferrer"> optimización de software AMD , página 195 para una implementación. Esto le da el montaje de código para un sistema x86 directamente.

Ver una variante en de Stanford-bit haciendo girar los cortes La versión de Stanford se parece el mejor para mí. Se ve muy fácil de código como ASM x86.

Ninguna de estas instrucciones de uso sucursales.

Estos se puede generalizar a las versiones de 64 bits.

Con las versiones de 32 o 64 bits, es posible pensar en hacer una versión SIMD. SSE2 hará 4 dobles palabras o dos palabras cuádruples (de cualquier manera 128 bits) En seguida. Lo que se quiere hacer es poner en práctica el popcount el 32 o 64 bits en cada uno de los 2 o 4 registros disponibles. Usted va a terminar con 2 o 4 series de popcounts en los registros XMM Cuando acabes; paso final es la de almacenar y añadir los popcounts juntos para obtener la respuesta final. Adivinación, Yo esperaría que hacerlo un poco mejor haciendo 4 paralelo 32 popcounts bits en lugar de 2 popcounts paralelo de 64 bits, como este último es probable que tenga 1 o 2 instrucciones adicionales en cada iteración, y es fácil de añadir 4, valores de 32 bits junto el final.

Answer 3

Si Had POPCNT:

http: // Kent-Vandervelden .blogspot.com / 2009/10 / conteo de bits en la población de conteo-and.html

http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011/compiler_c/intref_cls/common/intref_sse42_ATA.htm

Answer 4

Yo sugeriría la implementación de una de las rutinas optimizadas 32 bits de POPCNT Hacker , pero que lo haga por 4 x 32 bit número entero elementos en un vector de SSE. A continuación, puede procesar 128 bits por iteración, que debe dar alrededor de 4 veces el rendimiento en comparación con una rutina de optimización escalar 32 bits.