Manquements de cache et facilité d'utilisation dans les systèmes d'entité

Dernièrement, j'ai recherché et implémenté un système d'entité pour mon framework. Je pense que j'ai lu la plupart des articles, des reddits et des questions à ce sujet que j'ai pu trouver, et jusqu'à présent, je pense que je saisis assez bien l'idée.

Cependant, cela a soulevé des questions sur le comportement global de C ++, le langage dans lequel j'implémente le système d'entités, ainsi que certains problèmes d'utilisation.

Ainsi, une approche serait de stocker directement un tableau de composants dans l'entité, ce que je n'ai pas fait car cela ruine la localité du cache lors de l'itération à travers les données. Pour cette raison, j'ai décidé d'avoir un tableau par type de composant, donc tous les composants du même type sont contigus en mémoire, ce qui devrait être la solution optimale pour une itération rapide.

Mais, lorsque je dois itérer des tableaux de composants pour faire quelque chose avec eux à partir d'un système sur une implémentation de jeu réelle, je remarque que je travaille presque toujours avec deux types de composants ou plus à la fois. Par exemple, le système de rendu utilise conjointement le composant Transformer et le modèle pour effectuer un appel de rendu. Ma question est, puisque je n'itère pas de manière linéaire un tableau contigu à la fois dans ces cas, est-ce que je sacrifie immédiatement les gains de performances de l'allocation de composants de cette façon? Est-ce un problème lorsque j'itère, en C ++, deux tableaux contigus différents et utilise des données des deux à chaque cycle?

Une autre chose que je voulais vous demander, c'est comment garder les références aux composants ou aux entités, car la nature même de la façon dont les composants sont placés en mémoire, ils peuvent facilement changer de position dans le tableau ou le tableau pourrait être réaffecté pour être développé ou rétrécissement, laissant mes pointeurs ou poignées de composant invalides. Comment recommandez-vous de gérer ces cas, car je me retrouve souvent à vouloir opérer sur les transformations et autres composants à chaque image et si mes poignées ou pointeurs ne sont pas valides, il est assez compliqué de faire des recherches à chaque image.

Tout d'abord, je ne dirais pas que dans ce cas, vous optimisez trop tôt, en fonction de votre cas d'utilisation. Quoi qu'il en soit, vous avez posé une question intéressante et, comme je l'ai moi-même expérimenté, je vais peser. Je vais essayer d'expliquer comment j'ai fini par faire les choses et ce que j'ai trouvé en chemin.

• Chaque entité contient un vecteur de descripteurs de composants génériques qui peuvent représenter n'importe quel type.
• Chaque poignée de composant peut être déréférencée pour produire un pointeur T * brut. *Voir ci-dessous.
• Chaque type de composant possède son propre pool, un bloc de mémoire continu (taille fixe dans mon cas).

Il convient de noter que non, vous ne pourrez pas toujours traverser un pool de composants et faire la chose idéale et propre. Il y a, comme vous l'avez dit, des liens incontournables entre les composants, dans lesquels vous devez vraiment traiter les choses une entité à la fois.

