¿Por qué mi caché L3 de 8M no proporciona ningún beneficio para matrices de más de 1M?
Me inspiré en esta pregunta para escribir un programa simple para probar el ancho de banda de memoria de mi máquina en cada nivel de caché:
Por qué vectorizar el bucle no tiene mejora de rendimiento
Mi código usa memset para escribir en un búfer (o búferes) una y otra vez y mide la velocidad. También guarda la dirección de cada búfer para imprimir al final. Aquí está el listado:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#define SIZE_KB {8, 16, 24, 28, 32, 36, 40, 48, 64, 128, 256, 384, 512, 768, 1024, 1025, 2048, 4096, 8192, 16384, 200000}
#define TESTMEM 10000000000 // Approximate, in bytes
#define BUFFERS 1
double timer(void)
{
struct timeval ts;
double ans;
gettimeofday(&ts, NULL);
ans = ts.tv_sec + ts.tv_usec*1.0e-6;
return ans;
}
int main(int argc, char **argv)
{
double *x[BUFFERS];
double t1, t2;
int kbsizes[] = SIZE_KB;
double bandwidth[sizeof(kbsizes)/sizeof(int)];
int iterations[sizeof(kbsizes)/sizeof(int)];
double *address[sizeof(kbsizes)/sizeof(int)][BUFFERS];
int i, j, k;
for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
iterations[k] = TESTMEM/(kbsizes[k]*1024);
for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
{
// Allocate
for (j = 0; j < BUFFERS; j++)
{
x[j] = (double *) malloc(kbsizes[k]*1024);
address[k][j] = x[j];
memset(x[j], 0, kbsizes[k]*1024);
}
// Measure
t1 = timer();
for (i = 0; i < iterations[k]; i++)
{
for (j = 0; j < BUFFERS; j++)
memset(x[j], 0xff, kbsizes[k]*1024);
}
t2 = timer();
bandwidth[k] = (BUFFERS*kbsizes[k]*iterations[k])/1024.0/1024.0/(t2-t1);
// Free
for (j = 0; j < BUFFERS; j++)
free(x[j]);
}
printf("TESTMEM = %ld\n", TESTMEM);
printf("BUFFERS = %d\n", BUFFERS);
printf("Size (kB)\tBandwidth (GB/s)\tIterations\tAddresses\n");
for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
{
printf("%7d\t\t%.2f\t\t\t%d\t\t%x", kbsizes[k], bandwidth[k], iterations[k], address[k][0]);
for (j = 1; j < BUFFERS; j++)
printf(", %x", address[k][j]);
printf("\n");
}
return 0;
}
Y los resultados (con TAMPONES = 1):
TESTMEM = 10000000000
BUFFERS = 1
Size (kB) Bandwidth (GB/s) Iterations Addresses
8 52.79 1220703 90b010
16 56.48 610351 90b010
24 57.01 406901 90b010
28 57.13 348772 90b010
32 45.40 305175 90b010
36 38.11 271267 90b010
40 38.02 244140 90b010
48 38.12 203450 90b010
64 37.51 152587 90b010
128 36.89 76293 90b010
256 35.58 38146 d760f010
384 31.01 25431 d75ef010
512 26.79 19073 d75cf010
768 26.20 12715 d758f010
1024 26.20 9536 d754f010
1025 18.30 9527 90b010
2048 18.29 4768 d744f010
4096 18.29 2384 d724f010
8192 18.31 1192 d6e4f010
16384 18.31 596 d664f010
200000 18.32 48 cb2ff010
Puedo ver fácilmente el efecto de la caché L1 de 32K y la caché L2 de 256K. Lo que no entiendo es por qué el rendimiento cae repentinamente después de que el tamaño del búfer de memset excede 1M. Se supone que mi caché L3 es de 8M. Sucede tan repentinamente también, no se reduce en absoluto como cuando se excedió el tamaño de la caché L1 y L2.
Mi procesador es el Intel i7 3700. Los detalles de la caché L3 de /sys/devices/system/cpu/cpu0/cache son:
level = 3
coherency_line_size = 64
number_of_sets = 8192
physical_line_partition = 1
shared_cpu_list = 0-7
shared_cpu_map = ff
size = 8192K
type = Unified
ways_of_associativity = 16
Pensé que intentaría usar múltiples buffers-llamar a memset en 2 buffers de 1M cada uno y ver si el rendimiento caería. Con BUFFERS = 2, obtengo:
TESTMEM = 10000000000
BUFFERS = 2
Size (kB) Bandwidth (GB/s) Iterations Addresses
8 54.15 1220703 e59010, e5b020
16 51.52 610351 e59010, e5d020
24 38.94 406901 e59010, e5f020
28 38.53 348772 e59010, e60020
32 38.31 305175 e59010, e61020
36 38.29 271267 e59010, e62020
40 38.29 244140 e59010, e63020
48 37.46 203450 e59010, e65020
64 36.93 152587 e59010, e69020
128 35.67 76293 e59010, 63769010
256 27.21 38146 63724010, 636e3010
384 26.26 25431 63704010, 636a3010
512 26.19 19073 636e4010, 63663010
768 26.20 12715 636a4010, 635e3010
1024 26.16 9536 63664010, 63563010
1025 18.29 9527 e59010, f59420
2048 18.23 4768 63564010, 63363010
4096 18.27 2384 63364010, 62f63010
8192 18.29 1192 62f64010, 62763010
16384 18.31 596 62764010, 61763010
200000 18.31 48 57414010, 4b0c3010
Parece que ambos buffers de 1M permanecen en la caché L3. Pero trate de aumentar el tamaño de cualquiera de los búfer muy ligeramente y el rendimiento disminuye.
He estado compilando con-O3. No hace mucha diferencia (excepto posiblemente desenrollar los bucles sobre BUFFERS). Probé con-O0 y es lo mismo excepto por las velocidades L1. la versión gcc es 4.9.1.
Para resumir, tengo una 2 parte pregunta:
- ¿Por qué mi caché L3 de 8 MB no proporciona ningún beneficio en bloques de memoria de más de 1 M?
- ¿Por qué la caída en el rendimiento es tan repentina?
EDITAR:
Como sugirió Gabriel Southern, corrí mi código con perf usando BUFFERS=1 con solo un tamaño de búfer a la vez. Este fue el mandato completo:
perf stat -e dTLB-loads,dTLB-load-misses,dTLB-stores,dTLB-store-misses -r 100 ./a.out 2> perfout.txt
El -r significa que perf ejecutará un. out 100 veces y devolverá el promedio estadísticas.
La salida de perf, con #define SIZE_KB {1024}:
Performance counter stats for './a.out' (100 runs):
1,508,798 dTLB-loads ( +- 0.02% )
0 dTLB-load-misses # 0.00% of all dTLB cache hits
625,967,550 dTLB-stores ( +- 0.00% )
1,503 dTLB-store-misses ( +- 0.79% )
0.360471583 seconds time elapsed ( +- 0.79% )
Y con #define SIZE_KB {1025}:
Performance counter stats for './a.out' (100 runs):
1,670,402 dTLB-loads ( +- 0.09% )
0 dTLB-load-misses # 0.00% of all dTLB cache hits
626,099,850 dTLB-stores ( +- 0.00% )
2,115 dTLB-store-misses ( +- 2.19% )
0.503913416 seconds time elapsed ( +- 0.06% )
Así que parece que hay más errores de TLB con el búfer de 1025K. Sin embargo, con este buffer de tamaño, el programa hace alrededor de 9500 llamadas de memset, por lo que todavía es menos de 1 miss por llamada memset.
3 answers
Respuesta corta:
Su versión de memset comienza a usar almacenes no temporales al inicializar una región de memoria mayor que 1 MB. Como resultado, la CPU no almacena estas líneas en su caché, a pesar de que su caché L3 es mayor que 1 MB. En consecuencia, el rendimiento está limitado por el ancho de banda de memoria disponible en el sistema para valores de búfer mayores de 1 MB.
Detalles:
Antecedentes:
Probé el código que proporcionaste en varios sistemas diferentes e inicialmente se centró en la investigación de la TLB porque pensé que podría haber una paliza en el nivel 2 TLB. Sin embargo, ninguno de los datos que recogí confirmó esa hipótesis.
Algunos de los sistemas que probé usaron Arch Linux que tiene la última versión de glibc, mientras que otros usaron Ubuntu 10.04 que usa una versión anterior de eglibc. Pude reproducir el comportamiento descrito en la pregunta al usar un binario vinculado estáticamente al probar con múltiples CPU diferentes arquitectura. El comportamiento en el que me centré fue una diferencia significativa en el tiempo de ejecución entre cuando SIZE_KB era 1024 y cuando era 1025. La diferencia de rendimiento se explica por un cambio en el código ejecutado para las versiones lenta y rápida.
Código de montaje
Usé perf record y perf annotate para recopilar un rastro del código ensamblador en ejecución para ver cuál era la ruta del código caliente. El código se muestra a continuación utilizando el siguiente formato:
percentage time executing instruction | address | instruction.
He copió el hot loop de la versión más corta que omite la mayor parte de la dirección y tiene una línea que conecta el borde posterior del bucle y el encabezado del bucle.
Para la versión compilada en Arch Linux el hot loop fue (para ambos tamaños 1024 y 1025):
2.35 │a0:┌─+movdqa %xmm8,(%rcx)
54.90 │ │ movdqa %xmm8,0x10(%rcx)
32.85 │ │ movdqa %xmm8,0x20(%rcx)
1.73 │ │ movdqa %xmm8,0x30(%rcx)
8.11 │ │ add $0x40,%rcx
0.03 │ │ cmp %rcx,%rdx
│ └──jne a0
Para el binario Ubuntu 10.04 el hot loop cuando se ejecuta con un tamaño de 1024 fue:
│a00:┌─+lea -0x80(%r8),%r8
0.01 │ │ cmp $0x80,%r8
5.33 │ │ movdqa %xmm0,(%rdi)
4.67 │ │ movdqa %xmm0,0x10(%rdi)
6.69 │ │ movdqa %xmm0,0x20(%rdi)
31.23 │ │ movdqa %xmm0,0x30(%rdi)
18.35 │ │ movdqa %xmm0,0x40(%rdi)
0.27 │ │ movdqa %xmm0,0x50(%rdi)
3.24 │ │ movdqa %xmm0,0x60(%rdi)
16.36 │ │ movdqa %xmm0,0x70(%rdi)
13.76 │ │ lea 0x80(%rdi),%rdi
│ └──jge a00
Para la versión Ubuntu 10.04 que se ejecuta con un tamaño de búfer de 1025, el hot loop fue:
│a60:┌─+lea -0x80(%r8),%r8
0.15 │ │ cmp $0x80,%r8
1.36 │ │ movntd %xmm0,(%rdi)
0.24 │ │ movntd %xmm0,0x10(%rdi)
1.49 │ │ movntd %xmm0,0x20(%rdi)
44.89 │ │ movntd %xmm0,0x30(%rdi)
5.46 │ │ movntd %xmm0,0x40(%rdi)
0.02 │ │ movntd %xmm0,0x50(%rdi)
0.74 │ │ movntd %xmm0,0x60(%rdi)
40.14 │ │ movntd %xmm0,0x70(%rdi)
5.50 │ │ lea 0x80(%rdi),%rdi
│ └──jge a60
La diferencia clave aquí es que la la versión más lenta usaba movntd instrucciones, mientras que las versiones más rápidas usaban movdqa instrucciones. El manual de Desarrolladores de software de Intel dice lo siguiente sobre las tiendas no temporales:
Para el tipo de memoria WC en particular, el procesador nunca parece leer los datos en la jerarquía de caché. En cambio, la pista no temporal puede se implementará cargando un búfer interno temporal con el equivalente a una línea de caché alineada sin llenar estos datos a la cache.
Así que esto parece explicar el comportamiento donde usar memset con valores mayores a 1 MB no encaja en la caché. La siguiente pregunta es por qué hay una diferencia entre el sistema Ubuntu 10.04 y el sistema Arch Linux, y por qué se selecciona 1 MB como punto de corte. Para investigar esa pregunta miré el código fuente de glibc:
Código Fuente para memset
Mirando el repositorio git de glibc en sysdeps/x86_64/memset.S el primer commit que encontré interesante fue b2b671b677d92429a3d41bf451668f476aa267ed
La descripción del commit es:
Memset más rápido en x64
Esta implementación acelera memset de varias maneras. Lo primero es evitar costoso salto computado. Segundo es el uso de hecho de que los argumentos de memset se alinean la mayor parte del tiempo a 8 bytes.
Resultados de Benchmark en: kam.mff.cuni.cz / ~ondra/benchmark_string / memset_profile_result27_04_13.tar.bz2
Y el sitio web referenciado tiene algunos datos de perfiles interesantes.
El diff de la confirmación muestra que el código para memset se simplifica mucho y se eliminan los almacenes no temporales. Esto coincide con lo que muestra el código perfilado de Arch Linux.
Mirando el código anterior Vi que la elección de si usar almacenes no temporales parecía hacer uso de un valor descrito como The largest cache size
L(byte32sse2_pre):
mov __x86_shared_cache_size(%rip),%r9d # The largest cache size
cmp %r9,%r8
ja L(sse2_nt_move_pre)
El código para calcular esto está en: sysdeps/x86_64/cacheinfo.c
Aunque parece que hay código para calcular el tamaño real de la caché compartida, el valor predeterminado también es 1 MB :
long int __x86_64_shared_cache_size attribute_hidden = 1024 * 1024;
Así que sospecho que se está utilizando el valor predeterminado, pero puede haber alguna otra razón por la que el código esté seleccionando 1MB como punto de corte.
En cualquier caso, la respuesta general a su pregunta parece ser que la versión de memset en su sistema está utilizando almacenes no temporales cuando configuración de una región de memoria superior a 1 MB.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-05-20 16:36:47
Dado el desmontaje de Gabriel del código de ensamblado generado, creo que este es de hecho el problema [Editar: su respuesta fue editada, ahora aparece como la causa raíz, así que estamos de acuerdo]:
Tenga en cuenta que movnt es una tienda de streaming, que puede tener (dependiendo de la implementación micro-arquitectónica exacta) varios impactos:
- Tiene una semántica de ordenación débil (lo que le permite ser más rápido).
- Ha mejorado la latencia si sobrescribe una línea completa (no es necesario obtener datos anteriores y fusión).
- Tiene una pista no temporal, por lo que es incaqueable.
#1 y #2 pueden mejorar la latencia y el ancho de banda de estas operaciones si están vinculadas a la memoria, pero #3 básicamente las obliga a estar vinculadas a la memoria incluso si podrían caber en algún nivel de caché. Esto probablemente supera los beneficios, ya que la latencia de memoria/BW son significativamente peores para empezar.
Por lo tanto, su implementación de la biblioteca de memset probablemente esté usando un umbral incorrecto para cambiar a versión de streaming-stores (supongo que no se molesta en comprobar el tamaño de su LLC, pero suponiendo que 1M es residente de memoria es bastante extraño). Sugiero probar bibliotecas alternativas, o deshabilitar la capacidad del compilador para generarlas (si es compatible).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-07-28 05:48:22
Su benchmark solo está escribiendo en memoria, nunca leyendo, usando memset que probablemente esté inteligentemente diseñado para no leer nada de la caché en la memoria. Puede muy bien ser que con este código, donde solo se utiliza la mitad de la capacidad de la memoria caché, simplemente no hay ganancia de rendimiento en comparación con la memoria raw. El hecho de que escribir en memoria raw esté bastante cerca de la velocidad L2 puede ser una pista. Si L2 se ejecuta a 26 GB / seg, la memoria principal a 18 GB / seg, ¿qué puede esperar realmente para la caché L3?
Está midiendo el rendimiento, no la latencia. Intentaría un punto de referencia donde realmente se utiliza la fuerza de la caché L3, el suministro de datos con menor latencia que la memoria principal.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-05-20 05:19:00