Qu’est-ce que la fragmentation de la mémoire?

J’ai entendu le terme “fragmentation de la mémoire” utilisé à quelques resockets dans le cadre de l’allocation de mémoire dynamic C ++. J’ai trouvé quelques questions sur la façon de gérer la fragmentation de la mémoire, mais je ne trouve pas de question directe qui le traite lui-même. Alors:

  • Qu’est-ce que la fragmentation de la mémoire?
  • Comment savoir si la fragmentation de la mémoire est un problème pour mon application? Quel type de programme est le plus susceptible de souffrir?
  • Quelles sont les bonnes manières de gérer la fragmentation de la mémoire?

Aussi:

  • J’ai entendu dire que l’utilisation d’allocations dynamics peut augmenter la fragmentation de la mémoire. Est-ce vrai? Dans le contexte de C ++, je comprends que tous les conteneurs standard (std :: ssortingng, std :: vector, etc.) utilisent l’allocation de mémoire dynamic. Si ceux-ci sont utilisés tout au long d’un programme (en particulier std :: ssortingng), la fragmentation de la mémoire est-elle plus susceptible de poser problème?
  • Comment la fragmentation de la mémoire peut-elle être traitée dans une application STL lourde?

Imaginez que vous ayez une “grande” (32 octets) de mémoire libre:

---------------------------------- | | ---------------------------------- 

Maintenant, allouez-en une partie (5 allocations):

 ---------------------------------- |aaaabbccccccddeeee | ---------------------------------- 

Maintenant, libérez les quatre premières allocations mais pas la cinquième:

 ---------------------------------- | eeee | ---------------------------------- 

Maintenant, essayez d’allouer 16 octets. Oups, je ne peux pas, même s’il y a presque deux fois plus de liberté.

Sur les systèmes dotés de mémoire virtuelle, la fragmentation pose moins de problèmes que vous ne le pensez, car les allocations importantes ne doivent être contiguës que dans l’espace d’adressage virtuel et non dans l’ espace d’adressage physique . Donc, dans mon exemple, si j’avais une mémoire virtuelle avec une taille de page de 2 octets, je pourrais faire mon allocation de 16 octets sans problème. La mémoire physique ressemblerait à ceci:

 ---------------------------------- |ffffffffffffffeeeeff | ---------------------------------- 

alors que la mémoire virtuelle (étant beaucoup plus grande) pourrait ressembler à ceci:

 ------------------------------------------------------... | eeeeffffffffffffffff ------------------------------------------------------... 

Le symptôme classique de la fragmentation de la mémoire est que vous essayez d’allouer un gros bloc et que vous ne pouvez pas, même si vous semblez avoir suffisamment de mémoire libre. Une autre conséquence possible est l’incapacité du processus à libérer de la mémoire sur le système d’exploitation (car certains objects sont encore utilisés dans tous les blocs du système d’exploitation, même si ces blocs ne sont plus utilisés).

Tactiques pour empêcher la fragmentation de la mémoire en C ++ en allouant des objects provenant de différentes zones en fonction de leur taille et / ou de leur durée de vie prévue. Donc, si vous voulez créer beaucoup d’objects et les détruire tous plus tard, allouez-les à partir d’un pool de mémoire. Toutes les autres allocations que vous effectuez entre elles ne proviendront pas du pool, elles ne seront donc pas situées entre elles en mémoire, de sorte que la mémoire ne sera pas fragmentée en conséquence.

En général, vous n’avez pas à vous soucier de cela, à moins que votre programme ne soit long et qu’il alloue beaucoup de ressources. C’est lorsque vous avez des mélanges d’objects de courte durée et de longue durée que vous êtes le plus à risque, mais même alors, malloc fera de son mieux pour vous aider. Fondamentalement, ignorez-le jusqu’à ce que votre programme ait des échecs d’allocation ou que le système manque de mémoire de manière inattendue (attrapez ceci dans les tests, de préférence!).

