Comment bénéficier du cache CPU dans un moteur de jeu de système de composants d'entité?

15

Je lis souvent dans les documentations du moteur de jeu ECS qui est une bonne architecture pour utiliser judicieusement le cache cpu.

Mais je ne peux pas comprendre comment nous pouvons bénéficier du cache cpu.

Si les composants sont enregistrés dans un tableau (ou un pool), dans une mémoire contiguë, c'est un bon moyen d'utiliser le cache cpu MAIS uniquement si nous lisons les composants de manière séquentielle.

Lorsque nous utilisons des systèmes, ils ont besoin d'une liste d'entités qui est une liste d'entités qui ont des composants avec des types spécifiques.

Mais ces listes donnent les composants de manière aléatoire et non séquentielle.

Alors, comment concevoir un ECS pour maximiser le hit du cache?

ÉDITER :

Par exemple, un système Physic a besoin d'une liste d'entités pour l'entité qui a les composants RigidBody et Transform (Il y a un pool pour RigidBody et un pool pour les composants Transform).

Ainsi, sa boucle de mise à jour des entités sera la suivante:

for (Entity eid in entitiesList) {
    // Get rigid body component
    RigidBody *rigidBody = entityManager.getComponentFromEntity<RigidBody>(eid);

    // Get transform component
    Transform *transform = entityManager.getComponentFromEntity<Transform>(eid);

    // Do something with rigid body and transform component
}

