Est-il utile d'utiliser des pools de particules dans des langages gérés?

10

J'allais mettre en place un pool d'objets pour mon système de particules en Java, je trouve cela sur Wikipedia. Pour reformuler, il dit que les pools d'objets ne valent pas la peine d'être utilisés dans des langages gérés comme Java et C #, car les allocations ne prennent que des dizaines d'opérations par rapport à des centaines dans des langages non gérés comme C ++.

Mais comme nous le savons tous, chaque instruction peut nuire aux performances du jeu. Par exemple, un pool de clients dans un MMO: les clients n'entreront pas et ne sortiront pas trop rapidement du pool. Mais les particules peuvent se renouveler des dizaines de fois en une seconde.

La question est: vaut-il la peine d'utiliser un pool d'objets pour les particules (en particulier celles qui meurent et se recréent rapidement) dans un langage géré?

Gustavo Maciel
la source

Réponses:

14

Oui, ça l'est.

Le temps d'allocation n'est pas le seul facteur. L'allocation peut avoir des effets secondaires, tels que l'induction d'une passe de récupération de place, qui peut non seulement avoir un impact négatif sur les performances, mais également des performances imprévisibles. Les détails de cela dépendront de votre choix de langue et de plate-forme.

Le regroupement améliore également généralement la localité de référence pour les objets du pool, par exemple en les conservant tous dans des tableaux contigus. Cela peut améliorer les performances tout en itérant le contenu du pool (ou au moins la partie active de celui-ci) car l'objet suivant dans l'itération aura tendance à déjà être dans le cache de données.

La sagesse conventionnelle d'essayer d'éviter toute allocation dans vos boucles de jeu les plus profondes s'applique toujours même dans les langages gérés (en particulier sur, par exemple, le 360 ​​lorsque vous utilisez XNA). Les raisons en sont légèrement différentes.


la source
+1 Mais, vous n'avez pas précisé si cela valait la peine lorsque vous utilisez des structures: en gros, ce n'est pas le cas (la mise en commun des types de valeur ne donne rien) - à la place, vous devriez avoir un seul (ou éventuellement un ensemble de) tableau pour les gérer à la place.
Jonathan Dickinson
2
Je n'ai pas abordé la chose structurée depuis l'OP mentionné en utilisant Java et je ne suis pas aussi familier avec la façon dont les types / structures de valeur fonctionnent dans ce langage.
Il n'y a pas de structures en Java, seulement des classes (toujours sur le tas).
Brendan Long
1

Pour Java, il n'est pas si utile de regrouper des objets *, car le premier cycle GC pour les objets encore autour les remaniera en mémoire, les déplaçant hors de l'espace "Eden" et perdant potentiellement la localité spatiale dans le processus.

  • Il est toujours utile dans n'importe quelle langue de regrouper des ressources complexes qui sont très coûteuses à détruire et à créer comme des threads. Celles-ci peuvent valoir la peine d'être regroupées, car les dépenses de création et de destruction n'ont pratiquement rien à voir avec la mémoire associée au descripteur d'objet de la ressource. Cependant, les particules ne rentrent pas dans cette catégorie.

Java offre une allocation rapide en rafale à l'aide d'un allocateur séquentiel lorsque vous allouez rapidement des objets dans l'espace Eden. Cette stratégie d'allocation séquentielle est super rapide, plus rapide qu'en mallocC car elle regroupe simplement la mémoire déjà allouée de manière séquentielle directe, mais elle présente l'inconvénient que vous ne pouvez pas libérer des morceaux de mémoire individuels. C'est aussi une astuce utile en C si vous voulez simplement allouer des choses super rapidement pour, disons, une structure de données où vous n'avez pas besoin d'en supprimer quoi que ce soit, ajoutez simplement tout, puis utilisez-le et jetez le tout plus tard.

En raison de cet inconvénient de ne pas pouvoir libérer des objets individuels, le GC Java, après un premier cycle, copiera toute la mémoire allouée depuis l'espace Eden vers de nouvelles régions de mémoire en utilisant un allocateur de mémoire plus lent et plus général qui permet à la mémoire de être libéré en morceaux individuels dans un thread différent. Ensuite, il peut jeter la mémoire allouée dans l'espace Eden dans son ensemble sans se soucier des objets individuels qui ont maintenant été copiés et vivent ailleurs dans la mémoire. Après ce premier cycle GC, vos objets peuvent finir par être fragmentés en mémoire.