Les bibliothèques standard ne sont pas pires que toute autre qui alloue de la mémoire, et les conteneurs standard ont tous un paramètre de modèle Alloc que vous pouvez utiliser pour affiner leur stratégie d’allocation si cela est absolument nécessaire.

Qu’est-ce que la fragmentation de la mémoire?

La fragmentation de la mémoire se produit lorsque la majeure partie de votre mémoire est allouée dans un grand nombre de blocs non contigus, ou morceaux, ce qui laisse un bon pourcentage de votre mémoire totale non allouée, mais inutilisable pour la plupart des scénarios typiques. Cela entraîne des exceptions de mémoire insuffisante ou des erreurs d’allocation (c.-à-d. Que malloc renvoie null).

La manière la plus simple d’y penser est d’imaginer que vous avez un grand mur vide sur lequel vous devez placer des images de différentes tailles . Chaque image prend une certaine taille et vous ne pouvez évidemment pas la diviser en morceaux plus petits pour la rendre compatible. Vous avez besoin d’un endroit vide sur le mur, de la taille de l’image, sinon vous ne pouvez pas le mettre en place. Maintenant, si vous commencez à accrocher des images sur le mur et que vous ne faites pas attention à la façon dont vous les arrangez, vous vous retrouverez bientôt avec un mur partiellement couvert d’images et même si vous avez des espaces vides parce qu’ils sont plus grands que les spots disponibles. Vous pouvez toujours accrocher de très petites images, mais la plupart ne conviennent pas. Donc, vous devrez réorganiser (ceux qui sont déjà sur le mur) pour faire de la place pour plus de choses.

Maintenant, imaginez que le mur est votre mémoire (tas) et que les images sont des objects. C’est la fragmentation de la mémoire.

Comment savoir si la fragmentation de la mémoire est un problème pour mon application? Quel type de programme est le plus susceptible de souffrir?

Un signe révélateur que vous pourriez être confronté à la fragmentation de la mémoire est la présence de nombreuses erreurs d’allocation, en particulier lorsque le pourcentage de mémoire utilisée est élevé – mais vous n’avez pas encore épuisé toute la mémoire. pour les objects que vous essayez d’allouer.

Lorsque la mémoire est fortement fragmentée, les allocations de mémoire prendront probablement plus de temps car l’allocateur de mémoire doit faire plus d’efforts pour trouver un espace approprié pour le nouvel object. Si, à son tour, vous avez de nombreuses allocations de mémoire (ce que vous faites probablement depuis que vous avez fini avec la fragmentation de la mémoire), le temps d’allocation peut même entraîner des retards notables.

Quelles sont les bonnes manières de gérer la fragmentation de la mémoire?

Utilisez un bon algorithme pour allouer de la mémoire. Au lieu d’allouer de la mémoire pour beaucoup de petits objects, pré-alloue la mémoire pour un tableau contigu de ces objects plus petits. Parfois, un peu de gaspillage lors de l’allocation de mémoire peut être un facteur de performance et peut vous éviter de devoir gérer une fragmentation de la mémoire.

La fragmentation de la mémoire est le même concept que la fragmentation du disque: elle fait référence au gaspillage de l’espace parce que les zones utilisées ne sont pas suffisamment compactées.

Supposons que, pour un simple exemple de jouet, vous disposez de dix octets de mémoire:

  | | | | | | | | | | | 0 1 2 3 4 5 6 7 8 9 

Allouons maintenant trois blocs de trois octets, nommés A, B et C:

  | A | A | A | B | B | B | C | C | C | | 0 1 2 3 4 5 6 7 8 9 

Désactivez maintenant le bloc B:

  | A | A | A | | | | C | C | C | | 0 1 2 3 4 5 6 7 8 9 

