una - ¿Por qué la asignación de memoria para procesos es lenta y puede ser más rápida?

view lenta mysql

Question

Conozco relativamente cómo funciona la memoria virtual. Toda la memoria de proceso se divide en páginas y cada página de la memoria virtual se asigna a una página en la memoria real o una página en el archivo de intercambio o puede ser una página nueva, lo que significa que la página física aún no está asignada. OS asigna nuevas páginas a la memoria real bajo demanda, no cuando una aplicación solicita memoria con malloc , pero solo cuando una aplicación realmente accede a cada página desde la memoria asignada. Pero todavía tengo preguntas.

Me di cuenta de esto cuando estaba perfilando mi aplicación con la herramienta de perf Linux.

Hay aproximadamente un 20% de tiempo en las funciones del kernel: clear_page_orig , __do_page_fault y get_page_from_free_list . Esto es mucho más de lo que esperaba para esta tarea y he realizado algunas investigaciones.

Comencemos con un pequeño ejemplo:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define SIZE 1 * 1024 * 1024

int main(int argc, char *argv[]) {
  int i;
  int sum = 0;
  int *p = (int *) malloc(SIZE);
  for (i = 0; i < 10000; i ++) {
    memset(p, 0, SIZE);
    sum += p[512];
  }
  free(p);
  printf("sum %d/n", sum);
  return 0;
}

Supongamos que memset es solo un procesamiento de memoria. En este caso, asignamos una pequeña porción de memoria una vez y la reutilizamos una y otra vez. Ejecutaré este programa así:

$ gcc -O1 ./mem.c && time ./a.out

-O1 requerido porque el clang con -O2 elimina por completo el bucle y calcula el valor al instante.

Los resultados son: usuario: 0.520s, sys: 0.008s. Según perf , el 99% de este tiempo está en memset de libc . Entonces, para este caso, el rendimiento de escritura es de aproximadamente 20 Gigabytes / s, que es más que el rendimiento teórico de 12.5 Gb / s para mi memoria. Parece que esto se debe a la memoria caché L3 de la CPU.

Deje la prueba de cambio y empiece a asignar memoria en bucle (no repetiré las mismas partes del código):

#define SIZE 1 * 1024 * 1024
for (i = 0; i < 10000; i ++) {
  int *p = (int *) malloc(SIZE);
  memset(p, 0, SIZE);
  free(p);
}

El resultado es exactamente el mismo. Creo que free no libera memoria para el sistema operativo, simplemente lo coloca en una lista libre dentro del proceso. Y malloc en la siguiente iteración solo obtiene exactamente el mismo bloque de memoria. Es por eso que no hay una diferencia notable.

Vamos a comenzar a aumentar TAMAÑO desde 1 megabyte. El tiempo de ejecución crecerá poco a poco y se saturará cerca de 10 Megabytes (no hay diferencia para mí entre 10 y 20 megabytes).

#define SIZE 10 * 1024 * 1024
for (i = 0; i < 1000; i ++) {
  int *p = (int *) malloc(SIZE);
  memset(p, 0, SIZE);
  free(p);
}

El tiempo muestra: usuario: 1.184s, sys: 0.004s. perf informes de perf más del 99% del tiempo en memset , pero el rendimiento es de aproximadamente 8.3 Gb / s. En ese punto, entiendo lo que está pasando, más o menos.

Si continuaremos aumentando el tamaño del bloque de memoria, en algún momento (para mí en 35 Mb) el tiempo de ejecución aumentará dramáticamente: usuario: 0.724s, sys: 3.300s.

#define SIZE 40 * 1024 * 1024
for (i = 0; i < 250; i ++) {
  int *p = (int *) malloc(SIZE);
  memset(p, 0, SIZE);
  free(p);
}

Según perf , memset consumirá solo el 18% de una vez.