Cependant, il y a des cas (comme je l'ai trouvé) où en effet, vous pouvez littéralement écrire une boucle for pour un type de composant particulier et faire un grand usage de vos lignes de cache CPU. Pour ceux qui ne connaissent pas ou souhaitent en savoir plus, jetez un œil à https://en.wikipedia.org/wiki/Locality_of_reference . Sur la même note, lorsque cela est possible, essayez de conserver la taille de votre composant inférieure ou égale à la taille de la ligne de cache de votre processeur. La taille de ma ligne était de 64 octets, ce qui, je crois, est courant.

Dans mon cas, faire l'effort de mettre en œuvre le système en valait la peine. J'ai vu des gains de performances visibles (profilés bien sûr). Vous devrez décider par vous-même si c'est une bonne idée. Les gains de performances les plus importants que j'ai vus dans plus de 1000 entités.

Une autre chose que je voulais vous demander, c'est comment garder les références aux composants ou aux entités, car la nature même de la façon dont les composants sont placés en mémoire, ils peuvent facilement changer de position dans le tableau ou le tableau pourrait être réaffecté pour être développé ou rétrécissement, laissant mes pointeurs ou poignées de composant invalides. Comment recommandez-vous de gérer ces cas, car je me retrouve souvent à vouloir opérer sur les transformations et autres composants à chaque image et si mes poignées ou pointeurs ne sont pas valides, il est assez compliqué de faire des recherches à chaque image.

J'ai également résolu ce problème personnellement. J'ai fini par avoir un système où:

• Chaque descripteur de composant contient une référence à un index de pool
• Lorsqu'un composant est «supprimé» ou «supprimé» d'un pool, le dernier composant de ce pool est déplacé (littéralement avec std :: move) vers l'emplacement désormais libre, ou aucun si vous venez de supprimer le dernier composant.
• Lorsqu'un «échange» se produit, j'ai un rappel qui informe tous les auditeurs, afin qu'ils puissent mettre à jour tous les pointeurs concrets (par exemple T *).

* J'ai découvert qu'essayer de toujours déréférencer les poignées des composants lors de l'exécution dans certaines sections de code à haute utilisation avec le nombre d'entités avec lesquelles je faisais face était un problème de performances. Pour cette raison, je maintiens maintenant certains pointeurs T bruts dans les parties critiques de la performance de mon projet, mais sinon j'utilise les poignées de composants génériques, qui devraient être utilisées dans la mesure du possible. Je les garde valides comme mentionné ci-dessus, avec le système de rappel. Vous n'aurez peut-être pas besoin d'aller aussi loin.

Mais surtout, essayez des choses. Jusqu'à ce que vous obteniez un scénario réel, tout ce que quelqu'un dit ici n'est qu'une façon de faire, ce qui peut ne pas vous convenir.

Est ce que ça aide? Je vais essayer de clarifier tout ce qui n'est pas clair. Toutes les corrections sont également appréciées.

Pour répondre à ceci:

Ma question est, puisque je n'itère pas de manière linéaire un tableau contigu à la fois dans ces cas, est-ce que je sacrifie immédiatement les gains de performances de l'allocation de composants de cette façon? Est-ce un problème lorsque j'itère, en C ++, deux tableaux contigus différents et utilise des données des deux à chaque cycle?

Non (du moins pas nécessairement). Le contrôleur de cache doit, dans la plupart des cas, être capable de gérer efficacement la lecture de plusieurs tableaux contigus. L'important est d'essayer si possible d'accéder à chaque tableau de façon linéaire.

Pour le démontrer, j'ai écrit un petit benchmark (les mises en garde habituelles du benchmark s'appliquent).

Commençant par une structure vectorielle simple:

struct float3 { float x, y, z; };

J'ai trouvé qu'une boucle sommant chaque élément de deux tableaux séparés et stockant le résultat dans un troisième fonctionnait exactement de la même manière qu'une version où les données source étaient entrelacées dans un seul tableau et le résultat stocké dans un troisième. J'ai quand même trouvé, si j'entrelaçais le résultat avec la source, la performance en souffrait (par environ un facteur 2).

Si j'accédais aux données au hasard, les performances souffraient d'un facteur entre 10 et 20.

Timings (10 000 000 éléments)

accès linéaire

• tableaux séparés 0,21s
• source entrelacée 0,21s
• source entrelacée et résultat 0.48s

accès aléatoire (décommenter random_shuffle)

• tableaux séparés 2.42s
• source entrelacée 4.43s
• source et résultat entrelacés 4.00s

Source (compilé avec Visual Studio 2013):

#include <Windows.h>
#include <vector>
#include <algorithm>
#include <iostream>

struct float3 { float x, y, z; };

float3 operator+( float3 const &a, float3 const &b )
{
    return float3{ a.x + b.x, a.y + b.y, a.z + b.z };
}

struct Both { float3 a, b; };

struct All { float3 a, b, res; };


// A version without any indirection
void sum( float3 *a, float3 *b, float3 *res, int n )
{
    for( int i = 0; i < n; ++i )
        *res++ = *a++ + *b++;
}

void sum( float3 *a, float3 *b, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = a[*index] + b[*index];
}

void sum( Both *both, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = both[*index].a + both[*index].b;
}

void sum( All *all, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        all[*index].res = all[*index].a + all[*index].b;
}

class PerformanceTimer
{
public:
    PerformanceTimer() { QueryPerformanceCounter( &start ); }
    double time()
    {
        LARGE_INTEGER now, freq;
        QueryPerformanceCounter( &now );
        QueryPerformanceFrequency( &freq );
        return double( now.QuadPart - start.QuadPart ) / double( freq.QuadPart );
    }
private:
    LARGE_INTEGER start;
};

