performance - ¿Por qué la velocidad de memcpy() cae dramáticamente cada 4 KB?

memory malloc (3)

memcpy() la velocidad de memcpy() notando que la velocidad disminuye drásticamente en i * 4KB. El resultado es el siguiente: el eje Y es la velocidad (MB / segundo) y el eje X es el tamaño del búfer para memcpy() , aumentando de 1 KB a 2 MB. La Subfigura 2 y la Subfigura 3 detallan la parte de 1KB-150KB y 1KB-32KB.

Ambiente:

CPU: Intel (R) Xeon (R) CPU E5620 @ 2.40GHz

Sistema operativo: 2.6.35-22-generic # 33-Ubuntu

Indicadores del compilador GCC: -O3 -msse4 -DINTEL_SSE4 -Wall -std = c99

Supongo que debe estar relacionado con las memorias caché, pero no puedo encontrar un motivo de los siguientes casos no compatibles con la memoria caché:

Dado que la degradación del rendimiento de estos dos casos es causada por bucles hostiles que leen bytes dispersos en el caché, desperdiciando el resto del espacio de una línea de caché.

Aquí está mi código:

void memcpy_speed(unsigned long buf_size, unsigned long iters){ struct timeval start, end; unsigned char * pbuff_1; unsigned char * pbuff_2; pbuff_1 = malloc(buf_size); pbuff_2 = malloc(buf_size); gettimeofday(&start, NULL); for(int i = 0; i < iters; ++i){ memcpy(pbuff_2, pbuff_1, buf_size); } gettimeofday(&end, NULL); printf("%5.3f/n", ((buf_size*iters)/(1.024*1.024))/((end.tv_sec - / start.tv_sec)*1000*1000+(end.tv_usec - start.tv_usec))); free(pbuff_1); free(pbuff_2); }

ACTUALIZAR

Teniendo en cuenta las sugerencias de @usr, @ChrisW y @Leeor, rehice la prueba de manera más precisa y el siguiente gráfico muestra los resultados. El tamaño del búfer es de 26 KB a 38 KB, y lo probé todos los demás 64 B (26 KB, 26 KB + 64 B, 26 KB + 128 B, ..., 38 KB). Cada prueba se repite 100.000 veces en aproximadamente 0,15 segundos. Lo interesante es que la caída no solo ocurre exactamente en el límite de 4 KB, sino que también sale en 4 * i + 2 KB, con una amplitud de caída mucho menor.

PD

@Leeor ofreció una forma de llenar la gota, agregando un búfer ficticio de 2KB entre pbuff_1 y pbuff_2 . Funciona, pero no estoy seguro de la explicación de Leeor.

Dado que está bucleando muchas veces, creo que los argumentos sobre las páginas que no se asignan son irrelevantes. En mi opinión, lo que está viendo es el efecto del precaptador de hardware que no está dispuesto a cruzar el límite de la página para no causar fallas de página (potencialmente innecesarias).

Espero que sea porque:

Cuando el tamaño del bloque es un múltiplo de 4KB, entonces malloc asigna nuevas páginas desde el O / S.
Cuando el tamaño del bloque no es un múltiplo de 4 KB, entonces malloc asigna un rango de su montón (ya asignado).
Cuando las páginas se asignan desde el O / S, entonces están "frías": tocarlas por primera vez es muy caro.

Supongo que si haces una memcpy única antes del primer gettimeofday , eso "calentará" la memoria asignada y no verás este problema. En lugar de hacer una memcpy inicial, incluso escribir un byte en cada página de 4KB asignada podría ser suficiente para precalentar la página.

Por lo general, cuando quiero una prueba de rendimiento como la suya, la codifico como sigue:

// Run in once to pre-warm the cache runTest(); // Repeat startTimer(); for (int i = count; i; --i) runTest(); stopTimer(); // use a larger count if the duration is less than a few seconds // repeat test 3 times to ensure that results are consistent

La memoria generalmente se organiza en 4k páginas (aunque también hay soporte para tamaños más grandes). El espacio de direcciones virtuales que ve su programa puede ser contiguo, pero no es necesariamente el caso en la memoria física. El sistema operativo, que mantiene un mapeo de direcciones virtuales a físicas (en el mapa de la página) generalmente intentaría mantener juntas las páginas físicas, pero eso no siempre es posible y pueden estar rotas (especialmente en el uso prolongado donde pueden intercambiarse ocasionalmente) )

