Técnicas para mantener los datos en el caché, localidad?

Question

Para el código de ultra-rápida que es esencial que mantengamos localidad de referencia- a mantener la mayor cantidad de datos que se utiliza junto estrechamente, en la caché de la CPU:

http://en.wikipedia.org/wiki/Locality_of_reference

¿Qué técnicas son para lograr esto? ¿Podría la gente dar ejemplos?

Me interesan los ejemplos de Java y C/C++. Es interesante saber cómo las personas usan para detener el intercambio de caché.

Saludos

Answer 1

Esto es probablemente demasiado genérico para tener una respuesta clara. Los enfoques en C o C++ en comparación con Java diferirán bastante (la forma en que el lenguaje establece los objetos difiere).

Lo básico sería, mantener los datos a los que se accederá en bucles cerrados juntos. Si su bucle opera en tipo T, y tiene miembros m1 ... mN, pero solo m1 ... m4 se usan en la ruta crítica, considere dividir T en T1 que contiene m1 ... m4 y T2 que contiene m4. ..Minnesota. Es posible que desee agregar a T1 un puntero que haga referencia a T2. Intente evitar los objetos que no están alineados con respecto a los límites de caché (depende de la plataforma).

Use contenedores contiguos (matriz antigua simple en C, vector en C++) e intente administrar las iteraciones para que suban o bajen, pero no salten aleatoriamente por todo el contenedor. Las listas son asesinas para la localidad, dos nodos consecutivos en una lista pueden estar en ubicaciones aleatorias completamente diferentes.

Los contenedores de objetos (y los genéricos) en Java también son un asesino, mientras que en un Vector las referencias son contiguas, los objetos reales no (hay un nivel extra de indirección). En Java hay muchas variables adicionales (si new dos objetos uno después del otro, los objetos probablemente terminen en ubicaciones de memoria casi contiguas, aunque habrá algo de información adicional (generalmente dos o tres punteros) de Datos de administración de objetos en el medio. GC moverá objetos, pero con suerte no empeorará las cosas de lo que era antes de ejecutarse.

Si se está enfocando en Java, cree estructuras de datos compactas, si tiene un objeto que tiene una posición, y que se debe acceder en un ciclo cerrado, considere mantener un tipo primitivo x y y dentro de su objeto en lugar de crear un Point y mantener una referencia. Los tipos de referencia deben actualizarse, y eso significa una diferente asignación, una indirección adicional y menos localidad.

Answer 2

En el mundo Java JIT se va a trabajar duro para lograr esto, y tratando de adivinar esto es probable que sea contraproducente. This SO question aborda los problemas específicos de Java de forma más completa.

Answer 3

Dos técnicas comunes incluyen:

• Minimalism (de tamaño de los datos y/o el tamaño del código/caminos)
• Uso de caché técnicas ajenos

ejemplo para minimalismo: En el trazado de rayos (un paradigma de renderización de gráficos 3D), es un enfoque común utilizar árboles Kd de 8 bytes para almacenar datos de escenas estáticas. El algoritmo transversal se ajusta a unas pocas líneas de código. Entonces, el árbol Kd a menudo se compila de una manera que minimiza el número de pasos transversales al tener nodos grandes y vacíos en la parte superior del árbol ("Heurística del área de superficie" de Havran).

Las predicciones erróneas suelen tener una probabilidad del 50%, pero son de menor costo, porque en realidad muchos nodos caben en una línea de caché (¡considere que obtiene 128 nodos por KiB!) Y uno de los dos nodos secundarios siempre un vecino directo en la memoria.

Ejemplo de técnicas de memoria oculta:Morton array indexing, también conocido como Z-order-curve-indexing. Este tipo de indexación puede ser preferible si usualmente se accede a elementos de matriz cercanos en una dirección impredecible. Esto podría ser valioso para datos de imagen o voxel de gran tamaño donde podría tener 32 o incluso 64 bytes de píxeles grandes, y luego millones de ellos (la típica cámara compacta es de megapíxeles, ¿no?) O incluso miles de millones para simulaciones científicas.

Sin embargo, ambas técnicas tienen una cosa en común: mantener las cosas más visitada con frecuencia cercana, la menor frecuencia cosas pueden estar más lejos, que abarca toda la gama de caché L1 sobre la memoria principal para el disco duro, a continuación, otros equipos de la misma habitación, habitación contigua, mismo país, en todo el mundo, otros planetas.

Answer 4

Algunos trucos al azar que vienen a la mente y que algunos de ellos he utilizado recientemente:

reconsiderar su algoritmo. Por ejemplo, tiene una imagen con una forma y el algoritmo de procesamiento que busca las esquinas de la forma. En lugar de operar en los datos de imagen directamente, puede preprocesarlo, guardar todas las coordenadas de píxeles de la forma en una lista y luego operar en la lista. Evita los saltos al azar alrededor de la imagen

Reducir los tipos de datos. Regular int tomará 4 bytes, y si logra utilizar, p. uint16_t caché 2x más cosas

A veces puede utilizar mapas de bits, lo usé para procesar una imagen binaria. Almacenaba píxeles por bit, por lo que podía caber 8 * 32 píxeles en una sola línea de caché. Se realmente aumentado el rendimiento

Formulario de Java, puede utilizar JNI (no es difícil) y poner en práctica su código crítico en C para controlar la memoria