Étant donné que les objets peuvent finir par être fragmentés après ce premier cycle de GC, les avantages du regroupement d'objets lorsqu'il s'agit principalement d'améliorer les modèles d'accès à la mémoire (localité de référence) et de réduire les frais généraux d'allocation / désallocation sont largement perdus ... que vous obtiendrez généralement une meilleure localité de référence en allouant simplement de nouvelles particules tout le temps et en les utilisant pendant qu'elles sont encore fraîches dans l'espace Eden et avant qu'elles ne deviennent "anciennes" et potentiellement dispersées dans la mémoire. Cependant, ce qui peut être extrêmement utile (comme obtenir des performances rivalisant avec C en Java) est d'éviter d'utiliser des objets pour vos particules et de regrouper de vieilles données primitives simples. Pour un exemple simple, au lieu de:

class Particle
{
    public float x;
    public float y;
    public boolean alive;
}

Faites quelque chose comme:

class Particles
{
    // X positions of all particles. Resize on demand using
    // 'java.util.Arrays.copyOf'. We do not use an ArrayList
    // since we want to work directly with contiguously arranged
    // primitive types for optimal memory access patterns instead 
    // of objects managed by GC.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];
}

Maintenant, pour réutiliser la mémoire pour les particules existantes, vous pouvez le faire:

class Particles
{
    // X positions of all particles.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];

    // Next free position of all particles.
    public int next_free[];

    // Index to first free particle available to reclaim
    // for insertion. A value of -1 means the list is empty.
    public int first_free;
}

Maintenant, quand le nth particule meurt, pour permettre sa réutilisation, poussez-la dans la liste gratuite comme suit:

alive[n] = false;
next_free[n] = first_free;
first_free = n;

Lors de l'ajout d'une nouvelle particule, voyez si vous pouvez faire apparaître un index dans la liste gratuite:

if (first_free != -1)
{
     int index = first_free;

     // Pop the particle from the free list.
     first_free = next_free[first_free];

     // Overwrite the particle data:
     x[index] = px;
     y[index] = py;
     alive[index] = true;
     next_free[index] = -1;
}
else
{
     // If there are no particles in the free list
     // to overwrite, add new particle data to the arrays,
     // resizing them if needed.
}

Ce n'est pas le code le plus agréable à utiliser, mais avec cela, vous devriez pouvoir obtenir des simulations de particules très rapides avec un traitement séquentiel des particules très convivial pour le cache, car toutes les données de particules seront toujours stockées de manière contiguë. Ce type de représentant SoA réduit également l'utilisation de la mémoire car nous n'avons pas à nous soucier du remplissage, des métadonnées d'objet pour la réflexion / répartition dynamique, et il sépare les champs chauds des champs froids (par exemple, nous ne sommes pas nécessairement concernés par les données des champs comme la couleur d'une particule pendant le passage physique, il serait donc inutile de la charger dans une ligne de cache pour ne pas l'utiliser et l'expulser).

Pour faciliter l'utilisation du code, il peut être utile d'écrire vos propres conteneurs redimensionnables de base qui stockent des tableaux de flottants, des tableaux d'entiers et des tableaux de booléens. Encore une fois, vous ne pouvez pas utiliser de génériques et ArrayListici (au moins depuis la dernière fois que j'ai vérifié) car cela nécessite des objets gérés par GC, pas des données primitives contiguës. Nous voulons utiliser un tableau contigu int, par exemple, des tableaux non gérés par GC deInteger qui ne seront pas nécessairement contigus après avoir quitté l'espace Eden.

Avec les tableaux de types primitifs, ils sont toujours garantis contigus, et vous obtenez donc la localité de référence extrêmement souhaitable (pour le traitement séquentiel des particules, cela fait toute une différence) et tous les avantages que le regroupement d'objets est censé fournir. Avec un tableau d'objets, il est plutôt quelque peu analogue à un tableau de pointeurs qui commencent par pointer vers les objets de manière contiguë en supposant que vous les avez tous alloués en même temps dans l'espace Eden, mais après un cycle GC, peut pointer partout dans le mettre en mémoire.


la source
1
Ceci est un bon article sur la question, et après 5 ans de codage java, je peux le voir clairement; Java GC n'est certainement pas stupide, il n'a pas non plus été conçu pour la programmation de jeux (car il ne se soucie pas vraiment de la localisation des données et des trucs), donc nous ferions mieux de jouer à sa guise: P
Gustavo Maciel