Le problème est que le composant RigidBody de l'entité1 peut être à l'index 2 de son pool et le composant Tranform de l'entité1 à l'index 0 de son pool (car certaines entités peuvent avoir certains composants et pas l'autre et en raison de l'ajout / suppression d'entités / composants au hasard).

Donc, même si les composants sont contigus en mémoire, ils sont lus au hasard et il y aura donc plus de cache manquant, non?

À moins qu'il n'y ait un moyen de pré-extraire les prochains composants de la boucle?

Johnmph
la source
pouvez-vous nous montrer comment allouez-vous chaque composant?
concept3d
Avec un simple allocateur de pool et un gestionnaire de poignée pour avoir une référence de composant pour gérer la relocalisation des composants dans le pool (pour garder les composants contigus en mémoire).
Johnmph
Votre exemple de boucle suppose que les mises à jour des composants sont entrelacées par entité. Dans de nombreux cas, il est possible de mettre à jour les composants en bloc par type de composant (par exemple, mettre à jour tous les composants de corps rigide d'abord, puis mettre à jour toutes les transformations avec les données de corps rigide finies, puis mettre à jour toutes les données de rendu avec les nouvelles transformations ...) - cela peut améliorer le cache utiliser pour chaque mise à jour des composants. Je pense que ce type de structure est ce que Nick Wiggill propose ci-dessous.
DMGregory
C'est mon exemple qui est mauvais, en fait, c'est plus le système «mettre à jour toutes les transformations avec les données de corps rigides finies» que le système physique. Mais le problème reste le même, dans ces systèmes (mise à jour de transformation avec corps rigide, mise à jour de rendu avec transformation, ...), nous aurons besoin d'avoir plus d'un type de composant à la fois.
Johnmph
Vous ne savez pas si cela peut également être pertinent? gamasutra.com/view/feature/6345/…
DMGregory

Réponses:

13

L'article de Mick West explique en détail le processus de linéarisation des données des composants d'entité. Il a fonctionné pour la série Tony Hawk, il y a des années, sur un matériel beaucoup moins impressionnant qu'aujourd'hui, pour améliorer considérablement les performances. Il a essentiellement utilisé des tableaux globaux préalloués pour chaque type distinct de données d'entité (position, score et ainsi de suite) et référence chaque tableau dans une phase distincte de sa update()fonction à l' échelle du système. Vous pouvez supposer que les données de chaque entité seraient au même index de tableau dans chacun de ces tableaux globaux, donc par exemple, si le lecteur est créé en premier, il pourrait avoir ses données [0]dans chaque tableau.

Encore plus spécifique à l'optimisation du cache, les diapositives de Christer Ericsson pour C et C ++.

Pour donner un peu plus de détails, vous devez essayer d'utiliser des blocs de mémoire contigus (plus facilement alloués sous forme de tableaux) pour chaque type de données (par exemple, position, xy et z), afin d'assurer une bonne localité de référence, en utilisant chaque bloc de données de ce type dans des update()phases pour des raisons de localité temporelle, c'est-à-dire pour s'assurer que le cache n'est pas vidé via l'algorithme LRU du matériel avant d'avoir réutilisé toutes les données que vous avez l'intention de réutiliser, dans un update()appel donné . Comme vous l'avez laissé entendre, ce que vous ne voulez pas faire, c'est allouer vos entités et composants en tant qu'objets discrets via new, car les données de différents types sur chaque instance d'entité seront alors entrelacées, réduisant la localité de référence.

Si vous avez des interdépendances entre les composants (données) de sorte que vous ne pouvez absolument pas vous permettre de séparer certaines données des données associées (par exemple, Transform + Physics, Transform + Renderer), vous pouvez choisir de répliquer les données Transform dans les tableaux Physics et Renderer. , garantissant que toutes les données pertinentes correspondent à la largeur de ligne du cache pour chaque opération critique pour les performances.

N'oubliez pas que les caches L2 et L3 (si vous pouvez les supposer pour votre plate-forme cible) font beaucoup pour atténuer les problèmes que le cache L1 peut subir, comme une largeur de ligne restrictive. Ainsi, même en cas de défaillance L1, ce sont des filets de sécurité qui empêcheront le plus souvent les appels à la mémoire principale, qui sont des ordres de grandeur plus lents que les appels à n'importe quel niveau de cache.

Remarque sur l'écriture de données L'écriture n'appelle pas dans la mémoire principale. Par défaut, les systèmes actuels ont activé la mise en cache en écriture différée : l'écriture d'une valeur ne l'écrit que dans le cache (initialement), pas dans la mémoire principale, vous ne serez donc pas goulot d'étranglement. Ce n'est que lorsque les données sont demandées à la mémoire principale (ne se produira pas lorsqu'elles sont dans le cache) et qu'elles sont périmées, que la mémoire principale sera mise à jour à partir du cache.

Ingénieur
la source
1
Juste une note pour quiconque pourrait être nouveau dans C ++: std::vectorest fondamentalement un tableau redimensionnable dynamiquement et est donc également contigu (de facto dans les anciennes versions C ++ et de jure dans les versions C ++ plus récentes). Certaines implémentations de std::dequesont également "assez contiguës" (mais pas celles de Microsoft).
Sean Middleditch
2
@Johnmph Tout simplement: si vous n'avez pas de localité de référence, vous n'avez rien. Si deux éléments de données sont étroitement liés (tels que les informations spatiales et physiques), c'est-à-dire qu'ils sont traités ensemble, vous devrez peut-être les compacter en un seul composant, entrelacé. Mais gardez à l' esprit alors que toute autre logique ( par exemple, AI) qui tire parti de ces données spatiales peuvent alors souffrir en raison des données spatiales ne sont pas inclus à côté il . Cela dépend donc de ce qui nécessite le plus de performances (peut-être de la physique dans votre cas). Cela a-t-il du sens?
Ingénieur
1
@Johnmph oui, je suis totalement d'accord avec Nick, c'est sur la façon dont ils sont stockés en mémoire, si vous avez une entité avec des pointeurs vers deux composants qui sont loin dans la mémoire, vous n'avez pas de localité, ils doivent tenir dans une ligne de cache.
concept3d
2
@Johnmph: En effet, l'article de Mick West suppose des interdépendances minimales. Donc: minimisez les dépendances; Données répliquées le long des lignes de cache où vous ne pouvez pas minimiser ces dépendances ... par exemple , citons Transformer à côté à la fois modèle du solide indéformable et rendu; et afin d'ajuster les lignes de cache, vous devrez peut-être réduire autant que possible vos atomes de données ... cela pourrait être réalisé en partie en passant du point flottant au point fixe (4 octets contre 2 octets) par valeur décimale. Mais d'une manière ou d'une autre, peu importe comment vous le faites, vos données doivent s'adapter à la largeur de la ligne de cache comme l'a noté concept3d, pour des performances maximales.
Ingénieur
2
@Johnmph. Non. Chaque fois que vous écrivez des données Transform, vous les écrivez simplement dans les deux tableaux. Ce ne sont pas ces écrits dont vous devez vous inquiéter. Une fois que vous avez envoyé une écriture, c'est comme si c'était fait. Ce sont les lectures , plus tard dans la mise à jour, lorsque vous exécutez Physics and Renderer, qui doivent avoir accès à toutes les données pertinentes, immédiatement, dans une seule ligne de cache, de près et personnelle au CPU. De plus, si vous avez vraiment besoin de tout cela ensemble, vous effectuez des réplications supplémentaires ou vous vous assurez que la physique, la transformation et le rendu correspondent à une seule ligne de cache ... 64 octets sont communs et contiennent en fait beaucoup de données! ...
Ingénieur