Pourquoi malloc + memset est plus lent que calloc?

256

Il est connu que callocc'est différent mallocdu fait qu'il initialise la mémoire allouée. Avec calloc, la mémoire est mise à zéro. Avec malloc, la mémoire n'est pas effacée.

Donc, dans le travail quotidien, je considère calloccomme malloc+ memset. Par ailleurs, pour le plaisir, j'ai écrit le code suivant pour une référence.

Le résultat est déroutant.

Code 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++;
        }
}

Sortie du code 1:

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

Code 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++;
        }
}

Sortie du code 2:

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

Remplacer memsetpar bzero(buf[i],BLOCK_SIZE)dans Code 2 produit le même résultat.

Ma question est: pourquoi malloc+ est-il memsettellement plus lent que calloc? Comment callocfaire ça?

kingkai
la source

Réponses:

455

La version courte: utilisez toujours calloc()au lieu de malloc()+memset(). Dans la plupart des cas, ce seront les mêmes. Dans certains cas, calloc()fera moins de travail car il peut sauter memset()complètement. Dans d'autres cas, calloc()peut même tricher et ne pas allouer de mémoire! Cependant, malloc()+memset()fera toujours la totalité du travail.

Comprendre cela nécessite une courte visite du système de mémoire.

Visite rapide de la mémoire

Il y a quatre parties principales ici: votre programme, la bibliothèque standard, le noyau et les tables de pages. Vous connaissez déjà votre programme, alors ...

Les allocateurs de mémoire aiment malloc()et calloc()sont principalement là pour prendre de petites allocations (de 1 octet à 100 s de Ko) et les regrouper dans de plus grands pools de mémoire. Par exemple, si vous allouez 16 octets, vous essaierez d' malloc()abord d'extraire 16 octets de l'un de ses pools, puis de demander plus de mémoire au noyau lorsque le pool se tarira. Cependant, étant donné que le programme dont vous parlez alloue une grande quantité de mémoire à la fois, malloc()et calloc()demandera simplement cette mémoire directement à partir du noyau. Le seuil de ce comportement dépend de votre système, mais j'ai vu 1 Mio utilisé comme seuil.

Le noyau est responsable de l'allocation de la RAM réelle à chaque processus et de s'assurer que les processus n'interfèrent pas avec la mémoire des autres processus. C'est ce qu'on appelle la protection de la mémoire, elle est très courante depuis les années 1990, et c'est la raison pour laquelle un programme peut planter sans faire tomber tout le système. Ainsi, lorsqu'un programme a besoin de plus de mémoire, il ne peut pas simplement prendre la mémoire, mais à la place, il demande la mémoire du noyau en utilisant un appel système comme mmap()ou sbrk(). Le noyau donnera de la RAM à chaque processus en modifiant la table des pages.

Le tableau des pages mappe les adresses mémoire à la RAM physique réelle. Les adresses de votre processus, 0x00000000 à 0xFFFFFFFF sur un système 32 bits, ne sont pas de la mémoire réelle mais plutôt des adresses dans la mémoire virtuelle. Le processeur divise ces adresses en 4 pages de Ko, et chaque page peut être affectée à un morceau différent de RAM physique en modifiant la table des pages. Seul le noyau est autorisé à modifier la table des pages.

Comment ça ne marche pas

Voici comment l'allocation de 256 Mio ne fonctionne pas :

  1. Votre processus appelle calloc()et demande 256 Mio.

  2. La bibliothèque standard appelle mmap()et demande 256 Mio.

  3. Le noyau trouve 256 Mo de RAM inutilisée et le donne à votre processus en modifiant le tableau des pages.

  4. La bibliothèque standard met à zéro la RAM avec memset()et revient de calloc().

  5. Votre processus se termine finalement et le noyau récupère la RAM afin qu'elle puisse être utilisée par un autre processus.

Comment ça marche réellement

