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

12 minutos de lectura

avatar de usuario
reykai

se sabe que calloc es diferente a malloc en que inicializa la memoria asignada. Con calloc, la memoria se pone a cero. Con mallocla 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 del Código 2:

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

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

Mi pregunta es: Por que es malloc+memset mucho más lento que calloc? como puedo calloc ¿Haz eso?

avatar de usuario
dietrich epp

La versión corta: usar siempre calloc() en vez de malloc()+memset(). En la mayoría de los casos, serán los mismos. En algunos casos, calloc() hará menos trabajo porque puede saltar memset() enteramente. En otros casos, calloc() ¡incluso puede hacer trampa y no asignar ninguna memoria! Sin embargo, malloc()+memset() siempre hará la cantidad total de trabajo.

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

Recorrido rápido por la memoria

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

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

El kernel es responsable de asignar RAM real a cada proceso y asegurarse de que los procesos no interfieran con la memoria de otros procesos. 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 programa puede fallar sin que todo el sistema se caiga. Entonces, cuando un programa necesita más memoria, no puede simplemente tomar la memoria, sino que solicita la memoria del kernel mediante una llamada al sistema como mmap() o sbrk(). El kernel le 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 memoria real sino direcciones en memoria virtual. El procesador divide estas direcciones en páginas de 4 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.

como no funciona

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

  1. Tu proceso llama calloc() y pide 256 MiB.

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

  3. El kernel encuentra 256 MiB de RAM sin usar y se los da a su proceso modificando la tabla de páginas.

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

  5. Eventualmente, su proceso finaliza 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 diferencias principales.

  • Cuando su proceso obtiene nueva memoria del núcleo, 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 se filtren datos confidenciales, el kernel siempre borra la memoria antes de entregarla a un proceso. También podríamos borrar la memoria poniéndola a cero, y si la nueva memoria se pone a cero, también podríamos convertirla en una garantía, por lo que mmap() garantiza que la nueva memoria que devuelve siempre se pone a cero.

  • Hay muchos programas que asignan memoria pero no la usan de inmediato. A veces, la memoria se asigna pero nunca se usa. El núcleo lo sabe y es perezoso. Cuando asigna nueva memoria, el kernel no toca la tabla de páginas en absoluto y no le da RAM a su proceso. En cambio, encuentra algo de espacio de direcciones 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 la usa. Cuando su programa intenta leer o escribir desde esas direcciones, el procesador activa una fallo de página y el kernel interviene para asignar RAM a esas direcciones y reanuda su programa. Si nunca usa la memoria, la falla de la página nunca sucede y su programa nunca obtiene la RAM.

  • Algunos procesos asignan memoria y luego la leen sin modificarla. Esto significa que muchas páginas en la memoria a través de diferentes procesos pueden llenarse con ceros prístinos devueltos desde mmap(). Dado que estas páginas son todas iguales, el kernel hace que todas estas direcciones virtuales apunten a una única página de memoria compartida de 4 KiB llena de ceros. Si intenta escribir en esa memoria, el procesador activa otra falla de página y el núcleo interviene para brindarle una nueva página de ceros que no se comparte con ningún otro programa.

El proceso final se parece más a esto:

  1. Tu proceso llama calloc() y pide 256 MiB.

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

  3. El kernel encuentra 256 MiB de no utilizados espacio de dirección, toma nota sobre para qué se usa ahora ese espacio de direcciones y regresa.

  4. La biblioteca estándar sabe que el resultado de mmap() siempre se rellena con ceros (o estarán una vez que realmente obtiene algo de RAM), por lo que no toca la memoria, por lo que no hay fallas de página y la RAM nunca se le da a su proceso.

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

Si utiliza memset() poner a cero la página, memset() activará la falla de la página, hará que se asigne la RAM y luego la pondrá a cero aunque ya esté llena de ceros. Esta es una enorme cantidad de trabajo extra, y explica por qué calloc() es más rápido que malloc() y memset(). Si termina 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 unidad de administració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 núcleo. En general, el grupo compartido puede tener datos no deseados almacenados en él desde la memoria antigua que se usó y liberó con free()asi que calloc() podría tomar ese recuerdo y llamar memset() para limpiarlo. Las implementaciones comunes rastrearán qué partes del grupo compartido están impecables 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 poner a cero la memoria en su tiempo libre, en caso de que necesite obtener algo de memoria a cero más adelante. Linux no pone a cero la memoria antes de tiempo, y Dragonfly BSD recientemente también eliminó esta función de su kernel. Sin embargo, algunos otros núcleos no tienen memoria 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.

