Pourquoi malloc + memset est plus lent que calloc?

On sait que calloc est différent de malloc dans le sens où 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 calloc comme malloc + memset . Incidemment, pour le plaisir, j’ai écrit le code suivant pour un benchmark.

Le résultat est déroutant.

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

Sortie du code 1:

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

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

Sortie du code 2:

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

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

Ma question est la suivante: pourquoi malloc + memset est memset il beaucoup plus lent que le calloc ? Comment calloc peut- calloc faire ça?

La version courte: utilisez toujours calloc() au lieu de malloc()+memset() . Dans la plupart des cas, ils seront les mêmes. Dans certains cas, calloc() fera moins de travail car il peut ignorer complètement memset() . Dans d’autres cas, calloc() peut même sortingcher et ne pas allouer de mémoire! Cependant, malloc()+memset() fera toujours tout le 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 kernel et les tables de pages. Vous connaissez déjà votre programme, alors …

Les allocateurs de mémoire comme malloc() et calloc() sont la plupart du temps là pour prendre de petites allocations (de 1 à 100 octets) et les regrouper dans des pools de mémoire plus importants. Par exemple, si vous allouez 16 octets, malloc() essaiera d’abord d’obtenir 16 octets sur l’un de ses pools, puis demandera davantage de mémoire au kernel lorsque le pool s’exécute. Cependant, comme le programme dont vous parlez alloue une grande quantité de mémoire à la fois, malloc() et calloc() demandent simplement cette mémoire directement au kernel. Le seuil pour ce comportement dépend de votre système, mais j’ai vu 1 Mio utilisé comme seuil.

Le kernel 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. Cela s’appelle la protection de la mémoire, elle est très répandue depuis les années 1990, et c’est la raison pour laquelle un programme peut tomber en panne sans mettre tout le système hors service. Donc, quand un programme a besoin de plus de mémoire, il ne peut pas simplement prendre de la mémoire, mais il demande plutôt la mémoire du kernel en utilisant un appel système tel que mmap() ou sbrk() . Le kernel donnera de la RAM à chaque processus en modifiant la table de pages.

La table de pages mappe les adresses mémoire à la mémoire vive physique réelle. Les adresses de votre processus, 0x00000000 à 0xFFFFFFFF sur un système 32 bits, ne sont pas de vraies mémoires mais des adresses en mémoire virtuelle. Le processeur divise ces adresses en 4 pages KiB et chaque page peut être affectée à un autre morceau de RAM physique en modifiant la table de pages. Seul le kernel est autorisé à modifier la table de 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 kernel trouve 256 Mo de mémoire vive inutilisée et le donne à votre processus en modifiant la table de pages.

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

  5. Votre processus finit par se terminer et le kernel récupère la mémoire vive 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 pas de cette façon. Il y a trois différences majeures.

  • Lorsque votre processus obtient une nouvelle mémoire du kernel, cette mémoire a probablement déjà été utilisée par un autre processus. Ceci est un risque de sécurité. Et si cette mémoire avait des mots de passe, des clés de chiffrement ou des recettes de salsa secrètes? Pour éviter la fuite de données sensibles, le kernel scrute 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, donc mmap() garantit que la nouvelle mémoire renvoyée est toujours mise à zéro.

  • Il existe de nombreux programmes qui allouent de la mémoire mais n’utilisent pas la mémoire immédiatement. Quelques fois la mémoire est allouée mais jamais utilisée. Le kernel le sait et est paresseux. Lorsque vous allouez une nouvelle mémoire, le kernel ne touche pas du tout la table de pages et ne donne aucune mémoire vive à 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 les étapes du kernel affectent la RAM à ces adresses et reprennent votre programme. Si vous n’utilisez jamais la mémoire, le défaut de page ne se produit jamais et votre programme n’obtient jamais 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 renvoyés par mmap() . Comme ces pages sont toutes identiques, le kernel fait pointer toutes ces adresses virtuelles sur 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 kernel 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 kernel trouve 256 Mio d’ espace d’adresse inutilisé , fait une note sur l’utilisation de cet espace d’adresse et le retourne.

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

  5. Votre processus finit par s’arrêter et le kernel n’a pas besoin de récupérer la mémoire RAM car celle-ci n’a jamais été allouée.

Si vous utilisez memset() pour mettre la page à zéro, memset() déclenchera la page d’erreur, allouera la RAM, puis la réinitialisera même si elle est déjà remplie de zéros. Ceci représente une énorme quantité de travail supplémentaire et explique pourquoi calloc() est plus rapide que malloc() et memset() . Si de toute façon vous utilisez la mémoire, calloc() est toujours plus rapide que malloc() et memset() mais la différence n’est pas si ridicule.


Cela ne marche pas toujours

Tous les systèmes ne disposent pas de mémoire virtuelle paginée, de sorte que tous les systèmes ne peuvent pas utiliser ces optimisations. Cela s’applique aux très anciens processeurs comme le 80286 ainsi qu’aux processeurs intégrés 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 de la mémoire à partir d’un pool partagé au lieu d’aller directement au kernel. 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 avec free() , donc calloc() peut prendre cette mémoire et appeler memset() pour l’effacer. Les implémentations courantes suivront quelles parties du pool partagé sont immaculées et encore 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 kernel peut ou non ne pas avoir de mémoire dans son temps libre, au cas où vous auriez besoin d’obtenir de la mémoire remise à zéro ultérieurement. Linux n’a pas de mémoire à l’avance, et Dragonfly BSD a également récemment supprimé cette fonctionnalité de son kernel . Certains autres kernelx ne prévoient aucune mémoire à l’avance. La remise à zéro des pages au ralenti ne suffit pas pour expliquer les grandes différences de performances.

La fonction calloc() n’utilise pas de version spéciale alignée sur la mémoire de memset() , ce qui ne le rendrait pas beaucoup plus rapide. La plupart des implémentations memset() pour les processeurs modernes ressemblent à 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 que memset() est très rapide et que vous n’allez pas vraiment obtenir mieux pour de gros blocs de mémoire.

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

Tour 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() ?

Parce que sur de nombreux systèmes, dans le temps de traitement de réserve, le système d’exploitation calloc() à zéro la mémoire libre et la calloc() comme étant sûre pour calloc() . Ainsi, lorsque vous appelez calloc() , .

Sur certaines plates-formes de certains modes, malloc initialise la mémoire à une valeur typiquement non nulle avant de la renvoyer, de sorte que la seconde version pourrait bien initialiser la mémoire deux fois