Pourquoi std::allocator::deallocate nécessite-t-il une taille?

Question

std::allocator est une abstraction sur le modèle de mémoire sous-jacent, qui enveloppe la fonctionnalité d'appeler new et delete. delete n'a pas besoin de taille, mais deallocate() le nécessite.

void deallocate( T* p, std::size_t n );
"L'argument n doit être égal au premier argument de l'appel à allocate() qui a initialement produit p; sinon, le comportement est indéfini."

Pourquoi ?

Maintenant, je dois soit faire des calculs supplémentaires avant de désallouer, soit commencer à stocker les tailles que j'ai passées à allocate. Si je n'utilisais pas l'allocateur, je n'aurais pas à faire cela.

Answer 1

La conception de l'API std::allocator - le concept Allocator - vise à faciliter le travail des remplacements potentiels.

std::allocator est une abstraction sur le modèle de mémoire sous-jacent

Ça ne doit pas l'être! En général, un allocateur n'a pas besoin d'utiliser malloc et free du C, ni delete ou le new non en place. Oui, celui par défaut le fait généralement, mais le mécanisme de l'allocateur n'est pas simplement une abstraction sur le modèle de mémoire du C. Être différent est souvent tout le but d'un allocateur personnalisé. N'oubliez pas que les allocateurs sont remplaçables : un std::allocator particulier pourrait ne pas avoir besoin de la taille pour la désallocation, mais il est probable que tous remplacements en auront besoin.

Une implémentation conforme de std::allocator est libre d'affirmer que vous passez effectivement le bon n à deallocate, et de dépendre par ailleurs de la taille correcte.

Il arrive que malloc et free stockent la taille du morceau dans leurs structures de données. Mais en général, un allocateur pourrait ne pas le faire, et exiger qu'il le fasse est une pessimization prématurée. Supposons que vous aviez un allocateur de pool personnalisé et que vous allouez des morceaux d'entiers. Sur un système 64 bits typique, cela représenterait un surdébit de 200% pour stocker un size_t de 64 bits avec l'entier de 32 bits. L'utilisateur de l'allocateur est bien mieux placé pour soit stocker la taille avec l'allocation, soit déterminer la taille de manière moins coûteuse.

Les bonnes implémentations de malloc ne stockent pas la taille d'allocation pour chaque petite allocation; elles sont capables de déduire la taille du morceau à partir du pointeur lui-même, par exemple en dérivant un pointeur de bloc du pointeur de morceau, puis en inspectant l'en-tête de bloc pour la taille du morceau. Ce n'est qu'un détail bien sûr. Vous pourriez obtenir la limite inférieure sur la taille en utilisant des API spécifiques à la plate-forme, comme malloc_size sur OS X, _msize sur Windows, malloc_usable_size sur Linux.

Answer 2

Il est souvent utile pour les algorithmes d'allocation de mémoire de minimiser la quantité de surcharge qu'ils nécessitent. Certains algorithmes qui suivent les zones libres plutôt que les zones allouées peuvent réduire la surcharge totale à une faible valeur constante avec une surcharge par bloc nulle (les informations de suivi sont stockées entièrement dans les zones libres). Sur les systèmes utilisant de tels algorithmes, une demande d'allocation retire du stockage du pool libre, et une demande de désallocation ajoute du stockage au pool libre.

Si les demandes d'allocation pour 256 et 768 octets sont satisfaites en utilisant une région contiguë du pool, l'état du gestionnaire de mémoire serait identique à ce qu'il serait si deux demandes de 512 octets avaient été satisfaites en utilisant cette même région. Si le gestionnaire de mémoire se voyait passer un pointeur vers le premier bloc et qu'on lui demande de le libérer, il n'aurait aucun moyen de savoir si la première demande était de 256 octets, de 512 octets ou de tout autre nombre, et donc aucun moyen de savoir combien de mémoire devrait être ajoutée de nouveau au pool.

Implémenter "malloc" et "free" sur un tel système nécessiterait qu'il stocke la longueur de chaque bloc au début de sa zone de stockage et renvoie un pointeur vers l'adresse suivante convenablement alignée qui serait disponible après cette longueur. Il est certainement possible pour une implémentation de le faire, mais cela ajouterait 4 à 8 octets de surcharge à chaque allocation. Si l'appelant peut indiquer à la routine de désallocation combien de stockage ajouter de nouveau au pool de mémoire, une telle surcharge peut être éliminée.

Answer 3

De plus, il est assez facile d'adapter ce point de conception:   il suffit d'attribuer les choses comme une struct, et de stocker la taille comme un élément à l'intérieur de cette struct. Votre code appelant le désallouer sait maintenant quelle valeur fournir, car la structure elle-même la contient.

En faisant cela, vous faites essentiellement ce que toute autre implémentation de langage pourrait gracieusement faire pour vous. Vous faites simplement la même chose explicitement.

Maintenant, étant donné que nous parlons de C++, qui possède déjà une multitude de super classes de conteneurs déjà construites, je vous encourage sincèrement à éviter de "reinventer la roue" si vous le pouvez. Trouvez simplement un moyen d'utiliser l'une des super classes de conteneurs que le langage et la bibliothèque standard proposent déjà.

Sinon, assurez-vous d'emballer ce que vous construisez ici comme une classe de conteneur fait maison. Assurez-vous que la logique qui traite de l'allocateur et du désallouer ne se produit qu'une seule fois dans votre programme. (À savoir, dans cette classe) Parsemez-la généreusement de logique spécifiquement conçue pour détecter les bugs. (Par exemple, une valeur sentinelle insérée dans un objet lorsqu'il est alloué, et qui doit être trouvée lors de la désallocation de l'objet, et qui est effacée juste avant. Vérifications explicites de la valeur de taille stockée pour s'assurer qu'elle a du sens. Et ainsi de suite.)

Answer 4

Vous n'êtes pas obligé de suivre la taille. L'allocation standard ne suit pas la taille car elle suppose une taille pour toutes les allocations. Bien sûr, il existe différents types d'allocateurs pour différents usages. Un allocateur de taille de bloc, comme vous l'avez deviné, a une taille fixe. Certaines applications comme les jeux vidéo préallouent toute la mémoire à l'avance et éliminent la surcharge de devoir suivre la taille de chaque allocation.

La bibliothèque standard essaie d'être aussi générique que possible. Certains allocateurs doivent suivre la taille, d'autres non, mais tous les allocateurs doivent se conformer à l'interface.

Answer 5

Je n'ai pas de preuve concluante, mais mon intuition me dit que l'allocateur n'est pas obligé d'utiliser les opérateurs new/delete de C++ et pourrait très bien utiliser des routines de gestion de la mémoire qui n'ont pas la capacité d'allouer des tableaux et de connaître leurs tailles - comme malloc, par exemple.