Él calloc() función no está utilizando alguna 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 memset() Las implementaciones para los 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

para que puedas ver, memset() es muy rápido y realmente no obtendrá nada mejor para grandes bloques de memoria.

El hecho de que memset() poner 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 mayor (medí más de tres órdenes de magnitud en mi sistema entre malloc()+memset() y calloc()).

Truco de fiesta

En lugar de repetir 10 veces, escriba un programa que asigne memoria hasta malloc() o calloc() devuelve NULL.

¿Qué pasa si agregas memset()?

  • @Dietrich: la explicación de la memoria virtual de Dietrich sobre el sistema operativo que asigna la misma página llena de ceros muchas veces para calloc es fácil de verificar. Simplemente agregue un bucle que escriba datos basura en cada página de memoria asignada (escribir un byte cada 500 bytes debería ser suficiente). El resultado general debería volverse mucho más cercano, ya que el sistema se vería obligado a asignar realmente diferentes páginas en ambos casos.

    – kriss

    22 de abril de 2010 a las 6:43

  • @kriss: de hecho, aunque un byte cada 4096 es suficiente en la gran mayoría de los sistemas

    -Dietrich Epp

    22 de abril de 2010 a las 6:46

  • @mirabilos: En realidad, las implementaciones tienden a ser aún más sofisticadas. Memoria asignada por mmap() se asigna en grandes porciones, por lo que el malloc() / calloc() la implementación puede hacer un seguimiento de qué bloques aún están intactos y llenos de ceros. Asi que calloc() puede evitar tocar la memoria incluso si no recibe la memoria de mmap()es decir, ya formaba parte del montón pero aún no se ha utilizado.

    -Dietrich Epp

    31/03/2014 a las 20:49


  • @mirabilos: También he visto implementaciones con una “marca de agua alta”, donde las direcciones más allá de cierto punto se ponen a cero. No estoy seguro de lo que quiere decir con “propenso a errores”. Si le preocupa que las aplicaciones escriban en la memoria no asignada, es muy poco lo que puede hacer para evitar errores insidiosos, aparte de instrumentar el programa con mudflap.

    -Dietrich Epp

    31 de marzo de 2014 a las 21:24

  • Si bien no está relacionado con la velocidad, calloc también es menos propenso a errores. Eso es donde large_int * large_int resultaría en un desbordamiento, calloc(large_int, large_int) devoluciones NULLpero malloc(large_int * large_int) es un comportamiento indefinido, ya que no conoce el tamaño real del bloque de memoria que se devuelve.

    – Dunas

    23 de marzo de 2018 a las 9:41

Debido a que en muchos sistemas, en el tiempo libre de procesamiento, el sistema operativo configura la memoria libre en cero por sí solo y la marca como segura para calloc()así que cuando llames calloc()es posible que ya tenga memoria libre y puesta a cero para brindarle.

  • ¿Está seguro? ¿Qué sistemas hacen esto? Pensé que la mayoría de los sistemas operativos simplemente apagaban el procesador cuando estaban inactivos y ponían a cero la memoria a pedido para los procesos que se asignaban tan pronto como escribían en esa memoria (pero no cuando la asignaban).

    -Dietrich Epp

    22 de abril de 2010 a las 6:00

  • @Dietrich – No estoy seguro. Lo escuché una vez y me pareció una manera razonable (y razonablemente simple) de hacer calloc() más eficiente.

    – Chris Lutz

    22 de abril de 2010 a las 6:06


  • @Pierreten: no puedo encontrar ninguna buena información sobre calloc()-optimizaciones específicas y no tengo ganas de interpretar el código fuente de libc para el OP. ¿Puedes buscar algo que muestre que esta optimización no existe o no funciona?

    – Chris Lutz

    22 de abril de 2010 a las 6:13


  • @Dietrich: se supone que FreeBSD debe llenar las páginas con cero en el tiempo de inactividad: vea su configuración vm.idlezero_enable.

    – Zan Lince

    7 de marzo de 2011 a las 21:47

  • @DietrichEpp lo siento por necro, pero, por ejemplo, Windows hace esto.

    – Andreas Grapentin

    11/11/2014 a las 19:37


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.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad