Des exemples convaincants d'allocateurs C ++ personnalisés?

Quelles sont de très bonnes raisons d'abandonner std::allocatoren faveur d'une solution personnalisée? Avez-vous rencontré des situations où cela était absolument nécessaire pour l'exactitude, les performances, l'évolutivité, etc.? Des exemples vraiment intelligents?

Les allocateurs personnalisés ont toujours été une fonctionnalité de la bibliothèque standard dont je n'avais pas vraiment besoin. Je me demandais simplement si quelqu'un ici sur SO pourrait fournir des exemples convaincants pour justifier leur existence.

Comme je le mentionne ici , j'ai vu l'allocateur STL personnalisé d'Intel TBB améliorer considérablement les performances d'une application multithread simplement en changeant un seul

std::vector<T>

à

std::vector<T,tbb::scalable_allocator<T> >

(c'est un moyen rapide et pratique de changer l'allocateur pour utiliser les tas astucieux de thread privé de TBB; voir page 7 de ce document )

Un domaine où les allocateurs personnalisés peuvent être utiles est le développement de jeux, en particulier sur les consoles de jeux, car ils n'ont qu'une petite quantité de mémoire et aucun échange. Sur de tels systèmes, vous voulez vous assurer que vous avez un contrôle strict sur chaque sous-système, de sorte qu'un système non critique ne puisse pas voler la mémoire d'un système critique. D'autres éléments comme les allocateurs de pool peuvent aider à réduire la fragmentation de la mémoire. Vous pouvez trouver un long article détaillé sur le sujet à l'adresse:

EASTL - Bibliothèque de modèles standard d'Electronic Arts

Je travaille sur un mmap-allocator qui permet aux vecteurs d'utiliser la mémoire d'un fichier mappé en mémoire. L'objectif est d'avoir des vecteurs qui utilisent le stockage qui sont directement dans la mémoire virtuelle mappés par mmap. Notre problème est d'améliorer la lecture de fichiers vraiment volumineux (> 10 Go) en mémoire sans surcharge de copie, j'ai donc besoin de cet allocateur personnalisé.

Jusqu'à présent, j'ai le squelette d'un allocateur personnalisé (qui dérive de std :: allocator), je pense que c'est un bon point de départ pour écrire ses propres allocateurs. N'hésitez pas à utiliser ce morceau de code comme vous le souhaitez:

#include <memory>
#include <stdio.h>

namespace mmap_allocator_namespace
{
        // See StackOverflow replies to this answer for important commentary about inheriting from std::allocator before replicating this code.
        template <typename T>
        class mmap_allocator: public std::allocator<T>
        {
public:
                typedef size_t size_type;
                typedef T* pointer;
                typedef const T* const_pointer;

                template<typename _Tp1>
                struct rebind
                {
                        typedef mmap_allocator<_Tp1> other;
                };

                pointer allocate(size_type n, const void *hint=0)
                {
                        fprintf(stderr, "Alloc %d bytes.\n", n*sizeof(T));
                        return std::allocator<T>::allocate(n, hint);
                }

                void deallocate(pointer p, size_type n)
                {
                        fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p);
                        return std::allocator<T>::deallocate(p, n);
                }

                mmap_allocator() throw(): std::allocator<T>() { fprintf(stderr, "Hello allocator!\n"); }
                mmap_allocator(const mmap_allocator &a) throw(): std::allocator<T>(a) { }
                template <class U>                    
                mmap_allocator(const mmap_allocator<U> &a) throw(): std::allocator<T>(a) { }
                ~mmap_allocator() throw() { }
        };
}

Pour l'utiliser, déclarez un conteneur STL comme suit:

using namespace std;
using namespace mmap_allocator_namespace;

vector<int, mmap_allocator<int> > int_vec(1024, 0, mmap_allocator<int>());

