¿El acceso a un único miembro de la estructura arrastra toda la estructura al caché?

Question

He estado leyendo Ulrich Drepper, "What every programmer should know about memory" y en la sección 3.3.2 Measurements of Cache Effects (en la mitad de la página) me da la impresión de que acceder a cualquier miembro de una estructura provoca que toda la estructura se arrastre a la memoria caché de la CPU.

¿Es esto correcto? Si es así, ¿cómo sabe el hardware sobre el diseño de estas estructuras? ¿O el código generado por el compilador fuerza de algún modo que se cargue toda la estructura?

O son las desaceleraciones del uso de estructuras más grandes, principalmente debido a la TLB causados ​​por las estructuras que se extendían a través de más páginas de memoria?

El struct ejemplo utilizado por Drepper es:

struct l { 
    struct l *n; 
    long int pad[NPAD]; 
    }; 

Dónde sizeof(l) se determina por NPAD es igual a 0, 7, 15 o 31 que resulta en estructuras que son 0, 56, 120, y 248 bytes aparte y suponiendo líneas de caché de 64 bytes y páginas de 4k.

Sólo iteración a través de la lista enlazada se pone significativamente más lento que la estructura crece, a pesar de que nada más que el puntero se está accediendo realidad.

Answer 1

El hardware no tiene ningún conocimiento sobre la estructura. Pero es cierto que el hardware carga en la memoria caché algunos bytes alrededor de los bytes a los que está accediendo. Esto se debe a que la línea de caché tiene un tamaño. No funciona en byte a byte, pero en p. Tamaño de 16 bytes a la vez.

Usted tiene que tener cuidado al hacer el pedido de los miembros de la estructura para que los miembros frecuentemente utilizados son cerca uno del otro. Por ejemplo, si usted tiene la siguiente estructura:

struct S { 
    int foo; 
    char name[64]; 
    int bar; 
}; 

Si el foo variables miembro y la barra se utilizan muy a menudo, el hardware se carga en la memoria caché los bytes alrededor foo, y cuando se le barra de acceso, que tendrá para cargar los bytes alrededor de la barra. Incluso si estos bytes alrededor de foo y alrededor de la barra nunca se usan. Ahora reescribir su estructura de la siguiente manera:

struct S { 
    int foo; 
    int bar; 
    char name[64]; 
}; 

Cuando se va a utilizar foo, el hardware se carga en la memoria caché los bytes alrededor de foo. Cuando use la barra, la barra ya estará en la memoria caché porque la barra está contenida en los bytes alrededor de foo. La CPU no tendrá que esperar que la barra esté en la memoria caché.

respuesta es: acceder a un solo miembro de la estructura no se tire toda la estructura en la memoria caché, pero tirar de algún otro miembro de la estructura en la memoria caché.

Answer 2

El hardware no se conoce el diseño de la estructura, pero sólo carga un número de bytes de todo el miembro accede a la memoria caché. Y sí, la desaceleración de las estructuras más grandes se debe a que luego se extenderán a más líneas de caché.

Answer 3

Por lo general, la caché L1 utiliza virtual addresses, si tiene acceso a un miembro de un struct, una cantidad específica de bytes se interpone en el caché (uno cache line, tamaño por lo general entre 8 y 512 bytes). Dado que todos los miembros struct están alineados uno junto al otro en la memoria, la posibilidad de que toda la estructura se pone en la memoria caché es algo grande (depende de sizeof(struct your_struct)) ...

Answer 4

Acceso a un miembro de la estructura hace que no más de una penalización de rendimiento de acceder cualquier otra área en la memoria. De hecho, puede haber una mejora en el rendimiento si accede a varios miembros de la estructura en la misma área, ya que el primer acceso puede almacenar en caché a otros miembros.

Answer 5

Mientras que la CPU puede ocuparse felizmente de cargas y tiendas tan pequeñas como de un byte, las cachés solo se ocupan de datos de tamaño "cacheline". En los libros de texto de arquitectura de computadora esto también se conoce como el "tamaño de bloque".

En la mayoría de los sistemas esto es 32 o 64 bytes. Puede ser diferente de una CPU a la siguiente, e incluso a veces de un nivel de memoria caché a la siguiente.

Además, algunas CPU realizan la captación previa especulativa; esto significa que si accede a las cachelines 5 y 6 en secuencia, intentará cargar la cacheline 7 sin que usted lo solicite.

Answer 6

"Solo iterar a través de la lista vinculada se vuelve significativamente más lento a medida que la estructura crece, aunque en realidad se está accediendo a nada más que al puntero".

Con NPAD = 0, cada línea de caché contiene 8 nodos de lista, por lo que puede ver por qué es el más rápido.

Con NPAD = 7, 15, 31, solo se debe cargar una línea de caché para cada nodo de la lista, y es posible que espere que todos tengan la misma velocidad: falta una caché por nodo. Pero un administrador de memoria moderno hará un almacenamiento en caché especulativo. Si tiene capacidad adicional (que probablemente sí lo hace, porque con la memoria moderna puede realizar múltiples lecturas en paralelo a la memoria principal), comenzará a cargar memoria cerca de la memoria que está utilizando. Aunque es una lista vinculada, si la construiste de alguna de las formas obvias, entonces hay una buena probabilidad de que estés accediendo a la memoria en secuencia. Por lo tanto, cuanto más cerca estén juntas en la memoria de los nodos de sus listas, más exitoso será el caché en términos de que ya tiene lo que necesita.

En el peor escenario posible, donde la memoria se extrae de swap mientras la usa, su programa estaría limitado por E/S de disco. Es posible que su tasa de progreso a través de la lista esté completamente determinada por la cantidad de nodos que haya por página, y es posible que vea que el tiempo empleado es directamente proporcional al tamaño del nodo, hasta 4k. No lo he intentado, sin embargo, y el sistema operativo será inteligente con el intercambio así como la MMU es inteligente con la memoria principal, por lo que no es necesariamente así de simple.