2 votes

Importance du remplissage dans l'allocation dynamique de mémoire

J'essaie d'implémenter un tas (liste libre implicite avec en-tête/pied) et je suis en train de décider si je dois y ajouter du remplissage. Quels sont les avantages concrets de l'ajout de rembourrages ? J'ai lu que cela réduit en quelque sorte la fragmentation, mais je ne comprends pas vraiment pourquoi c'est le cas. En outre, je suis intéressé par le type d'avantages en termes de performances que je peux obtenir en termes de temps.

Est-ce que cela aide aussi la localité dans mon programme et comment cela aide-t-il ?

Dois-je remplir tout le bloc dans un format de 4 ou 8 octets multiples ou dois-je remplir mon bloc en excluant l'en-tête et le pied de page ?

J'ai oublié de mentionner qu'il s'agit d'une implémentation C utilisant unistd sous linux.

1voto

Broman Points 5642

J'ai lu qu'il réduit en quelque sorte la fragmentation, mais je ne comprends pas vraiment pourquoi c'est le cas.

C'est exact. Et cela fonctionne parce que cela fixe une taille minimale pour les allocations. Disons que vous ajoutez du padding pour que chaque bloc fasse au moins 1kB. Cela signifie qu'il n'y aura jamais de situation où vous libérez une partie de la mémoire et où une allocation faite après cela ne tiendra pas dans cette mémoire nouvellement libérée, tant que la nouvelle allocation fait au maximum 1 ko.

Vous pouvez facilement constater cet effet par vous-même en réalisant quelques expériences simples sur une feuille de papier. Commencez par avoir une taille de bloc égale à votre mémoire totale. Bien sûr, il n'y aura pas de fragmentation, mais vous gaspillerez beaucoup de mémoire. Si la taille du bloc est égale à la moitié de la taille totale, c'est à peu près le même scénario, mais avec moins de gaspillage. Lorsque la taille du bloc correspond à un tiers de la mémoire totale, nous rencontrons d'abord la fragmentation. Et cela se produit lorsque le bloc du milieu est alloué.

En bref, le remplissage réduit la fragmentation mais nécessite plus de mémoire.

Dois-je remplir tout le bloc dans un format de 4 ou 8 octets multiples ou dois-je remplir mon bloc en excluant l'en-tête et le pied de page ?

Si vous l'implémentez de manière intelligente, vous pourrez alors modifier la taille du rembourrage en changeant simplement une variable. Trouvez donc un moyen de mesurer les problèmes et d'adapter le rembourrage à vos besoins.

Est-ce que cela aide aussi la localité dans mon programme et comment cela aide-t-il ?

C'est plus délicat. Cela peut aller dans les deux sens et dépend des programmes qui utilisent le tas. Mais mon intuition me dit que le remplissage diminuerait probablement la localité. Si c'est le cas, cela peut avoir un impact sur les performances à cause des ratés du cache.

1voto

cmaster Points 7460

Réponse de klutt donne la raison pour laquelle vous pouvez vouloir un peu de rembourrage (significatif). Cependant, il y a aussi une raison pour laquelle vous besoin de une certaine quantité minimale de rembourrage : Alignement.

Les blocs de mémoire que votre allocateur distribue doivent être utilisables avec n'importe quel type de données, et de nombreux types de données ont des exigences d'alignement. En général, un élément de données mal aligné fait ramper les accès comme une limace, mais certains types de données peuvent avoir une exigence d'alignement stricte. Par exemple, un processeur PPC ne peut tout simplement pas charger un vecteur (16 octets) à partir d'une adresse qui n'est pas divisible par 16. Ces exigences d'alignement sont très spécifiques à la plate-forme.

En tant que tel, votre allocateur doit aligner toute adresse mémoire qu'il renvoie sur le plus grand alignement requis par le CPU (16 octets dans le cas du PPC) et, par conséquent, remplir tous les blocs mémoire sur ce quantum minimum de mémoire.

Il peut même être judicieux de compléter les allocations de mémoire par des lignes de cache complètes (64 octets sur X86-64, si je ne me trompe pas), mais ce n'est pas une obligation.

À partir de cette taille de bloc minimale, les allocateurs complètent généralement les allocations à la puissance deux suivante, ou similaire, afin de réduire le nombre de tailles de blocs mémoire différentes qu'ils doivent gérer.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X