stackoverflowerror - java lang numberformatexception null solucion

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

Question

La situación:

Estoy optimizando una implementación de java puro del algoritmo de compresión LZF, que implica un gran número de bytes [] de acceso y matemáticas básicas para el hash y la comparación. El rendimiento realmente importa, porque el objetivo de la compresión es reducir los requisitos de E / S. No estoy publicando código porque todavía no se ha limpiado y puede reestructurarse mucho.

Las preguntas:

• ¿Cómo puedo escribir mi código para permitirle JIT-compilar a un formulario que usa operaciones SSE más rápidas?
• ¿Cómo puedo estructurarlo para que el compilador pueda eliminar fácilmente las verificaciones de límites de la matriz?
• ¿Hay alguna referencia amplia sobre la velocidad relativa de las operaciones matemáticas específicas (cuántos incrementos / decrementos se necesitan para igualar una suma / resta normal, qué tan rápido es el cambio o el acceso a una matriz)?
• ¿Cómo puedo trabajar para optimizar la ramificación? ¿Es mejor tener numerosas declaraciones condicionales con cuerpos cortos, o algunos largos, o cortos con condiciones anidadas?
• Con 1.6 JVM actual, ¿cuántos elementos deben copiarse antes de que System.arraycopy supere un ciclo de copiado?

Lo que ya hice

Antes de ser atacado por una optimización prematura: el algoritmo básico ya es excelente, pero la implementación de Java es menos de 2/3 de la velocidad del equivalente C. Ya he reemplazado los ciclos de copiado con System.arraycopy, trabajé en la optimización de loops y eliminé operaciones necesarias

Hago un uso intensivo de bit twiddling y octetos de embalaje en ints para rendimiento, así como cambio y enmascaramiento.

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

