java - Optimizando Long.bitCount

optimization bit-manipulation

Question

Tengo un programa que está haciendo una gran cantidad de llamadas a Long.bitCount (), tantas que está tomando 33% de ciclos en un núcleo de CPU. ¿Hay alguna forma de implementarlo que sea más rápida 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 unos pocos bits a la vez y agregando los resultados)

Pero no pude hacer nada mejor que una tabla de búsqueda de 2 ¹⁶ entradas con un bucle desenrollado manualmente (aproximadamente el 27% de la CPU).
¿De qué otra manera podría optimizarse esto para Java?

Nota : esta pregunta es sobre la optimización específica de Java, pero esta pregunta similar (sin lenguaje) tiene muchos otros algoritmos.

Answer 1

Ahora estoy usando este método, que intercala cuatro operaciones popcnt a la vez. Se basa 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é.

Answer 2

Desde mi entendimiento:

Yo usaría el 33% como un indicador solo como el perfilado 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 eficiencias de mi optimización en función de los cambios de tiempo totales. También incluiría una fase de advertencia para que el JIT pueda hacer sus optimizaciones.

De hecho, la cuenta de bits parece ser una de las partes clave de su algoritmo de todos modos ... si optimiza todo y logra 10 veces más rápido para todas las partes clave, aún tiene un perfil cercano al 33% para esta parte. Eso no es malo por esencia.

Inspirándose en este enlace http://bmagic.sourceforge.net/bmsse2opt.html , podría intentar usar la instrucción SSE presente en todos los procesadores Intel / AMD ahora si recuerdo bien (de lo contrario, podría volver a JAVA). Una parte interesante relacionada con el artículo es ... Que la mayoría de las veces, está vinculada a la memoria de todos modos. Pero todavía intentaría ver cómo esto podría funcionar para usted.

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

De todos modos, no hay acceso directo, debe probar varios métodos y ver qué es lo que aporta más beneficios. No cuente el% hasta el tiempo total invertido.

Answer 3

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 contador.

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 al hacer un seguimiento del número de conteo de bits establecido. Esto mueve la sobrecarga a la frecuencia con la que se configuran o borran los bits y hace que obtener el número de bits establecido sea trivial. Aparece en su caso de uso, el último es mucho más a menudo.

Answer 4

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

De lo contrario, creo que es posible que tengas que lidiar con eso en un nivel superior. Tener múltiples subprocesos trabajando en diferentes segmentos de datos a la vez (lo cual estoy seguro de que ya lo haces), procesando los datos mientras los recopilas, compartiendo el trabajo en varios sistemas, algo así.

Answer 5

No soy un experto en el tema, pero si no has visto estas páginas, pueden ayudarte:

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 buscar en las muchas bibliotecas de gráficos que existen, especialmente en aquellas de nivel inferior o que hablen directamente al hardware.

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

Answer 6

Si se encuentra en una CPU x86 reciente, hay una instrucción para esto, popcnt.

En versiones recientes de Java, Long.bitCount () usa esta instrucción. Simplemente use -XX: + UsePopCountInstruction (este es el valor predeterminado en las versiones recientes)

Sin embargo, hay algunos errores en JRE 6.0_u18 a 7.0_u5: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7063674

Answer 7

Si su máquina tiene una ALU entera 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 conteos 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 al de Java.

Answer 8

Sospecho que su aplicación está vinculada a la memoria en lugar de la CPU, es decir, dedica más tiempo a recuperar los valores de la memoria que a contar 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).