int main( int argc, char* argv[] )
{
    const int count = 10000000;

    std::vector< float3 > a( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > b( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > res( count );

    std::vector< All > all( count, All{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );
    std::vector< Both > both( count, Both{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );

    std::vector< int > index( count );
    int n = 0;
    std::generate( index.begin(), index.end(), [&]{ return n++; } );
    //std::random_shuffle( index.begin(), index.end() );

    PerformanceTimer timer;
    // uncomment version to test
    //sum( &a[0], &b[0], &res[0], &index[0], count );
    //sum( &both[0], &res[0], &index[0], count );
    //sum( &all[0], &index[0], count );
    std::cout << timer.time();
    return 0;
}

Réponse courte: profilez puis optimisez.

Longue réponse:

Mais, lorsque je dois itérer des tableaux de composants pour faire quelque chose avec eux à partir d'un système sur une implémentation de jeu réelle, je remarque que je travaille presque toujours avec deux types de composants ou plus à la fois.

Est-ce un problème lorsque j'itère, en C ++, deux tableaux contigus différents et utilise des données des deux à chaque cycle?

C ++ n'est pas responsable des erreurs de cache, car il s'applique à tout langage de programmation. Cela a à voir avec le fonctionnement de l'architecture CPU moderne.

Votre problème pourrait être un bon exemple de ce que l'on pourrait appeler une optimisation prématurée .

À mon avis, vous avez optimisé trop tôt pour la localisation du cache sans regarder les modèles d'accès à la mémoire du programme. Mais la plus grande question est celle-ci: aviez-vous vraiment besoin de ce type (localité de référence) d'optimisation?

Agner's Fog suggère que vous ne devriez pas optimiser avant de profiler votre application et / ou de savoir avec certitude où se trouvent les goulots d'étranglement. (Tout cela est mentionné dans son excellent guide. Lien ci-dessous)

Il est utile de savoir comment un cache est organisé si vous créez des programmes qui ont des structures de Big Data avec un accès non séquentiel et que vous souhaitez éviter les conflits de cache. Vous pouvez ignorer cette section si vous êtes satisfait de plus de directives heuristiques.

Malheureusement, ce que vous avez fait était en fait de supposer que l'allocation d'un type de composant par baie vous donnera de meilleures performances, alors qu'en réalité, vous pourriez avoir causé plus d'échecs de cache ou même des conflits de cache.

Vous devriez certainement consulter son excellent guide d'optimisation C ++ .

Une autre chose que je voulais vous demander, c'est comment garder les références aux composants ou aux entités, étant donné la nature même de la façon dont les composants sont mis en mémoire.

Personnellement, j'allouerai les composants les plus utilisés ensemble dans un seul bloc de mémoire, afin qu'ils aient des adresses "proches". Par exemple, un tableau ressemblera à ça:

[{ID0 Transform Model PhysicsComp }{ID10 Transform Model PhysicsComp }{ID2 Transform Model PhysicsComp }..] puis commencez à optimiser à partir de là si les performances ne sont pas "assez bonnes".

Ma question est, puisque je n'itère pas de manière linéaire un tableau contigu à la fois dans ces cas, est-ce que je sacrifie immédiatement les gains de performances de l'allocation de composants de cette façon?

Les chances sont que vous obtiendrez globalement moins de ratés de cache avec des tableaux "verticaux" séparés par type de composant que l'entrelacement des composants attachés à une entité dans un bloc de taille variable "horizontal", pour ainsi dire.

La raison en est que, premièrement, la représentation "verticale" aura tendance à utiliser moins de mémoire. Vous n'avez pas à vous soucier de l'alignement pour les tableaux homogènes alloués de manière contiguë. Avec des types non homogènes alloués dans un pool de mémoire, vous devez vous soucier de l'alignement car le premier élément du tableau peut avoir une taille et des exigences d'alignement totalement différentes du second. En conséquence, vous devrez souvent ajouter un rembourrage, comme dans un exemple simple:

// Assuming 8-bit chars and 64-bit doubles.
struct Foo
{
    // 1 byte
    char a;

    // 1 byte
    char b;
};

struct Bar
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Disons que nous voulons les entrelacer Fooet les Barstocker les uns à côté des autres en mémoire:

// Assuming 8-bit chars and 64-bit doubles.
struct FooBar
{
    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'

    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Maintenant, au lieu de prendre 18 octets pour stocker Foo et Bar dans des régions de mémoire distinctes, il faut 24 octets pour les fusionner. Peu importe si vous échangez la commande:

// Assuming 8-bit chars and 64-bit doubles.
struct BarFoo
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;

    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'
};

Si vous prenez plus de mémoire dans un contexte d'accès séquentiel sans améliorer de manière significative les modèles d'accès, vous aurez généralement plus de ratés de cache. En plus de cela, la foulée pour passer d'une entité à la suivante augmente et à une taille variable, ce qui vous oblige à faire des sauts de taille variable en mémoire pour passer d'une entité à la suivante juste pour voir lesquels ont les composants que vous '' suis intéressé par.

Ainsi, l'utilisation d'une représentation "verticale" comme vous le faites pour le stockage des types de composants est en fait plus susceptible d'être optimale que les alternatives "horizontales". Cela dit, le problème des échecs de cache avec la représentation verticale peut être illustré ici:

Où les flèches indiquent simplement que l'entité "possède" un composant. Nous pouvons voir que si nous essayions d'accéder à tous les composants de mouvement et de rendu d'entités qui ont les deux, nous finissons par sauter partout dans la mémoire. Ce type de modèle d'accès sporadique peut vous amener à charger des données dans une ligne de cache pour accéder, par exemple, à un composant de mouvement, puis accéder à plus de composants et faire expulser ces anciennes données, uniquement pour charger à nouveau la même région de mémoire qui a déjà été expulsée pour un autre mouvement. composant. Cela peut donc être très inutile de charger les mêmes régions de mémoire plus d'une fois dans une ligne de cache juste pour parcourir et accéder à une liste de composants.

Nettoyons un peu ce gâchis pour que nous puissions voir plus clairement:

Notez que si vous rencontrez ce type de scénario, c'est généralement longtemps après le démarrage du jeu, après l'ajout et la suppression de nombreux composants et entités. En général, lorsque le jeu démarre, vous pouvez ajouter toutes les entités et les composants pertinents ensemble, auquel cas ils peuvent avoir un modèle d'accès séquentiel très ordonné avec une bonne localité spatiale. Après beaucoup de suppressions et d'insertions, vous pourriez finir par obtenir quelque chose comme le désordre ci-dessus.

Un moyen très simple d'améliorer cette situation consiste à trier simplement vos composants en fonction de l'ID / index d'entité qui les possède. À ce stade, vous obtenez quelque chose comme ceci:

Et c'est un modèle d'accès beaucoup plus convivial pour le cache. Ce n'est pas parfait car nous pouvons voir que nous devons sauter certains composants de rendu et de mouvement ici et là, car notre système ne s'intéresse qu'aux entités qui ont à la fois , et certaines entités n'ont qu'un composant de mouvement et certaines n'ont qu'un composant de rendu , mais au moins vous finissez par être en mesure de traiter certains composants contigus (plus en pratique, généralement, car souvent vous attacherez des composants intéressants, comme peut-être plus d'entités dans votre système qui ont un composant de mouvement auront un composant de rendu que ne pas).

Plus important encore, une fois que vous les avez triés, vous ne chargerez pas les données d'une région de mémoire dans une ligne de cache pour les recharger ensuite en une seule boucle.

Et cela ne nécessite pas une conception extrêmement complexe, juste une passe de tri radix en temps linéaire de temps en temps, peut-être après avoir inséré et supprimé un tas de composants pour un type de composant particulier, auquel cas vous pouvez le marquer comme besoin d'être trié. Un tri Radix raisonnablement implémenté (vous pouvez même le paralléliser, ce que je fais) peut trier un million d'éléments en environ 6 ms sur mon i7 quadricœur, comme illustré ici:

Sorting 1000000 elements 32 times...
mt_sort_int: {0.203000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_sort: {1.248000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_radix_sort: {0.202000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
std::sort: {1.810000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
qsort: {2.777000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

Ce qui précède consiste à trier un million d'éléments 32 fois (y compris le délai memcpyavant et après le tri des résultats). Et je suppose que la plupart du temps, vous n'aurez pas réellement plus d'un million de composants à trier, donc vous devriez très facilement être en mesure de vous faufiler de temps en temps sans provoquer de bégaiements notables de la fréquence d'images.