Obviamente, la memoria se asigna desde el SO y se libera en cada paso. Como mencioné antes, el sistema operativo debe borrar cada página asignada antes de su uso. Así que el 27.3% de clear_page_orig no parece extraordinario: es solo 4s * 0.273 ≈ 1.1 segundos para clear mem, lo mismo que obtenemos en el tercer ejemplo. memset tomó 17.9%, lo que lleva a ≈ 700 mseg, que es normal debido a la memoria ya en la memoria caché L3 después de clear_page_orig (primer y segundo ejemplo).

Lo que no puedo entender, ¿por qué el último caso es 2 veces más lento que memset para la memoria + memset para el caché L3? ¿Puedo hacer algo con eso?

Los resultados son reproducibles (con pequeñas diferencias) en Mac OS nativo, Ubuntu bajo VMware y la instancia de Amazon c4.large.

Además, creo que hay espacio para la optimización en dos niveles:

• en el nivel del sistema operativo . Si el sistema operativo sabe que devuelve una página a la misma aplicación a la que pertenecía anteriormente, no puede borrarla.
• en el nivel de la CPU . Si la CPU sabe que la página solía ser gratuita, no puede borrar la página en la memoria. Simplemente puede borrarlo en la memoria caché y moverlo a la memoria solo después de algún procesamiento en la memoria caché.

Answer 1

Lo que sucede aquí es un poco complicado ya que involucra unos pocos sistemas diferentes, pero definitivamente no está relacionado con el costo del cambio de contexto; su programa realiza muy pocas llamadas al sistema (verifique esto usando strace ).

Primero, es importante comprender algunos principios básicos sobre la forma en que generalmente funcionan las implementaciones de malloc :

1. La mayoría de las implementaciones de malloc obtienen una gran cantidad de memoria del sistema operativo al llamar a sbrk o mmap durante la inicialización. La cantidad de memoria obtenida se puede ajustar en algunas implementaciones malloc . Una vez que se obtiene la memoria, típicamente se divide en diferentes clases de tamaño y se organiza en una estructura de datos para que cuando un programa solicite memoria con, por ejemplo, malloc(123) , la implementación malloc pueda encontrar rápidamente una memoria que coincida con esos requisitos.
2. Cuando llame free , la memoria se devuelve a una lista libre y puede reutilizarse en llamadas posteriores a malloc . Algunas implementaciones de malloc te permiten sintonizar con precisión cómo funciona esto.
3. Cuando asigna grandes cantidades de memoria, la mayoría de las implementaciones de malloc simplemente pasan llamadas para grandes cantidades de memoria directamente a la llamada del sistema mmap , que asigna "páginas" de memoria a la vez. Para la mayoría de los sistemas, 1 página de memoria tiene 4096 bytes.
4. Relacionado, la mayoría de los sistemas operativos intentarán borrar las páginas de memoria antes de distribuirlas a procesos que hayan solicitado memoria a través de mmap o sbrk . Es por esto que ves llamadas a clear_page_orig en la salida de perf. Esta función intenta escribir 0s en páginas de memoria.

Ahora, estos principios se cruzan con otra idea que tiene muchos nombres, pero comúnmente se denomina "paginación por demanda". Lo que significa "paginación demandada" es que cuando un programa de usuario solicita un trozo de memoria del sistema operativo (por ejemplo, llamando a mmap ), la memoria se asigna en el espacio de direcciones virtuales del proceso, pero aún no hay memoria física RAM respaldando esa memoria .

Aquí hay un resumen del proceso de búsqueda de demanda:

1. Un programa llamado mmap para asignar 500MB de RAM.
2. El kernel mapea una región de direcciones en el espacio de direcciones del proceso para los 500 MB de RAM solicitados. Asigna unas "pocas" páginas (dependientes del SO) (4096 bytes cada una, normalmente) de RAM física para respaldar esas direcciones virtuales.
3. El programa de usuario comienza a acceder a la memoria escribiendo en ella.
4. Eventualmente, el programa de usuario accederá a una dirección que es válida, pero no tiene RAM física que la respalde.
5. Esto genera un error de página en la CPU.
6. El núcleo responde al error de página al ver que el proceso está accediendo a una dirección válida, pero una sin RAM física que la respalda.
7. El kernel luego encuentra RAM para asignar a esa región. Esto puede ser lento si la memoria para otros procesos necesita ser escrita en el disco, primero ("intercambiada").

