¿Cómo puedo codificar Java para permitir el uso de SSE y la eliminación de la verificación de límites (u otras optimizaciones avanzadas)?

StackOverflow https://stackoverflow.com/questions/1352422

Pregunta

La situación:

Estoy optimizando una implementación en Java pura del algoritmo de compresión LZF, que implica mucho acceso a bytes[] y matemáticas int básicas para hash y comparación.El rendimiento realmente importa, porque el objetivo de la compresión es reducir los requisitos de E/S.No publicaré código porque aún no se ha limpiado y es posible que se haya reestructurado en gran medida.

Las preguntas:

  • ¿Cómo puedo escribir mi código para permitirle compilarlo JIT en un formulario utilizando operaciones SSE más rápidas?
  • ¿Cómo puedo estructurarlo para que el compilador pueda eliminar fácilmente las comprobaciones de los límites de la matriz?
  • ¿Existen referencias amplias sobre la velocidad relativa de operaciones matemáticas específicas (cuántos incrementos/decrementos se necesitan para igualar una suma/resta normal, qué tan rápido es shift-o vs.un acceso a la matriz)?
  • ¿Cómo puedo trabajar para optimizar la ramificación? ¿Es mejor tener numerosas sentencias condicionales con cuerpos cortos, unas cuantas largas o cortas con condiciones anidadas?
  • Con la JVM 1.6 actual, ¿cuántos elementos se deben copiar antes de que System.arraycopy supere un ciclo de copia?

Lo que ya he hecho:

Antes de que me ataquen por optimización prematura:el algoritmo básico ya es excelente, pero la implementación de Java es menos de 2/3 de la velocidad de C equivalente.Ya reemplacé los bucles de copia con System.arraycopy, trabajé en la optimización de bucles y eliminé operaciones innecesarias.

Hago un uso intensivo de la manipulación de bits y el empaquetado de bytes en enteros para mejorar el rendimiento, así como el cambio y el enmascaramiento.

Por razones legales, no puedo ver implementaciones en bibliotecas similares y las bibliotecas existentes tienen términos de licencia demasiado restrictivos para su uso.

Requisitos para una BUENA respuesta (aceptada):

  • Respuestas inaceptables: "esto es más rápido" sin una explicación de cuánto Y por qué, O no se ha probado con un compilador JIT.
  • Respuestas límite: no han sido probados con nada anterior a Hotspot 1.4
  • Respuestas básicas: proporcionará una regla general y una explicación de por qué es más rápido en el nivel del compilador y aproximadamente cuánto más rápido
  • Buenas respuestas: incluya un par de ejemplos de código para demostrar
  • Excelentes respuestas: tener puntos de referencia con JRE 1.5 y 1.6
  • Respuesta perfecta: Es de alguien que trabajó en el compilador HotSpot y puede explicar completamente o hacer referencia a las condiciones para utilizar una optimización y cuánto más rápida suele ser.Puede incluir código Java y código ensamblador de muestra generado por HotSpot.

También:Si alguien tiene enlaces que detallan los aspectos básicos de la optimización del Hotspot y el rendimiento de las ramificaciones, son bienvenidos.Sé lo suficiente sobre el código de bytes como para que sería útil un sitio que analice el rendimiento a nivel de código de bytes en lugar de código fuente.

(Editar) Respuesta parcial:Eliminación de control de límites:

Esto está tomado del enlace proporcionado a la wiki interna de HotSpot en: https://wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination

HotSpot eliminará las comprobaciones de límites en todos los bucles for con las siguientes condiciones:

  • La matriz es invariante en bucle (no reasignada dentro del bucle)
  • La variable del índice tiene un paso constante (aumenta/disminuye en una cantidad constante, en un solo lugar si es posible)
  • La matriz está indexada por una función lineal de la variable.

Ejemplo: int val = array[index*2 + 5]

O: int val = array[index+9]

NO: int val = array[Math.min(var,index)+7]

Versión inicial del código:

Esta es una versión de muestra.No lo robes, porque es una versión inédita del código del proyecto de base de datos H2.La versión final será de código abierto.Esta es una optimización del código aquí: Compresión H2 Código LZF