Maintenant, que se passe-t-il si nous essayons d’allouer un bloc de quatre octets D? Eh bien, nous avons quatre octets de mémoire libre, mais nous ne disposons pas de quatre octets contigus de mémoire libre, nous ne pouvons donc pas atsortingbuer D! Ceci est une utilisation inefficace de la mémoire, car nous aurions dû être en mesure de stocker D, mais nous n’en avons pas pu. Et nous ne pouvons pas déplacer C pour faire de la place, car il est très probable que certaines variables de notre programme pointent vers C, et nous ne pouvons pas trouver et modifier automatiquement toutes ces valeurs.

Comment savez-vous que c’est un problème? Le plus grand signe est que la taille de la mémoire virtuelle de votre programme est considérablement plus grande que la quantité de mémoire que vous utilisez réellement. Dans un exemple réel, vous aurez beaucoup plus de dix octets de mémoire, donc D se verra atsortingbuer un octet 9 et les octets 3-5 restront inutilisés, à moins que vous n’atsortingbuiez quelque chose de trois octets de long ou plus petit.

Dans cet exemple, 3 octets ne sont pas un gâchis, mais considérez un cas plus pathologique où deux allocations d’un couple d’octets sont, par exemple, séparées de 10 mégaoctets dans la mémoire, et vous devez allouer un bloc de 10 mégaoctets + 1 octet. Il faut aller demander au système d’exploitation plus de dix méga-octets de mémoire virtuelle de plus pour le faire, même si vous n’avez qu’un seul octet de manque d’espace.

Comment l’en empêchez-vous? Les pires cas ont tendance à se produire lorsque vous créez et détruisez fréquemment de petits objects, car cela a tendance à produire un effet «fromage suisse» avec de nombreux petits objects séparés par de nombreux petits trous, ce qui rend impossible Lorsque vous savez que vous allez faire cela, une stratégie efficace consiste à pré-allouer un grand bloc de mémoire en tant que pool pour vos petits objects, puis à gérer manuellement la création des petits objects dans ce bloc, plutôt que de laisser l’allocateur par défaut le gère.

En général, moins vous faites d’allocations, moins la mémoire risque d’être fragmentée. Cependant, le TSL gère ce problème de manière assez efficace. Si vous avez une chaîne qui utilise l’intégralité de son allocation actuelle et que vous y ajoutez un caractère, elle ne se ré-affecte pas simplement à sa longueur actuelle plus une, elle double sa longueur. Il s’agit d’une variante de la stratégie de «pool pour les petites allocations fréquentes». La chaîne saisit une grande partie de la mémoire afin de pouvoir traiter efficacement les petites augmentations répétées sans faire de petites réallocations répétées. En fait, tous les conteneurs STL font ce genre de choses, vous n’avez donc généralement pas besoin de trop vous soucier de la fragmentation causée par la réallocation automatique des conteneurs STL.

Bien sûr, les conteneurs STL ne regroupent pas la mémoire entre eux. Par conséquent, si vous prévoyez de créer de nombreux petits conteneurs (plutôt que quelques conteneurs à redimensionner fréquemment), vous devrez peut-être éviter la fragmentation de la même manière que vous. serait pour tous les petits objects fréquemment créés, STL ou non.

  • Qu’est-ce que la fragmentation de la mémoire?

La fragmentation de la mémoire est le problème de la mémoire devenant inutilisable même si elle est théoriquement disponible. Il existe deux types de fragmentation: la fragmentation interne est la mémoire allouée mais qui ne peut pas être utilisée (par exemple, lorsque la mémoire est allouée par blocs de 8 octets, mais que le programme ne répète que 4 octets). La fragmentation externe est le problème de la séparation de la mémoire libre en plusieurs petits blocs, de sorte que les demandes d’allocation importantes ne peuvent pas être satisfaites, même si la mémoire libre globale est suffisante.

  • Comment savoir si la fragmentation de la mémoire est un problème pour mon application? Quel type de programme est le plus susceptible de souffrir?