Cuando su flujo de memoria cruza un límite de 4k páginas, la CPU debe detenerse y obtener una nueva traducción; si ya vio la página, puede almacenarse en la memoria caché en el TLB, y el acceso se optimiza para ser el más rápido, pero si esto es el primer acceso (o si tiene demasiadas páginas para que los TLB se aferren), la CPU tendrá que detener el acceso a la memoria e iniciar una página sobre las entradas del mapa de la página, eso es relativamente largo ya que cada nivel es de hecho una memoria leída por sí misma (en máquinas virtuales es incluso más larga, ya que cada nivel puede necesitar un paseo de página completo en el host).

Su función memcpy puede tener otro problema: al asignar memoria por primera vez, el sistema operativo simplemente creará las páginas en el mapa de páginas, pero las marcará como no accedidas y sin modificaciones debido a las optimizaciones internas. El primer acceso puede no solo invocar una búsqueda de página, sino también una ayuda que le dice al sistema operativo que la página va a ser utilizada (y almacenada en, para las páginas de búfer de destino), lo que requeriría una costosa transición a algún manejador de SO.

Para eliminar este ruido, asigne los almacenamientos intermedios una vez, realice varias repeticiones de la copia y calcule el tiempo amortizado. Eso, por otro lado, le daría un rendimiento "cálido" (es decir, después de calentar los cachés) para que los tamaños de caché se reflejen en sus gráficos. Si desea obtener un efecto "frío" sin sufrir latencias de paginación, es posible que desee enjuagar los cachés entre iteraciones (solo asegúrese de no medir el tiempo)

EDITAR

Vuelve a leer la pregunta y pareces estar haciendo una medición correcta. El problema con mi explicación es que debería mostrar un aumento gradual después de 4k*i , ya que en cada caída de ese tipo paga la penalización nuevamente, pero luego debe disfrutar del viaje gratis hasta los próximos 4k. No explica por qué hay tales "picos" y después de ellos la velocidad vuelve a la normalidad.

Creo que se enfrenta a un problema similar al problema crítico de zancadas vinculado a su pregunta: cuando el tamaño del búfer es una buena ronda 4k, ambos búferes se alinearán con los mismos conjuntos en la memoria caché y se sincronizarán unos con otros. Su L1 es de 32k, por lo que no parece un problema al principio, pero suponiendo que la información L1 tiene 8 formas, de hecho es un envoltorio de 4k para los mismos conjuntos, y tiene 2 * 4 bloques con exactamente la misma alineación (suponiendo que la asignación se realizó contiguamente) por lo que se superponen en los mismos conjuntos. Es suficiente que el LRU no funcione exactamente como esperabas y seguirás teniendo conflictos.

Para comprobar esto, intentaría malloc un búfer ficticio entre pbuff_1 y pbuff_2, hacerlo 2k grande y esperar que rompa la alineación.

EDIT2:

Ok, ya que esto funciona, es hora de elaborar un poco. Supongamos que asigna dos matrices 4k a rangos 0x1000-0x1fff y 0x2000-0x2fff . establecer 0 en su L1 contendrá las líneas a 0x1000 y 0x2000, el conjunto 1 contendrá 0x1040 y 0x2040, y así sucesivamente. En estos tamaños no tiene problemas con la agitación, todos pueden coexistir sin desbordar la asociatividad de la memoria caché. Sin embargo, cada vez que realiza una iteración, tiene una carga y una tienda que accede al mismo conjunto; supongo que esto puede causar un conflicto en el HW. Peor aún: necesitarás múltiples iteraciones para copiar una sola línea, lo que significa que tienes una congestión de 8 cargas + 8 tiendas (menos si vectorizas, pero aún mucho), todas dirigidas al mismo conjunto pobre, soy bonita Seguro que hay un montón de colisiones escondidas allí.

También veo que la guía de optimización de Intel tiene algo que decir específicamente sobre eso (ver 3.6.8.2):

Aliasing de memoria de 4 KByte se produce cuando el código accede a dos ubicaciones de memoria diferentes con un desplazamiento de 4 KByte entre ellas. La situación de alias 4-KByte puede manifestarse en una rutina de copia de memoria donde las direcciones del búfer fuente y búfer de destino mantienen un desplazamiento constante y el desplazamiento constante pasa a ser un múltiplo del incremento de bytes de una iteración a la siguiente.
...
las cargas tienen que esperar hasta que las tiendas hayan sido retiradas antes de que puedan continuar. Por ejemplo, en el desplazamiento 16, la carga de la siguiente iteración es el almacén de iteraciones actual con alias de 4 KByte, por lo tanto, el bucle debe esperar hasta que se complete la operación de almacenamiento, haciendo que todo el bucle sea serializado. La cantidad de tiempo necesario para esperar disminuye con una compensación mayor hasta que el desplazamiento de 96 resuelve el problema (ya que no hay tiendas pendientes en el momento de la carga con la misma dirección).