Lógicamente, esto es idéntico a la versión de desarrollo, pero usa un bucle for(...) para recorrer la entrada, y un bucle if/else para una lógica diferente entre los modos literal y de referencia inversa.Reduce el acceso a la matriz y las comprobaciones entre modos.

public int compressNewer(final byte[] in, final int inLen, final byte[] out, int outPos){
        int inPos = 0;
        // initialize the hash table
        if (cachedHashTable == null) {
            cachedHashTable = new int[HASH_SIZE];
        } else {
            System.arraycopy(EMPTY, 0, cachedHashTable, 0, HASH_SIZE);
        }
        int[] hashTab = cachedHashTable;
        // number of literals in current run
        int literals = 0;
        int future = first(in, inPos);
        final int endPos = inLen-4;

        // Loop through data until all of it has been compressed
        while (inPos < endPos) {
                future = (future << 8) | in[inPos+2] & 255;
//                hash = next(hash,in,inPos);
                int off = hash(future);
                // ref = possible index of matching group in data
                int ref = hashTab[off];
                hashTab[off] = inPos;
                off = inPos - ref - 1; //dropped for speed

                // has match if bytes at ref match bytes in future, etc
                // note: using ref++ rather than ref+1, ref+2, etc is about 15% faster
                boolean hasMatch = (ref > 0 && off <= MAX_OFF && (in[ref++] == (byte) (future >> 16) && in[ref++] == (byte)(future >> 8) && in[ref] == (byte)future));

                ref -=2; // ...EVEN when I have to recover it
                // write out literals, if max literals reached, OR has a match
                if ((hasMatch && literals != 0) || (literals == MAX_LITERAL)) {
                    out[outPos++] = (byte) (literals - 1);
                    System.arraycopy(in, inPos - literals, out, outPos, literals);
                    outPos += literals;
                    literals = 0;
                }

                //literal copying split because this improved performance by 5%

                if (hasMatch) { // grow match as much as possible
                    int maxLen = inLen - inPos - 2;
                    maxLen = maxLen > MAX_REF ? MAX_REF : maxLen;
                    int len = 3;
                    // grow match length as possible...
                    while (len < maxLen && in[ref + len] == in[inPos + len]) {
                        len++;
                    }
                    len -= 2;

                    // short matches write length to first byte, longer write to 2nd too
                    if (len < 7) {
                        out[outPos++] = (byte) ((off >> 8) + (len << 5));
                    } else {
                        out[outPos++] = (byte) ((off >> 8) + (7 << 5));
                        out[outPos++] = (byte) (len - 7);
                    }
                    out[outPos++] = (byte) off;
                    inPos += len;

                    //OPTIMIZATION: don't store hashtable entry for last byte of match and next byte
                    // rebuild neighborhood for hashing, but don't store location for this 3-byte group
                    // improves compress performance by ~10% or more, sacrificing ~2% compression...
                    future = ((in[inPos+1] & 255) << 16) | ((in[inPos + 2] & 255) << 8) | (in[inPos + 3] & 255);
                    inPos += 2;
                } else { //grow literals
                    literals++;
                    inPos++;
                } 
        }

        // write out remaining literals
        literals += inLen-inPos;
        inPos = inLen-literals;
        if(literals >= MAX_LITERAL){
            out[outPos++] = (byte)(MAX_LITERAL-1);
            System.arraycopy(in, inPos, out, outPos, MAX_LITERAL);
            outPos += MAX_LITERAL;
            inPos += MAX_LITERAL;
            literals -= MAX_LITERAL;
        }
        if (literals != 0) {
            out[outPos++] = (byte) (literals - 1);
            System.arraycopy(in, inPos, out, outPos, literals);
            outPos += literals;
        }
        return outPos; 
    }

Edición final:

He marcado la mejor respuesta hasta el momento como aceptada, ya que la fecha límite casi ha vencido.Como me tomó tanto tiempo decidir publicar el código, continuaré votando y respondiendo a los comentarios siempre que sea posible. Disculpas si el código está desordenado:esto representaba código en desarrollo, no pulido para su confirmación.

¿Fue útil?

Solución

No es una respuesta completa, simplemente no tengo tiempo para hacer las referencias detalladas a sus necesidades pregunta, pero espero sea de utilidad.

