Allocation dynamique de mémoire et gestion de la mémoire

Dans un jeu moyen, il y a des centaines voire des milliers d'objets dans la scène. Est-il tout à fait correct d'allouer de la mémoire pour tous les objets, y compris les coups de feu (balles), dynamiquement via new par défaut () ?

Dois-je en créer pool de mémoire pour l'allocation dynamique , ou n'y a-t-il pas lieu de s'en préoccuper? Que faire si la plate-forme cible est un appareil mobile?

Existe-t-il un besoin gestionnaire de mémoire dans un jeu mobile, s'il vous plaît? Je vous remercie.

Langage utilisé: C ++; Actuellement développé sous Windows, mais prévu pour être porté plus tard.

Dans un jeu moyen, il y a des centaines voire des milliers d'objets dans la scène. Est-il tout à fait correct d'allouer de la mémoire pour tous les objets, y compris les coups de feu (balles), dynamiquement via new () par défaut?

Cela dépend vraiment de ce que vous entendez par «correct». Si vous prenez le terme littéralement (et ignorez tout concept d'exactitude de la conception implicite), alors oui, il est parfaitement acceptable. Votre programme se compilera et fonctionnera correctement.

Il peut fonctionner de manière sous-optimale, mais il peut également fonctionner suffisamment bien pour être un jeu amusant et livrable.

Dois-je créer un pool de mémoire pour l'allocation dynamique, ou n'y a-t-il pas lieu de s'en préoccuper? Que faire si la plate-forme cible est un appareil mobile?

Profil et voir. En C ++, par exemple, l'allocation dynamique sur le tas est généralement une opération "lente" (en ce sens qu'elle implique de parcourir le tas à la recherche d'un bloc de taille appropriée). En C #, c'est généralement une opération extrêmement rapide car elle implique un peu plus qu'un incrément. Différentes implémentations de langage ont des caractéristiques de performances différentes en ce qui concerne l'allocation de mémoire, la fragmentation lors de la publication, etc.

La mise en œuvre d'un système de pool de mémoire peut certainement entraîner des gains de performances - et comme les systèmes mobiles sont généralement sous-alimentés par rapport aux systèmes de bureau, vous pouvez voir plus de gain sur une plate-forme mobile particulière que sur un ordinateur de bureau. Mais encore une fois, vous devez profiler et voir - si, actuellement, votre jeu est lent mais que l'allocation / libération de mémoire n'apparaît pas sur le profileur comme un point chaud, mettant en œuvre une infrastructure pour optimiser l'allocation de mémoire et l'accès probablement gagné '' t vous en avez pour votre argent.

Faut-il un gestionnaire de mémoire dans un jeu mobile, s'il vous plaît? Je vous remercie.

Encore une fois, profilez et voyez. Votre jeu fonctionne-t-il bien maintenant? Ensuite, vous n'aurez peut-être pas à vous inquiéter.

Tous ces avertissements mis à part, l'utilisation de l'allocation dynamique pour tout n'est pas strictement nécessaire et il peut donc être avantageux de l'éviter - à la fois en raison des gains de performances potentiels et de l'allocation de mémoire dont vous avez besoin pour suivre et éventuellement libérer. signifie que vous devez le suivre et éventuellement le publier, ce qui peut compliquer votre code.

En particulier, dans votre exemple d'origine, vous avez cité des "balles", qui ont tendance à être créées et détruites fréquemment - car de nombreux jeux impliquent beaucoup de balles, et les balles se déplacent rapidement et atteignent ainsi la fin de leur vie rapidement (et souvent violemment!). Ainsi, la mise en œuvre d'un allocateur de pool pour eux et des objets comme eux (tels que des particules dans un système de particules) peut généralement entraîner des gains d'efficacité et serait probablement le premier endroit pour commencer à envisager l'utilisation de l'allocation de pool.

Je ne sais pas si vous considérez une implémentation de pool de mémoire comme distincte d'un "gestionnaire de mémoire" - un pool de mémoire est un concept relativement bien défini, donc je peux dire avec une certaine certitude qu'ils peuvent être un avantage si vous les implémentez . Un "gestionnaire de mémoire" est un peu plus vague quant à sa responsabilité, donc je dois dire que si oui ou non il est nécessaire dépend de ce que vous pensez que le "gestionnaire de mémoire" ferait.

Par exemple, si vous considérez qu'un gestionnaire de mémoire est une chose qui intercepte simplement les appels à new / delete / free / malloc / que ce soit et fournit des diagnostics sur la quantité de mémoire que vous allouez, ce que vous fuyez, et cetera - alors cela peut être utile outil pour le jeu en cours de développement pour vous aider à déboguer les fuites et à régler la taille optimale de votre pool de mémoire, etc.

Je n'ai pas grand-chose à ajouter à l'excellente réponse de Josh, mais je commenterai ceci:

Dois-je créer un pool de mémoire pour l'allocation dynamique, ou n'y a-t-il pas lieu de s'en préoccuper?

Il existe un juste milieu entre les pools de mémoire et l'appel newà chaque allocation. Par exemple, vous pouvez allouer un nombre défini d'objets dans un tableau, puis définir un indicateur sur eux pour les «détruire» ultérieurement. Lorsque vous avez besoin d'allouer plus, vous pouvez remplacer ceux avec le drapeau détruit. Ce genre de chose n'est que légèrement plus complexe à utiliser que new / delete (car vous auriez 2 nouvelles fonctions à cet effet) mais est simple à écrire et peut vous apporter de gros gains.

Est-il tout à fait correct d'allouer de la mémoire pour tous les objets, y compris les coups de feu (balles), dynamiquement via new par défaut ()?

Non bien sûr que non. Aucune allocation de mémoire n'est correcte pour tous les objets. L'opérateur new () est pour l' allocation dynamique , c'est-à-dire qu'il n'est approprié que si vous avez besoin que l'allocation soit dynamique, soit parce que la durée de vie de l'objet est dynamique soit parce que le type de l'objet est dynamique. Si le type et la durée de vie de l'objet sont connus statiquement, vous devez les allouer statiquement.

Bien sûr, plus vous disposez d'informations sur vos modèles d'allocation, plus rapidement ces allocations peuvent être effectuées via des allocateurs spécialisés, tels que des pools d'objets. Mais, ce sont des optimisations et vous ne devriez les faire que si elles sont nécessaires.

Un peu en écho à la suggestion de Kylotan, mais je recommanderais de résoudre ce problème au niveau de la structure de données lorsque cela est possible, pas au niveau de l'allocateur inférieur si vous pouvez l'aider.

Voici un exemple simple de la façon dont vous pouvez éviter d'allouer et de libérer à Foosplusieurs reprises en utilisant un tableau avec des trous avec des éléments liés entre eux (en résolvant cela au niveau "conteneur" au lieu d'un niveau "allocateur"):