la fragmentation de la mémoire est un problème si votre programme utilise beaucoup plus de mémoire système que ce que nécessiteraient ses données de paylod réelles (et vous avez exclu les memory leaks).

  • Quelles sont les bonnes manières de gérer la fragmentation de la mémoire?

Utilisez un bon allocateur de mémoire. IIRC, ceux qui utilisent une stratégie de “meilleur ajustement” sont généralement beaucoup plus efficaces pour éviter la fragmentation, même si c’est un peu plus lent. Cependant, il a également été démontré que pour toute stratégie d’allocation, il existe des cas pathologiques les plus graves. Heureusement, les modèles d’allocation typiques de la plupart des applications sont en réalité relativement bénins pour les allocateurs. Il y a un tas de papiers là-bas si vous êtes intéressé par les détails:

  • Paul R. Wilson, Mark S. Johnstone, Michael Neely et David Boles. Allocation de stockage dynamic: une enquête et un examen critique. In Proceedings of 1995 Atelier international sur la gestion de la mémoire, Springer Verlag LNCS, 1995
  • Mark S.Johnstone, Paul R. Wilson. Le problème de la fragmentation de la mémoire: résolu? Dans ACM SIG-PLAN Notices, volume 34 n ° 3, pages 26-36, 1999
  • M. Garey, RL Graham et JD Ullman. Analyse des pires cas d’algorithmes d’allocation de mémoire. Quasortingème symposium annuel de l’ACM sur la théorie de l’informatique, 1972

Mettre à jour:
Google TCMalloc: Throc-Caching Malloc
Il s’est avéré qu’il est assez efficace pour gérer la fragmentation dans un processus de longue durée.


J’ai développé une application de serveur qui avait des problèmes de fragmentation de la mémoire sur HP-UX 11.23 / 11.31 ia64.

Cela ressemblait à ça. Un processus effectuait des allocations de mémoire et des désallocations et était exécuté pendant des jours. Et même s’il n’y avait pas de memory leaks, la consommation de mémoire du processus continuait à augmenter.

A propos de mon expérience Sur HP-UX, il est très facile de trouver la fragmentation de la mémoire à l’aide de HP-UX gdb. Vous définissez un point d’arrêt et lorsque vous appuyez dessus, vous exécutez cette commande: info heap et affichez toutes les allocations de mémoire pour le processus et la taille totale du segment de mémoire. Ensuite, continuez votre programme, puis quelque temps plus tard, vous atteignez le sharepoint rupture. Vous recommencez le info heap . Si la taille totale du segment de mémoire est supérieure mais que le nombre et la taille des allocations séparées sont identiques, il est probable que vous ayez des problèmes d’allocation de mémoire. Si nécessaire, faites quelques vérifications.

Ma façon d’améliorer la situation était la suivante. Après avoir effectué une parsing avec HP-UX gdb, j’ai constaté que les problèmes de mémoire étaient dus au fait que j’utilisais std::vector pour stocker certains types d’informations dans une firebase database. std::vector exige que ses données soient conservées dans un bloc. J’ai eu quelques conteneurs basés sur std::vector . Ces conteneurs ont été régulièrement recréés. Il arrivait souvent que de nouveaux enregistrements soient ajoutés à la firebase database et que les conteneurs soient ensuite recréés. Et comme les conteneurs recréés étaient plus gros, ils ne rentraient pas dans les blocs de mémoire disponibles et le runtime demandait un nouveau bloc plus important du système d’exploitation. Par conséquent, même en l’absence de memory leaks, la consommation de mémoire du processus a augmenté. J’ai amélioré la situation lorsque j’ai changé les conteneurs. Au lieu de std::vector j’ai commencé à utiliser std::deque qui a une manière différente d’allouer de la mémoire pour les données.

Je sais que l’une des façons d’éviter la fragmentation de la mémoire sur HP-UX consiste à utiliser soit l’allocation de blocs de petite taille, soit l’utilisation de MallocNextGen. Sur RedHat Linux, l’allocateur par défaut semble gérer assez bien l’allocation de nombreux petits blocs. Sous Windows, il existe un segment de mémoire à Low-fragmentation Heap qui résout le problème du grand nombre de petites allocations.