Conoce a tu enemigo

Se orienta a una combinación de la JVM (en esencia, el JIT) y el subsistema de CPU / memoria subyacente. Así, "Esto es más rápido en la JVM X" no es probable que sea válida en todos los casos cuando se mueven en optimizaciones más agresivos.

Si su mercado objetivo / aplicación será en gran medida funcionar en una arquitectura particular, usted debe considerar la inversión en herramientas específicas para ello.   * Si su rendimiento en x86 es el factor crítico luego de Intel VTune es excelente para perforación hacia abajo en el tipo de análisis de la producción JIT usted describe.  * Las diferencias entre 64 bits y 32 bits equipos conjuntos de investigación pueden ser considerables, especialmente en plataformas x86, donde convenciones de llamada pueden cambiar y enregistering oportunidades son muy diferentes.

Obtener las herramientas adecuadas

Se podría probable que desee obtener un perfilador de muestreo. La sobrecarga de la instrumentación (y el golpe asociado en cosas como en procesos en línea, la contaminación y la inflación caché tamaño del código) para sus necesidades específicas serían demasiado grandes. El analizador Intel VTune en realidad se puede utilizar para Java pesar de que la integración no es tan fuerte como los demás.
Si está utilizando la JVM sol y está satisfecho solamente saber cuál es la última versión mayor / está haciendo a continuación las opciones disponibles para investigar la salida del JIT son considerables si usted sabe un poco de montaje. Este artículo detalla algunos interesante análisis utilizando esta funcionalidad

Aprender de otras implementaciones

El historial de cambios cambiar la historia indica que ensamblador en línea anterior era, de hecho, contraproducente y que permitir que el compilador para tomar el control total de la salida (con ajustes en código en lugar de directivas en el montaje) dio mejores resultados.

Algunos Detalles

Desde LZF es, en una implementación eficiente no administrado en las CPU de escritorio moderno, gran parte del ancho de banda de memoria limitada (de ahí que se competían a la velocidad de un establecimiento de memoria unoptimised), necesitará su código de permanecer enteramente dentro de caché de nivel 1.
Como todos los campos estáticos tales que no se puede convertir en constantes debe ser colocado dentro de la misma clase que estos valores a menudo se colocan dentro de la misma área de memoria dedicada a los vtables y los metadatos asociados con las clases.

necesitarán ser evitado

asignaciones de objetos que no pueden ser atrapados por Análisis Escape (sólo en 1.6 en adelante).

El código c rel="noreferrer"> href="http://cvs.schmorp.de/liblzf/lzf_c.c?revision=1.37&view=markup" hace uso agresivo de desenroscado de bucles . Sin embargo, el rendimiento de este en los más antiguos (1.4 época) VM es depende en gran medida del modo de la JVM está en . Al parecer, esta última versión JVM de Sun son más agresivos en procesos en línea y desenrollado, especialmente en el modo servidor.

Los instrctions de recuperación previa generados por el compilador JIT puede hacer toda la diferencia en el código como el que está cerca de la memoria con destino.

"Ya viene directamente hacia nosotros"

Su objetivo está en movimiento, y continuará. Una vez más MarcLa experiencia previa de Lehmann:

  

Tamaño Hlog predeterminado es ahora 15 (cachés de CPU han aumentado)

Incluso cambios menores en la JVM puede implicar compilador significativos cambios

  

6544668 No vecorized operaciones de matriz que no se pueden alinear en tiempo de ejecución.   6536652 implementar algunas superword (SIMD) optimizaciones   6531696 no utilizan inmediata tienda valor de 16 bits a la memoria de las CPU Intel   6468290 Divide y asignar de Edén en una base por la CPU

Capitán Obvio

Medir, medir, medir. Si usted puede conseguir su biblioteca para incluir (en un archivo independiente DLL) de forma sencilla y fácil de ejecutar punto de referencia que registra la información relevante (versión VM, CPU, sistema operativo, la línea de comandos, etc.) y hace que esta simple para enviar de nuevo a usted se quiere aumentar su cobertura, lo mejor de todo lo que va a cubrir aquellas personas que lo usan esa atención.

Otros consejos

