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

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?

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.