Il peut être utilisé par exemple pour enregistrer chaque fois que de la mémoire est allouée. Ce qui est nécessaire est la structure de rebind, sinon le conteneur vectoriel utilise les méthodes d'allocation / désallocation des superclasses.

Mise à jour: L'allocateur de mappage de mémoire est maintenant disponible sur https://github.com/johannesthoma/mmap_allocator et est LGPL. N'hésitez pas à l'utiliser pour vos projets.

Je travaille avec un moteur de stockage MySQL qui utilise c ++ pour son code. Nous utilisons un allocateur personnalisé pour utiliser le système de mémoire MySQL plutôt que de rivaliser avec MySQL pour la mémoire. Cela nous permet de nous assurer que nous utilisons la mémoire comme l'utilisateur a configuré MySQL pour l'utiliser, et non "extra".

Il peut être utile d'utiliser des allocateurs personnalisés pour utiliser un pool de mémoire au lieu du tas. C'est un exemple parmi tant d'autres.

Dans la plupart des cas, il s'agit certainement d'une optimisation prématurée. Mais cela peut être très utile dans certains contextes (appareils embarqués, jeux, etc.).

Je n'ai pas écrit de code C ++ avec un allocateur STL personnalisé, mais je peux imaginer un serveur Web écrit en C ++, qui utilise un allocateur personnalisé pour la suppression automatique des données temporaires nécessaires pour répondre à une requête HTTP. L'allocateur personnalisé peut libérer toutes les données temporaires à la fois une fois que la réponse a été générée.

Un autre cas d'utilisation possible d'un allocateur personnalisé (que j'ai utilisé) est l'écriture d'un test unitaire pour prouver que le comportement d'une fonction ne dépend pas d'une partie de son entrée. L'allocateur personnalisé peut remplir la région mémoire avec n'importe quel modèle.

Lorsque vous travaillez avec des GPU ou d'autres coprocesseurs, il est parfois avantageux d'allouer des structures de données dans la mémoire principale d'une manière spéciale . Cette manière spéciale d'allouer de la mémoire peut être implémentée dans un allocateur personnalisé de manière pratique.

La raison pour laquelle l'allocation personnalisée via le runtime d'accélérateur peut être bénéfique lors de l'utilisation d'accélérateurs est la suivante:

1. grâce à une allocation personnalisée, le moteur d'exécution ou le pilote de l'accélérateur est notifié du bloc de mémoire
2. en outre, le système d'exploitation peut s'assurer que le bloc de mémoire alloué est verrouillé en page (certains appellent cette mémoire épinglée ), c'est-à-dire que le sous-système de mémoire virtuelle du système d'exploitation ne peut pas déplacer ou supprimer la page dans ou de la mémoire
3. si 1. et 2. maintiennent et qu'un transfert de données entre un bloc de mémoire à verrouillage de page et un accélérateur est demandé, le runtime peut accéder directement aux données de la mémoire principale car il sait où elles se trouvent et il peut être sûr que le système d'exploitation ne l'a pas fait déplacer / supprimer
4. cela enregistre une copie de la mémoire qui se produirait avec de la mémoire allouée de manière non verrouillée par page: les données doivent être copiées dans la mémoire principale vers une zone de transfert verrouillée par page à partir de avec l'accélérateur peut initialiser le transfert de données (via DMA )

J'utilise ici des allocateurs personnalisés; vous pourriez même dire que c'était pour contourner autre gestion de la mémoire dynamique personnalisée.

Contexte: nous avons des surcharges pour malloc, calloc, free, et les différentes variantes d'opérateur new et delete, et l'éditeur de liens fait heureusement que STL les utilise pour nous. Cela nous permet de faire des choses comme le regroupement automatique de petits objets, la détection de fuites, le remplissage d'alloc, le remplissage libre, l'allocation de remplissage avec des sentinelles, l'alignement de la ligne de cache pour certains allocs et le retard gratuit.

Le problème est que nous fonctionnons dans un environnement embarqué - il n'y a pas assez de mémoire pour effectuer correctement la détection des fuites sur une période prolongée. Au moins, pas dans la RAM standard - il y a un autre tas de RAM disponible ailleurs, grâce à des fonctions d'allocation personnalisées.

Solution: écrivez un allocateur personnalisé qui utilise le tas étendu et utilisez-le uniquement dans les composants internes de l'architecture de suivi des fuites de mémoire ... Tout le reste utilise par défaut les surcharges normales new / delete qui effectuent le suivi des fuites. Cela évite le suivi du tracker lui-même (et fournit également un peu de fonctionnalité d'emballage supplémentaire, nous connaissons la taille des nœuds de suivi).

Nous l'utilisons également pour conserver les données de profilage des coûts de fonction, pour la même raison; l'écriture d'une entrée pour chaque appel et retour de fonction, ainsi que pour les commutateurs de thread, peut rapidement coûter cher. L'allocateur personnalisé nous donne à nouveau des allocs plus petits dans une zone de mémoire de débogage plus grande.

J'utilise un allocateur personnalisé pour compter le nombre d'allocations / désallocations dans une partie de mon programme et mesurer combien de temps cela prend. Il existe d'autres moyens d'y parvenir, mais cette méthode est très pratique pour moi. Il est particulièrement utile que je puisse utiliser l'allocateur personnalisé uniquement pour un sous-ensemble de mes conteneurs.

Une situation essentielle: lors de l'écriture de code qui doit fonctionner au-delà des limites des modules (EXE / DLL), il est essentiel de conserver vos allocations et suppressions dans un seul module.

Là où j'ai rencontré cela, c'était une architecture de plugins sous Windows. Il est essentiel que, par exemple, si vous passez une chaîne std :: string à travers la limite de la DLL, toutes les réallocations de la chaîne se produisent à partir du tas d'où il provient, PAS du tas dans la DLL qui peut être différent *.

* C'est plus compliqué que cela en fait, comme si vous liez dynamiquement au CRT cela pourrait fonctionner de toute façon. Mais si chaque DLL a un lien statique vers le CRT, vous vous dirigez vers un monde de douleur, où des erreurs d'allocation fantôme se produisent continuellement.

Un exemple de la fois où j'ai utilisé ces derniers était le travail avec des systèmes embarqués très limités en ressources. Disons que vous avez 2k de RAM libres et que votre programme doit utiliser une partie de cette mémoire. Vous devez stocker par exemple 4-5 séquences quelque part qui ne sont pas sur la pile et en plus vous devez avoir un accès très précis sur l'endroit où ces choses sont stockées, c'est une situation où vous voudrez peut-être écrire votre propre allocateur. Les implémentations par défaut peuvent fragmenter la mémoire, cela peut être inacceptable si vous n'avez pas assez de mémoire et ne pouvez pas redémarrer votre programme.

Un projet sur lequel je travaillais utilisait AVR-GCC sur des puces de faible puissance. Nous avons dû stocker 8 séquences de longueur variable mais avec un maximum connu. L' implémentation de bibliothèque standard de la gestion de la mémoireest un wrapper fin autour de malloc / free qui garde une trace de l'endroit où placer les éléments en ajoutant au début chaque bloc de mémoire alloué avec un pointeur juste après la fin de cette partie de mémoire allouée. Lors de l'allocation d'un nouveau morceau de mémoire, l'allocateur standard doit parcourir chacun des morceaux de mémoire pour trouver le bloc suivant disponible dans lequel la taille de mémoire demandée conviendra. Sur une plate-forme de bureau, ce serait très rapide pour ces quelques éléments, mais vous devez garder à l'esprit que certains de ces microcontrôleurs sont très lents et primitifs en comparaison. De plus, le problème de la fragmentation de la mémoire était un problème majeur qui signifiait que nous n'avions vraiment pas d'autre choix que d'adopter une approche différente.

Nous avons donc implémenté notre propre pool de mémoire . Chaque bloc de mémoire était suffisamment grand pour contenir la plus grande séquence dont nous aurions besoin. Cela allouait des blocs de mémoire de taille fixe à l'avance et indiquait quels blocs de mémoire étaient actuellement utilisés. Nous l'avons fait en gardant un entier de 8 bits où chaque bit était représenté si un certain bloc était utilisé. Nous avons échangé l'utilisation de la mémoire ici pour tenter d'accélérer l'ensemble du processus, ce qui dans notre cas était justifié car nous poussions cette puce de microcontrôleur près de sa capacité de traitement maximale.

Il y a un certain nombre d'autres fois où je peux voir écrire votre propre allocateur personnalisé dans le contexte de systèmes embarqués, par exemple si la mémoire de la séquence n'est pas dans la mémoire vive principale comme cela pourrait souvent être le cas sur ces plates-formes .

Lien obligatoire vers la conférence CppCon 2015 d'Andrei Alexandrescu sur les allocateurs:

https://www.youtube.com/watch?v=LIb3L4vKZ7U

La bonne chose est que le simple fait de les concevoir vous fait penser à des idées sur la façon dont vous les utiliseriez :-)

Pour la mémoire partagée, il est essentiel que non seulement la tête de conteneur, mais également les données qu'elle contient soient stockées dans la mémoire partagée.

L'allocateur de Boost :: Interprocess est un bon exemple. Cependant, comme vous pouvez le lire ici, tout cela ne suffit pas, pour rendre tous les conteneurs STL compatibles avec la mémoire partagée (en raison des différents décalages de mappage dans différents processus, les pointeurs peuvent «casser»).

Il y a quelque temps, j'ai trouvé cette solution très utile pour moi: l' allocateur rapide C ++ 11 pour les conteneurs STL . Il accélère légèrement les conteneurs STL sur VS2017 (~ 5x) ainsi que sur GCC (~ 7x). C'est un allocateur à usage spécial basé sur le pool de mémoire. Il ne peut être utilisé avec les conteneurs STL que grâce au mécanisme que vous demandez.

J'utilise personnellement Loki :: Allocator / SmallObject pour optimiser l'utilisation de la mémoire pour les petits objets - il montre une bonne efficacité et des performances satisfaisantes si vous devez travailler avec des quantités modérées d'objets très petits (1 à 256 octets). Cela peut être jusqu'à ~ 30 fois plus efficace que l'allocation de nouvelles / suppressions C ++ standard si nous parlons d'allouer des quantités modérées de petits objets de différentes tailles. En outre, il existe une solution spécifique à VC appelée "QuickHeap", elle apporte les meilleures performances possibles (les opérations d'allocation et de désallocation il suffit de lire et d'écrire l'adresse du bloc alloué / retourné au tas, respectivement dans jusqu'à 99. (9)% des cas. - dépend des paramètres et de l'initialisation), mais au prix d'une surcharge notable - il a besoin de deux pointeurs par extension et d'un supplémentaire pour chaque nouveau bloc de mémoire. Il'

Le problème avec l'implémentation standard new / delete de C ++ est qu'il ne s'agit généralement que d'un wrapper pour l'allocation C malloc / free, et cela fonctionne bien pour des blocs de mémoire plus volumineux, comme 1024+ octets. Il a une surcharge notable en termes de performances et, parfois, de mémoire supplémentaire utilisée pour le mappage. Ainsi, dans la plupart des cas, les allocateurs personnalisés sont implémentés de manière à maximiser les performances et / ou à minimiser la quantité de mémoire supplémentaire nécessaire pour allouer de petits objets (≤ 1024 octets).

Dans une simulation graphique, j'ai vu des allocateurs personnalisés utilisés pour

1. Contraintes d'alignement std::allocatornon directement prises en charge.
2. Minimisation de la fragmentation en utilisant des pools séparés pour les allocations de courte durée (uniquement cette trame) et de longue durée.