Pregunta ¿Qué es un código "compatible con el caché"?


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

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


612
2018-05-22 18:37


origen


Respuestas:


Preliminares

En las computadoras modernas, solo las estructuras de memoria de nivel más bajo (el registros) puede 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 tal vez mil bytes total). En el otro extremo del espectro de la memoria (DRACMA), la memoria es muy barata (es decir, literalmente millones de veces más barato) pero toma 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 memoria caché, llamado 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 resto (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 estado latente (cfr. la charla de Herb Sutter que relacioné al comienzo). Parafraseando a Herb Sutter (consulte los enlaces a continuación): aumentar 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 caché al azar por lo general 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 caché es crucial para el rendimiento, ya que cada falta de caché da como resultado la obtención de datos de la RAM (o peor ...) que toma mucho de 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 arquitecturas informáticas modernas, el cuello de botella de rendimiento está dejando que la CPU muera (por ejemplo, accediendo a RAM o superior). Esto solo empeorará con el tiempo. El aumento en la frecuencia del procesador actualmente no es relevante para aumentar 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 programación adecuada:

Conceptos principales para el código de caché

Un aspecto muy importante del código de caché es todo acerca de el principio de localidad, cuyo objetivo es ubicar 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 accedió 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 el 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 programa 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 apropiado  contenedores

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

Bjarne Stroustrup presenta una muy buena ilustración de esto 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 bloqueo de caché  (Versión de Archive.org), que es de extrema importancia en la informática de alto rendimiento (por ejemplo, cfr. 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 (ej. ,) vs. ordenamiento de fila mayor (ej. ,) para almacenar matrices bidimensionales. Por ejemplo, considere la siguiente matriz:

1 2
3 4

En ordenamiento de fila principal, esto se almacena en la memoria como 1 2 3 4; en el orden de la columna principal 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!). Lamentablemente, 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 suma de todos los elementos en la matriz de ejemplo 2x2 anterior (vamos a llamarlo M)

Explotar el orden (por ejemplo, cambiar el índice de columna primero en )

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 )

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 sumas). En la práctica, la diferencia de rendimiento puede ser mucho más grande.

Evita las ramas impredecibles

Las arquitecturas modernas cuentan con tuberías y los compiladores 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 ramas (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 sin clasificar?

Evitar funciones virtuales

En el contexto de , virtual los métodos representan un tema controvertido con respecto a fallas en el 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 arquitecturas modernas con cachés multiprocesador se llama compartir falsamente. Esto ocurre cuando cada procesador individual está tratando de usar datos en otra región de memoria e intenta almacenarlos en el mismo 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 por 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 caché en la memoria RAM (que probablemente no es lo que quiere decir en este contexto) es el llamado 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.


798
2018-05-22 18:39



Además de la respuesta de @Marc Claesen, creo que un ejemplo instructivo clásico de código poco amigable es el código que escanea una matriz bidimensional C (por ejemplo, una imagen de mapa de bits) en lugar de 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<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 grandes matrices (por ejemplo, imágenes de más de 10 bps de 10 megapíxeles 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.


121
2018-05-22 19:51



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 resto 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 al caché: std::valarray. valarray sobrecarga la mayoría de los operadores aritméticos, por lo que puedo (por ejemplo) decir a = b + c + d; (dónde 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 preferimos leer cada a[n], b[n], c[n] y d[n] una vez, haga el cálculo, escriba el resultado, incremente n y repite hasta que terminemos.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 resto 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é. Por lo tanto, cuando la memoria caché va a cargar un elemento, busca el menos utilizado recientemente3 elemento entre esos 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 conozco a nadie que haya hecho eso, y dado lo poco que valarray se acostumbra, me sorprendería al menos ver que alguien lo hace tampoco.

  2. En caso de que alguien se pregunte cómo valarray (diseñado específicamente para el rendimiento) podría ser tan malo, se reduce a una cosa: realmente fue diseñado para máquinas como las antiguas Crays, 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.


74
2018-05-31 18:18



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

Desde que etiquetó la pregunta con C ++, aquí está el obligatorio típica mierda C ++. Tony Albrecht de Errores de programación orientada a objetos es también una gran introducción al tema.


28
2018-05-22 21:03



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

Naive matrix multiplicaly se parece a

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 N es grande, p. Si N * sizeof(elemType) es mayor que el tamaño de caché, luego cada acceso 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<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k==;k<N;i++) {
         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 de Fancier funcionan en mosaicos 2D, optimizan para cachés múltiples (L1, L2, TLB), y así sucesivamente.

Algunos resultados de googlear "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

Locking Tile está muy relacionado:

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


20
2018-05-29 03:50



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é.


12
2018-05-22 19:58



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 suma a la predicción de ramas, 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 compilador (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.


4
2017-08-08 17:50



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 una tabla llamada Product ser almacenado tiene 3 atributos, es decir int32_t key, char name[56] y int32_t price, entonces el tamaño total de una tupla es 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 Product estructura 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 Productmesa. 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 la matriz de estructuras (Diseño de filas) como las 3 matrices separadas (Diseño de columnas), tenemos una tienda de filas y un almacén de columnas en nuestra mesa 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<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 filas en esta consulta, ya que solo requiere un subconjunto de atributos y, en el diseño de columnas, estamos haciendo exactamente eso, es decir, solo accediendo a la columna de precios.

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

En el caso del diseño de filas cuando se lee una línea de caché, el valor de precio de solo 1 (cacheline_size/product_struct_size = 64/64 = 1) tuple se lee, 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 falta de caché en el caso de un diseño de fila.

En el caso del diseño de columna cuando se lee una línea de caché, el valor de precio de 16 (cacheline_size/price_int_size = 64/4 = 16) tuples se lee, porque 16 valores de precios contiguos almacenados en la memoria se llevan a la memoria caché, de modo que por cada decimosexta tupla se produce una falla en la caché en el caso del diseño de la 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 ese experimento usted mismo usando los datos de TPC-H punto de referencia, y comparar los tiempos de ejecución para ambos diseños. los wikipedia el artículo 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 convirtiera en memoria caché.


1
2018-03-30 02:19