Journal Veuillez instancier ce journal avant de le lire

16
9
oct.
2014
/* attention ce journal est très légèrement technique, il ne suit pas la ligne éditoriale de linuxfr, vous n'y trouverez donc ni recette de cuisine, ni histoire de motards */

class journal < typename… Users > {

Bonjour Nal!

Si tu as lu mon précédent journal, tu sais que je me remets à jour en C++ en écrivant un petit prototype de jeu afin d'explorer ou de redécouvrir certaines parties de l'univers de cette plateforme de développement en kit.

Cette semaine, je me suis intéressé aux variadic templates (patrons en nombre variable en français?) et au policy based design (dessein basé sur la police?) pour implémenter un petit entity system (système à entités ça c'est facile!): bourrines.

Si ce bourrin entity system n'a pas pour but de faire de la concurrence à des bibliothèques plus sérieuses, il s'inspire fortement de la référence java dans le domaine, artemis tout en usant de la possibilité qu'offre C++ de bien gérer la mémoire.

Pour ceux qui ont raté les journaux de rewind<, un entity system est une architecture très à la mode dans les jeux vidéos: il s'agit d'une variante du role pattern combiné avec des principes du data oriented programming. Pour simplifier et éviter de massacrer la langue de Jacques Toubon, un système à entité dans un jeu peu se résumer à:

  • presque tout élément du jeu (décors, avatars, pnjs, objets, bonus, tirs, plateformes…) est une entité.
  • une entité peut se voir attribuer ou retirer des composants.
  • un composant est un ensemble de données simples (PDO ie plain data object).
  • le moteur du jeu est constitués de systèmes.
  • un système est un ensemble d'algorithmes qui peuvent créer et détruire des entités ainsi que lire, écrire et transformer leurs composants.

Dans ma version de cette architecture, j'ai fait en sorte:

  • de pouvoir changer facilement de layout mémoire pour les entités et les composants via des stores: c'est l'application du policy based design.
  • de générer ces layouts à la compilation sans avoir à écrire de code intrusif dans les composants: c'est là qu'intervient l'usage des variadic templates, par exemple au lieu de créer une struct à la main avec un champ par composant, j'ai fait une classe component_struct qui hérite récursivement d'elle même en ajoutant un champ correspondant à un template de sa liste.

Si tu es un peu perdu, le mieux est regarder le benchmark que j'ai écrit pour comparer les performances des deux layouts en mémoire:

  • je crée, fait rebondir et détruis un grand nombre de sprites sur l'écran.
  • chaque sprite est une entité.
  • chaque entité a des composants pour la position, l'image à afficher, sa durée de vie…
  • un hera_system donne la vie aux sprites.
  • un hades_system les tue au bout d'un moment.
  • un hades_system les tue au bout d'un moment.
  • un move_system les déplacent.
  • un render_system les affiche.

Chez moi, le layout array of struct est environ 2% plus rapide, mais je n'ai pas encore creusé et profilé le sujet pour savoir où sont vraiment les goulots d'étranglements.

Sources

};

class journal< U, Users… > : public journal< Users… > {

Bonjour à toi aussi U! Que penses-tu de mon code? Comment ferais-tu pour l'améliorer?

};

benchmark

  • # bizarre

    Posté par . Évalué à 6. Dernière modification le 09/10/14 à 18:04.

    Pour moi, le layout mémoire idéal d'un système à entité consiste à regrouper par composant.

    L'entité est simplement un nombre, nombre qui sert de clef dans un conteneur à composants, pour retrouver les composants.

    L'idée est que chaque système manipule un nombre réduit de composants sur un grand nombre d'entités, ainsi on bénéficie d'une meilleure localité d'accès pour les caches.

    Le conteneur peut être une hashmap ou un arbre.

    "La première sécurité est la liberté"

    • [^] # Re: bizarre

      Posté par . Évalué à 2.

      Le conteneur peut être une hashmap ou un arbre.

      Localité des données et arbre (ou hashmap) ne font pas bon ménage (vu que c'est bourré d'indirections). Ou alors, il y a un truc que je n'ai pas compris.

      • [^] # Re: bizarre

        Posté par . Évalué à 2.

        Les indirections sont bien plus local que dans un système classique.

        "La première sécurité est la liberté"

    • [^] # Re: bizarre

      Posté par (page perso) . Évalué à 3.

      L'entité est simplement un nombre, nombre qui sert de clef dans un conteneur à composants, pour retrouver les composants.

      C'est le cas!

      typedef std::size_t entity;

      Pour moi, le layout mémoire idéal d'un système à entité consiste à regrouper par composant.

      C'est implémenté par le store struct_of_array.

      template< typename Component, typename... Components >
      class store_base< Component, Components... > : private store_base< Components... > {
      (...)
      typedef std::vector<boost::optional<Component>> component_vector;
      (...)
      component_vector components_;
      > Le conteneur peut être une hashmap ou un arbre.

      Ici c'est un simple vecteur pour être plus sympa avec le cache!

      (Désolé pour le formattage, le parseur markdown de linuxfr a l'air cassé).

      http://devnewton.bci.im

  • # gné

    Posté par . Évalué à 3. Dernière modification le 09/10/14 à 18:19.

    je ne suis pas très fluant en cpp mais j'aime bien comprendre.
    peux-tu nous dire ce que tu essayes de bencher.
    pour moi un bench c'est:
    - une problématique (là on l'a il me semble : faire bouger des sprites à l'écran et qu'il leur arrive des trucs),
    - des critères d'évaluations (?),
    - des solutions candidates (on en a une, entity system + variadic templates + policy based design, c'est ça ?)
    - des outils pour dérouler le bench
    - une analyse
    - une conclusion

    • [^] # Re: gné

      Posté par . Évalué à 8.

      Il compare le layout "struct of array" vs "array of struct" pour voir quelle est le meilleur en terme de performance.

  • # Benchmark

    Posté par . Évalué à 4.

    Il serait probablement plus pertinent de commenter tous les appels à SDL_* pour benchmarker l'effet du layout mémoire.
    (sinon sur ma machine, une large majorité du temps est consommé par la stack graphique).

    Comme profiler pour ce genre de cas, je te conseille perf, par ex:

    perf record -e cycles,cache-misses,stalled-cycles-frontend,branch-misses ./superpaflaballe
    perf report

    Ça permet de voir assez finement les effets des choix d'organisation de la mémoire.

    Dernier point, ton benchmark étant simple, il omet une des difficultés (à mon goût) des E/S : comment stocker de manière efficaces des composants pour N entités sachant que les entités n'ont pas toutes les mêmes composants.

    (dans mon cas j'ai choisis après divers test : une entité représente un index, et les composants sont stockés dans des std::vector. Ça permet d'améliorer l'utilisation du cache pour l'opération la plus couteuse : la maj des systèmes)

    • [^] # Re: Benchmark

      Posté par . Évalué à 3.

      Dernier point, ton benchmark étant simple, il omet une des difficultés (à mon goût) des E/S : comment stocker de manière efficaces des composants pour N entités sachant que les entités n'ont pas toutes les mêmes composants.

      Il doit mal expliquer mais en fait, c'est exactement ce qu'il fait : comparer comment stocker les entités. Avec deux variantes : "struct of array" et "array of struct".

      (dans mon cas j'ai choisis après divers test : une entité représente un index, et les composants sont stockés dans des std::vector. Ça permet d'améliorer l'utilisation du cache pour l'opération la plus couteuse : la maj des systèmes)

      Dans son cas, ce sont aussi des vector. Et toutes les entités ont potentiellement tous les composants (d'après ce que j'en ai compris).

      • [^] # Re: Benchmark

        Posté par . Évalué à 1.

        Il doit mal expliquer mais en fait, c'est exactement ce qu'il fait : comparer comment stocker les entités. Avec deux variantes : "struct of array" et "array of struct".

        Oui. Mais ce que je voulais souligner c'est que la difficulté est dans "comment les stocker efficacement, sachant que toutes les entités n'ont pas nécessairement tous les composants".

        • [^] # Re: Benchmark

          Posté par (page perso) . Évalué à 2.

          comment les stocker efficacement, sachant que toutes les entités n'ont pas nécessairement tous les composants

          Ca dépends quelle efficacité tu recherches. C'est un problème de space versus time versus flexibility. Dans les deux layouts que je présente, on sacrifie l'espace: chaque entité créé provoque une allocation égale à la taille de tous les composants.

          Si tu as des idées d'autres layouts, je cherche de l'inspiration!

          http://devnewton.bci.im

          • [^] # Re: Benchmark

            Posté par (page perso) . Évalué à 2. Dernière modification le 10/10/14 à 08:59.

            Toutes ces histoires de layout mémoire, ça m'a rappelé une présentation que j'avais trouvée il y a quelques temps sur le Net.
            Et chance !! Je l'ai retrouvée ici.
            Attention, c'est technique mais comme c'est toi qui as commencé… :D

            • [^] # Re: Benchmark

              Posté par (page perso) . Évalué à 2.

              Merci!

              C'est intéressant, je me demande comment détecter les cas complètement contre-intuitif comme celui de la page 30.

              http://devnewton.bci.im

          • [^] # Re: Benchmark

            Posté par . Évalué à 2.

            Pour chaque entité tu alloues tous les composants ? Pourquoi pas seulement, les composants utiles ?

            "La première sécurité est la liberté"

            • [^] # Re: Benchmark

              Posté par (page perso) . Évalué à 2.

              Oui! Je cherche une idée de "store" qui minimise l'occupation mémoire pour comparer!

              http://devnewton.bci.im

              • [^] # Re: Benchmark

                Posté par . Évalué à 3.

                Il y a as dans boost (ou eigen) de vecteurs creux ?

                Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

                • [^] # Re: Benchmark

                  Posté par (page perso) . Évalué à 4.

                  • [^] # Re: Benchmark

                    Posté par . Évalué à 3.

                    Ça ne pourrait pas t'aider pour avoir un compris entre des données contiguës et un volume de données maîtrisée ?

                    Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

                    • [^] # Re: Benchmark

                      Posté par (page perso) . Évalué à 2.

                      Sans doute, je vais creuser le sujet…

                      http://devnewton.bci.im

                      • [^] # Re: Benchmark

                        Posté par . Évalué à 2.

                        Ou alors tu le code toi-même : un vector pour le stockage et un hashmap pour l'association composant <-> entity.

                        "La première sécurité est la liberté"

                        • [^] # Re: Benchmark

                          Posté par . Évalué à 4.

                          Quand on en arrive à ce genre de choses où on maintiens N*2 structures de taille M/2 (avec N nombre de types de composants et M nombre max d'entité), j'ai du mal à voir l'intérêt de garder une entité comme un numéro plutôt qu'une structure qui contient une référence/pointeur vers chacun de ces composants.

                          Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

                          • [^] # Re: Benchmark

                            Posté par . Évalué à -1.

                            Cela évite d'utiliser des pointeurs :)

                            "La première sécurité est la liberté"

          • [^] # Re: Benchmark

            Posté par . Évalué à 3.

            chaque entité créé provoque une allocation égale à la taille de tous les composants

            Si tu utilises un vector par type de composant tu peux limiter sa taille du tableau à "entité_max qui a ce composant - entité_min qui a ce composant + 1".
            Mais oui, ce stockage gaspille de la mémoire

            Si tu as des idées d'autres layouts, je cherche de l'inspiration!

            Pas tellement. J'avais commencé avec une implémentation simple : chaque système avait une map.
            Après quelques tests et benchmarks (cf mon commentaire sur perf), chaque système contient finalement :
            * un tableau (brut) de Composant (moins coûteux qu'un vector)
            * un std::vector d'entités, pour savoir quelles entités ont ce composant. Ce vector est trié pour optimiser l'utilisation du cache quand le système est mis à jour.

            Rien de bien original, mais ça me suffit pour mon usage :-)

  • # j'ai vu bien pire

    Posté par . Évalué à 8. Dernière modification le 09/10/14 à 18:50.

    Le code est plutôt clair est lisible (j'aime pas les #pragma, mais je suis old-school), je ne me suis pas penché sur le design, quelques remarques/questions en vitesse :

    • dans framerate.cpp :
    ...
     if (current_ticks - last_frame_ticks >= max_frame_ticks) {
      max_ticks = current_ticks - last_frame_ticks;
    }
    ...

    utiliser std::max ?

    • Je vois que tu utilises souvent des shared_ptr, je n'ai pas encore bien regardé le besoin à haut niveau, mais parfois, les unique_ptr font l'affaire et te coûteront probablement moins cher ;

    • Sinon, évite d'utiliser std::endl, '\n' est ce que tu veux utiliser dans 99% des cas (dans ton cas, c'est juste dans le main(), donc ça changera rien mais mieux vaut prendre des bonnes habitudes) ;

    • Dans assets.cpp, tu dois pouvoir initialiser pathPrefixes_ à l'aide d'une intializer list, ça t'évite d'avoir à ré-allouer. (pareil qu'avant : dans ce contexte c'est du chipotage, mais il s'agit de prendre le pli).

    Si j'ai du temps et que je m'ennuie, j'essaierai de prendre du recul et voir comment tout ce tient.

  • # Coin !

    Posté par . Évalué à 3.

    Je pense que si la différence entre les deux n'est pas visible, c'est d'une part (comme dit plus haut) parce qu'il y a les appels SDL qui prennent beaucoup de temps, et d'autre part, parce que tes composants sont petits et peu nombreux, ce qui fait que même avec le layout "array of struct", tu as une bonne localité des données. Il faudrait faire le même test avec des données plus grosses et je pense qu'on verrait la différence. J'essaierai de bricoler un truc si je trouve du temps.

    • [^] # Re: Coin !

      Posté par (page perso) . Évalué à 2.

      A l'oeil nu, c'est invisible, surtout que je limite les fps à 60.

      Par contre dans la console, le boost::timer::auto_cpu_timer écrit des infos qui ne prenne pas en compte certaines opérations de la SDL (le swap de buffer par exemple).

      On pourrait de la même façon mesurer chaque système indépendamment pour avoir une analyse plus précise, mais un bon profileur doit savoir le faire tout seul comme un grand.

      Plus qu'à trouver un bon profileur!

      http://devnewton.bci.im

      • [^] # Re: Coin !

        Posté par . Évalué à 2.

        valgrind? Note que je ne sais pas vraiment m'en servir, mais ça à l'air d'être puissant.

      • [^] # Re: Coin !

        Posté par . Évalué à 3.

        Utilise SunStudio (marche sous linux, gratuit). Contrairement a valgrind, SunStudio (collect) a environ 3% de penalité (slowdown).
        Valgrind, c'est 10-50x sur de larges applications… souvent le rendant inutilisable comme profileur.

  • # POD vs PDO

    Posté par (page perso) . Évalué à 3.

    Commentaire inutile et donc indispensable, on parle plutôt de Plain_old_data_structure donc POD que de PDO :-)

  • # Traduction

    Posté par . Évalué à 3.

    Design ça se traduit par conception, et policy par politique :)

    Bon après pour le tout, va savoir comment le traduire sans que ça fasse pitié…

    • [^] # Re: Traduction

      Posté par . Évalué à 3.

      C'est donc une politique de conception ou une conception politicienne :)

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.