D’après ce que je comprends, dans une application lourde en STL, vous devez d’abord identifier les problèmes. Les allocateurs de mémoire (comme dans libc) gèrent en fait le problème de nombreuses petites allocations, ce qui est typique pour std::ssortingng (par exemple, dans mon application serveur, il y a beaucoup de chaînes STL mais comme causer des problèmes). Mon impression est que vous devez éviter les allocations fréquentes et importantes. Malheureusement, il existe des situations où vous ne pouvez pas les éviter et devez changer votre code. Comme je l’ai dit dans mon cas, j’ai amélioré la situation en passant à std::deque . Si vous identifiez votre fragment de mémoire, il est possible d’en parler plus précisément.

La fragmentation de la mémoire est le plus susceptible de se produire lorsque vous allouez et libérez de nombreux objects de tailles différentes. Supposons que vous ayez la disposition suivante en mémoire:

 obj1 (10kb) | obj2(20kb) | obj3(5kb) | unused space (100kb) 

Maintenant, lorsque obj2 est publié, vous disposez de 120 Ko de mémoire inutilisée, mais vous ne pouvez pas allouer un bloc complet de 120 Ko, car la mémoire est fragmentée.

Les techniques courantes pour éviter cet effet incluent les tampons en anneau et les pools d’objects . Dans le contexte de la STL, des méthodes telles que std::vector::reserve() peuvent aider.

Une réponse très détaillée sur la fragmentation de la mémoire peut être trouvée ici.

http://library.softwareverify.com/memory-fragmentation-your-worst-nightmare/

Ceci est l’aboutissement de 11 années de réponses à la fragmentation de la mémoire que j’ai fournies aux personnes qui m’ont posé des questions sur la fragmentation de la mémoire sur softwareverify.com

Qu’est-ce que la fragmentation de la mémoire?

Lorsque votre application utilise la mémoire dynamic, elle alloue et libère des morceaux de mémoire. Au début, la totalité de l’espace mémoire de votre application est un bloc de mémoire libre contigu. Cependant, lorsque vous allouez et libérez des blocs de taille différente, la mémoire commence à être fragmentée , c’est-à-dire qu’à la place d’un gros bloc contigu libre et d’un nombre de blocs alloués contigus, des blocs alloués et libres sont mélangés. Les blocs libres ayant une taille limitée, il est difficile de les réutiliser. Par exemple, vous pouvez avoir 1000 octets de mémoire libre, mais vous ne pouvez pas allouer de mémoire pour un bloc de 100 octets, car tous les blocs libres ont une longueur maximale de 50 octets.

Une autre source de fragmentation, inévitable mais moins problématique, est que dans la plupart des architectures, les adresses mémoire doivent être alignées sur 2, 4, 8 etc. limites d’octets (les adresses doivent être des multiples de 2, 4, 8, etc.) Même si vous avez par exemple une structure contenant 3 champs de caractères, votre structure peut avoir une taille de 12 au lieu de 3, car chaque champ est aligné sur une limite de 4 octets.

Comment savoir si la fragmentation de la mémoire est un problème pour mon application? Quel type de programme est le plus susceptible de souffrir?

La réponse évidente est que vous obtenez une exception de mémoire insuffisante.

Apparemment, il n’y a pas de moyen portable de détecter la fragmentation de la mémoire dans les applications C ++. Voir cette réponse pour plus de détails.

Quelles sont les bonnes manières de gérer la fragmentation de la mémoire?

C’est difficile en C ++, puisque vous utilisez des adresses de mémoire directe dans des pointeurs et que vous n’avez aucun contrôle sur les références à une adresse mémoire spécifique. La réorganisation des blocs de mémoire alloués (comme le fait le ramasse-miettes Java) n’est donc pas une option.

