Comment éviter la fragmentation du tas?

Question

Je travaille actuellement sur un projet de traitement d'images médicales qui nécessite une énorme quantité de mémoire. Puis-je faire quelque chose pour éviter la fragmentation du tas et pour accélérer l’accès aux données d’image déjà chargées en mémoire?

L'application a été écrite en C ++ et fonctionne sous Windows XP.

MODIFIER: l'application effectue un prétraitement des données d'image, tel que le reformatage, le calcul de tables de conversion, l'extraction d'images secondaires intéressantes ... L'application nécessite environ 2 Go de RAM pendant le traitement, dont environ 1,5 Go peuvent être utilisés pour les données d'image.

Answer 1

Si vous effectuez un traitement d’images médicales, il est probable que vous allouiez de gros blocs à la fois (images 512x512, 2 octets par pixel). La fragmentation vous mordra si vous allouez des objets plus petits entre les allocations de tampons d’image.

L'écriture d'un allocateur personnalisé n'est pas nécessairement difficile pour ce cas d'utilisation particulier. Vous pouvez utiliser l'allocateur C ++ standard pour votre objet Image, mais pour le tampon de pixels, vous pouvez utiliser une allocation personnalisée gérée dans votre objet Image. Voici un aperçu rapide et sale:

• Utilisez un tableau statique de structures, chaque structure a:
  • Un bloc de mémoire solide pouvant contenir N images. Ce découpage vous aidera à contrôler la fragmentation. Essayez un nombre initial de 5 ou plus.
  • Un tableau parallèle de bools indiquant si l'image correspondante est utilisée
• Pour allouer, recherchez dans le tableau un tampon vide et définissez son indicateur.
  • Si aucune n'est trouvée, ajoutez une nouvelle structure à la fin du tableau
• Pour désallouer, recherchez le tampon correspondant dans le ou les tableaux et effacez le drapeau booléen

Ce n’est qu’une idée simple, laissant beaucoup de place à la variation. L'astuce principale consiste à éviter de libérer et de réaffecter les tampons de pixels de l'image.

Answer 2

Il y a des réponses, mais il est difficile d'être général sans connaître les détails du problème.

J'assume Windows XP 32 bits.

Essayez d’éviter d’avoir besoin de 100 Mo de mémoire contiguë. Si vous n’êtes pas chanceux, quelques dll aléatoires se chargeront à des points non probants dans votre espace d’adresse disponible, ce qui réduira rapidement les très grandes zones de mémoire contiguë. En fonction des API dont vous avez besoin, cela peut être assez difficile à éviter. Il peut être assez surprenant de constater que le simple fait d'allouer quelques blocs de 400 Mo de mémoire en plus d'une utilisation de mémoire «normale» peut vous laisser avec nulle part où allouer un dernier petit bloc de 40 Mo.

D'autre part, préallouez des morceaux de taille raisonnable à la fois. De l'ordre de 10 Mo environ est une bonne taille de bloc de compromis. Si vous parvenez à partitionner vos données dans ce type de morceaux, vous pourrez remplir l'espace d'adressage de manière raisonnablement efficace.

Si vous allez toujours manquer d’espace d’adresse, vous devrez pouvoir faire défiler des blocs en fonction du type d’algorithme de mise en cache. Le choix des bons blocs pour la recherche de pages dépendra beaucoup de votre algorithme de traitement et nécessitera une analyse minutieuse.

Choisir une autre page est une autre décision. Vous pourriez décider de simplement les écrire dans des fichiers temporaires. Vous pouvez également étudier l'API Address Windowing Extenstions de Microsoft. Dans les deux cas, vous devez être prudent dans la conception de votre application pour nettoyer tous les pointeurs qui pointent vers quelque chose qui va être renvoyé, sinon de très mauvaises choses (tm) se produiront.

Bonne chance!

Answer 3

Si vous envisagez d'effectuer des opérations sur une matrice d'image de grande taille, envisagez une technique appelée "mosaïque". L'idée est généralement de charger l'image en mémoire de sorte que le même bloc d'octets contigu ne contienne pas de pixels sur une ligne, mais plutôt un carré dans un espace 2D. Cela s'explique par le fait que vous feriez davantage d'opérations plus proches les unes des autres en 2D plutôt que sur une seule ligne de balayage.