En lo que a comprobación de límites eliminación se refiere, creo que la nueva JDK ya incluirá un algoritmo mejorado que elimina que, siempre que sea posible. Estos son los dos papeles principales en este tema:

  • V. Mikheev, S. Fedoseev, V. Sukharev, N. Lipsky. 2002 Mejora efectiva de bucle de versiones en Java . Enlace. Este documento es de los chicos de Excelsior, que implementan la técnica en su Jet JVM.
  • Würthinger, Thomas, Christian Wimmer, y Hanspeter Mössenböck. 2007. Comprobar límites de la matriz para la Eliminación del compilador Java HotSpot cliente . PPPJ. Enlace . Ligeramente basada en el documento anterior, esta es la aplicación que creo que será incluido en la próxima JDK . Las alcanzados aceleraciones se presentaron también.

También existe esta entrada del blog , que analiza uno de los papeles de manera superficial, y también presenta algunos resultados de evaluación comparativa, no sólo para las matrices, sino también para la aritmética en el nuevo JDK. Los comentarios de la entrada de blog también son muy interesantes, ya que los autores de los trabajos anteriores presentan algunos comentarios muy interesantes y discuten argumentos. Además, hay algunas referencias a otras entradas de blog similares sobre este tema.

Espero que ayuda.

Es bastante improbable que se necesita para ayudar al compilador JIT tanto con la optimización de un sencillo algoritmo cálculo de números como LZW. ShuggyCoUk menciona esto, pero creo que merece una atención especial:

La caché de uso de su código será un factor importante.

Hay que reducir el tamaño de su conjunto de Woking y mejorar el acceso de localidad de datos tanto como sea posible. Usted habla de "embalaje bytes en enteros para el rendimiento". Esto suena como el uso de enteros para mantener los valores de byte con el fin de tenerlos alineados por palabras. No hagas eso! El mayor tamaño conjunto de datos serán mayores que cualquier ganancia (I Una vez convertido un número ECC crujido código de int [] a byte [] y tengo una velocidad de 2x-up).

En la remota posibilidad de que usted no sabe esto: si usted necesita para tratar algunos datos como dos bytes y enteros, que no tiene que cambiar y | -mask - utilice ByteBuffer.asIntBuffer() y métodos relacionados.

  

Con la actual 1.6 JVM, cuántos   elementos deben ser copiados antes   System.arraycopy late un bucle copiar?

Es mejor hacer la referencia a sí mismo. Cuando lo hice camino de regreso cuando en Java 1,3 veces, que estaba en algún lugar alrededor de 2000 elementos.

Muchas respuestas hasta ahora, pero un par de cosas adicionales:

  • Medir, medir, medir.Por mucho que la mayoría de los desarrolladores de Java adviertan contra las micro evaluaciones comparativas, asegúrese de comparar el rendimiento entre los cambios.Por lo general, no vale la pena mantener las optimizaciones que no dan como resultado mejoras mensurables (por supuesto, a veces es una combinación de cosas, y eso se vuelve más complicado).
  • Los bucles estrechos importan tanto con Java como con C (y lo mismo ocurre con las asignaciones de variables; aunque no lo controlas directamente, HotSpot eventualmente tendrá que hacerlo).Me las arreglo para prácticamente duplicar la velocidad de decodificación UTF-8 reorganizando el bucle cerrado para manejar mayúsculas y minúsculas de un solo byte (ascii de 7 bits) como un bucle interno apretado (más), dejando fuera otros casos.
  • No subestime el costo de asignar y/o borrar matrices grandes: si desea que la codificación/decodificación lzf sea más rápida también para fragmentos pequeños/medianos (no solo de tamaño megabyte), tenga en cuenta que TODAS las asignaciones de byte[]/int[ ] son ​​algo costosos;no por GC, sino porque JVM DEBE limpiar el espacio.

La implementación de H2 también se ha optimizado bastante (por ejemplo:ya no borra la matriz hash, esto a menudo tiene sentido);y de hecho ayudé a modificarlo para usarlo en otro proyecto Java.Mi contribución fue principalmente cambiarlo para que fuera más óptimo para casos sin transmisión, pero eso no afectó los estrechos bucles de codificación/decodificación.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top