Rendimiento de Malloc en un entorno multiproceso

Question

He estado realizando algunos experimentos con el marco de OpenMAP y he encontrado algunos resultados extraños que no estoy seguro de saber explicar.

Mi objetivo es crear esta enorme matriz y luego llenarla con valores. Hice algunas partes de mi código como bucles paralelos para obtener el rendimiento de mi entorno multiproceso. Estoy ejecutando esto en una máquina con 2 procesadores xeon de cuatro núcleos, por lo que puedo poner hasta 8 subprocesos de forma segura allí.

Todo funciona como se esperaba, pero por alguna razón el bucle for que realmente asigna las filas de mi matriz tiene un rendimiento máximo impar cuando se ejecuta con solo 3 hilos. A partir de ahí, agregar algunos hilos más hace que mi ciclo tarde más. Con 8 hilos que toman realmente más tiempo que necesitaría con solo uno.

Ésta es mi bucle paralelo:

int width = 11; 
int height = 39916800; 
vector<vector<int> > matrix; 
matrix.resize(height);  
#pragma omp parallel shared(matrix,width,height) private(i) num_threads(3) 
{ 
    #pragma omp for schedule(dynamic,chunk) 
    for(i = 0; i < height; i++){ 
    matrix[i].resize(width); 
    } 
} /* End of parallel block */ 

Esto me hizo pensar: ¿hay un problema de rendimiento conocido cuando se llama a malloc (que supongo que es lo que el método de cambio de tamaño de la clase de plantilla vector es realmente llamando) en un entorno multiproceso? Encontré algunos artículos que decían algo sobre la pérdida de rendimiento al liberar espacio en montón en un entorno multiproceso, pero nada específico acerca de la asignación de espacio nuevo como en este caso.

Solo para dar un ejemplo, coloco debajo de un gráfico el tiempo que le toma al bucle finalizar en función del número de subprocesos para el bucle de asignación, y un bucle normal que solo lee datos de esta gran matriz más adelante.

Las dos veces donde midieron utilizando la función gettimeofday y parecen volver resultados muy similares y precisos a través de diferentes instancias de ejecución. Entonces, ¿alguien tiene una buena explicación?

Answer 1

Tiene razón acerca de vector :: resize() que llama internamente malloc. Implementación de malloc es bastante complicado. Puedo ver varios lugares donde malloc puede conducir a la contención en un entorno de subprocesos múltiples.

1. malloc probablemente mantiene una estructura de datos global en el espacio de usuario para administrar el espacio de direcciones del montón del usuario. Esta estructura de datos global debería estar protegida contra el acceso y la modificación simultáneos. Algunos asignadores tienen optimizaciones para aliviar la cantidad de veces que se accede a esta estructura de datos global ... No sé hasta qué punto ha llegado Ubuntu.

2. malloc asigna espacio de direcciones. Por lo tanto, cuando empiece a tocar la memoria asignada, pasará por un "error de página suave", que es un error de página que permite que el núcleo del sistema operativo asigne la RAM de respaldo para el espacio de direcciones asignado. Esto puede ser costoso debido al viaje al kernel y requeriría que el kernel tome algunos bloqueos globales para acceder a sus propias estructuras de datos de recursos de RAM globales.

3. el asignador de espacio de usuario probablemente mantiene algo de espacio asignado para dar nuevas asignaciones. Sin embargo, una vez que esas asignaciones se agoten, el asignador debería volver al kernel y asignar más espacio de direcciones del kernel. Esto también es costoso y requeriría un viaje al kernel y al kernel que toma algunos bloqueos globales para acceder a sus estructuras de datos relacionadas con la administración global del espacio de direcciones.

En resumen, estas interacciones podrían ser bastante complicadas. Si se encuentra con estos cuellos de botella, le sugiero que simplemente "asigne previamente" su memoria. Esto implicaría asignarlo y luego tocarlo todo (todo desde un solo hilo) para que pueda usar esa memoria más tarde desde todos sus hilos sin tener que enfrentarse a contención de bloqueo a nivel de usuario o kernel.

Answer 2

Los asignadores de memoria son definitivamente un posible punto de contención para varios subprocesos.

Fundamentalmente, el montón es una estructura de datos compartida, ya que es posible asignar memoria en un hilo y desasignarlo en otro. De hecho, su ejemplo hace exactamente eso: el "cambio de tamaño" liberará memoria en cada uno de los subprocesos de trabajo, que inicialmente se asignó en otro lugar.

Las implementaciones típicas de malloc incluidas con gcc y otros compiladores utilizan un bloqueo global compartido y funcionan razonablemente bien entre subprocesos si la presión de asignación de memoria es relativamente baja. Sin embargo, por encima de un determinado nivel de asignación, los hilos comenzarán a serializarse en el bloqueo, se producirá un cambio de contexto excesivo y la eliminación de la caché, y el rendimiento se degradará. Su programa es un ejemplo de algo que es asignación pesada, con un alloc + dealloc en el bucle interno.

Me sorprende que un compilador compatible con OpenMP no tenga una mejor implementación roscada de malloc? Ciertamente existen, eche un vistazo a this question para obtener una lista.

Answer 3

Técnicamente, el STL vector usa el std::allocator que finalmente llama al new. new a su vez llama a la libc malloc (para su sistema Linux).

Esta implementación malloc es bastante eficiente como asignador de propósito general, es seguro para subprocesos, sin embargo no es escalable (el malloc de la libra de GNU se deriva del dlmalloc de Doug Lea). Existen numerosos asignadores y documentos que mejoran el uso de dlmalloc para proporcionar una asignación escalable.

Sugiero que eche un vistazo a Hoard del Dr. Emery Berger, tcmalloc de Google y Intel Threading Building Blocks allocator escalable.