Un allocateur personnalisé peut aider en gérant l’allocation de petits objects dans un plus gros bloc de mémoire et en réutilisant les emplacements libres dans ce bloc.

Ceci est une version super simplifiée pour les nuls.

Lorsque des objects sont créés en mémoire, ils sont ajoutés à la fin de la partie utilisée en mémoire.

Si un object qui n’est pas à la fin de la partie de mémoire utilisée est supprimé, ce qui signifie que cet object se trouve entre 2 autres objects, il créera un “trou”.

C’est ce qu’on appelle la fragmentation.

Lorsque vous souhaitez append un élément sur le tas, l’ordinateur doit effectuer une recherche d’espace pour cet élément. C’est pourquoi les allocations dynamics, si elles ne sont pas effectuées sur un pool de mémoire ou avec un allocateur en pool, peuvent ralentir les choses. Pour une application STL lourde, si vous faites du multi-threading, il y a l’ allocateur Hoard ou la version TBB Intel .

Maintenant, lorsque la mémoire est fragmentée, deux choses peuvent se produire:

  1. Il faudra faire plus de recherches pour trouver un bon espace pour coller de “gros” objects. Autrement dit, avec de nombreux petits objects éparpillés pour trouver un morceau de mémoire contigieux, cela pourrait dans certaines conditions être difficile (ils sont extrêmes).
  2. La mémoire n’est pas une entité facile à lire. Les processeurs sont limités à combien ils peuvent contenir et où. Ils le font en échangeant des pages si un élément dont ils ont besoin est un endroit mais les adresses actuelles en sont une autre. Si vous devez constamment changer de page, le traitement peut ralentir (là encore, des scénarios extrêmes ont un impact sur les performances). Voir cette publication sur la mémoire virtuelle .

La fragmentation de la mémoire se produit car des blocs de mémoire de tailles différentes sont demandés. Considérons un tampon de 100 octets. Vous demandez deux caractères, puis un entier. Maintenant, vous libérez les deux caractères, puis demandez un nouvel entier, mais cet entier ne peut pas tenir dans l’espace des deux caractères. Cette mémoire ne peut pas être réutilisée car elle ne se trouve pas dans un bloc contigu assez grand pour être ré-alloué. En plus de cela, vous avez invoqué beaucoup de surcharge d’allocateur pour vos caractères.

Essentiellement, la mémoire ne vient que dans des blocs d’une certaine taille sur la plupart des systèmes. Une fois que vous séparez ces blocs, ils ne peuvent plus être rejoints tant que le bloc entier n’est pas libéré. Cela peut conduire à l’utilisation de blocs entiers lorsque seule une petite partie du bloc est utilisée.

Le principal moyen de réduire la fragmentation du tas consiste à effectuer des allocations plus importantes et moins fréquentes. À l’extrême, vous pouvez utiliser un segment géré capable de déplacer des objects, au moins, dans votre propre code. Cela élimine complètement le problème – du sharepoint vue de la mémoire, de toute façon. Evidemment, les objects en mouvement ont un coût. En réalité, vous n’avez vraiment de problème que si vous allouez souvent de très petites quantités. Utiliser des conteneurs contigus (vector, ssortingng, etc.) et allouer autant de ressources humaines que possible (toujours une bonne idée des performances) est le meilleur moyen de le réduire. Cela augmente également la cohérence du cache, ce qui accélère l’exécution de votre application.

Ce que vous devez retenir, c’est que sur un système de bureau 32 bits x86, vous avez une mémoire de 2 Go, qui est divisée en 4 Ko “(il est certain que la taille de la page est la même sur tous les systèmes x86). Vous devrez appeler une fragmentation omgwtfbbq pour avoir un problème. La fragmentation est vraiment un problème du passé, car les tas modernes sont excessivement importants pour la grande majorité des applications, et il existe une prédominance de systèmes capables de le supporter, tels que les tas gérés.