struct FooNode
{
    explicit FooNode(const Foo& ielement): element(ielement), next(-1) {}

    // Stores a 'Foo'.
    Foo element;

    // Points to the next foo available; either the
    // next used foo or the next deleted foo. Can
    // use SoA and hoist this out if Foo doesn't 
    // have 32-bit alignment.
    int next;
};

struct Foos
{
    // Stores all the Foo nodes.
    vector<FooNode> nodes;

    // Points to the first used node.
    int first_node;

    // Points to the first free node.
    int free_node;

    Foos(): first_node(-1), free_node(-1)
    {
    }

    const FooNode& operator[](int n) const
    {
         return data[n];
    }

    void insert(const Foo& element)
    {
         int index = free_node;
         if (index != -1)
         {
              // If there's a free node available,
              // pop it from the free list, overwrite it,
              // and push it to the used list.
              free_node = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              // If there's no free node available, add a 
              // new node and push it to the used list.
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         // If the node being removed is the first used
         // node, pop it from the used list.
         if (first_node == n)
              first_node = data[n].next;

         // Push the node to the free list.
         data[n].next = free_node;
         free_node = n;
    }
};

Quelque chose à cet effet: une liste d'index à liaison unique avec une liste gratuite. Les liens d'index vous permettent de sauter des éléments supprimés, de supprimer des éléments en temps constant et également de récupérer / réutiliser / écraser des éléments libres avec une insertion en temps constant. Pour parcourir la structure, vous faites quelque chose comme ceci:

for (int index = foos.first_node; index != -1; index = foos[index].next)
    // do something with foos[index]

Et vous pouvez généraliser le type de structure de données "tableau de trous liés" ci-dessus en utilisant des modèles, en plaçant un nouvel appel manuel et un dtor pour éviter l'exigence d'une affectation de copie, en le faisant invoquer des destructeurs lorsque des éléments sont supprimés, en fournissant un itérateur avancé, etc. I a choisi de garder l'exemple très en C pour illustrer plus clairement le concept et aussi parce que je suis très paresseux.

Cela dit, cette structure a tendance à se dégrader dans la localité spatiale après avoir supprimé et inséré beaucoup de choses vers / depuis le milieu. À ce stade, lenext liens pourraient vous faire marcher dans les deux sens le long du vecteur, recharger les données précédemment supprimées d'une ligne de cache dans le même parcours séquentiel (cela est inévitable avec toute structure de données ou allocateur qui permet la suppression à temps constant sans mélanger les éléments lors de la récupération) espaces du milieu avec insertion à temps constant et sans utiliser quelque chose comme un jeu de bits parallèle ou un removeddrapeau). Pour restaurer la convivialité du cache, vous pouvez implémenter une méthode de copie et d'échange comme ceci:

Foos(const Foos& other)
{
    for (int index = other.first_node; index != -1; index = other[index].next)
        insert(foos[index].element);
}

void Foos::swap(Foos& other)
{
     nodes.swap(other.nodes):
     std::swap(first_node, other.first_node);
     std::swap(free_node, other.free_node);
}

// ... then just copy and swap:
Foos(foos).swap(foos);

Maintenant, la nouvelle version est à nouveau compatible avec le cache à parcourir. Une autre méthode consiste à stocker une liste distincte d'index dans la structure et à les trier périodiquement. Une autre consiste à utiliser un jeu de bits pour indiquer les indices utilisés. Cela vous fera toujours traverser le jeu de bits dans un ordre séquentiel (pour le faire efficacement, vérifiez 64 bits à la fois, par exemple en utilisant FFS / FFZ). Le jeu de bits est le plus efficace et non intrusif, ne nécessitant qu'un bit parallèle par élément pour indiquer ceux qui sont utilisés et lesquels sont supprimés au lieu de nécessiter des nextindex 32 bits , mais le plus long à bien écrire (il ne être rapide pour la traversée si vous vérifiez un bit à la fois - vous avez besoin de FFS / FFZ pour trouver un bit activé ou non immédiatement parmi 32+ bits à la fois pour déterminer rapidement les plages d'indices occupés).

Cette solution liée est généralement la plus facile à implémenter et non intrusive (ne nécessite pas de modification Foopour stocker un removedindicateur), ce qui est utile si vous souhaitez généraliser ce conteneur pour travailler avec n'importe quel type de données si cela ne vous dérange pas que 32 bits frais généraux par élément.

Dois-je créer un pool de mémoire pour l'allocation dynamique, ou n'y a-t-il pas lieu de s'en préoccuper? Que faire si la plate-forme cible est un appareil mobile?

avoir besoin est un mot fort et je suis partisan de travailler dans des domaines très critiques pour les performances comme le lancer de rayons, le traitement d'image, les simulations de particules et le traitement de maillage, mais il est relativement très coûteux d'allouer et de libérer des objets minuscules utilisés pour un traitement très léger comme les balles. et des particules individuellement contre un allocateur de mémoire de taille variable à usage général. Étant donné que vous devriez être en mesure de généraliser la structure de données ci-dessus en un jour ou deux pour stocker tout ce que vous voulez, je pense que ce serait un échange utile pour éliminer ces coûts d'allocation / désallocation de tas purement et simplement d'être payés pour chaque chose minuscule. En plus de réduire les coûts d'allocation / désallocation, vous obtenez une meilleure localité de référence traversant les résultats (moins de ratés de cache et de défauts de page, par exemple).

En ce qui concerne ce que Josh a mentionné à propos de GC, je n'ai pas étudié l'implémentation de GC de C # aussi étroitement que Java, mais les allocateurs de GC ont souvent un allocation initialec'est très rapide car cela utilise un allocateur séquentiel qui ne peut pas libérer de mémoire du milieu (presque comme une pile, vous ne pouvez pas supprimer des choses du milieu). Ensuite, il paie les coûts élevés pour permettre de supprimer des objets individuels dans un thread séparé en copiant la mémoire et en purgeant la mémoire précédemment allouée dans son ensemble (comme détruire la pile entière à la fois tout en copiant les données vers quelque chose de plus comme une structure liée), mais parce que c'est fait dans un thread séparé, cela ne stagne pas nécessairement autant les threads de votre application. Cependant, cela entraîne un coût caché très important d'un niveau supplémentaire d'indirection et la perte générale de LOR après un cycle GC initial. Cependant, c'est une autre stratégie pour accélérer l'allocation - la rendre moins chère dans le thread appelant, puis faire le travail coûteux dans un autre. Pour cela, vous avez besoin de deux niveaux d'indirection pour référencer vos objets au lieu d'un car ils finiront par être mélangés en mémoire entre le temps que vous allouez initialement et après un premier cycle.

Une autre stratégie dans la même veine qui est un peu plus facile à appliquer en C ++ est tout simplement de ne pas prendre la peine de libérer vos objets dans vos threads principaux. Il suffit de continuer à ajouter et d'ajouter et d'ajouter à la fin d'une structure de données qui ne permet pas de supprimer des éléments du milieu. Cependant, marquez les éléments à supprimer. Ensuite, un thread séparé pourrait prendre en charge le travail coûteux de création d'une nouvelle structure de données sans les éléments supprimés, puis échanger atomiquement la nouvelle avec l'ancien, par exemple, une grande partie du coût des éléments d'allocation et de libération peut être transférée à un thread séparé si vous pouvez faire l'hypothèse que la demande de suppression d'un élément ne doit pas être satisfaite immédiatement. Cela permet non seulement de libérer moins cher en ce qui concerne vos threads, mais aussi d'allouer moins cher, car vous pouvez utiliser une structure de données beaucoup plus simple et plus stupide qui n'a jamais à gérer les cas de suppression depuis le milieu. C'est comme un conteneur qui n'a besoin que d'unpush_backfonction d'insertion, une clearfonction pour supprimer tous les éléments et swappour échanger le contenu avec un nouveau conteneur compact excluant les éléments supprimés; c'est tout pour la mutation.