Optimización de Long.BitCount

https://stackoverflow.com/questions/4839128

27-10-2019
|

Pregunta

Tengo un programa que está haciendo una gran cantidad de llamadas a Long.BitCount (), tantos que está tomando el 33% de los ciclos en un núcleo de CPU. ¿Hay alguna manera de implementarlo que sea más rápido que la versión Sun JDK?

Yo he tratado:

Este algoritmo (Creo que así es exactamente como lo implementa el JDK)
Tablas de búsqueda de varios tamaños entre 2⁸ y 2²² (mirando algunos bits a la vez y agregando los resultados)

Pero no podría hacerlo mejor que un 2¹⁶-La de búsqueda de entrada con un bucle manualmente sincronizado (alrededor del 27% de la CPU).
¿De qué otra forma podría esto ser optimizado para Java?

Nota: Esta pregunta es sobre la optimización específica de Java, pero Esta pregunta similar (del lenguaje-agnóstico) tiene muchos otros algoritmos.

Solución

Si está en una CPU X86 reciente, hay una instrucción para esto, PopCnt.

En versiones recientes de Java, Long.BitCount () utiliza esta instrucción. Solo use -xx:+usePopCountInstruction (este es el valor predeterminado en las versiones recientes)

Sin embargo, hay algunos errores con él en JRE 6.0_U18 a 7.0_U5:http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7063674

Otros consejos

Este parece ser uno de esos problemas que es simplemente perfecto para que la GPU trabaje. Debería poder reducir su tiempo por un par de órdenes de magnitud.

De lo contrario, creo que puede tener que lidiar con eso en un nivel superior. Tener múltiples hilos trabajando en diferentes segmentos de datos a la vez (que estoy seguro de que ya hace), procesando los datos mientras lo recopila, compartiendo el trabajo en múltiples sistemas, algo así.

Si la máquina tiene un Alu entero que puede procesar datos más amplios que algunos múltiplos de 64 bits (también conocidos como SIMD, como SSE2 o VMX), puede calcular los recuentos de bits en varios elementos de 64 bits a la vez.

Desafortunadamente, esto requerirá que proporcione implementaciones específicas de la máquina en un lenguaje de nivel inferior que Java.

Sospecho que su aplicación está vinculada a la memoria en lugar de a CPU, es decir, pasa más tiempo buscando los valores de la memoria que contando sus bits. En ese caso, debe intentar reducir el tamaño del conjunto de trabajo o mejorar la localidad de acceso para reducir las fallas de caché (si el algoritmo lo permite).

No soy un experto en el tema, pero en caso de que no hayas visto estas páginas, pueden ayudar:

http://www.reddit.com/r/programming/comments/84sht/fast_bit_couting_algorithms/

http://www-graphics.stanford.edu/~seander/bithacks.html

También es posible que desee pinchar las muchas bibliotecas gráficas, especialmente aquellas que son de nivel inferior y/o hablan directamente con el hardware.

EDITAR: Parece que puede usar la instrucción POPCNT relativamente recién introducida (disponible en algunos procesadores AMD e Intel recientes) para un aumento de velocidad potencial, si tiene la opción de escribir un código específico de plataforma de bajo nivel y puede apuntar a esa arquitectura específica . http://kent-vandervelden.blogspot.com/2009/10/counting-bitspobulation-count-and.html y otro artículo con puntos de referencia: http://www.strchr.com/crc32_popcnt

De mi entendimiento:

Usaría el 33% como indicador solo, ya que el perfil para métodos pequeños realmente podría cambiar el rendimiento general. Así que ejecutaría el algoritmo en un gran conjunto de datos y vería el tiempo total. Y consideraría las eficiías de mi optimización en función de los cambios de tiempo total. También incluiría una fase de advertencia para que el JIT pueda hacer sus optimizaciones.