Cela ne réduira pas votre utilisation de la mémoire, mais pourrait avoir un impact considérable sur la permutation de pages et les performances.

Answer 4

Sans plus d'informations sur le problème (par exemple, le langage), vous pouvez éviter le désaffectation des allocations en réutilisant les allocations et non en les affectant, en les exploitant et en les libérant. Un allocateur tel que dlmalloc gère mieux la fragmentation que les tas Win32.

Answer 5

Ce que vous allez frapper ici est la limite de la plage d'adresses virtuelle, qui avec Windows 32b vous donne au plus 2 Go. Vous devez également savoir que l’utilisation d’une API graphique telle que DirectX ou OpenGL utilisera des portions étendues de ces 2 Go pour le tampon d’image, les textures et autres données similaires.

1,5-2 Go pour une application 32b est assez difficile à atteindre. La méthode la plus élégante consiste à utiliser les systèmes d’exploitation 64b et 64b. Même avec un système d’exploitation 64b et une application 32b, cela peut être relativement viable, tant que vous utilisez LARGE_ADDRESS_AWARE .

Toutefois, comme vous devez stocker des données d'image, vous pourrez peut-être également contourner ce problème en utilisant Mappage de fichiers en tant que magasin de mémoire - vous pouvez le faire de manière à disposer d'une mémoire validée et accessible, mais sans utiliser d'adresse virtuelle. .

Answer 6

En supposant que vous vouliez dire éviter la fragmentation et non éviter la défragmentation . Devinez également que vous travaillez avec un langage non géré (probablement c ou C ++). Je suggérerais que vous allouiez de gros morceaux de mémoire, puis que vous allouiez des allocations de tas à partir des blocs de mémoire alloués. Ce pool de mémoire, car contient de gros blocs de mémoire, est moins sujet à la fragmentation. Pour résumer, vous devez implémenter un allocateur de mémoire personnalisé.

Voir quelques idées générales sur ce ici .

Answer 7

Je pense que vous utilisez quelque chose de non géré, car dans les plateformes gérées, le système (ramasse-miettes) prend en charge la fragmentation.

Pour C / C ++, vous pouvez utiliser un autre allocateur que celui par défaut. (il y avait déjà quelques discussions sur les allocateurs sur stackowerflow).

Vous pouvez également créer votre propre stockage de données. Par exemple, dans le projet sur lequel je travaille actuellement, nous avons un stockage personnalisé (pool) pour les bitmaps (nous les stockons dans un grand morceau de mémoire contigus), car nous en avons beaucoup, et nous gardons trace des tas fragmentation et défragmenter quand la fragmentation est trop grande.

Answer 8

Vous devrez peut-être implémenter la gestion manuelle de la mémoire. Les données de l'image ont-elles vécu longtemps? Sinon, vous pouvez utiliser le modèle utilisé par le serveur Web Apache: allouer de grandes quantités de mémoire et les placer dans des pools de mémoire. Passez ces pools comme dernier argument des fonctions afin qu'ils puissent utiliser le pool pour répondre au besoin d'allouer de la mémoire temporaire. Une fois la chaîne d’appel terminée, vous ne devez plus utiliser toute la mémoire du pool. Vous pouvez ainsi nettoyer la zone mémoire et l’utiliser à nouveau. Les allocations sont rapides, car elles ne signifient que l'ajout d'une valeur à un pointeur. La désallocation est très rapide car vous allez libérer de très grands blocs de mémoire à la fois.

Si votre application est multithread, vous devrez peut-être stocker le pool dans le stockage local des unités d'exécution afin d'éviter les frais de communication entre unités d'exécution.

Answer 9

Si vous pouvez isoler exactement les endroits où vous êtes susceptible d’allouer de gros blocs, vous pouvez (sous Windows) appeler directement VirtualAlloc au lieu de passer par le gestionnaire de mémoire. Cela évitera la fragmentation au sein du gestionnaire de mémoire normal.

Il s’agit d’une solution simple qui ne nécessite pas l’utilisation d’un gestionnaire de mémoire personnalisé.