¿Cuál es la diferencia entre el " código hostil de caché " y el código " amigable de caché "?

¿Cómo puedo asegurarme de escribir código eficiente en caché?

Preliminares

En las computadoras modernas, solo las estructuras de memoria de nivel más bajo (los registros ) pueden mover datos en ciclos de un solo reloj. Sin embargo, los registros son muy caros y la mayoría de los núcleos de las computadoras tienen menos de una docena de registros (unos pocos cientos o quizás mil bytes en total). En el otro extremo del espectro de memoria ( DRAM ), la memoria es muy barata (es decir, literalmente millones de veces más barata ) pero tarda cientos de ciclos después de una solicitud para recibir los datos. Para cerrar esta brecha entre súper rápido y costoso y súper lento y barato están las memorias caché, llamado L1, L2, L3 en velocidad y costo decrecientes. La idea es que la mayoría del código de ejecución golpeará con frecuencia un pequeño conjunto de variables, y el resto (un conjunto de variables mucho más grande) con poca frecuencia. Si el procesador no puede encontrar los datos en la caché L1, entonces se ve en la caché L2. Si no está allí, entonces caché L3, y si no está allí, memoria principal. Cada uno de estos "errores" es costoso en el tiempo.

(La analogía es que la memoria caché es la memoria del sistema, ya que la memoria del sistema es demasiado almacenamiento en el disco duro. El almacenamiento en el disco duro es muy barato pero muy lento).

El almacenamiento en caché es uno de los principales métodos para reducir el impacto de la latencia . Parafraseando a Herb Sutter (cfr. Enlaces a continuación): aumentar el ancho de banda es fácil, pero no podemos salir de la latencia .

Los datos siempre se recuperan a través de la jerarquía de memoria (la más pequeña == la más rápida a la más lenta). Un hit / miss de caché generalmente se refiere a un hit / miss en el nivel más alto de caché en la CPU; por nivel más alto quiero decir el más grande == más lento. La tasa de aciertos de la memoria caché es crucial para el rendimiento, ya que cada falta de memoria caché da como resultado la obtención de datos de la RAM (o peor ...), lo que lleva mucho tiempo (cientos de ciclos para RAM, decenas de millones de ciclos para HDD). En comparación, la lectura de datos de la caché (nivel más alto) generalmente toma solo unos pocos ciclos.

En las arquitecturas informáticas modernas, el cuello de botella de rendimiento está dejando la matriz de la CPU (por ejemplo, acceder a RAM o superior). Esto solo empeorará con el tiempo. El aumento en la frecuencia del procesador ya no es relevante para aumentar el rendimiento. El problema es el acceso a la memoria. Los esfuerzos de diseño de hardware en las CPU, por lo tanto, actualmente se centran principalmente en la optimización de cachés, captación previa, canalizaciones y concurrencia. Por ejemplo, las CPU modernas gastan alrededor del 85% de los troqueles en cachés y hasta el 99% para almacenar / mover datos.

Hay mucho que decir sobre el tema. Aquí hay algunas referencias excelentes sobre cachés, jerarquías de memoria y programación adecuada:

• La página de Agner Fog . En sus excelentes documentos, puede encontrar ejemplos detallados que abarcan lenguajes que van desde el ensamblaje hasta C ++.
• Si le gustan los videos, le recomiendo que eche un vistazo a la charla de Herb Sutter sobre arquitectura de máquinas (youtube) (¡específicamente verifique las 12:00 en adelante!).
• Diapositivas sobre la optimización de la memoria por Christer Ericson (director de tecnología @ Sony)
• Artículo de LWN.net " Lo que todo programador debe saber sobre la memoria "

Conceptos principales para el código compatible con caché

Un aspecto muy importante del código compatible con caché tiene que ver con el principio de localidad , cuyo objetivo es colocar los datos relacionados en la memoria para permitir un almacenamiento en caché eficiente. En términos de la memoria caché de la CPU, es importante tener en cuenta las líneas de memoria caché para comprender cómo funciona: ¿cómo funcionan las líneas de memoria caché?