De hecho, la cosa de conteo de bits parece ser una de las partes clave de su algoritmo de todos modos ... si optimiza todo y logra obtener 10 veces más rápido para toda la parte clave, aún perfilas algo cerca del 33% para esta parte. Eso no es malo por esencia.

Inspirando a este enlace http://bmagic.sourceforge.net/bmsse2opt.html Puede intentar usar la instrucción SSE presente en todo el procesador Intel/AMD ahora si no recuerdo bien (siempre podría fallar a Java de lo contrario). Una parte interreladora sobre el artículo es ... que la mayoría de las veces, de todos modos está vinculado a la memoria. Pero aún trataría de ver cómo podría funcionar para ti.

Una GPU sería perfecta para un procesamiento increíblemente rápido (fácil de cien veces uno de un núcleo de CPU) y ancho de banda. El principal problema sería impulsar los datos a la memoria dedicada a CPU y recuperar el resultado. Pero si no solo realiza el conteo de bits sino más operaciones, esto podría generar grandes ganancias.

De todos modos, no hay atajo, debe probar varios enfoques y ver qué brindan más ganancia. No cuente el % a través del tiempo total que pasó.

Ahora estoy usando este método, que entrelaza cuatro operaciones POPCNT a la vez. Está basado en esta implementación de c.

private static final long M0=0x5555555555555555L,
                          M1=0x3333333333333333L,
                          M2=0x0f0f0f0f0f0f0f0fL;
public void store4Tags(long tag0, long tag1, long tag2, long tag3) {
    long count0 = tag0,
         count1 = tag1,
         count2 = tag2,
         count3 = tag3;
    count0 = (count0 & M0) + ((count0 >>> 1) & M0);
    count1 = (count1 & M0) + ((count1 >>> 1) & M0);
    count2 = (count2 & M0) + ((count2 >>> 1) & M0);
    count3 = (count3 & M0) + ((count3 >>> 1) & M0);

    count0 = (count0 & M1) + ((count0 >>> 2) & M1);
    count1 = (count1 & M1) + ((count1 >>> 2) & M1);
    count2 = (count2 & M1) + ((count2 >>> 2) & M1);
    count3 = (count3 & M1) + ((count3 >>> 2) & M1);

    count0 = (count0 + (count0 >>> 4)) & M2;
    count1 = (count1 + (count1 >>> 4)) & M2;
    count2 = (count2 + (count2 >>> 4)) & M2;
    count3 = (count3 + (count3 >>> 4)) & M2;

    count0 += count0 >>> 8;
    count1 += count1 >>> 8;
    count2 += count2 >>> 8;
    count3 += count3 >>> 8;

    count0 += count0 >>> 16;
    count1 += count1 >>> 16;
    count2 += count2 >>> 16;
    count3 += count3 >>> 16;

    count0 += count0 >>> 32;
    count1 += count1 >>> 32;
    count2 += count2 >>> 32;
    count3 += count3 >>> 32;

    storeWithPopCnt(tag0, 0x3f & (int) count0);
    storeWithPopCnt(tag1, 0x3f & (int) count1);
    storeWithPopCnt(tag2, 0x3f & (int) count2);
    storeWithPopCnt(tag3, 0x3f & (int) count3);
}

Esto supera ligeramente la versión de la tabla de búsqueda y no consume caché.

En lugar de optimizar esta función, es probable que esté mejor optimizando el uso de esta función. Por ejemplo, podrías mantener un mostrador.

public void set(int n) {
   if(!get(n)) bitCount++;
   // set the bit
}
public void clear(int n) {
   if(get(n)) bitCount--;
   // clear the bit
}
public int bitCount() {
   return bitCount;
}

Esto evita escanear los datos realizando un seguimiento del número de recuento de bits establecidos. Esto mueve la sobrecarga a la frecuencia con la que los bits y el set o se aclaran y hace que la cantidad de bits establezca trivial. Aparece en su caso de uso, el último es mucho más a menudo.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow