¿Qué es un código “compatible con el caché”?

¿Cuál es la diferencia entre ” código hostil de caché ” y el códigocompatible con caché “?

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

Preliminares

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

(La analogía es que la memoria caché es para la memoria del sistema, ya que la memoria del sistema es para el almacenamiento en el disco duro. El almacenamiento en el disco duro es súper 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 (enlaces a continuación): boost el ancho de banda es fácil, pero no podemos comprar nuestra manera de salir de la latencia .

Los datos siempre se recuperan a través de la jerarquía de la memoria (más pequeño == más rápido a más lento). 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 me refiero al más grande == más lento. La tasa de aciertos de caché es crucial para el rendimiento, ya que cada caché falla al obtener 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 del caché (nivel más alto) generalmente solo requiere un puñado de ciclos.

En las architectures de computadoras modernas, el cuello de botella de rendimiento está dejando morir a la CPU (por ejemplo, acceder a la RAM o más). Esto solo empeorará con el tiempo. El aumento en la frecuencia del procesador actualmente no es relevante para boost el rendimiento. El problema es el acceso a memoria. Por lo tanto, los esfuerzos de diseño de hardware en las CPU se centran en gran medida en la optimización de cachés, captación previa, tuberías y concurrencia. Por ejemplo, las CPU modernas gastan alrededor del 85% de los 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 progtwigción adecuada:

  • La página de Agner Fog . En sus excelentes documentos, puede encontrar ejemplos detallados que cubren idiomas que van desde el ensamblaje hasta C ++.
  • Si le gustan los videos, le recomiendo echar un vistazo a la charla de Herb Sutter sobre architecture de máquinas (youtube) (específicamente, ¡marque las 12:00 en adelante!).
  • Diapositivas sobre la optimización de la memoria por Christer Ericson (director de tecnología @ Sony)
  • El artículo de LWN.net ” Lo que todo progtwigdor debería saber sobre la memoria

Conceptos principales para el código de caché

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

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

  1. Localidad temporal : cuando se accedía a una ubicación de memoria determinada, es probable que se vuelva a acceder 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 : esto 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 memoria RAM, normalmente se obtiene una mayor cantidad de memoria que la que se solicitó específicamente porque muy a menudo el progtwig requerirá esa información pronto. Los cachés de disco duro 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 contenedores apropiados de C ++

Un ejemplo simple de caché amigable versus no compatible con caché es el estándar de c ++ std::vector std::list . Los elementos de un std::vector se almacenan en la memoria contigua y, como tal, acceder a ellos es mucho más fácil de usar en caché que acceder a elementos en una std::list , que almacena su contenido en cualquier lugar. Esto se debe a la localidad espacial.

Bjarne Stroustrup nos ofrece una muy buena ilustración 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 de algoritmos

Siempre que sea posible, intente adaptar sus estructuras de datos y el orden de los cálculos de una manera que permita el uso máximo de la memoria caché. Una técnica común en este sentido es el locking de caché (versión de Archive.org) , que es de extrema importancia en la informática de alto rendimiento (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 column-major (por ejemplo, fortran , matlab ) vs. ordenamiento de filas principales (por ejemplo, c , c ++ ) para almacenar matrices bidimensionales. Por ejemplo, considere la siguiente matriz:

 1 2 3 4 

En ordenamiento de fila mayor, esto se almacena en la memoria como 1 2 3 4 ; en el ordenamiento de columna mayor 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 se recuperarán también y se almacenarán en una línea de caché. Si se explota la ordenación, esto dará como resultado menos accesos a la memoria (porque los siguientes valores que son necesarios para los cálculos posteriores ya están en una línea de caché).

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

Explotando el orden (por ejemplo, cambiando el índice de 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 ejemplo simple, explotar el orden aproximadamente duplica la velocidad de ejecución (ya que el acceso a la memoria requiere mucho más ciclos que el cálculo de las sums). En la práctica, la diferencia de rendimiento puede ser mucho mayor.

Evita las twigs impredecibles

Las architectures modernas cuentan con tuberías y los comstackdores se están volviendo muy buenos en la reordenación del código para minimizar las demoras debido al acceso a la memoria. Cuando su código crítico contiene twigs (impredecibles), es difícil o imposible precapturar datos. Esto conducirá indirectamente a más fallas en la caché.

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

Evitar funciones virtuales

En el contexto de c ++ , virtual métodos virtual 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 inducir errores de caché durante la búsqueda, pero esto solo ocurre si la función específica no se llama con frecuencia (de lo contrario, probablemente se almacenará en caché), por lo que algunos consideran que esto no es un problema. Para referencia sobre este tema, mira: ¿Cuál es el costo de rendimiento de tener un método virtual en una clase de C ++?

Problemas comunes

Un problema común en las architectures modernas con cachés multiprocesador se llama uso compartido falso . Esto ocurre cuando cada procesador individual intenta utilizar 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 hilos se hacen esperar induciendo errores de caché en esta situación. Ver también (gracias a @Matt para el enlace): ¿Cómo y cuándo alinearse al tamaño de la línea de caché?

Un síntoma extremo de un pobre almacenamiento en memoria caché en la memoria RAM (que probablemente no es lo que quiere decir en este contexto) es el llamado golpeteo . 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 instructivo clásico de código no compatible con caché es un código que escanea una matriz bidimensional C (por ejemplo, una imagen de bitmap) en forma de columna en lugar de hacerlo en filas.

Los elementos que están adyacentes en una fila también son adyacentes en la memoria, por lo que acceder a ellos en secuencia significa acceder a ellos en orden de memoria ascendente; esto es amigable con el caché, ya que el caché tiende a captar previamente los bloques de memoria contiguos.

En su lugar, acceder a dichos elementos en forma de columna es poco amigable, ya que los elementos en la misma columna están distantes entre ellos (en particular, su distancia es igual al tamaño de la fila), así que cuando usas este patrón de acceso, están saltando en la memoria, lo que puede desperdiciar el esfuerzo de la memoria 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 

a

 // Cache-unfriendly version - jumps around in memory for no good reason for(unsigned int x=0; x 

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

Optimizar el uso de la memoria caché se reduce 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 realmente tiene dos dimensiones: espacio y tiempo.

  • Espacial

La dimensión espacial también se reduce a dos cosas: en primer lugar, queremos empaquetar nuestra información de manera densa, para que más información encaje en esa memoria limitada. Esto significa (por ejemplo) que necesita una mejora importante en la complejidad computacional para justificar 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 ubiquen juntas. Un caché típico funciona en “líneas”, lo que significa que cuando se 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, la memoria caché puede cargar 128 o 256 bytes cerca de ese. Para aprovechar esto, generalmente desea disponer de los datos para maximizar la probabilidad de que también use los demás 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 rest de los datos en esa línea de caché es casi gratuito. 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 la cantidad 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.

Como ha etiquetado esto como C ++, señalaré un ejemplo clásico de un diseño relativamente hostil en caché: std::valarray . valarray sobrecarga la mayoría de los operadores aritméticos, por lo que puedo (por ejemplo) decir a = b + c + d; (donde a , b , c y d son todos valarrays) para agregar elementos de esas matrices.

El problema con esto es que pasa por un par de entradas, coloca los resultados de manera temporal, recorre otro par de entradas, y así sucesivamente. Con una gran cantidad de datos, el resultado de un cálculo puede desaparecer del caché antes de ser utilizado en el próximo 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]); , generalmente preferiríamos leer cada uno a[n] , b[n] , c[n] y d[n] una vez, hacer el cálculo, escribir el resultado, incrementar n y repetir hasta que hayamos terminado. 2

Line Sharing

El segundo factor importante es evitar compartir líneas. Para entender esto, probablemente necesitemos hacer una copia de seguridad y mirar un poco cómo se organizan los cachés. La forma más simple de caché se asigna directamente. Esto significa que una dirección en la memoria principal solo se puede almacenar en un lugar específico en la memoria caché. Si utilizamos dos elementos de datos que se asignan al mismo lugar en la memoria caché, funcionan mal: cada vez que utilizamos un elemento de datos, el otro debe eliminarse de la memoria caché para dejar espacio para la otra. El rest de la memoria caché puede estar vacía, pero esos elementos no usarán otras partes de la memoria caché.

Para evitar esto, la mayoría de los cachés son lo que se llama “conjunto asociativo”. Por ejemplo, en un caché asociativo conjunto de 4 vías, cualquier elemento de la memoria principal se puede almacenar en cualquiera de los 4 lugares diferentes en el caché. Entonces, cuando la memoria caché va a cargar un elemento, busca el elemento usado menos recientemente entre los cuatro, lo vacía a la memoria principal y carga el nuevo elemento en su lugar.

El problema es probablemente bastante obvio: para una memoria caché de mapeo directo, dos operandos que se asignan a la misma ubicación de caché pueden conducir a un mal comportamiento. Un caché asociativo conjunto de N vías aumenta el número de 2 a N + 1. Organizar un caché en más “formas” requiere un circuito adicional y, en general, funciona más lento, por lo que (por ejemplo) un caché asociativo de 8192 vías tampoco suele ser 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, el mapeo exacto de la dirección a la caché varía entre procesadores por lo demás similares. Sin embargo, en algunos casos, puede valer la pena asignar un gran búfer y, a continuación, usar solo partes de lo que asignó para garantizar que no se compartan datos en las mismas líneas de caché (aunque es probable que necesite detectar el procesador exacto y actuar en consecuencia para hacer esto).

  • Compartir falsamente

Hay otro elemento relacionado llamado “uso compartido falso”. Esto surge en un sistema multiprocesador o multinúcleo, donde dos (o más) procesadores / núcleos tienen datos que están separados, pero se encuentran en la misma línea de caché. Esto fuerza a los dos procesadores / núcleos a coordinar su acceso a los datos, aunque cada uno tiene su propio elemento de datos separado. Especialmente si los dos modifican los datos en alternancia, esto puede conducir a una desaceleración masiva, ya que los datos tienen que ser transportados constantemente entre los procesadores. Esto no se puede curar fácilmente organizando el caché en más “formas” o algo similar. La forma principal de evitarlo es garantizar 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 a 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 plantillas de expresión. Estoy bastante seguro de que la respuesta es que sí, que podría hacerse y que si fuera así, probablemente sería una victoria bastante sustancial. Sin embargo, no estoy al tanto de que alguien haya hecho eso, y dado lo poco que se usa el valarray , me sorprendería al menos ver que alguien también lo hace.

  2. En caso de que alguien se valarray cómo valarray (diseñado específicamente para el rendimiento) podría estar tan mal, se reduce a una cosa: fue diseñado para máquinas como los Crays antiguos, que usaban la 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 las memorias caché realmente no miden con precisión el elemento usado recientemente, pero utilizan alguna heurística que se pretende que sea similar sin tener que mantener un sello de tiempo completo para cada acceso.

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

Desde que etiquetó la pregunta con C ++, aquí está la mierda C ++ típica obligatoria. Las trampas de la progtwigción orientada a objetos de Tony Albrecht también son una excelente introducción al tema.

Simplemente acumulando: el ejemplo clásico de código no compatible con caché versus caché es el “locking de caché” de la matriz multiplicada.

Naive matrix multiplicaly se parece a

 for(i=0;i 

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

Hay muchas maneras 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 ciclo interno, use todos los elementos:

 int itemsPerCacheLine = CacheLineSize / sizeof(elemType); for(i=0;i 

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 de Fancier funcionan en mosaicos 2D, optimizan para cachés múltiples (L1, L2, TLB), y así sucesivamente.

Algunos resultados de googlear "locking 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 locking de caché optimizado.

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

Locking Tile 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 en el chip de la CPU. Tiene un 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 llegar a la memoria del sistema que no está en la CPU y es relativamente mucho más lento de acceder.

Lógicamente, para el conjunto de instrucciones de la CPU solo debe referirse a las direcciones de memoria en un espacio de direcciones virtuales gigantes. Cuando accedes a una sola dirección de memoria, la CPU irá a buscarla. en los viejos tiempos, obtenía solo esa única dirección. Pero hoy la CPU buscará un montón de memoria alrededor del bit que solicitó y lo copiará en el caché. Supone que si solicitó una dirección particular es muy probable que va a solicitar una dirección cercana muy pronto. Por ejemplo, si estuviera copiando un búfer, leería y escribiría desde direcciones consecutivas, una después de la otra.

Así que hoy, cuando recuperas una dirección, verifica el primer nivel de la memoria caché para ver si ya ha leído esa dirección en la memoria caché, si no la encuentra, esta es una falla de la memoria caché y debe pasar al siguiente nivel caché para encontrarlo, hasta que finalmente tenga que salir a la memoria principal.

El código compatible con caché intenta mantener los accesos muy juntos en la memoria para minimizar los errores de caché.

Así que un ejemplo sería imaginar que desea copiar una tabla gigante de dos dimensiones. Está organizado con la fila de acceso consecutiva en la memoria, y una fila sigue a la siguiente inmediatamente después.

Si copió los elementos una fila a la vez de izquierda a derecha, eso sería amigable con el caché. Si decidió copiar la tabla una columna a la vez, debería copiar la misma cantidad exacta de memoria, pero sería poco amigable con la memoria caché.

Es necesario aclarar que no solo los datos deben ser compatibles con la memoria caché, sino que también son tan importantes para el código. Esto se sum a la predicción de twigs, reordenamiento de instrucciones, evitando divisiones reales y otras técnicas.

Normalmente, cuanto más denso sea el código, menos líneas de caché se necesitarán 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 por todos lados, ya que normalmente requerirán una o más líneas de caché propias, lo que dará como resultado menos líneas de caché para los datos.

Una función debe comenzar en una dirección de alineación de línea de caché. Aunque hay conmutadores de comstackdor (gcc) para esto, tenga en cuenta que si las funciones son muy cortas, puede ser un desperdicio que cada una ocupe toda una línea de caché. 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 los resultados en dos líneas de caché están 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 constructos, compile y revise el tamaño y el perfil del código generado.

Como @Marc Claesen mencionó que una de las maneras 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 de caché amigable 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, el almacén de filas y el almacén de columnas. En la tienda de filas, como su nombre indica, las tuplas se almacenan en filas. Supongamos que una tabla llamada Product está almacenando tiene 3 atributos, es decir, int32_t key, char name[56] e int32_t price , por lo que el tamaño total de una tupla es de 64 bytes.

Podemos simular una ejecución de consulta de almacén de filas muy básica en la memoria principal creando una matriz de estructuras de Product con tamaño N, donde N es el número de filas en la tabla. Tal disposición de memoria también se llama matriz de estructuras. Entonces la estructura para el 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 tabla Product . Tal disposición de memoria también se llama struct of arrays. 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 el conjunto de estructuras (Diseño de filas) como las 3 matrices separadas (Diseño de columnas), tenemos el almacén de filas y el almacén de columnas en nuestra tabla Product presente en nuestra memoria.

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

 SELECT SUM(price) FROM PRODUCT 

Para la tienda de fila, podemos convertir la consulta SQL anterior en

 int sum = 0; for (int i=0; i 

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

 int sum = 0; for (int i=0; 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 filas en esta consulta, ya que solo requiere un subconjunto de atributos y en el diseño de columnas solo estamos haciendo eso, es decir, solo accediendo a la columna de precios.

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

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 ) tuple, porque nuestro tamaño de estructura de 64 bytes llena toda nuestra línea de caché, por lo que por cada tupla se produce una falta de caché en el caso de un diseño de fila.

En el caso del diseño de columnas cuando se lee una línea de caché, se lee el valor de 16 cacheline_size/price_int_size = 64/4 = 16 ( cacheline_size/price_int_size = 64/4 = 16 ), porque 16 valores de precios contiguos almacenados en la memoria se introducen en la caché, por lo que cada decimosexta tupla una falta de caché ocurre en caso de disposición 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 dicho experimento usando los datos de referencia de 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 sum, de modo que se convirtiera en memoria caché.

Tenga en cuenta que las memorias caché no solo almacenan en caché la memoria continua. Tienen múltiples líneas (al menos 4), por lo que la memoria discontinua y superpuesta a menudo se puede almacenar con la misma eficacia.

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