programacion - java cache library

¿Qué puedo hacer en código Java para optimizar el almacenamiento en caché de la CPU?

Question

Al escribir un programa Java, ¿tengo influencia sobre cómo la CPU utilizará su caché para almacenar mis datos? Por ejemplo, si tengo una matriz a la que se accede mucho, ¿ayuda si es lo suficientemente pequeña como para caber en una línea de caché (típicamente 128 bytes en una máquina de 64 bits)? ¿Qué pasa si mantengo un objeto muy usado dentro de ese límite? ¿Puedo esperar que la memoria utilizada por sus miembros esté unida y permanezca en el caché?

Antecedentes: estoy construyendo un árbol digital comprimido, que está fuertemente inspirado en los arreglos de Judy , que están en C. Aunque estoy principalmente detrás de sus técnicas de compresión de nodos, Judy tiene la optimización del caché de CPU como un objetivo de diseño central y los tipos de nodo como así como la heurística para cambiar entre ellos está muy influenciada por eso. Me preguntaba si tengo alguna posibilidad de obtener esos beneficios, también?

Editar : El consejo general de las respuestas hasta ahora es, no intente micro-optimizar los detalles del nivel de la máquina cuando se está tan lejos de la máquina como en Java. Estoy totalmente de acuerdo, así que sentí que tenía que agregar algunos (con suerte) comentarios aclaratorios, para explicar mejor por qué creo que la pregunta todavía tiene sentido. Estos son a continuación:

Hay algunas cosas que generalmente son más fáciles de manejar para las computadoras debido a la forma en que se construyen. He visto que el código Java se ejecuta notablemente más rápido en datos comprimidos (desde la memoria), aunque la descompresión tuvo que usar ciclos de CPU adicionales. Si los datos se almacenaron en el disco, es obvio por qué eso es así, pero por supuesto en RAM es el mismo principio.

Ahora, las ciencias de la computación tienen mucho que decir sobre lo que son, por ejemplo, la ubicación de referencia es excelente en C y creo que sigue siendo genial en Java, tal vez incluso más, si ayuda a optimizar el tiempo de ejecución para hacer cosas más inteligentes. Pero cómo lo logras puede ser muy diferente. En C, podría escribir código que administre trozos de memoria más grandes y utilice punteros adyacentes para datos relacionados.

En Java, no puedo (y no quiero) saber mucho sobre cómo la memoria va a ser administrada por un tiempo de ejecución particular. Así que también tengo que llevar las optimizaciones a un mayor nivel de abstracción. Mi pregunta es básicamente, ¿cómo hago eso? Para la localidad de referencia, ¿qué significa "muy cerca" en el nivel de abstracción en el que estoy trabajando en Java? Mismo objeto? ¿El mismo tipo? Mismo conjunto?

En general, no creo que las capas de abstracción cambien las "leyes de la física", metafóricamente hablando. Duplicar su matriz en tamaño cada vez que se quede sin espacio es una buena estrategia en Java, incluso aunque ya no llame a malloc() .

Answer 1

A mi leal saber y entender: No. Basta con escribir en código máquina para obtener ese nivel de optimización. Con el ensamblaje estás a un paso de distancia porque ya no controlas dónde se almacenan las cosas. Con un compilador estás a dos pasos de distancia porque ni siquiera controlas los detalles del código generado. Con Java estás a tres pasos de distancia porque hay una JVM que interpreta tu código sobre la marcha.

No conozco construcciones en Java que te permitan controlar las cosas en ese nivel de detalle. En teoría, usted podría influir indirectamente en cómo organiza su programa y sus datos, pero está tan lejos que no veo cómo podría hacerlo de manera confiable, ni siquiera saber si estaba sucediendo o no.

Answer 2

Hasta ahora el consejo es bastante fuerte, en general es mejor no intentar y ser más astuto que el JIT. Pero como dices, algunos conocimientos sobre los detalles a veces son útiles.

Con respecto al diseño de memoria para objetos, Jvm de Sun (ahora Oracle) coloca objetos en memoria por tipo (es decir, dobles y largos primero, luego entradas y flotantes, luego cortos y caracteres, luego bytes y booleanos y finalmente referencias de objeto). Puede obtener más detalles aquí ..

Las variables locales generalmente se mantienen en la pila (es decir, referencias y tipos primitivos).

Como Nick menciona, la mejor forma de garantizar el diseño de la memoria en Java es mediante el uso de matrices primitivas. De esta forma, puede asegurarse de que los datos estén contiguos en la memoria. Sin embargo, tenga cuidado con los tamaños de matriz, los GC tienen problemas con arreglos grandes. También tiene la desventaja de que tienes que hacer algo de gestión de la memoria por ti mismo.

Por el lado positivo, puede usar un patrón de Flyweight para obtener facilidad de uso similar a Objetos mientras mantiene un rendimiento rápido.

Si necesita un empuje adicional en rendimiento, generar su propio bytecode sobre la marcha ayuda con algunos problemas, siempre que el código generado se ejecute suficientes veces y el caché de código nativo de su máquina virtual no se llene (lo que desactiva el JIT para todos los prácticos propósitos).

Answer 3

La clave para un buen rendimiento con Java es escribir código idiomático, en lugar de tratar de burlar el compilador JIT. Si escribe su código para tratar de influir en él para que haga las cosas de cierta manera en el nivel de instrucción nativo, es más probable que se pegue un tiro en el pie.

Eso no quiere decir que los principios comunes como la localidad de referencia no importen. Sí lo hacen, pero consideraría el uso de matrices y demás para ser código idiomático consciente del rendimiento, pero no "complicado".

HotSpot y otros tiempos de ejecución de optimización son extremadamente inteligentes sobre cómo optimizan el código para procesadores específicos. (Por ejemplo, revise esta discusión. ) Si fuera un experto programador de lenguaje de máquina, escribiría lenguaje de máquina, no Java. Y si no lo estoy, sería imprudente pensar que podría hacer un mejor trabajo optimizando mi código que los expertos.

Además, incluso si conoce la mejor manera de implementar algo para una CPU en particular, la belleza de Java es write-once-run-anywhere. Los trucos inteligentes para "optimizar" el código de Java tienden a dificultar las oportunidades de optimización para que el JIT lo reconozca. El código directo que se adhiere a las expresiones comunes es más fácil de reconocer para el optimizador. Por lo tanto, incluso cuando obtiene el mejor código Java para su banco de pruebas, ese código puede funcionar de manera horrible en una arquitectura diferente, o en el mejor de los casos, no aprovechar las ventajas de las mejoras en futuros JIT.

Si quieres un buen rendimiento, mantenlo simple. Los equipos de personas realmente inteligentes están trabajando para hacerlo rápido.

Answer 4

Si está por debajo de una mejora de unos pocos puntos porcentuales, ¡utilice C, donde obtendrá una mejora del 50-100%!

Si cree que la facilidad de uso de Java lo convierte en un mejor lenguaje para usar, entonces no lo arruine con optimizaciones cuestionables.

La buena noticia es que Java hará muchas cosas ocultas para mejorar su código en tiempo de ejecución, pero es casi seguro que no hará el tipo de optimizaciones de las que está hablando.

Si decide usar Java, simplemente escriba su código lo más claramente posible, no tome en cuenta las optimizaciones menores. (Los más importantes como usar las colecciones correctas para el trabajo correcto, no asignar / liberar objetos dentro de un bucle, etc. todavía valen la pena)

Answer 5

Si los datos que está procesando están primordial o totalmente compuestos de elementos primitivos (por ejemplo, en problemas numéricos), le aconsejaría lo siguiente.

Asigne una estructura plana de matrices de primitivas de tamaño fijo en el momento de la inicialización, y asegúrese de que los datos que contiene se compacten / desfragmente periódicamente (0-> n donde n es el índice máximo más pequeño posible dado el recuento de elementos), para iterar sobre el uso de un for-loop. Esta es la única manera de garantizar la asignación contigua en Java, y la compactación además sirve para mejorar la localidad de referencia. La compactación es beneficiosa, ya que reduce la necesidad de iterar sobre elementos no utilizados, reduciendo el número de condicionales: Como el ciclo for itera, la terminación ocurre antes, y menos iteración = menos movimiento a través del montón = menos posibilidades de que falte un caché. Mientras que la compactación crea una sobrecarga en sí misma, esto puede hacerse solo periódicamente (con respecto a las áreas principales de procesamiento), si así lo desea.

Aún mejor, puede intercalar valores en estas matrices preasignadas. Por ejemplo, si está representando transformaciones espaciales para muchos miles de entidades en el espacio 2D, y está procesando las ecuaciones de movimiento para cada una de ellas, puede tener un ciclo cerrado como

int axIdx, ayIdx, vxIdx, vyIdx, xIdx, yIdx;

//Acceleration, velocity, and displacement for each
//of x and y totals 6 elements per entity.
for (axIdx = 0; axIdx < array.length; axIdx += 6) 
{
    ayIdx = axIdx+1;
    vxIdx = axIdx+2;
    vyIdx = axIdx+3;
    xIdx = axIdx+4;
    yIdx = axIdx+5;

    //velocity1 = velocity0 + acceleration 
    array[vxIdx] += array[axIdx];
    array[vyIdx] += array[ayIdx];

    //displacement1 = displacement0 + velocity
    array[xIdx] += array[vxIdx];
    array[yIdx] += array[vxIdx];
}

Este ejemplo ignora cuestiones tales como la representación de aquellas entidades que utilizan sus asociados (x, y) ... la representación siempre requiere elementos no primitivos (por lo tanto, referencias / indicadores). Si necesita tales instancias de objetos, entonces ya no puede garantizar la referencia de la localidad, y probablemente saltará por todo el montón. Entonces, si puedes dividir tu código en secciones donde tienes un procesamiento intensivo como se muestra arriba, este enfoque te ayudará mucho. Para los juegos, al menos, AI, el terreno dinámico y la física pueden ser algunos de los aspectos más intensivos en el procesador, y son todos numéricos, por lo que este enfoque puede ser muy beneficioso.