Le processus ci-dessus fonctionnerait, mais cela ne se produit tout simplement pas de cette façon. Il existe trois différences majeures.

  • Lorsque votre processus obtient une nouvelle mémoire du noyau, cette mémoire a probablement été utilisée par un autre processus auparavant. Il s'agit d'un risque pour la sécurité. Que faire si cette mémoire a des mots de passe, des clés de chiffrement ou des recettes secrètes de salsa? Pour empêcher les données sensibles de fuir, le noyau nettoie toujours la mémoire avant de la donner à un processus. Nous pourrions aussi bien nettoyer la mémoire en la mettant à zéro, et si une nouvelle mémoire est mise à zéro, nous pourrions aussi bien en faire une garantie, mmap()garantissant ainsi que la nouvelle mémoire qu'elle retourne est toujours mise à zéro.

  • Il existe de nombreux programmes qui allouent de la mémoire mais ne l'utilisent pas tout de suite. Parfois, la mémoire est allouée mais jamais utilisée. Le noyau le sait et est paresseux. Lorsque vous allouez de la nouvelle mémoire, le noyau ne touche pas du tout au tableau des pages et ne donne aucune RAM à votre processus. Au lieu de cela, il trouve un espace d'adressage dans votre processus, note ce qui est censé y aller et promet qu'il y mettra de la RAM si votre programme l'utilise réellement. Lorsque votre programme essaie de lire ou d'écrire à partir de ces adresses, le processeur déclenche une erreur de page et le noyau assigne la RAM à ces adresses et reprend votre programme. Si vous n'utilisez jamais la mémoire, l'erreur de page ne se produit jamais et votre programme n'obtient jamais réellement la RAM.

  • Certains processus allouent de la mémoire puis la lisent sans la modifier. Cela signifie que beaucoup de pages en mémoire à travers différents processus peuvent être remplies de zéros vierges retournés mmap(). Comme ces pages sont toutes identiques, le noyau fait pointer toutes ces adresses virtuelles une seule page de mémoire partagée de 4 Ko remplie de zéros. Si vous essayez d'écrire dans cette mémoire, le processeur déclenche une autre erreur de page et le noyau intervient pour vous donner une nouvelle page de zéros qui n'est partagée avec aucun autre programme.

