/* 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.
};
class journal< U, Users… > : public journal< Users… > {
Bonjour à toi aussi U! Que penses-tu de mon code? Comment ferais-tu pour l'améliorer?
};
# bizarre
Posté par Nicolas Boulay (site web personnel) . Évalué à 6. Dernière modification le 09 octobre 2014 à 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 rewind (Mastodon) . Évalué à 2.
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 Nicolas Boulay (site web personnel) . É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 devnewton 🍺 (site web personnel) . Évalué à 3.
C'est le cas!
typedef std::size_t entity;
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_;
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é).
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
# gné
Posté par steph1978 . Évalué à 3. Dernière modification le 09 octobre 2014 à 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 rewind (Mastodon) . Évalué à 8.
Il compare le layout "struct of array" vs "array of struct" pour voir quelle est le meilleur en terme de performance.
[^] # Re: gné
Posté par devnewton 🍺 (site web personnel) . Évalué à 3.
C'est ça!
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
# Benchmark
Posté par pepp . É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 rewind (Mastodon) . Évalué à 3.
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 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 pepp . Évalué à 1.
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 devnewton 🍺 (site web personnel) . Évalué à 2.
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!
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
[^] # Re: Benchmark
Posté par Blackknight (site web personnel, Mastodon) . Évalué à 2. Dernière modification le 10 octobre 2014 à 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 devnewton 🍺 (site web personnel) . É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.
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
[^] # Re: Benchmark
Posté par Nicolas Boulay (site web personnel) . É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 devnewton 🍺 (site web personnel) . Évalué à 2.
Oui! Je cherche une idée de "store" qui minimise l'occupation mémoire pour comparer!
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
[^] # Re: Benchmark
Posté par barmic . É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 devnewton 🍺 (site web personnel) . Évalué à 4.
http://www.boost.org/doc/libs/1_56_0/libs/numeric/ublas/doc/vector_sparse.htm
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
[^] # Re: Benchmark
Posté par barmic . É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 devnewton 🍺 (site web personnel) . Évalué à 2.
Sans doute, je vais creuser le sujet…
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
[^] # Re: Benchmark
Posté par Nicolas Boulay (site web personnel) . É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 barmic . É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 Nicolas Boulay (site web personnel) . Évalué à -1.
Cela évite d'utiliser des pointeurs :)
"La première sécurité est la liberté"
[^] # Re: Benchmark
Posté par pepp . Évalué à 3.
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
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 :-)
[^] # Re: Benchmark
Posté par devnewton 🍺 (site web personnel) . Évalué à 2.
Tu as mis les sources quelque-part?
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
[^] # Re: Benchmark
Posté par pepp . Évalué à 1.
Sur github https://github.com/SoupeauCaillou/sac
# j'ai vu bien pire
Posté par nazcafan . Évalué à 8. Dernière modification le 09 octobre 2014 à 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 :
framerate.cpp: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, lesunique_ptrfont 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 initialiserpathPrefixes_à 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 rewind (Mastodon) . É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 devnewton 🍺 (site web personnel) . É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!
Le post ci-dessus est une grosse connerie, ne le lisez pas sérieusement.
[^] # Re: Coin !
Posté par freem . Évalué à 2.
valgrind? Note que je ne sais pas vraiment m'en servir, mais ça à l'air d'être puissant.
[^] # Re: Coin !
Posté par guepe . É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 serge_sans_paille (site web personnel) . Évalué à 3.
Commentaire inutile et donc indispensable, on parle plutôt de Plain_old_data_structure donc POD que de PDO :-)
# Traduction
Posté par Victor . É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 barmic . É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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.