Los siguientes aspectos particulares son de gran importancia para optimizar el almacenamiento en caché:

1. Localidad temporal : cuando se accedió a una ubicación de memoria dada, es probable que se acceda nuevamente a la misma ubicación en el futuro cercano. Idealmente, esta información aún se almacenará en caché en ese punto.
2. Localidad espacial : se refiere a colocar datos relacionados cerca uno del otro. El almacenamiento en caché ocurre en muchos niveles, no solo en la CPU. Por ejemplo, cuando lee de la RAM, generalmente se obtiene una porción de memoria más grande de lo que se solicitó específicamente porque muy a menudo el programa requerirá esos datos pronto. Los cachés de HDD siguen la misma línea de pensamiento. Específicamente para cachés de CPU, la noción de líneas de caché es importante.

Use apropiado c ++ contenedores

Un ejemplo simple de caché amigable versus caché hostil es c ++'s std::vectorversus std::list. Los elementos de a std::vectorse almacenan en una memoria contigua y, como tal, acceder a ellos es mucho más amigable con la caché que acceder a elementos en a std::list, que almacena su contenido en todo el lugar. Esto se debe a la localidad espacial.

Bjarne Stroustrup da una muy buena ilustración de esto en este clip de YouTube (¡gracias a @Mohammad Ali Baydoun por el enlace!).

No descuides el caché en la estructura de datos y el diseño del algoritmo

Siempre que sea posible, intente adaptar sus estructuras de datos y el orden de los cálculos de manera que permita el uso máximo de la memoria caché. Una técnica común a este respecto es el bloqueo de caché (versión Archive.org) , que es de extrema importancia en la informática de alto rendimiento (cfr. Por ejemplo ATLAS ).

Conocer y explotar la estructura implícita de los datos.

Otro ejemplo simple, que muchas personas en el campo a veces olvidan es la columna mayor (ej. fortran,matlab) vs. ordenamiento de fila mayor (ej. C,c ++) para almacenar matrices bidimensionales. Por ejemplo, considere la siguiente matriz:

1 2
3 4

En el orden de filas principales, esto se almacena en la memoria como 1 2 3 4; en el orden de columnas principales, esto se almacenaría como 1 3 2 4. Es fácil ver que las implementaciones que no explotan este orden se encontrarán rápidamente con problemas de caché (¡fácilmente evitables!). Desafortunadamente, veo cosas como esta muy a menudo en mi dominio (aprendizaje automático). @MatteoItalia mostró este ejemplo con más detalle en su respuesta.

Al recuperar un determinado elemento de una matriz de la memoria, los elementos cercanos también se recuperarán y se almacenarán en una línea de caché. Si se explota el orden, esto dará como resultado menos accesos a la memoria (porque los siguientes valores que se necesitan para cálculos posteriores ya están en una línea de caché).

Para simplificar, suponga que la memoria caché comprende una sola línea de memoria caché que puede contener 2 elementos de matriz y que cuando un elemento determinado se recupera de la memoria, el siguiente también lo es. Digamos que queremos tomar la suma de todos los elementos en el ejemplo de matriz 2x2 anterior (vamos a llamarlo M):

Explotar el orden (por ejemplo, cambiar el índice de la columna primero en c ++):

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

No explotar el orden (por ejemplo, cambiar el índice de fila primero en c ++):

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

En este simple ejemplo, explotar el orden duplica aproximadamente la velocidad de ejecución (ya que el acceso a la memoria requiere muchos más ciclos que calcular las sumas). En la práctica, la diferencia de rendimiento puede ser mucho mayor.

Evitar ramas impredecibles

