¿Por qué Malloc + Memset es más lento que Calloc?

Se sabe que calloc es diferente de malloc porque inicializa la memoria asignada. Con calloc , la memoria se establece en cero. Con malloc , la memoria no se borra.

Entonces en el trabajo diario, considero a calloc como malloc + memset . A propósito, para divertirme, escribí el siguiente código para un punto de referencia.

El resultado es confuso.

Código 1:

 #include #include #define BLOCK_SIZE 1024*1024*256 int main() { int i=0; char *buf[10]; while(i<10) { buf[i] = (char*)calloc(1,BLOCK_SIZE); i++; } } 

Salida del Código 1:

 time ./a.out **real 0m0.287s** user 0m0.095s sys 0m0.192s 

Código 2:

 #include #include #include #define BLOCK_SIZE 1024*1024*256 int main() { int i=0; char *buf[10]; while(i<10) { buf[i] = (char*)malloc(BLOCK_SIZE); memset(buf[i],'\0',BLOCK_SIZE); i++; } } 

Salida del Código 2:

 time ./a.out **real 0m2.693s** user 0m0.973s sys 0m1.721s 

Reemplazar memset con bzero(buf[i],BLOCK_SIZE) en el Código 2 produce el mismo resultado.

Mi pregunta es: ¿Por qué memset + memset es mucho más lento que calloc ? ¿Cómo puede calloc hacer eso?

La versión corta: siempre use calloc() lugar de malloc()+memset() . En la mayoría de los casos, serán lo mismo. En algunos casos, calloc() hará menos trabajo porque puede omitir memset() completo. En otros casos, ¡ calloc() puede incluso engañar y no asignar memoria! Sin embargo, malloc()+memset() siempre hará la cantidad completa de trabajo.

Comprender esto requiere un breve recorrido por el sistema de memoria.

Recorrido rápido de la memoria

Aquí hay cuatro partes principales: su progtwig, la biblioteca estándar, el kernel y las tablas de páginas. Ya conoces tu progtwig, entonces …

Los asignadores de memoria como malloc() y calloc() están principalmente allí para tomar pequeñas asignaciones (cualquier cosa desde 1 byte hasta 100s de KB) y agruparlas en grupos de memoria más grandes. Por ejemplo, si asigna 16 bytes, malloc() primero intentará obtener 16 bytes de uno de sus grupos, y luego solicitará más memoria del núcleo cuando el grupo se seque. Sin embargo, dado que el progtwig que está preguntando está asignando una gran cantidad de memoria a la vez, malloc() y calloc() simplemente solicitarán esa memoria directamente desde el kernel. El umbral para este comportamiento depende de su sistema, pero he visto usar 1 MiB como umbral.

El kernel es responsable de asignar RAM real a cada proceso y de asegurarse de que los procesos no interfieran con la memoria de otros procesos. Esto se llama protección de la memoria, ha sido muy común desde la década de 1990, y es la razón por la que un progtwig puede fallar sin derribar todo el sistema. Entonces, cuando un progtwig necesita más memoria, no puede simplemente tomar la memoria, sino que solicita la memoria del kernel usando una llamada al sistema como mmap() o sbrk() . El núcleo dará RAM a cada proceso modificando la tabla de páginas.

La tabla de páginas asigna direcciones de memoria a la RAM física real. Las direcciones de su proceso, 0x00000000 a 0xFFFFFFFF en un sistema de 32 bits, no son una memoria real, sino que son direcciones en la memoria virtual. El procesador divide estas direcciones en 4 páginas KiB, y cada página puede asignarse a una pieza diferente de RAM física modificando la tabla de páginas. Solo el kernel puede modificar la tabla de páginas.

Cómo no funciona

Así es como la asignación de 256 MiB no funciona:

  1. Tu proceso llama a calloc() y solicita 256 MiB.

  2. La biblioteca estándar llama a mmap() y solicita 256 MiB.

  3. El kernel encuentra 256 MiB de RAM no utilizada y la entrega a su proceso modificando la tabla de páginas.

  4. La biblioteca estándar pone a cero la RAM con memset() y vuelve de calloc() .

  5. Finalmente, su proceso finaliza y el kernel recupera la RAM para que pueda ser utilizada por otro proceso.

Cómo funciona realmente

El proceso anterior funcionaría, pero simplemente no sucede de esta manera. Hay tres diferencias principales.

  • Cuando su proceso obtiene nueva memoria del kernel, esa memoria probablemente fue utilizada por algún otro proceso anteriormente. Este es un riesgo de seguridad. ¿Qué pasa si esa memoria tiene contraseñas, claves de encriptación o recetas secretas de salsa? Para evitar que los datos sensibles se filtren, el kernel siempre limpia la memoria antes de pasarla a un proceso. También podríamos restregar la memoria poniendo a cero, y si la memoria nueva se pone a cero, podemos también hacerla una garantía, por lo que mmap() garantiza que la nueva memoria que devuelve siempre se ponga a cero.

  • Hay muchos progtwigs que asignan memoria pero no usan la memoria de inmediato. Algunas veces se asigna memoria pero nunca se usa. El núcleo sabe esto y es flojo. Cuando asigna nueva memoria, el kernel no toca la tabla de páginas y no le da ninguna RAM a su proceso. En su lugar, encuentra algún espacio de direcciones en su proceso, toma nota de lo que se supone que debe ir allí, y hace la promesa de que pondrá RAM allí si su progtwig alguna vez realmente lo usa. Cuando su progtwig intenta leer o escribir desde esas direcciones, el procesador desencadena un error de página y el núcleo pasa a asignar RAM a esas direcciones y reanuda su progtwig. Si nunca usa la memoria, la falla de la página nunca ocurre y su progtwig nunca obtiene la RAM.

  • Algunos procesos asignan memoria y luego leen sin modificarla. Esto significa que muchas páginas en la memoria en diferentes procesos pueden llenarse con ceros prístinos devueltos por mmap() . Dado que estas páginas son todas iguales, el núcleo hace que todas estas direcciones virtuales señalen una única página de memoria compartida de 4 KB llena de ceros. Si intenta escribir en esa memoria, el procesador desencadena otro error de página y el kernel interviene para darle una nueva página de ceros que no se comparte con ningún otro progtwig.

