¿Por qué malloc + memset es más lento que calloc?

Question

¿Por qué malloc + memset es más lento que calloc?

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

Así que en el trabajo diario, considero calloc como malloc+memset. Por cierto, por diversión, escribí el siguiente código para un punto de referencia.

El resultado es confuso.

Código 1:

#include<stdio.h>
#include<stdlib.h>
#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<stdio.h>
#include<stdlib.h>
#include<string.h>
#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 de código 2:

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

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

Mi pregunta es: ¿por Qué es malloc+memset mucho más lenta que calloc? ¿Cómo puede calloc hacer eso?

222

c malloc

Author: Philip Conrad, 2010-04-22

Source

3 answers

Porque en muchos sistemas, en el tiempo de procesamiento libre, el sistema operativo va poniendo memoria libre a cero por sí solo y marcándola segura para calloc(), por lo que cuando llame a calloc(), puede que ya tenga memoria libre a cero para darle.

10

Author: Chris Lutz,
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
2010-04-22 05:48:20

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

0

Author: Stewart,
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
2010-04-22 05:51:20

score 390 · Accepted Answer

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

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

Recorrido rápido de la memoria

Hay cuatro partes principales aquí: su programa, la biblioteca estándar, el kernel, y las tablas de páginas. Ya conoces tu programa, así que...

Los asignadores de memoria como malloc() y calloc() están principalmente allí para tomar asignaciones pequeñas (desde 1 byte hasta 100 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 pedirá más memoria del núcleo cuando el grupo se agote. Sin embargo, dado que el programa que estás preguntando está asignando una gran cantidad de memoria a la vez, malloc() y calloc() solo pedirán esa memoria directamente desde el núcleo. El umbral para este comportamiento depende de su sistema, pero he visto 1 MiB utilizado como el umbral.

El núcleo es responsable de asignar RAM real a cada proceso y asegurarse de que los procesos no interfieran con la memoria de otros procesos. Esto se llama protección de memoria, ha sido muy común desde la década de 1990, y es la razón por la que un programa puede bloquearse sin derribar todo el sistema. Así que cuando un programa necesita más memoria, no solo puede tomar la memoria, sino que pide la memoria del núcleo 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 las 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 memoria real, sino direcciones en memoria virtual. El el procesador divide estas direcciones en 4 páginas KiB, y cada página se puede asignar a una pieza diferente de RAM física modificando la tabla de páginas. Solo el núcleo puede modificar la tabla de páginas.

Cómo no funciona

Así es como asignar 256 MB no funciona:

Su proceso llama calloc() y pide 256 MiB.
La biblioteca estándar llama a mmap() y pide 256 MiB.
El núcleo encuentra 256 MiB de RAM sin usar y se lo da a su proceso modificando la tabla de páginas.
La biblioteca estándar pone a cero la RAM con memset() y devuelve calloc().
Su proceso eventualmente sale, y el núcleo 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 grandes diferencia.

Cuando su proceso obtiene nueva memoria del núcleo, esa memoria probablemente fue utilizada por algún otro proceso anteriormente. Esto es un riesgo para la seguridad. ¿Qué pasa si esa memoria tiene contraseñas, claves de cifrado o recetas de salsa secretas? Para evitar que los datos confidenciales se filtren, el núcleo siempre limpia la memoria antes de darla a un proceso. También podríamos limpiar la memoria poniéndola a cero, y si la nueva memoria se pone a cero, también podríamos hacerla una garantía, por lo que mmap() garantías que la nueva memoria que devuelve siempre está puesta a cero.
Hay un montón de programas por ahí que asignar memoria, pero no utilizar la memoria de inmediato. Algunas veces se asigna memoria pero nunca se usa. El núcleo lo sabe y es perezoso. Cuando asigna nueva memoria, el núcleo no toca la tabla de páginas en absoluto y no le da RAM a su proceso. En su lugar, encuentra algún espacio de dirección en su proceso, toma nota de lo que se supone que debe ir allí y promete que pondrá RAM allí si su programa alguna vez realmente lo usa. Cuando su programa 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 programa. Si nunca usa la memoria, el error de página nunca ocurre y su programa nunca obtiene la RAM.
Algunos procesos asignan memoria y luego leen de ella sin modificarla. Esto significa que una gran cantidad de páginas en la memoria a través de diferentes procesos puede ser llenado con ceros prístinos devueltos desde mmap(). Dado que estas páginas son todas iguales, el núcleo hace que todas estas direcciones virtuales apunten a una sola página compartida de 4 Kb de memoria llena de ceros. Si intenta escribir en esa memoria, el procesador desencadena otro error de página y el núcleo interviene para darle una nueva página de ceros que no se comparte con ningún otro programa.

El proceso final se parece más a esto:

Su proceso llama calloc() y pide 256 MiB.
La biblioteca estándar llama a mmap() y pide 256 MiB.
El núcleo encuentra 256 MiB de espacio de direcciones no utilizado , toma nota de para qué se usa ese espacio de direcciones ahora, y devuelve.
La biblioteca estándar sabe que el resultado de mmap() siempre está lleno de ceros (o será una vez que realmente obtenga algo de RAM), por lo que no toque la memoria, por lo que no hay ningún error de página, y la RAM nunca se da a su proceso.
Su proceso eventualmente sale, y el núcleo no necesita recuperar la RAM porque nunca fue asignada en primer lugar.

Si usas memset() para poner a cero la página, memset() activará el error de página, hará que la RAM se asigne y luego la pondrá a cero aunque ya esté llena de ceros. Esto es una enorme cantidad de trabajo extra, y explica por qué calloc() es más rápido que malloc() y memset(). Si terminas usando la memoria de todos modos, calloc() sigue siendo 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 a procesadores integrados que son demasiado pequeños para una sofisticada unidad de gestión de memoria.

Esto tampoco siempre trabaje 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 núcleo. En general, el grupo compartido puede tener datos basura almacenados en ella desde la memoria antigua que se usó y 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 están prístinas y aún están llenas de ceros, pero no todas las implementaciones lo hacen.

Disipando algunos errores respuestas

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

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

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

Así que puedes ver, memset() es muy rápido y realmente no vas a conseguir nada mejor para grandes bloques de memoria.

El hecho de que memset() esté poniendo a cero la memoria 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 más grande (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 programa que asigne memoria hasta que malloc() o calloc() devuelva NULL.

¿Qué pasa si añades memset()?