Las arquitecturas modernas cuentan con canalizaciones y los compiladores se están volviendo muy buenos reordenando el código para minimizar los retrasos debido al acceso a la memoria. Cuando su código crítico contiene ramas (impredecibles), es difícil o imposible obtener datos previamente. Esto conducirá indirectamente a más errores de caché.

Esto se explica muy bien aquí (gracias a @ 0x90 para el enlace): ¿Por qué procesar una matriz ordenada es más rápido que procesar una matriz no ordenada?

Evitar funciones virtuales

En el contexto de c ++, los virtualmétodos representan un tema controvertido con respecto a los errores de caché (existe un consenso general de que deben evitarse cuando sea posible en términos de rendimiento). Las funciones virtuales pueden provocar errores de caché durante la búsqueda, pero esto solo sucede si la función específica no se llama con frecuencia (de lo contrario, probablemente se almacenaría en caché), por lo que algunos consideran que no es un problema. Para referencia sobre este problema, consulte: ¿Cuál es el costo de rendimiento de tener un método virtual en una clase C ++?

Problemas comunes

Un problema común en las arquitecturas modernas con cachés multiprocesador se denomina intercambio falso . Esto ocurre cuando cada procesador individual intenta usar datos en otra región de memoria e intenta almacenarlos en la misma línea de caché . Esto hace que la línea de caché, que contiene datos que otro procesador puede usar, se sobrescriba una y otra vez. Efectivamente, diferentes subprocesos se hacen esperar al inducir errores de caché en esta situación. Ver también (gracias a @Matt por el enlace): ¿Cómo y cuándo alinearse con el tamaño de la línea de caché?

Un síntoma extremo de almacenamiento en caché deficiente en la memoria RAM (que probablemente no sea lo que quiere decir en este contexto) es la llamada paliza . Esto ocurre cuando el proceso genera continuamente fallas de página (por ejemplo, accede a la memoria que no está en la página actual) que requieren acceso al disco.

Además de la respuesta de @Marc Claesen, creo que un ejemplo clásico instructivo de código no apto para caché es el código que escanea una matriz bidimensional C (por ejemplo, una imagen de mapa de bits) en forma de columna en lugar de en forma de fila.

Los elementos adyacentes en una fila también son adyacentes en la memoria, por lo tanto, acceder a ellos en secuencia significa acceder a ellos en orden ascendente de memoria; Esto es compatible con la memoria caché, ya que la memoria caché tiende a captar previamente bloques contiguos de memoria.

En cambio, acceder a dichos elementos en forma de columna no es amigable con la memoria caché, ya que los elementos en la misma columna están distantes entre sí en memoria (en particular, su distancia es igual al tamaño de la fila), por lo que cuando usa este patrón de acceso, están saltando en la memoria, potencialmente desperdiciando el esfuerzo del caché de recuperar los elementos cercanos en la memoria.

Y todo lo que se necesita para arruinar el rendimiento es pasar de

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

a

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

Este efecto puede ser bastante dramático (varios órdenes de magnitudes en velocidad) en sistemas con cachés pequeños y / o trabajando con matrices grandes (por ejemplo, imágenes de más de 10 megapíxeles y 24 bpp en máquinas actuales); Por esta razón, si tiene que hacer muchos escaneos verticales, a menudo es mejor rotar la imagen de 90 grados primero y realizar varios análisis más tarde, limitando el código no compatible con el caché solo a la rotación.

La optimización del uso de caché se reduce en gran medida a dos factores.

Localidad de referencia

El primer factor (al que otros ya han aludido) es la localidad de referencia. Sin embargo, la localidad de referencia tiene dos dimensiones: espacio y tiempo.

• Espacial

La dimensión espacial también se reduce a dos cosas: primero, queremos empaquetar nuestra información densamente, para que quepa más información en esa memoria limitada. Esto significa (por ejemplo) que necesita una mejora importante en la complejidad computacional para justificar las estructuras de datos basadas en pequeños nodos unidos por punteros.

En segundo lugar, queremos que la información que se procesará en conjunto también se ubique en conjunto. Un caché típico funciona en "líneas", lo que significa que cuando accede a cierta información, otra información en direcciones cercanas se cargará en el caché con la parte que tocamos. Por ejemplo, cuando toco un byte, el caché puede cargar 128 o 256 bytes cerca de ese. Para aprovechar eso, generalmente desea que los datos se organicen para maximizar la probabilidad de que también use esos otros datos que se cargaron al mismo tiempo.

Para un ejemplo realmente trivial, esto puede significar que una búsqueda lineal puede ser mucho más competitiva con una búsqueda binaria de lo que cabría esperar. Una vez que haya cargado un elemento de una línea de caché, usar el resto de los datos en esa línea de caché es casi gratis. Una búsqueda binaria se vuelve notablemente más rápida solo cuando los datos son lo suficientemente grandes como para que la búsqueda binaria reduzca el número de líneas de caché a las que accede.

• Hora

La dimensión de tiempo significa que cuando realiza algunas operaciones en algunos datos, desea (tanto como sea posible) realizar todas las operaciones en esos datos a la vez.

Puesto que usted ha etiquetado esto como C ++, voy a señalar a un ejemplo clásico de un diseño relativamente caché hostil: std::valarray. valarraysobrecargas operadores aritméticos más, por lo que pueden (por ejemplo) dicen a = b + c + d;(donde a, b, cy dson todos valarrays) para hacer Además elemento a elemento de esas matrices.

El problema con esto es que atraviesa un par de entradas, coloca los resultados de forma temporal, recorre otro par de entradas, etc. Con una gran cantidad de datos, el resultado de un cálculo puede desaparecer del caché antes de usarse en el siguiente cálculo, por lo que terminamos leyendo (y escribiendo) los datos repetidamente antes de obtener nuestro resultado final. Si cada elemento del resultado final será algo así como (a[n] + b[n]) * (c[n] + d[n]);, en general, preferimos que nos gustaría leer cada una a[n], b[n], c[n]y d[n]una vez, hacer el cálculo, escribir el resultado, incremento ny repetir 'hasta que hemos terminado. ²

Line Sharing

El segundo factor importante es evitar el intercambio de líneas. Para comprender esto, probablemente necesitemos hacer una copia de seguridad y observar un poco cómo están organizados los cachés. La forma más simple de caché es el mapeo directo. Esto significa que una dirección en la memoria principal solo se puede almacenar en un lugar específico en la memoria caché. Si usamos dos elementos de datos que se asignan al mismo lugar en el caché, funciona mal: cada vez que usamos un elemento de datos, el otro tiene que ser eliminado del caché para dejar espacio para el otro. El resto del caché puede estar vacío, pero esos elementos no usarán otras partes del caché.

Para evitar esto, la mayoría de las memorias caché son lo que se denomina "conjunto asociativo". Por ejemplo, en un caché asociativo de conjuntos de 4 vías, cualquier elemento de la memoria principal se puede almacenar en cualquiera de los 4 lugares diferentes del caché. Entonces, cuando el caché va a cargar un elemento, busca el elemento ³ utilizado menos recientemente entre esos cuatro, lo vacía en la memoria principal y carga el nuevo elemento en su lugar.

El problema es probablemente bastante obvio: para una memoria caché asignada directamente, dos operandos que se asignan a la misma ubicación de memoria caché pueden conducir a un mal comportamiento. Un caché asociativo de conjuntos de N vías aumenta el número de 2 a N + 1. Organizar un caché en más "formas" requiere circuitos adicionales y generalmente funciona más lento, por lo que (por ejemplo) un caché asociativo de 8192 vías rara vez es una buena solución.