Requisitos para una respuesta BUENA (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 se han probado con nada antes de 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: incluye un par de muestras de código para demostrar
• Excelentes respuestas: tienen puntos de referencia con JRE 1.5 y 1.6
• Respuesta PERFECTA: la hace alguien que trabajó en el compilador de HotSpot, y puede explicar completamente o hacer referencia a las condiciones para que se use una optimización, y cuánto más rápido suele ser. Podría incluir el código de Java y el código de ensamblaje de muestra generado por HotSpot.

Además: si alguien tiene enlaces que detallan las agallas de la optimización de Hotspot y el rendimiento de la bifurcación, son bienvenidos. Sé lo suficiente sobre bytecode que sería útil un sitio que analice el rendimiento en un bytecode en lugar de un código fuente.

(Editar) Respuesta parcial: Limitación de límite de comprobación:

Esto se toma del enlace suministrado al wiki interno de HotSpot en: https://wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination

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

• Array es invariante de bucle (no reasignado dentro del bucle)
• La variable índice tiene una zancada constante (aumenta / disminuye en cantidad constante, en un solo punto si es posible)
• Array está indexado por una función lineal de la variable.

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

O bien: int val = array[index+9]

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

Primera versión del código:

Esta es una versión de muestra. No robarlo, porque es una versión inédita del código para el proyecto de base de datos H2. La versión final será de código abierto. Esta es una optimización del código aquí: código H2 CompressLZF

Lógicamente, esto es idéntico a la versión de desarrollo, pero uno usa un ciclo for (...) para pasar por la entrada, y un ciclo if / else para una lógica diferente entre los modos literal y de retroreferencia. 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:

Marqué la mejor respuesta hasta el momento, ya que el plazo casi ha terminado. Dado que tardé tanto en decidir publicar el código, continuaré votando y respondiendo a los comentarios siempre que sea posible. Disculpas si el código es desordenado: esto representa código en desarrollo, no pulido para cometer.

Answer 1

En lo que respecta a la eliminación de cheques de límites , creo que el nuevo JDK ya incluirá un algoritmo mejorado que lo elimina, siempre que sea posible. Estos son los dos documentos principales sobre este tema:

• V. Mikheev, S. Fedoseev, V. Sukharev, N. Lipsky. 2002 Mejora efectiva de versiones de bucles en Java . Link . Este documento es de los chicos de Excelsior, quienes implementaron la técnica en su Jet JVM.
• Würthinger, Thomas, Christian Wimmer y Hanspeter Mössenböck. 2007. Array Bounds Check Elimination para Java HotSpot Client Compiler . PPPJ. Link . Ligeramente basado en el documento anterior, esta es la implementación que creo que se incluirá en el próximo JDK . Las aceleraciones logradas también se presentan.

También está this entrada de blog, que discute superficialmente uno de los artículos, y también presenta algunos resultados de evaluación comparativa, no solo para las matrices, sino también para la aritmética en el nuevo JDK. Los comentarios de la entrada del blog también son muy interesantes, ya que los autores de los artículos anteriores presentan algunos comentarios muy interesantes y discuten los argumentos. Además, hay algunos consejos para otras publicaciones de blog similares sobre este tema.

Espero eso ayude.

Answer 2

Es bastante improbable que necesites ayudar al compilador JIT para optimizar un algoritmo sencillo de cálculo de números como LZW. ShuggyCoUk lo mencionó, pero creo que merece una atención especial:

La facilidad de almacenamiento en caché de tu código será un factor importante.

Debe reducir el tamaño de su conjunto de trabajo y mejorar la ubicación de acceso a datos tanto como sea posible. Usted menciona "empacar bytes en ints para el rendimiento". Esto suena como usar ints para mantener los valores de byte con el fin de alinearlos con la palabra. ¡No hagas eso! El tamaño aumentado del conjunto de datos superará cualquier ganancia (una vez convertí un código de procesamiento numérico de ECC de int [] a byte [] y obtuve una aceleración de 2x).

En el caso de que no sepas esto: si necesitas tratar algunos datos como bytes y entradas, no tienes que desplazarlos y | -mascararlos- usan ByteBuffer.asIntBuffer() y métodos relacionados.

Con 1.6 JVM actual, ¿cuántos elementos deben copiarse antes de que System.arraycopy supere un ciclo de copiado?

Mejor haz el punto de referencia tú mismo. Cuando lo hice allá en Java 1.3 veces, fue en algún lugar alrededor de 2000 elementos.

Answer 3

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

• Mida, mida, mida. Por mucho que la mayoría de los desarrolladores de Java adviertan contra micro-benchmarking, asegúrese de comparar el rendimiento entre los cambios. En general, no vale la pena mantener las optimizaciones que no resultan en mejoras medibles (por supuesto, a veces es una combinación de cosas, y eso se vuelve más complicado)
• Los ciclos estrictos importan tanto con Java como con C (y lo mismo con las asignaciones de variables; aunque no lo controle directamente, HotSpot eventualmente tendrá que hacerlo). Logro prácticamente duplicar la velocidad de decodificación UTF-8 reorganizando el circuito cerrado para manejar el caso de un solo byte (ascii de 7 bits) como un circuito interno ajustado (er), dejando otros casos fuera.
• No subestime el costo de asignar y / o borrar grandes matrices: si quiere que la codificación / decodificación lzf sea más rápida también para fragmentos pequeños / medianos (no solo para megabytes), tenga en cuenta que TODAS las asignaciones de byte [] / int [ ] son ​​algo costosos; no por GC, sino porque JVM DEBE despejar el espacio.

La implementación de H2 también se ha optimizado bastante (por ejemplo: ya no borra la matriz de hash, esto a menudo tiene sentido); y en realidad ayudé a modificarlo para usarlo en otro proyecto de Java. Mi contribución fue solo cambiarla, pero es más óptima para casos sin transmisión, pero eso no tocó los logos de codificación / decodificación ajustados.

Answer 4

No es una respuesta completa, simplemente no tengo tiempo para hacer los puntos de referencia detallados que su pregunta necesita, pero espero que sean útiles.

Conoce a tu enemigo

Está apuntando a una combinación de la JVM (en esencia, el JIT) y el subsistema CPU / Memoria subyacente. Por lo tanto, "Esto es más rápido en JVM X" no es probable que sea válido en todos los casos a medida que se avanza hacia optimizaciones más agresivas.

Si su mercado / aplicación objetivo se ejecutará en gran medida en una arquitectura particular, debería considerar invertir en herramientas específicas para ello. * Si tu rendimiento en x86 es el factor crítico, entonces el VTune de Intel es excelente para profundizar en el tipo de análisis de salida de jit que describes. * Las diferencias entre JIT de 64 bits y 32 bits pueden ser considerables, especialmente en las plataformas x86 donde las convenciones de llamadas pueden cambiar y las oportunidades de enregistering son muy diferentes.

Obtenga las herramientas adecuadas

Es probable que desee obtener un generador de perfiles de muestreo. La sobrecarga de la instrumentación (y los inconvenientes asociados en cosas como la inflación, la contaminación del caché y la inflación del tamaño del código) para sus necesidades específicas sería demasiado grande. El analizador intel VTune puede usarse para Java, aunque la integración no es tan estrecha como otras.
Si está utilizando la JVM solar y está feliz de saber cuál es la última / mejor versión, entonces las opciones disponibles para investigar la salida de la JIT son considerables si conoce un poco de ensamblaje. Este artículo detalla algunos análisis interesantes usando esta funcionalidad

Aprende de otras implementaciones

El historial de cambio del historial indica que el ensamblaje en línea anterior era de hecho contraproducente y que permitir al compilador tomar el control total de la salida (con ajustes en el código en lugar de directivas en el ensamblaje) arrojó mejores resultados.

Algunos detalles

Dado que LZF es, en una implementación eficiente no administrada en un CPUS de escritorio moderno, en gran parte limitado al ancho de banda de memoria (por lo tanto, se lo compara con la velocidad de una memcpy no optimizada), necesitará que el código permanezca completamente dentro del nivel 1.
Como tal, cualquier campo estático que no pueda convertir en constantes debe colocarse dentro de la misma clase, ya que estos valores a menudo se colocarán dentro de la misma área de memoria dedicada a los vtables y metadatos asociados con las clases.

Las asignaciones de objetos que no pueden ser atrapadas por Escape Analysis (solo en 1.6 en adelante) deberán evitarse.

El código c hace un uso agresivo del desenrollado del lazo. Sin embargo, el rendimiento de este en VM más antiguas (1,4 era) depende en gran medida del modo en el que se encuentra la JVM . Aparentemente, las últimas versiones de sun jvm son más agresivas al enderezar y desenrollar, especialmente en el modo de servidor.

Las instrcciones de captación previa generadas por el JIT pueden marcar la diferencia en un código como este, que está cerca de la memoria encuadernada.

"Va directo hacia nosotros"

Tu objetivo se está moviendo, y continuará. Nuevamente la experiencia previa de Marc Lehmann:

el tamaño predeterminado de HLOG ahora es 15 (los cachés de la CPU han aumentado)

Incluso las pequeñas actualizaciones de jvm pueden implicar cambios importantes en el compilador

6544668 No incluye operaciones de matriz que no se pueden alinear en tiempo de ejecución. 6536652 Implemente algunas optimizaciones de superpalabras (SIMD) 6531696 no utilice el almacén de valores de 16 bits inmediato en la memoria en Intel cpus 6468290 Divida y asigne fuera de eden por cada CPU

Capitán Obvio

Medir, medir, medir SI puede hacer que su biblioteca incluya (en un dll separado) un punto de referencia simple y fácil de ejecutar que registra la información relevante (versión vm, CPU, sistema operativo, conmutadores de línea de comandos, etc.) y hace que enviarlo de vuelta a usted sea sencillo. aumentar su cobertura, lo mejor de todo es que cubrirá a las personas que lo usan que se preocupan.