La razón más probable por la que ve una degradación del rendimiento en el último caso es porque:

1. Su kernel se ha agotado de la página de memoria zero''d que puede distribuirse para satisfacer su pedido de 40 MB, por lo que está poniendo a cero la memoria una y otra vez, como lo demuestra su rendimiento de rendimiento.
2. Está generando pagefaults a medida que accede a la memoria que aún no está asignada. Como está accediendo a 40mb en lugar de a 10mb, generará más fallas de página ya que hay más páginas de memoria que necesitan ser mapeadas.
3. Como señaló otra respuesta, memset es O (n), lo que significa que cuanto más memoria necesite para escribir, más tiempo llevará.
4. Menos probable, ya que 40mb no es mucha RAM en estos días, pero revisa la cantidad de memoria libre en tu sistema solo para asegurarte de que tienes suficiente RAM.

Si su aplicación es extremadamente sensible al rendimiento, puede llamar a mmap directamente y:

1. pase el indicador MAP_POPULATE que causará que todas las fallas de página ocurran por adelantado y mapee toda la memoria física; entonces no pagará el costo por el error de página en el acceso.
2. pase el indicador MAP_UNINITIALIZED que intentará evitar poner a cero páginas de memoria antes de distribuirlas a su proceso. Tenga en cuenta que el uso de esta bandera es un problema de seguridad y no debe utilizarse a menos que comprenda completamente las implicaciones de usar esta opción. Es posible que al proceso se le puedan emitir páginas de memoria que fueron utilizadas por otros procesos no relacionados para almacenar información sensible. También tenga en cuenta que su kernel debe compilarse para permitir esta opción. La mayoría de los núcleos (como el kernel de AWS Linux) no vienen con esta opción activada de forma predeterminada. Casi seguramente no deberías usar esta opción.

Te advierto que este nivel de optimización casi siempre es un error; la mayoría de las aplicaciones tienen mucha menos fruta para la optimización que no implica la optimización del costo de la falla de la página. En una aplicación real, recomendaría:

1. Evitar el uso de memset en grandes bloques de memoria a menos que sea realmente necesario. La mayoría de las veces, no es necesario poner a cero la memoria antes de volver a usarla por el mismo proceso.
2. Evitar asignar y liberar los mismos fragmentos de memoria una y otra vez; quizás simplemente puede asignar un bloque grande por adelantado y volver a usarlo según sea necesario más adelante.
3. Si MAP_POPULATE indicador MAP_POPULATE anterior, si el costo de la página falla en el acceso es realmente perjudicial para el rendimiento (poco probable).

Deje los comentarios si tiene alguna pregunta y estaremos encantados de editar esta publicación y ampliarla un poco si es necesario.

Answer 2

No estoy seguro, pero estoy dispuesto a apostar el costo del cambio de contexto de modo de usuario a kernel, y viceversa, domina todo lo demás. memset también toma un tiempo significativo. Recuerda que será O (n).

Actualizar

Creo que gratis no libera memoria para el sistema operativo, simplemente lo coloca en una lista libre dentro del proceso. Y malloc en la siguiente iteración solo obtiene exactamente el mismo bloque de memoria. Es por eso que no hay una diferencia notable.

Esto es, en principio, correcto. La implementación clásica de malloc asigna memoria en una lista de enlace único; free simplemente establece una bandera que dice que la asignación ya no se usa. A medida que pasa el tiempo, malloc reasigna la primera vez que puede encontrar un bloque libre lo suficientemente grande. Esto funciona bastante bien, pero puede conducir a la fragmentación.

Hay una serie de implementaciones slicker ahora, vea este artículo de Wikipedia .