En última instancia, este factor es más difícil de controlar en código portátil. Su control sobre dónde se colocan sus datos suele ser bastante limitado. Peor aún, la asignación exacta de la dirección al caché varía entre procesadores similares. Sin embargo, en algunos casos, puede valer la pena hacer cosas como asignar un búfer grande y luego usar solo partes de lo que asignó para asegurarse de que los datos no compartan las mismas líneas de caché (aunque probablemente necesite detectar el procesador exacto y actuar en consecuencia para hacer esto).

• Falso intercambio

Hay otro elemento relacionado llamado "intercambio falso". Esto surge en un sistema multiprocesador o multinúcleo, donde dos (o más) procesadores / núcleos tienen datos separados, pero se encuentran en la misma línea de caché. Esto obliga a los dos procesadores / núcleos a coordinar su acceso a los datos, a pesar de que cada uno tiene su propio elemento de datos separado. Especialmente si los dos modifican los datos alternativamente, esto puede conducir a una desaceleración masiva ya que los datos deben ser constantemente transportados entre los procesadores. Esto no se puede curar fácilmente organizando el caché en más "formas" o algo así tampoco. La forma principal de prevenirlo es asegurarse de que dos subprocesos raramente (preferiblemente nunca) modifiquen datos que posiblemente podrían estar en la misma línea de caché (con las mismas advertencias sobre la dificultad de controlar las direcciones en las que se asignan los datos).

1. Aquellos que conocen bien C ++ podrían preguntarse si esto está abierto a la optimización a través de algo así como plantillas de expresión. Estoy bastante seguro de que la respuesta es sí, podría hacerse y, de ser así, probablemente sería una victoria bastante sustancial. Sin embargo, no estoy al tanto de que alguien lo haya hecho, y dado lo poco que valarrayse acostumbra, al menos me sorprendería ver que alguien también lo haga.

2. En caso de que alguien se pregunte cómo valarray(diseñado específicamente para el rendimiento) podría estar tan mal, todo se reduce a una cosa: realmente fue diseñado para máquinas como los Crays más antiguos, que usaban memoria principal rápida y sin caché. Para ellos, este realmente era un diseño casi ideal.

3. Sí, estoy simplificando: la mayoría de los cachés en realidad no miden con precisión el elemento utilizado menos recientemente, pero usan algo de heurística que pretende estar cerca de eso sin tener que mantener una marca de tiempo completa para cada acceso.

Bienvenido al mundo del diseño orientado a datos. El mantra básico es Ordenar, Eliminar Ramas, Lote, Eliminar virtualllamadas, todos los pasos hacia una mejor localidad.

Como etiquetó la pregunta con C ++, aquí está la típica tontería obligatoria de C ++ . Las trampas de la programación orientada a objetos de Tony Albrecht también es una gran introducción al tema.

Simplemente acumulando: el ejemplo clásico de código amigable con la caché versus código amigable con la caché es el "bloqueo de caché" de la matriz de multiplicación.

La matriz ingenua se ve así:

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k==;k<N;i++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

Si Nes grande, por ejemplo, si N * sizeof(elemType)es mayor que el tamaño del caché, entonces cada acceso a src2[k][j]será un error de caché.

Hay muchas formas diferentes de optimizar esto para un caché. Aquí hay un ejemplo muy simple: en lugar de leer un elemento por línea de caché en el bucle interno, use todos los elementos:

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k=0;k<N;k++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

Si el tamaño de la línea de caché es de 64 bytes, y estamos operando en flotantes de 32 bits (4 bytes), entonces hay 16 elementos por línea de caché. Y el número de errores de caché a través de esta simple transformación se reduce aproximadamente 16 veces.

Las transformaciones más sofisticadas operan en mosaicos 2D, optimizan para múltiples cachés (L1, L2, TLB), y así sucesivamente.

Algunos resultados de Google "bloqueo de caché":

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

Una buena animación de video de un algoritmo de bloqueo de caché optimizado.

http://www.youtube.com/watch?v=IFWgwGMMrh0

El mosaico de bucles está muy relacionado:

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

Los procesadores de hoy trabajan con muchos niveles de áreas de memoria en cascada. Entonces la CPU tendrá un montón de memoria que está en el chip de la CPU. Tiene acceso muy rápido a esta memoria. Hay diferentes niveles de caché, cada uno de acceso más lento (y más grande) que el siguiente, hasta que llegue a la memoria del sistema que no está en la CPU y es relativamente más lenta de acceder.

Lógicamente, para el conjunto de instrucciones de la CPU, solo se refieren a las direcciones de memoria en un espacio de direcciones virtual gigante. Cuando accede a una sola dirección de memoria, la CPU la buscará. en los viejos tiempos, obtendría solo esa dirección. Pero hoy, la CPU buscará un montón de memoria alrededor del bit que solicitó y la copiará en la memoria caché. Se supone que si solicitó una dirección en particular, es muy probable que solicite una dirección cercana muy pronto. Por ejemplo, si estuviera copiando un búfer, leería y escribiría desde direcciones consecutivas, una justo después de la otra.

Así que hoy, cuando busca una dirección, verifica el primer nivel de caché para ver si ya leyó esa dirección en caché, si no la encuentra, entonces esta es una falta de caché y tiene que pasar al siguiente nivel de caché para encontrarlo, hasta que finalmente tenga que salir a la memoria principal.

El código amigable de caché intenta mantener los accesos juntos en la memoria para minimizar las fallas de caché.

Entonces, un ejemplo sería imaginar que desea copiar una tabla gigante de 2 dimensiones. Se organiza con la fila de alcance en forma consecutiva en la memoria, y una fila sigue a la siguiente justo después.

Si copiara los elementos de una fila a la vez de izquierda a derecha, eso sería compatible con la memoria caché. Si decidiera copiar la tabla una columna a la vez, copiaría exactamente la misma cantidad de memoria, pero sería poco amigable para la caché.

Es necesario aclarar que no solo los datos deben ser compatibles con la memoria caché, sino que es igual de importante para el código. Esto se suma a la predicción de ramales, el reordenamiento de instrucciones, evitar divisiones reales y otras técnicas.

Por lo general, cuanto más denso sea el código, se necesitarán menos líneas de caché para almacenarlo. Esto da como resultado que haya más líneas de caché disponibles para los datos.

El código no debe llamar a funciones en todo el lugar, ya que generalmente requerirán una o más líneas de caché propias, lo que resulta en menos líneas de caché para los datos.

Una función debe comenzar en una dirección amigable de alineación de línea de caché. Aunque existen conmutadores de compilación (gcc) para esto, tenga en cuenta que si las funciones son muy cortas, puede ser un desperdicio que cada una ocupe una línea de caché completa. Por ejemplo, si tres de las funciones más utilizadas encajan dentro de una línea de caché de 64 bytes, esto es menos derrochador que si cada una tiene su propia línea y da como resultado dos líneas de caché menos disponibles para otro uso. Un valor de alineación típico podría ser 32 o 16.

Así que dedique un tiempo extra para hacer que el código sea denso. Pruebe diferentes construcciones, compile y revise el tamaño y el perfil del código generado.

Como @Marc Claesen mencionó que una de las formas de escribir código compatible con caché es explotar la estructura en la que se almacenan nuestros datos. Además de eso, otra forma de escribir código compatible con caché es: cambiar la forma en que se almacenan nuestros datos; luego escriba un nuevo código para acceder a los datos almacenados en esta nueva estructura.

Esto tiene sentido en el caso de cómo los sistemas de bases de datos linealizan las tuplas de una tabla y las almacenan. Hay dos formas básicas de almacenar las tuplas de una tabla, es decir, almacenar filas y almacenar columnas. En el almacén de filas, como su nombre indica, las tuplas se almacenan en filas. Supongamos que una tabla llamada que Productse almacena tiene 3 atributos, es decir , int32_t key, char name[56]y int32_t price, por lo tanto, el tamaño total de una tupla es 64bytes.