El proceso final se parece más a esto:

  1. Tu proceso llama a calloc() y solicita 256 MiB.

  2. La biblioteca estándar llama a mmap() y solicita 256 MiB.

  3. El kernel encuentra 256 MiB de espacio de direcciones sin usar , hace una nota sobre para qué se utiliza ese espacio de direcciones y lo devuelve.

  4. La biblioteca estándar sabe que el resultado de mmap() siempre está lleno de ceros (o lo será una vez que obtenga algo de RAM), por lo que no toca la memoria, por lo que no hay un error de página, y la RAM nunca se da a tu proceso

  5. Finalmente, su proceso finaliza y el kernel no necesita reclamar la RAM porque nunca se asignó en primer lugar.

Si utiliza memset() para memset() a cero la página, memset() desencadenará el error de página, causará que se asigne la RAM y luego la ponga a cero, aunque ya esté llena de ceros. Esta es una enorme cantidad de trabajo adicional, y explica por qué calloc() es más rápido que malloc() y memset() . Si terminas usando la memoria de todos modos, calloc() es aún más rápido que malloc() y memset() pero la diferencia no es tan ridícula.


Esto no siempre funciona

No todos los sistemas tienen memoria virtual paginada, por lo que no todos los sistemas pueden usar estas optimizaciones. Esto se aplica a procesadores muy antiguos como el 80286, así como procesadores integrados que son demasiado pequeños para una unidad de gestión de memoria sofisticada.

Esto tampoco siempre funcionará con asignaciones más pequeñas. Con asignaciones más pequeñas, calloc() obtiene memoria de un grupo compartido en lugar de ir directamente al kernel. En general, el conjunto compartido puede tener datos no deseados almacenados en él de la memoria anterior que se usó y se liberó con free() , por lo que calloc() podría tomar esa memoria y llamar a memset() para eliminarla. Las implementaciones comunes rastrearán qué partes del grupo compartido son prístinas y aún están llenas de ceros, pero no todas las implementaciones hacen esto.

Disipando algunas respuestas incorrectas

Dependiendo del sistema operativo, el kernel puede o no borrar la memoria en su tiempo libre, en caso de que necesite obtener algo de memoria puesta a cero más tarde. Linux no borra la memoria antes de tiempo, y Dragonfly BSD recientemente también eliminó esta característica de su kernel . Sin embargo, algunos otros kernels no tienen memoria por adelantado. Poner a cero las páginas durante el tiempo de inactividad no es suficiente para explicar las grandes diferencias de rendimiento de todos modos.

La función calloc() no está usando alguna versión especial de memset() alineada con la memoria, y eso no lo haría mucho más rápido de todos modos. La mayoría de las implementaciones memset() para procesadores modernos se ven así:

 function memset(dest, c, len) // one byte at a time, until the dest is aligned... while (len > 0 && ((unsigned int)dest & 15)) *dest++ = c len -= 1 // now write big chunks at a time (processor-specific)... // block size might not be 16, it's just pseudocode while (len >= 16) // some optimized vector code goes here // glibc uses SSE2 when available dest += 16 len -= 16 // the end is not aligned, so one byte at a time while (len > 0) *dest++ = c len -= 1 

Entonces, pueden ver, memset() es muy rápido y realmente no van a obtener nada mejor para grandes bloques de memoria.

El hecho de que memset() es la memoria de memset() cero que ya está puesta a cero significa que la memoria se pone a cero dos veces, pero eso solo explica una diferencia de rendimiento de 2x. La diferencia de rendimiento aquí es mucho mayor (medí más de tres órdenes de magnitud en mi sistema entre malloc()+memset() y calloc() ).

Truco de fiesta

En lugar de hacer un bucle 10 veces, escriba un progtwig que asigne memoria hasta que malloc() o calloc() devuelva NULL.

¿Qué sucede si agrega memset() ?

Debido a que en muchos sistemas, en tiempo de procesamiento adicional, el sistema operativo va por ahí configurando la memoria libre a cero y marcando seguro para calloc() , así que cuando llame a calloc() , puede que ya tenga memoria cero libre para darle .

En algunas plataformas, en algunos modos, malloc inicializa la memoria a un valor típicamente distinto de cero antes de devolverlo, por lo que la segunda versión podría inicializar la memoria dos veces