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

Question

Quelles sont vraiment de bonnes raisons pour abandonner std :: allocator en faveur d'une solution personnalisée? Avez-vous rencontré des situations où cela était absolument nécessaire pour la correction, la performance, l'évolutivité, etc.? Des exemples vraiment intelligents?

Les allocateurs personnalisés ont toujours été une fonctionnalité de la bibliothèque standard pour laquelle je n’ai pas eu grand besoin. Je me demandais si quelqu'un sur SO pourrait fournir des exemples convaincants pour justifier son existence.

Answer 1

Comme je mentionne ici , j'ai vu le fichier STL personnalisé d'Intel TBB. allocator améliore considérablement les performances d’une application multithread en modifiant simplement une

std::vector<T>

à

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

(c’est un moyen rapide et pratique de changer l’allocateur pour qu’il utilise les superbes tas privés de threads de TBB; voir page 7 de ce document )

Answer 2

Un domaine dans lequel les allocateurs personnalisés peuvent être utiles est le développement de jeux, en particulier sur les consoles de jeux, car ils ne disposent que de peu de mémoire et ne sont pas échangeables. 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, tels que les allocateurs de pool, peuvent aider à réduire la fragmentation de la mémoire. Vous trouverez un long article détaillé sur le sujet à l’adresse suivante:

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

Answer 3

Je travaille sur un allocateur mmap qui permet aux vecteurs d'utiliser la mémoire de un fichier mappé en mémoire. L’objectif est d’avoir des vecteurs utilisant un stockage qui sont directement dans la mémoire virtuelle mappée par mmap. Notre problème est de améliorer la lecture de fichiers très volumineux (> 10 Go) dans la mémoire sans copie les frais généraux, donc j'ai 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 début pointer pour écrire ses propres allocateurs. N'hésitez pas à utiliser ce morceau de code de la manière que vous voulez:

#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 utiliser cela, 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 se connecter chaque fois que de la mémoire est allouée. Qu'est-ce qui est nécessaire est la structure de ré-association, sinon le conteneur de vecteur utilise les super-classes allocate / deallocate méthodes.

Mise à jour: l'allocateur de mappage de mémoire est désormais disponible à l'adresse https://github.com/johannesthoma/mmap_allocator"/a > et est LGPL. N'hésitez pas à l'utiliser pour vos projets.

Answer 4

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 lorsque l'utilisateur a configuré MySQL, et non pas "extra".

Answer 5

Il peut être utile d’utiliser des allocateurs personnalisés pour utiliser un pool de mémoire au lieu du segment de mémoire. C'est un exemple parmi beaucoup 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 intégrés, jeux, etc.).

Answer 6

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 à la réponse à une requête HTTP. L’allocateur personnalisé peut libérer toutes les données temporaires en même temps, une fois la réponse générée.

Un autre cas d'utilisation possible d'un allocateur personnalisé (que j'ai utilisé) consiste à écrire 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 de la mémoire avec n'importe quel modèle.

Answer 7

Lorsque vous travaillez avec des GPU ou d’autres co-processeurs, il est parfois avantageux d’allouer les structures de données en mémoire principale de 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 par le biais de l'exécution de l'accélérateur peut être bénéfique lors de l'utilisation d'accélérateurs est la suivante:

1. par une allocation personnalisée, le moteur ou le moteur de l’accélérateur est averti du bloc de mémoire
2. De plus, le système d’exploitation peut s’assurer que le bloc de mémoire alloué est verrouillé par une page (certains appellent cette mémoire bloquée ), c’est-à-dire que le sous-système de mémoire virtuelle du système d’exploitation peut ne pas être déplacé. ou supprimer la page dans ou de la mémoire
3. si 1. et 2. sont mis en attente et qu'un transfert de données entre un bloc de mémoire à verrouillage de page et un accélérateur est demandé, le moteur d'exécution peut accéder directement aux données dans la mémoire principale, car il sait où elles se trouvent et il peut en être sûr. le système ne l'a pas déplacé / retiré
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: les données doivent être copiées dans la mémoire principale vers une zone de stockage intermédiaire verrouillée à partir de l'accélérateur, ce qui permet d'initialiser le transfert de données. (via DMA)

Answer 8

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

Contexte: nous avons des surcharges pour malloc, calloc, free et les différentes variantes de l'opérateur new et delete, et l'éditeur de liens oblige heureusement STL à les utiliser pour nous. Cela nous permet d’effectuer des tâches telles que le regroupement automatique de petits objets, la détection de fuites, le remplissage alloué, le remplissage libre, l’allocation de remplissage avec les sentinelles, l’alignement de la ligne de cache pour certains allocations et la libération libre différée.

Le problème est que nous fonctionnons dans un environnement intégré - il n’ya pas assez de mémoire pour réellement comptabiliser correctement la détection des fuites sur une longue période. Du moins, pas dans la RAM standard - il existe un autre tas de RAM disponible ailleurs, via des fonctions d'allocation personnalisées.

Solution: écrivez un allocateur personnalisé qui utilise le segment de mémoire étendu et utilisez-le uniquement dans les éléments internes de l'architecture de suivi des fuites de mémoire ... Toutes les autres valeurs par défaut correspondent aux surcharges normales. suivi des fuites. Cela évite le suivi du traqueur lui-même (et fournit un peu de fonctionnalité d’emballage supplémentaire, nous connaissons également la taille des nœuds de suivi).

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

Answer 9

J'utilise un allocateur personnalisé pour compter le nombre d'allocations / désallocations dans une partie de mon programme et pour mesurer le temps que cela prend. Cela pourrait être réalisé de différentes manières, mais cette méthode est très pratique pour moi. Il est particulièrement utile que je puisse utiliser l’allocateur personnalisé pour seulement un sous-ensemble de mes conteneurs.

Answer 10

Une situation essentielle: lors de la rédaction de code devant fonctionner à travers les limites de modules (EXE / DLL), il est essentiel de conserver vos allocations et suppressions dans un seul module.

Là où je suis tombé sur une architecture de plugin sous Windows. Par exemple, si vous transmettez un std :: string au-delà de la limite de la DLL, il est essentiel que toute réaffectation de la chaîne se produise à partir du segment de mémoire d'où il provient, PAS le segment de mémoire dans la DLL, qui peut être différent *.

* C’est plus compliqué que cela en réalité, car si vous liez dynamiquement au CRT, cela pourrait quand même fonctionner. Mais si chaque DLL a un lien statique vers le tube cathodique, vous vous dirigez dans un monde de souffrances, où des erreurs d’allocation fantôme se produisent continuellement.

Answer 11

C’est pourquoi je travaillais avec des systèmes intégrés très limités en ressources. Disons que vous avez 2k de RAM libre et que votre programme doit utiliser une partie de cette mémoire. Vous devez stocker 4-5 séquences quelque part qui ne se trouve pas sur la pile et vous devez en outre disposer d'un accès très précis sur l'endroit où ces éléments sont stockés. 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 que vous 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. La mise en œuvre de la gestion de la mémoire par la bibliothèque standard est une mince couche malloc / free qui garde la trace de l'endroit où placer les éléments en ajoutant à chaque bloc de mémoire alloué un pointeur situé juste après la fin de la 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 prochain bloc disponible où la taille de mémoire demandée tiendra. Sur une plate-forme de bureau, cela 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 faisait que nous n'avions vraiment pas d'autre choix que d'adopter une approche différente.

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

Je vois souvent d'autres situations où vous écrivez votre propre allocateur personnalisé dans le contexte de systèmes intégrés, par exemple si la mémoire de la séquence n'est pas dans le bélier principal, comme cela pourrait souvent être le cas sous sur ces plates-formes .

Answer 12

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

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

Answer 13

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

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

Ce qui est bien, c’est que le simple fait de les concevoir vous fait penser à des façons de les utiliser: -)

Answer 14

Il y a quelque temps, cette solution m'était très utile: allocateur Fast C ++ 11 pour les conteneurs STL . Il accélère légèrement les conteneurs STL sur le VS2017 (~ 5x) ainsi que sur le 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.

Answer 15

Personnellement, j'utilise 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 de très petite taille (1 à 256 octets). Elle peut être jusqu'à 30 fois plus efficace que l'allocation de suppression / suppression C ++ standard si nous parlons d'allouer des quantités modérées de petits objets de nombreuses tailles différentes. En outre, il existe une solution spécifique à VC appelée "QuickHeap", qui offre les meilleures performances possibles (les opérations allocate et libéallocate lisent et écrivent simplement l'adresse du bloc alloué / renvoyé à heap, respectivement jusqu'à 99. (9)% cas - dépend des paramètres et de l'initialisation), mais au prix d'un surcoût important - il faut deux pointeurs par extension et un extra pour chaque nouveau bloc de mémoire. C'est une solution rapide pour travailler avec de grandes quantités (10 000 ++) d'objets créés et supprimés si vous n'avez pas besoin d'une grande variété de tailles d'objets (cela crée un pool individuel pour chaque taille d'objet, de 1 à 1023 octets dans la mise en œuvre actuelle, les coûts d’initialisation risquent donc de minimiser l’amélioration globale des performances, mais vous pouvez également allouer / désaffecter des objets factices avant que l’application ne passe dans sa phase critique de performances).

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

Answer 16

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

1. Les contraintes d'alignement que std :: allocator ne supportaient pas directement.
2. Minimiser la fragmentation en utilisant des pools distincts pour les allocations de courte durée (uniquement cette base) et de longue durée.