Podemos simular una ejecución de consulta de almacén de filas muy básica en la memoria principal creando una matriz de Productestructuras con tamaño N, donde N es el número de filas en la tabla. Tal diseño de memoria también se llama matriz de estructuras. Entonces, la estructura del Producto puede ser como:

struct Product
{
   int32_t key;
   char name[56];
   int32_t price'
}

/* create an array of structs */
Product* table = new Product[N];
/* now load this array of structs, from a file etc. */

De manera similar, podemos simular una ejecución de consulta de almacén de columnas muy básica en la memoria principal creando 3 matrices de tamaño N, una matriz para cada atributo de la Producttabla. Tal diseño de memoria también se denomina estructura de matrices. Entonces, las 3 matrices para cada atributo de Producto pueden ser como:

/* create separate arrays for each attribute */
int32_t* key = new int32_t[N];
char* name = new char[56*N];
int32_t* price = new int32_t[N];
/* now load these arrays, from a file etc. */

Ahora, después de cargar tanto la matriz de estructuras (diseño de fila) como las 3 matrices separadas (diseño de columna), tenemos el almacén de filas y el almacén de columnas en nuestra tabla Productpresentes en nuestra memoria.

Ahora pasamos a la parte del código amigable de caché. Suponga que la carga de trabajo en nuestra tabla es tal que tenemos una consulta de agregación sobre el atributo de precio. Como

SELECT SUM(price)
FROM PRODUCT

Para el almacén de filas podemos convertir la consulta SQL anterior en

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + table[i].price;

Para el almacén de columnas podemos convertir la consulta SQL anterior en

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + price[i];

El código para el almacén de columnas sería más rápido que el código para el diseño de la fila en esta consulta, ya que solo requiere un subconjunto de atributos y en el diseño de la columna estamos haciendo exactamente eso, es decir, solo acceder a la columna de precios.

Suponga que el tamaño de la línea de caché es 64bytes.

En el caso del diseño de filas cuando se lee una línea de caché, se lee el valor de precio de solo 1 ( cacheline_size/product_struct_size = 64/64 = 1) tupla, porque nuestro tamaño de estructura de 64 bytes y llena toda nuestra línea de caché, por lo que por cada tupla se produce una pérdida de caché en caso de que de un diseño de fila.

En el caso del diseño de columna cuando se lee una línea de caché, se lee el valor de precio de 16 ( cacheline_size/price_int_size = 64/4 = 16) tuplas, porque 16 valores de precio contiguos almacenados en la memoria se llevan al caché, por lo que por cada decimosexta tupla se produce una pérdida de caché en caso de diseño de columna.

Por lo tanto, el diseño de la columna será más rápido en el caso de una consulta dada, y es más rápido en dichas consultas de agregación en un subconjunto de columnas de la tabla. Puede probar tal experimento usted mismo utilizando los datos del punto de referencia TPC-H y comparar los tiempos de ejecución para ambos diseños. El artículo de wikipedia sobre sistemas de bases de datos orientados a columnas también es bueno.

Entonces, en los sistemas de bases de datos, si la carga de trabajo de la consulta se conoce de antemano, podemos almacenar nuestros datos en diseños que se adaptarán a las consultas en la carga de trabajo y acceder a los datos de estos diseños. En el caso del ejemplo anterior, creamos un diseño de columna y cambiamos nuestro código para calcular la suma de modo que se volviera amigable con la caché.

Tenga en cuenta que los cachés no solo almacenan en caché la memoria continua. Tienen varias líneas (al menos 4), por lo que la memoria discontinua y superpuesta a menudo se puede almacenar con la misma eficiencia.

Lo que falta en todos los ejemplos anteriores son puntos de referencia medidos. Hay muchos mitos sobre el rendimiento. A menos que lo midas, no lo sabes. No complique su código a menos que tenga una mejora medida .