Le processus final ressemble plus à ceci:

  1. Votre processus appelle calloc()et demande 256 Mio.

  2. La bibliothèque standard appelle mmap()et demande 256 Mio.

  3. Le noyau trouve 256 Mo d' espace d'adressage inutilisé , note à quoi cet espace d'adressage est maintenant utilisé et retourne.

  4. La bibliothèque standard sait que le résultat de mmap()est toujours rempli de zéros (ou le sera une fois qu'il aura effectivement de la RAM), donc il ne touche pas la mémoire, donc il n'y a pas de défaut de page, et la RAM n'est jamais donnée à votre processus .

  5. Votre processus se termine finalement et le noyau n'a pas besoin de récupérer la RAM car elle n'a jamais été allouée en premier lieu.

Si vous utilisez memset()pour mettre à zéro la page, memset()cela déclenchera l'erreur de page, provoquera l'allocation de la RAM, puis la mettra à zéro même si elle est déjà remplie de zéros. C'est une énorme quantité de travail supplémentaire, et explique pourquoi calloc()est plus rapide que malloc()et memset(). Si vous finissez par utiliser la mémoire de toute façon, calloc()c'est toujours plus rapide que malloc()et memset()mais la différence n'est pas aussi ridicule.


Ça ne marche pas toujours

Tous les systèmes n'ont pas de mémoire virtuelle paginée, donc tous les systèmes ne peuvent pas utiliser ces optimisations. Cela s'applique aux très vieux processeurs comme le 80286 ainsi qu'aux processeurs intégrés qui sont tout simplement trop petits pour une unité de gestion de mémoire sophistiquée.

Cela ne fonctionnera pas toujours avec des allocations plus petites. Avec des allocations plus petites, calloc()obtient la mémoire d'un pool partagé au lieu d'aller directement au noyau. En général, le pool partagé peut contenir des données indésirables stockées dans l'ancienne mémoire utilisée et libérée free(), il calloc()peut donc prendre cette mémoire et appeler memset()pour l'effacer. Les implémentations communes suivront quelles parties du pool partagé sont vierges et toujours remplies de zéros, mais toutes les implémentations ne le font pas.

Dissiper certaines mauvaises réponses

Selon le système d'exploitation, le noyau peut ou non mettre à zéro la mémoire pendant son temps libre, au cas où vous auriez besoin de récupérer de la mémoire à zéro plus tard. Linux ne remet pas à zéro la mémoire à l'avance, et Dragonfly BSD a également récemment supprimé cette fonctionnalité de son noyau . Cependant, certains autres noyaux n'effectuent aucune mémoire à l'avance. La mise à zéro des pages pendant l'inactivité n'est pas suffisante pour expliquer les grandes différences de performances de toute façon.

La calloc()fonction n'utilise pas de version spéciale alignée sur la mémoire de memset(), et cela ne la rendrait pas beaucoup plus rapide de toute façon. La plupart des memset()implémentations pour les processeurs modernes ressemblent un peu à ceci:

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

Donc, vous pouvez voir, memset()c'est très rapide et vous n'allez pas vraiment obtenir mieux pour les gros blocs de mémoire.

Le fait de mettre à memset()zéro la mémoire qui est déjà mise à zéro signifie que la mémoire est mise à zéro deux fois, mais cela n'explique qu'une différence de performances de 2x. La différence de performances ici est beaucoup plus importante (j'ai mesuré plus de trois ordres de grandeur sur mon système entre malloc()+memset()et calloc()).

Truc de fête

Au lieu de boucler 10 fois, écrivez un programme qui alloue de la mémoire jusqu'à ce que malloc()ou calloc()renvoie NULL.

Que se passe-t-il si vous ajoutez memset()?

Dietrich Epp
la source
7
@Dietrich: l'explication de la mémoire virtuelle de Dietrich sur le système d'exploitation allouant plusieurs fois la même page remplie de zéro pour calloc est facile à vérifier. Ajoutez simplement une boucle qui écrit des données indésirables dans chaque page de mémoire allouée (l'écriture d'un octet tous les 500 octets devrait suffire). Le résultat global devrait alors devenir beaucoup plus proche car le système serait obligé d'allouer réellement différentes pages dans les deux cas.
kriss
1
@kriss: en effet, bien qu'un octet tous les 4096 soit suffisant sur la grande majorité des systèmes
Dietrich Epp
En fait, calloc()fait souvent partie de la mallocsuite d'implémentation, et donc optimisé pour ne pas appeler bzerolors de l'obtention de la mémoire mmap.
mirabilos
1
Merci d'avoir édité, c'est presque ce que j'avais en tête. Au début, vous déclarez toujours utiliser calloc au lieu de malloc + memset. Veuillez indiquer 1. par défaut pour malloc 2. si une petite partie du tampon doit être mise à zéro, définissez cette partie 3. sinon utilisez calloc. En particulier, NE PAS malloc + memset toute la taille (utilisez calloc pour cela) et NE PAS par défaut tout appeler car cela gêne des choses comme valgrind et les analyseurs de code statique (toute la mémoire est soudainement initialisée). A part ça, je pense que ça va.
employé du mois
5
Bien qu'il ne soit pas lié à la vitesse, il callocest également moins sujet aux bogues. Autrement dit, où large_int * large_intentraînerait un débordement, calloc(large_int, large_int)renvoie NULL, mais malloc(large_int * large_int)est un comportement indéfini, car vous ne connaissez pas la taille réelle du bloc de mémoire renvoyé.
Dunes
12

Parce que sur de nombreux systèmes, en moins de temps de traitement, le système d'exploitation définit automatiquement la mémoire libre à zéro et la marque comme sûre calloc(), donc lorsque vous appelez calloc(), il peut déjà avoir une mémoire libre et zéro à vous donner.

Chris Lutz
la source
2
Êtes-vous sûr? Quels systèmes font cela? Je pensais que la plupart des systèmes d'exploitation arrêtaient simplement le processeur lorsqu'ils étaient inactifs et mettaient à zéro la mémoire à la demande pour les processus alloués dès qu'ils écrivent dans cette mémoire (mais pas lorsqu'ils l'allouent).
Dietrich Epp du
@Dietrich - Pas sûr. Je l'ai entendu une fois et cela semblait être un moyen raisonnable (et raisonnablement simple) de rendre calloc()plus efficace.
Chris Lutz
@Pierreten - Je ne trouve pas de bonnes informations sur les calloc()optimisations spécifiques et je n'ai pas envie d'interpréter le code source libc pour l'OP. Pouvez-vous rechercher quoi que ce soit pour montrer que cette optimisation n'existe pas / ne fonctionne pas?
Chris Lutz
13
@Dietrich: FreeBSD est censé remplir à zéro les pages en temps d'inactivité: voir son paramètre vm.idlezero_enable.
Zan Lynx
1
@DietrichEpp désolé pour necro, mais par exemple Windows le fait.
Andreas Grapentin
1

Sur certaines plates-formes dans certains modes, malloc initialise la mémoire à une valeur généralement non nulle avant de la renvoyer, de sorte que la deuxième version pourrait bien initialiser la mémoire deux fois

Stewart
la source