CatchChallenger et son datapack/db

Bonjour,

C’est quoi un datapack? C’est le pack de donnée contenant les données du jeux, les ressources si vous préférez. Pour CatchChallenger, c’est les monstres, les attaques, les images, les items et leurs utilisations, les maps, …

En comparant avec certains datapacks (PWO, PokeNet, Pokemium) pour faire des outils d’importation automatique, pour faciliter le passage sur mon jeu, je me suis rendu compte des problèmes des autres datapack:

http://catchchallenger.first-world.info/wiki/CatchChallenger_vs_other

Les traductions sont dans tout les coins (en plus de pouvoir avoir des choses sans traduction et des traductions qui ne sont relié à rien). Plein d’informations sont sortie de leur contexte, soit j’ai eu du mal à comprends ce que c’été, soit j’ai simplement pas compris. C’est souvent une simple liste d’éléments dans un fichier texte (par exemple ont sais même pas à quel map c’est relié, quel monstre, bot, …). Ça veux dire que si ont supprime un ligne, ça décale tout et tout deviens faux. Pour trouver certaines info sur les map, je doit résoudre la map avec son nom, puis de sont nom vers l’info, et donc si le nom change l’info n’est plus trouvable…

Vous aller me demander, mais quel format utilise t’il? Des fois des fichiers binaires, mais bien souvent un mix de fichiers textes de différents types: texte brute avec de simple retour à la ligne, des fichiers ini et des fichiers xml. Le tout en même temps, cela oblige de lire et de programmer de différente manière, cela est typique quand les développeurs ont beaucoup changé sur un même projet. La perte de performance lié au fichiers texte n’est pas important car tout datapack devrai (coté client et serveur) être chargé en mémoire et pas analysé en temps réel.

Avec CatchChallenger, c’est que du xml. Les traductions sont juste au dessous du texte en anglais (avec un lang= »fr » dans la définition de la balise), les attaques à apprendre pour les monstres sont dans la balise du même montres. Les ids sont la pour garder en base de données des nombres simple, minimiser l’espace en db, ne pas changer les références en cas de changement de nom, faire une indexation plus efficace. J’ai vu dans les autres datapack, qu’il y avais pas mal d’info que je n’utilisais pas, comme la classe, l’habitat, … informations que j’ai rajouter dans le xml car le format le permet. Et plus tard pris en compte dans l’application. Le faite d’avoir du xml permet d’organiser les items sous formes de liste mais aussi sous forme d’arbre, ce qui est trés pratique pour les données lié.

Le format des images est assez anarchique dans les autres datapack, elle n’ont pas le même centrage (raison?), certaines avec un fond transparent, d’autre avec un fond noir ou rose, … CatchChallenger supporte le gif, png et jpeg pour s’adapter aux images les plus diverses (jpeg pour les fonds d’écran, png pour les monstres en grands et miniatures, gif pour les miniatures et attaque animé), au choix de celui qui fait le datapack. Le datapack officiel à des images sur font transparent.

L’avantage lié à ces formats comme le xml, png/jpeg/gif (même si ce n’été pas recherché), c’est qu’il sont utilisable dans un navigateur, par exemple pour afficher comme je le fait actuellement sur le site officiel, les images des items/joureurs dans les pages web. Vous pouvez donc voir la partie statique du datapack, comme les informations en temps réél de la base de donnée.

Les données que j’ai vu sont buggées dans la plus part des datapack, même les liens entre les maps. Souvent car il sont à 2 endroits et qu’il ont été mise à jour des fois d’un coté, des fois d’un autre coté. Donc j’ai du coder un minimum de contrôle pour l’importation. Par exemple les attaques, il y as juste l’information power, et pas le changements de status si besoin, cela à cause du format ini pas adapté pour ça. Le xml permet des éléments optionnel, donc pour les bot de combats, ont peu spécifier ou non les attaques des monstres, pour les montres sauvage, ont peu soit ecrire le niveau min/max avec levelMin/levelMax ou un niveau unique avec level.

Dans la db, il stocke des données statique, statiquement, je m’explique… La maximum de vie est stocker sous forme de hp, donc si le datapack change le nombre de hp, il faut adapter toutes la base de données. En plus garder quelque chose en base de donnée alors qu’on l’as dans le datapack c’est bête, ça bouffe de la place en base de données. Dans ce cas, pour minimiser la base de donnée, j’aurai fait un type text, avec comme contenu: « HP:+50;SP:-10 ». Cela permet de ne pas prendre de place quand il n’y as pas de bonus (90% du temps), et de s’adapter au contenu du datapack. Bien sur si un objet est tenu, il est mieux de calculer les bonus directement depuis l’objet, au lieux de stocker l’effet en db. Cela permet d’adapté l’effet, et de limité le nombre d’effet possible. Ensuite une bonne utilisation des types, tant coté C++ que coté db est important pour limiter la taille mémoire et disque, et les index pour obtenir rapidement les infos en gardant à l’espris qu’une db sera toujours lente (et donc avec un temps d’accès).

Le datapack de CatchChallenger est commun entre le client et le serveur. C’est le même. Cela veux dire que si des personnes essayent de m’attaquer juste pour me faire fermer ou pour essayer de me faire cracher du fric, chaque personne s’étant connecté sur un serveur précis, peu facilement remonté le même serveur avec le même contenu lui même, depuis chez lui avec se petit connexion adsl de campagne. Hors fichiers lourd (image, musique), 80% en balise, et 60% en volume sont commun entre le serveur et le client. Le serveur doit avoir la partie client pour que le client puisse télécharger le datapack pour jouer. Et la partie spécifique au serveur qui se retrouve sur le client est minime (<1%). Une grosse partie la pour pouvoir faire les calcules coté client et coté serveur. Car si c’est fait juste coté serveur, cela oblige d’avoir de RTT (round-trip delay time (RTD) or round-trip time (RTT)).

Grace à cela, je me prémuni aussi des fermetures arbitraire de mon serveur. Imaginons que X essaye de faire fermer mon serveur entier par ovh (donc avec Ultracopier, …). Juste parce-que cette personne dit que mon jeu est trop proche d’un autre. Pas grave, je peu l’héberger chez moi, chaque personne peu le reprendre en plus si besoin. Et donc mon serveur se retrouve avec juste des sites, pas le serveur de jeu, et ont peu donc rien lui reprochez. Cela permet aussi que chaqu’un dispose du datapack pour faire sont propre contenu, et donc cela ne limite pas la créativité.

Apparemment PWO, PokeNet, Pokemium, ont été codé par des amateurs (comme beaucoup de petit jeux et de jeux de fan). Sur l’implémentation c’est pas grave car ça peu facilement être changer. Par contre sur le protocole et le datapack cela est fortement handicapant. Le protocole permet une bonne réactivité, sécurité et communication. Et le datapack, d’être repris, modifié, …

Le projet avance, petit à petit. Vu que je le fait sur mon temps libre, il avance pas aussi rapidement que je le voudrai. Pour la version 0.2 beaucoup de changements ont déjà été fait. Mais le changement de moteur n’as pas toujours été fait (Qt -> Qt Quick 2 pour accélération matériel, scripting, …). La roadmap est défini, et sera surement publié pour la sortie de la version 0.4. Avec la 1.0 prévu pour fin 2014 au pire.

Mantle d’amd

Bonjour,

Mantle d’AMD, c’est la nouvelle API qu’AMD veux pousser, ayant des implications commerciales et financière, je m’en méfie. Le principe ce n’est pas de facilité comme OpenGL, mais bien mettre le développeur à sa place, c’est à dire qu’il fasse le travail qui doivent faire, et qu’il ai tout les éléments en main pour le faire. Je suis 100% d’accords avec cela, surtout si ont peu garder OpenGL.

Un développeur qui juste alloue la mémoire, y accède puis la désalloue, c’est facile pour lui, mais il as pas conscience de l’emplacement de la mémoire, des latences, … alors que si ont lui fait charger la mémoire depuis le CPU vers le GPU, il vois ce qu’il fait, il as conscience de la latence (passé par le PCIe), ce qui lui permet de mieux coder. C’est la 1ere fois que un grands s’intéresse à la partie logiciel/algo qui est une grosse partie des performances, autant voir plus que le hardware. La puissance des pc est régulièrement doublé, et pourtant les logiciel/OS ne vont pas 100x plus vite qu’il y as 15ans (ça serai même le contraire). Par contre OpenGL contrairement à DirectX, permet des extension personnalisé, et donc d’exposé des truc de teste, ou spécifique aux matériel, contrairement à ce que j’ai cru lire que critique Mantle.

Attention tout de même à la sécurité, car l’accès aux matériel trop brute est mauvais coté sécurité si ont donne les accès au application. Je m’explique, si pour gagner en performance un laisse l’accés au disque brute car le FS (ntfs, ext4) est trop lent, oui, si le développeur est compétant il peu gagner en performance. Mais il à accès à tout, une application même en utilisateur normale, pour lire/écrire sur le hdd comme un administrateur car la gestion des droits ce fait coté FS, et donc il saute cette gestion des droits.

Sous linux nous avons Gallium3D, qui correspondrai à Mantle, qui lui n’est pas exposé directement à l’espace utilisateur si je ne me trompe pas. Par contre OpenGL comme Gallium3D sont libre, pas de grosse limitation, tout le monde peu participer, faire un driver, mettre en commun le travail. Je ne serai pas surpris si, comme par hazard AMD qui bosse sur leur driver livre Gallium3D, nous disait que Mantle viens de la, ou à un lien. Libre veux dire potentiellement que ce n’est pas limité à une platforme (console, pc, téléphone).

Pour toujours vous donner un exemple avec le FS. Si le FS est lent, c’est pour une raison (goulot d’étranglement, mauvaise organisation des accès disques). Sauter le FS permet de contourner cela, mais tout le monde doit coder plus, ne pas tomber dans les mêmes erreurs que le FS, … alors qu’il serai mieux de corriger le FS pour que tout le monde en profite. Je pense la même chose que Gallium3D/Mantle, donner accès au couche basse permet de contourner les lenteurs des couches hautes correspondante, mais ce qui vas être fait en attaquant directement les couches basses, doit être reporté tant que possible dans les couches hautes.

AMD annonce 10x en performance contre un algo OpenGL directement optimisé. C’est possible, j’ai vu assez souvent ce genre d’optimisation entre du C/C++ correcte et de l’assembleur. Par contre avec du C/C++ optimisé et pas juste correcte (utilisation en plus de tout les mots clef et autre optimisations fourni par le compilateur), l’écart diminue. Par contre je pense que la partie super-scalaire du au très grands nombre de cœur des carte graphique n’est pas exploité correctement. Donc la différence serai la même que entre du C mal fait et de l’assembleur. C’est un peu comme utiliser du multi-thread pour en utiliser, sans faire gaffe de pas faire trop de communication entre les cpu. Ca optimise mais ça tire par vraiment partie du multi-coeur. Encore pire avec une carte graphique. Je demande à voir en pratique avec un moteur déjà bien optimisé type Unreal engine 4. Si ça ce confirme cela veut dire aussi qu’il y as encore du chemin pour que les couches hautes exploite correctement le GPU. Mais je crois, qu’on peu écrire des shaders spécifique (assembleur pour carte graphique), plutot que de faire des shaders compilé. Mais même sur les shaders compilé avec LLVM, c’est de mieux en mieux, mais il y as encore du chemin.

Donc pour résumer rapidement mon point de vue: Attention au grande annonce qui pourrai être la juste pour remettre à flot AMD, attention à la sécurité, attention à la licence, mais concept intéressant si vraiment ça se traduit par des performances, et dans ce cas, optimisé mieux les couches au dessus, et changer si besoin les API au dessus.

Bye

Compression de données pour l’envoi en ligne

Bonjour,

Je vais vous parler de la compression de données pour avoir sur la destination une arborescence. Cela peut être mis en parallèle avec l’html (page web), qui elle aussi a besoin d’avoir une arborescence de fichiers chargé coté client pour fonctionner. La compression de données est là pour que les données mettent moins de temps à télécharger. Mais le temps n’est pas que le temps de téléchargement, c’est temps de téléchargement + temps de compression + temps de décompression (que j’oublie car coté client, et donc par fait une une machine avec concurrence des ressources).

La compression ajoute une taille fixe (un entête) aux données. La grosse majorité des compressions ne commence à être efficace qu’à partir de 100 octets, mais n’est vraiment intéressante qu’après 15Ko. Pour on choisira une compression lourde, plus les tailles de début de compression, et compression optimal seront grosse (avec xz par exemple). De ce fait, compresser un fichier non compressible, ne fera que lui rajouter de la taille. Vous devez donc filtrer ce qui doit être compressé ou pas.

En fonction de votre protocole, les fichiers non compressés peuvent être envoyés à la queue ou dans un block. Dans mon cas, les fichiers sont assez petits <100octets, mais très répétitifs. La mise dans un block (suite binaire des données des différents fichiers), permet de tirer avantage de la compression sur ce genre de fichier. Mais la où l’on pouvait faire simplement un cache par fichier (pré-compresser le fichier, et renvoyer ceux-ci sur demande), c’est plus difficile car la compression et sur plusieurs fichiers. Certains choisiront de compresser dynamiquement à chaque fois. D’autres mettront un cache, car comme moi, le téléchargement du datapack ce fait soit depuis le début, soit depuis la mise à jour, donc la majorité des fichiers envoyés seront contenu dans les mêmes listes. La gestion du cache, ou même de la compression dynamique doit être bien faite car cela rend sensible votre serveur aux attaques DDOS.

Comme dans une page html, les fichiers de mon datapack sont liés entre eux. Les compresser ensemble permet de compresser la référence « toto » dans tout les fichiers d’un coup, ce qui rend la compression encore plus efficace. Or le protocole http actuel (le 1), ne fait pas ça (en plus de compresser en gzip), ce qui fait perdre beaucoup de bande passante.

Pour éviter le transfert et la compression de données inutiles sur le datapack, les ressources sont préalablement bien compressées (ogg en mono dans mon cas, quantization des fichiers png /!\ trés important, …). Je peux aussi virer tout les caractères utiles que pour la compréhension humaine des xml (indentation, retours à la ligne, …), mais qui peux être inversé.

J’ai aussi passé de la définition d’action sur fichiers de 8Bits à 1Bits pour avoir un minimum de compression naturelle, efficace sans compression, ou avec compression légère (gzip/zlib). Cela est applicable à tout. Par exemple pour l’envoi des déplacements des joueurs, il n’y a pas de compression car les données sont censées être toutes aléatoires. Et le reste compressé par le protocole: pas de nom de map, mais un id (de 8 ou 16Bits).

Au final, cela me permet de reduire la taille du datapack original de 4Mo à 200Ko transféré max sans les musiques.

Voila pour la compression des données pour la transmission dans vos applications.

Path finding coté serveur et split via plugin

Bonjour,

Le path finding est une technique pour résoudre un chemin entre 2 points, et savoir si ont peu aller de l’un à l’autre. Cette technique est assez lourde, et peu consommer énormément de ressources pour des maps assez grande.

Pourquoi ne pas le faire coté serveur? Car comme dit précédemment les ressources cotés serveur sont précieuse, et ceux même en limitant la taille du path finding. Mais alors comment faire? Vous devez normalement ne pas résoudre les collisions en temps réel (car plein d’exception à une simple couche collision), et donc avoir un tableau de true/false représentant les tiles où vous pouvez marcher. Maintenant vous transformez cela en entier (int ou autre type qui peu contenir le nombre de tile max de votre map sur 2), et vous résolvez par zone. C’est à dire que 2 tiles l’un à coté de l’autre où l’ont peu marché sont dans la même zone. Si le point A et B sont dans la même zone, c’est qu’il y as un chemain entre les 2. Un tile isolé n’est pas une zone où l’ont peu marcher: Si ont est dessus, le changement d’orientation ne change pas la position (donc pas de contrôle si c’est marchable).

Coté transmissions de données, vous faites aux choix:

vous transmettez aux clients le point de destination d’un joueur, et c’est lui qui fait la résolution
Ou chaque joueur transmet les vecteurs de déplacement décomposé

La petite difficulté c’est le passage de zone, je m’explique: les passages qui font que l’ont peu passer que d’une zone à l’autre et pas l’inverse (c’est pour ça que ce n’est pas une zone unique). Ou encore si votre map est continue mais découpé en chunk (comme ma map en extérieur), vous devez valider que les 2 zone marchable des 2 maps sont bien en contact (et plus généralement boucler pour voir si la zone source et la destination sont bien en contacte, qui à dit path finding?).

Voila qui vous donnera ont grosse optimisation de votre serveur.

Certain m’ont suggéré de mettre la partie commune entre mon client et mon serveur en plugin, et peu être aussi le serveur pour les fois ou il est intégré au client (pour la version solo). Et en regardant « Mega drivers » pour mesa, j’ai la même conclusion. Faire du dynamique c’est bien car ça permet d’externaliser les parties communes pour les maj et les corrections. Mais ça freine l’évolution, dans le sens qu’il ne faut pas changer tout le temps les symboles (fonctions/méthodes) exportées. Certain ont décidé de ne jamais mettre à jour (pour garder la retro compatibilité des vieux programmes), d’autre ont des cycles de mise à jour. Pour Ultracopier les interfaces sont stables (peu de changement, et mineur), et vu que peu (actuellement pas) de plugins fait par d’autre, alors les changements sont fait à chaque versions majeures. Mais pour CatchChallenger, vu que je ne sais pas vraiment la forme définitive, et que la lib commune change tout le temps (je rajoute/supprime tout le temps des fonctions). J’ai décidé de mettre tout en statique, cela ne freinera pas l’évolution, et permettra une meilleur optimisation LTO. Cela permet de mieux compresser par upx, et aussi de faire moins de contrôle (car les info/arguments ne viennes pas de l’extérieur).

En espérant vous avoir éclairé, bye.

Profiling et optimisation générale

Bonjour,

Je vais traiter du profiling de vos programmes, de l’analyse de la vitesse, de la loi de wirth: le logiciel ralentit plus vite que le matériel n’accélère. Mes propos sont trés généraux, les articles suivant parleront plus de micro-optimisation dans des cas précis.

Les ordinateurs peuvent traiter facilement des milliards d’instructions par secondes (177 millards pour un Intel Core i7 Extreme Edition 3960X).

Comment profiler?

A première vue cela semble facile: on lance le profiler comme valgrind sous linux, et boom, c’est fini. Même si c’est déjà un début que peu de développeurs font, si c’est mal fait cela ne sert à rien.

Il faut avant tout isoler les cas de test, c’est à dire les cas plus ou moins probable d’utilisation. Un cas souvent oublié: le démarrage. Et oui, tout le monde démarre le programme avant de l’utiliser, or peu de développeurs profilent cette partie où intervient souvent le disque dur et le FS (car pas mal de fichier sont chargé).

Sous ultracopier j’ai isolé ces cas de test:

Copie/déplacement de gros fichiers
Copie d’une liste raisonnable de petits fichiers (<10000 fichiers)
Cas que j’ai rajouté car Ultracopier est des fois utilisé comme ça, et que nos hdd devienne de plus en plus gros: 2 000 000 fichiers, tailles mixtes, destination/sources mixte

Ensuite je me suis aperçu durant l’analyse que l’obtention des modules via une bête liste chaînée prends pas mal de temps, je suis donc passé à une MultiHash.

Un dernier exemple : ouvrir plusieurs fichiers avec un éditeur texte est normal. Or, quand je tentait ça avec kwrite, il fallait 10 minutes à cause d’un problème d’initialisation (corrigé depuis).

Optimiser l’algorithmique

Vous devez évaluer le coût de chaque opération. Votre profiler peut vous y aider.

Essayer de mettre un minimum de chose dans vos boucles. Par exemple, pour 2 boucles imbriqués, mettez l’instanciation en dehors des 2 boucles, cela permet de ne pas désallouer et réallouer vos variables à l’infini.

Evitez de trop presser la mémoire: évitez les allocations inutiles, évitez d’utiliser trop de mémoire. Lorsque vous utilisez beaucoup de donnée, pensez à la cohérence des données dans le cache (accéder à une donnée située à l’adresse X, puis accéder à une donnée située à l’adresse X + 1024 provoque une erreur de cache (cache miss), forçant le cache à être rechargé).

Faites la différence entre le temps d’appel d’une fonction, et le temps total passé dans cette fonction (temps d’appel multiplié par le nombre d’appel).

Bien coder

Ne pas coder un crapware qui fait tout et n’importe quoi, fait partie de la conception générale. Si le logiciel est trop fourni d’options, l’utilisateur vas s’y perdre. Un mode détaillé peu aider.

Les fonctionalités peu utilisées doivent être mises à part (sous forme de patch ou de plugins).

Un code clair est très important.

Le fait de faire tout ça peut vous aider à vous protéger du software bloat, cause de ralentissement logiciel.

Les sections lentes

Soit une section est lente car elle est mal codé.

Évitez qu’une fonction fasse intervenir le hdd puis le cpu, puis de nouveau le hdd. Car à chaque fois l’un des éléments attends l’autre (valable pour d’autre éléments).

Quand ont recherche un éléments dans une longue liste, il faut souvent parcourir toutes la liste, cela prend du cpu et demande beaucoup d’accès à des zones mémoire fragmentées. Lorsque c’est possible, utilisé une table de hashage: celà vous évitera de nombreux parcours de liste.

Soit c’est du à sa nature et cela ne peuT être changé (une compression xz mettra toujours plus de temps qu’une compression gzip; parsING d’un fichier xml).

Dans ce cas essayer de la mettre dans un thread à coté, ou/et d’utilisé les events.

Il ce peu que ce soit la lib que vous utilisez qui ralentisse votre programme. Hormis signaler les ralentissements excessifs au mainteneur ou aider à l’optimisation de la lib, ont ne peut pas y faire grands chose.

Une partie des compilateurs supporte la compilation de fonction optimisé pour un certain cpu, cela peu être utile pour utiliser toutes les instructions du votre cpu (et gagner en performance). Dans certain cas, compilé votre programme pour votre cpu peu être intéressant (ce qui souvent ne le rends plus distribuable à d’autre). Un serveur applicatif qui est sur un serveur dédié spécifique (et qui ne vas pas en bouger), dans ce cas, le compiler sur le serveur même pour le cpu précis du serveur dédié peu être avantageux.

Les caches

On ne parle pas ici du cache processeur, mais des caches en général.

Les caches ne sont pas toujours une bonne idée. Je m’explique : si pour faire un calcul il me faut 10ms et que l’accès au cache demande 15ms (swap?), alors l’utilisation du cache ralenti les performances.

Comment déterminer si un cache est utile? Il faut pour cela mesure le temps d’accès au cache dans un scénario d’utilisation courant. Un cache utilisé souvent et qui est de petite taille a de bonne chance d’être préchargé par le processeur, ce qui va rendre son accès quasiment gratuit.

Attention : un cache de plusieurs centaines de Mo prendra plusieurs centaines de millisecondes pour être parcouru. L’algorithme qui fait le lien entre les données d’entrée et la position dans le cache doit être bien pensé et bien codé. Cela veux dire: ne pas parcourir chaque entrée du cache si le cache contiens des millions d’entrée ; utiliser plusieurs niveaux d’indirection (des sous dossier) au lieu de tout mettre dans une liste (dans un même dossier ; dans le cas réel de dossiers sur un FS, les performances sont fortement amoindries pour les dossiers de plus de 10000 entrée – surtout si les noms sont des hashs).

Il faut analyser le temps de traitement des données : plus il sera grands face au temps d’accès du cache, mieux cela sera. Quand le cache ne fait gagner que 10% alors passer votre chemin, ça fait plus de code, plus difficile à lire.

Régénération du cache, c’est quoi? Le cache peu/doit être mit à jour. Par exemple à chaque écriture de la données entrantes, la donnée sortant doit changer. Si cette donnée est aléatoire et change souvent, un cache risque de coûter plus cher qu’il ne rapporte. Le ratio mise à jour du cache/temps d’accès du cache/temps de génération de la donnée est important.

Voila quel exemple pour mieux comprendre:

Si mon image est une image de caméra, elle change par définition à chaque frame. Mettre en cache une frame avec l’effet « noir et blanc » ne servira à rien, vu que l’image ne se répétera pas – et le cache ne sera jamais utilisé en lecture.
Si le traitement de mon image se fait en 100ms, que je fait 2 lectures du résultat final avec l’effet « noir et blanc », et que le cache met 50ms, cela veux dire: 1er accéss 100ms, 2eme accéss: 50ms. Le gain apporté par le cache est trop faible.
Si maintenant, j’upload mon image, et que je veux l’afficher des milliers de fois sur mon site web avec l’effet « noir et blanc », et que le cache met 5ms, cela veux dire: 1er accès 100ms chaque 1000 lecture, autre accéss: 5ms pour les autres accès. Le cache nous est très utile dans ce cas.

Il faut bien sur voir les problématiques de cohérence de cache.

Les threads

Nous nous dirigeons vers des machines massivement multi-processeur (cpu, gpu…).

Il faut voir l’aspect synchronisation entre les threads. En effet, si vous avez 2000 thread qui se synchronisent (ça peu être juste pour attendre le résultat d’un calcul), et que chaque thread fait le traitement en 1s, cela serait dramatique de mettre aussi 1s par thread pour se synchroniser. Car 2000 thread en fonction de la taille des données transmise, du bus, … ça peu rapidement faire un goulot d’étranglement. Une structure de thread en arbre (1 maître pour 50 esclave) peu aider. La complexité peu être facilement quarré (temps de synchronisation d’un éléments = nombre de threads car il faut parcourir la liste des thread * nombre d’éléments qui doivent le faire = nombre de threads)

Ensuite il y a la localité des données. Si le thread à ses info pour travailler dans le cache de son processeur, il vas travailler sans attendre d’avoir la donnée. Mais si vous faite une grosse zone avec un mutex/vérou dessus, et que tout les threads y accèdent alors il vont plus attendre leur tour que travailler (idem pour la concurrence des autres ressources comme le hdd).

Il faut éviter de partager les données entre plusieurs threads. Un thread qui écrit une donnée accédé en lecture par un autre thread (ça peut être un mutex aussi : à la base, un mutex c’est une donnée à laquelle le processeur accède de manière atomique), alors le coeur gérant le thread en lecture va devoir remettre à jour son cache de données. Si les interactions de ce type sont trop fréquente, les performances vont s’en ressentir.

Si un thread accède à une variable protégé par un mutex, et que le thread qui à besoin de puissance accède à cette même variable via ce même mutex, mais 1000x plus. Alors c’est qu’il y as un problème car le mutex ralenti fortement le thread qui à besoin de puissance, juste pour que l’autre thread y accède 1/1000.

Mais bien optimiser son programme est plus important que d’utiliser des threads ou les possibilités du matériel. Un programme mal conçu sera lent avec ou sans multi-thread, et ce, quel que soit le CPU.

Les approximations et erreurs

A certains endroits, ont peut tolérer des erreurs, des incertitudes. On peut dire: c’est suffisamment correct.

Il faut utiliser cette logique quand c’est possible. Par exemple, le moteur de copie sur ultracopier remonte la vitesse de lecture. Cette vitesse peut être approximative. De plus, je lit depuis un autre thread la variable sans mutex, ça veux dire que ce que je lit peu être faux une fois sur 1 millions. Pas grave, ça ne sert qu’à l’affichage, et le fait de ne pas poser de mutex me permet de gagner en performance.

L’OS vous fournit des timers précis, ou un peu moins précis. Même chose pour les nombres aléatoires. Utilisez les correctement pour ne pas ralentir votre programme.

Ne pas dire non

J’ai rapporter des problèmes de performance à des développeurs (openTTD). Il m’ont dit: Nous ne voulons pas bosser sur ton problème spécifique qui demande 1 heures, car la gestions d’un autre problèmes (gestion des trains) est un vrai goulot d’étranglement depuis plusieurs années. Voila un bon contre exemple: il vaut mieux corriger un problème qui n’affecte qu’une partie des utilisateurs en 1h plutôt que se limiter à travailler sur un problème qui affecte tous les utilisateurs, mais qui est présent depuis plusieurs années et qui nécessitera encore de long moins de développement.

D’autre diront: non, un éditeur texte n’as pas besoin de performance. Alors qu’il pourrai gagner facilement en performance, consommer moins de cpu (et économisé de la batterie). Cela permet aussi de passer sur des ordinations un peu vieux. Pourquoi faire un programme lent, quand on peu le faire rapide?

Chaque optimisation peut faire que le cpu diminue ses cache miss, que tel ou tel cache de données est mieux exploité, que l’OS swap moins. Il ne faut pas le faire à l’extrême, ni contre le bon sens, mais faire toutes les optimisations facile peu aider un programme à être plus efficace. Cela permet aussi d’apprendre les bons réflexes pour directement bien coder la prochaine fois.

Ne pas considérer les optimisations comme une tache annexe. Cela rends l’optimisation difficile quand elle n’est pas fait en amont (comme la sécurité).

Cas particulier: les cms subissant des attaques DDOS vont résister bien plus facilement si il sont optimisés, car il faudra un botnet et une bande passante plus importante pour saturer le serveur. Alors que s’il ne faut que quelques requêtes par secondes pour saturer le serveur, faut juste 1000 bot chargeant des pages sur le site à quelque page toutes les 10s (navigation normale), et le serveur est saturé. Et vu que les vrai visiteurs naviguent à cette vitesse, comme voulez vous faire la différence? (aucune protection ne marchera). Sans parler du fait que le confort de navigation est meilleur sur un site rapide.

Ne pas répéter comme un perroquet : « Google/Microsoft/Apple/Linux/Untel à dit… » Il peuvent se tromper, vous pouvez avoir mal compris leurs arguments, ou leur cas d’utilisation peut ne pas s’appliquer à la personne que vous conseillez. Ne répéter que si vous comprenez bien les implications de ce que vous dites.

Les erreurs à éviter

La perte de performance est inévitable dans l’absolu (même si vous codez en assembleur : vous voudrez alors écrire du code un peu lisible, or un code lisible n’est pas la meilleure manière d’écrire du code assembleur). Par contre faire un CMS en PHP avec framework qui est 1000x plus lent que du PHP pur, cela n’est pas acceptable.

Une astuces pour les performances peut être vrai en générale, mais pas forcément dans votre cas. Et elle peut tout simplement être mal implémentée. Il vaut mieux ne pas utiliser les variables globales, ni les goto. Mais si une série de goto permet de faire en 100 lignes ce qu’un code sans fait en 5000 lignes, alors foncez! C’est l’un des cas particulier où son usage est conseillé. C’est surement que l’algorithme veux ça (ou la prise en main utilisateurs, …).

Tout à un coût. Analyser bien le coût de ce qu’on vous dit avant de vous lancer. Par exemple grouper les CSS pour avoir moins de taille au final et moins de requête HTTP semble avantageux, mais ce n’est pas toujours vrai: car si 1 CSS sur 10 change, vous re-téléchargez tout les CSS de la page. Alors qu’avec des CSS séparé, juste celui qui n’est pas en cache est téléchargé. Sur un groupement, il faut donc recalculer le groupement des CSS et leur compression à chaque fois en PHP + framework (qui est donc super long).

La compression avec upx peut vous faire gagner un peu de temps dans certains cas sur le chargement du programme en mémoire. Ce ne sera probablement pas le cas pour une petite application (<100Ko) car l’overhead associé au temps de décompression est alors plus fort (le point important ici est le ration temps de lecture sur disque / temps de décompression ; au delà d’une certaine taille, il est toujours plus lent de lire sur disque, mais la différence peut être négligeable voire s’inverser si on traite un petit fichier).

Ne dites pas: les utilisateurs veulent voir les temps rééls et veulent qu’on exploite tous les CPU. Par exemple une fois que vous avez écrit un gros fichier et avant le flush() et close(), masquer la fenêtre, ça évitera de rester sur 100% de progression pendant plusieurs secondes. Vos utilisateurs vont surement vous dire: utilisez tout les cores de nos CPU ! Mais vont râler si votre application est plus lente que celle du voisin (juste car l’utilisation du multi coeur ralenti l’application).

Statique vs dynamique

Utilisé une bibliothèque en statique permet de minimiser les dépendances. Cela permet donc d’avoir moins de symboles à résoudre lors du chargement de la dll/so/… (qui rajoutent des symboles particuliers utilisés par le linker dynamique), ce qui permet d’avoir un meilleur temps de démarrage.

Cela permet aussi au compilateur de faire des optimisation inter-procédurale, particulièrement quand les optimisation sont fait au link (LTO).

En échange, cela ce traduit par moins de souplesse (pour mettre à jour la lib ont doit recompiler l’application). Cela fait une application plus grosses (mais plus facilement compressible avec upx).

Protocole pour mmorpg

Bonjour,

C’est mon retour d’expérience dans le domaine de la création d’un protocole pour un MMORPG (pokecraft). Mon 1er protocole étant dans la transmission de liste de copies un interne d’un Pc, il n’a que peu de rapport. Le protocole n’est pas fini ni définitif, mais ça fait plusieurs mois que je le travaille.

Cryptage et compression

Crypter la connexion ne sert théoriquement à rien (comme le http à ses débuts). D’après ce qu’ont m’a dit, une technique avec des hashs permet de transmettre le login/pass en hash sans possibilités de l’intercepter. J’ai donc choisi de la rendre optionnelle (je sais pas ce qui va passer par la dans le futur, et que les hardcores gamers soient protégés pour jouer 24h/24)

Le découpage des paquets, le flux non constant des données, le traitement rapide de bloque de données ne permettent pas une compression naturelle et transparente comme le ferait le http avec le gzip. Rien que l’entête de compression ajoute au moins 8 bits à chaque transmission, et la compression n’est efficace qu’a parti de 128 octets (données majoritairement non compressible, compression mixte). Il a donc été choisi de bien écrire le protocole pour éviter la redondance de données similaires. Mais pour les données arbitraires une compression fixe a été choisie: xz pour les éléments qui peuvent être mis en cache (soit dans le data pack directement, soit dans un cache sur le disque), Zlib pour la compression/décompression dynamique.

Minimisation des latences

Un point important appliqué dans pas mal de jeu, la minimisation des latences. Ici le jeu s’y prête grace à un gameplay principalement mono-joueur (multi-joueur fait pas les clans, leagues, …). Donc cela se résume à envoyer des données groupées, et de préférence avant que le client en as besoin. Par exemple, une liste de nombre aléatoire est envoyé pour que le client puisse dedans (liste gardé côté serveur pour faire la même chose). Ça évite le trafic réseau et les lenteurs pour tous les éléments aléatoires spécifiques au joueur.

Quand le joueur va vraiment avoir besoin d’attendre (attente du choix d’une attaque d’un autre joueur), alors c’est au client de le faire attendre (message d’attente).

Séparation du statique et du dynamique

Les données sont séparées en statique (le datapack) et dynamique (envoyée par le protocole). Cela permet de juste faire un rsync pour envoyé le datapack quand il y a un changement, histoire de minimiser les données envoyées, car les données ne changent que très peu (majoritairement statique). Et les données dynamiques sont transmises à la volée en fonction de leur type.

Protocole adpaté pour étre réparti

Le protocole est fait pour être découpé côté serveur. Les paquets de gestion de chat, de gestion de map, gestion des données locales au joueur (combat, inventaire…), sont faits pour être réparti sur plusieurs threads avec une bande passante minimale et sans latence (prêt pour un cluster?). Coté serveur le tout est réparti par des messages asynchrones pour ne jamais bloquer les différents éléments.

Attention, ici l’utilisation de threads est la pour éviter qu’une tache bloquante ne bloque les autres. Je pense à la répartition des déplacements des joueurs sur les autres joueurs, qui a une complexité carré et donc une fâcheuse tendance à mettre le cpu à 100% (surtout que c’est une partie trés solicité). Mais il y a aussi les accès disque ou les accès bloquant à la base de données, qui s’il ne serai pas mis dans un thread à part, bloquerai les joueurs, ou induirai des latences.

Les taches comme les combats, utilisation des objects ont une compléxité fixe, donc en plus d’étre très rapide, les répartir sur plusieurs thread/serveur ne servirai à rien (pose de mutex, induction de lenteur réseau, passage d’un traitement de 1µs à 1ms, soit 1000x plus lent). Et ils sont bien plus rapides que par exemple l’est la répartition des déplacements des joueurs sur les autres joueurs. Les traiter sur 1 cpu permet de ne pas rajouter de couche pour traiter ces données qui ce compte en centaines d’octects.

Datapack

Comment apporter de la souplesse pour ne pas obliger tout le monde à avoir la même histoire, même monstres à combattre, mêmes maps, …? C’est simple, il suffit de faire varier le datapack en function du serveur. Donc ce dernier doit contenir le contenu du jeu, graphisme, audio, données diverses, objets de l’inventaire, … Le client se comporte donc comme un navigateur (lecture avec des codecs déjà connus), les formats supportés sont donc multi-platforme comme: png, xml, ogg, …

Conculsion

L’écriture d’un protocole demande du temps, surtout de ce genre. Il faut bien veiller à l’asynchronisme (pour de pas avoir d’influence des latences), la minimisation de bande passante, et la fléxibilité. Ne rajoutez pas de compression, au d’autre couche du genre car ça vas être mieux, calculer les coups de ces couches (en terme de bande passante, cpu, latences, …). Vous devez aussi trouver quel sont les packets/messages/ordres qui vont étre appeller tout le temps, pour concentrer vos effort et minimiser encore la bande passante.

Qt, select(), poll() et epoll()

Bonjour, je viens vous parler d’un problème récurent avec Qt. La boucle d’évènement, c’est la base de Qt, car c’est grâce à elle que Qt fait ces signaux/slots, les divers events, le réseau, et bien d’autre chose.

Problème

Le problème est le suivant. Ce système s’appuie sur les mécanismes interne de l’os, select() est utilisé sur les systèmes unix. Hors ce procédé est obsoléte, en plus, plus il as de chose utilisé ou non, plus il vas être lent (complexité n(x)). Exemple:

En programmation, ça veux dire que si vous avec 30 sockets tcp d’ouvert (ça arrive souvent avec un navigateur moderne), 40 dossiers surveillés (pour les changements), bref une bonne partie des choses basé sur les events, et qui utilise un nombre minimal de connexion signals/slots (les programmes en compte je pense 150 pour les plus petit, 500 pour les moyens). Alors l’application vas ralentir car elle vas regarder dans une liste des choses ouverte celle qui corresponds à la votre
Coté utilisateur: Les applications comme Ultracopier, ktorrent, dolphin (explorateur de fichiers), … vont ralentir petit à petit. ktorrent vas être beaucoup plus lent qu’il ne le devrai juste à cause de cette histoire (d’un ordre de 10x d’après l’auteur)

Solution

L’utilisation d’epoll() permet d’avoir une complexité fixe n(1), ça veux dire que le temps de traitement est fixe, et donc ne dépends pas du nombre de fichier affiché à l’écran, du nombre de torrent ouvert, du nombre de socket tcp ouvert.

Qt dit que c’est pour l’utilisation mémoire, hors sur les petites applications 10Ko de mémoire, c’est pas ce qui vas changer grands choses, surtout que chez moi (mesuré avec l’outils massif de valgrind), le système signals/slots + les autres truc de Qt consomme 90% de la mémoire prise par mon application. Et les grosses application deviennes impraticable ou trés lent. Et les gros bureaux comme KDE, qui ont des dizaines de milliers de descripteur ouvert, j’en parle même pas.

Conclusion

Hors il n’existe pour l’instant aucun event dispatcher fini/stable avec epoll pour Qt que j’ai pu trouver. Il serai utile de trouver ce genre d’event dispatcher, pour avoir accès à ces méthodes même si Qt ne veux pas y passer.

N’étant pas un expert sur ce que je vous ai dit plus haut, il ce peu qu’il y ai des erreurs.

Création de mmorpg

Bonjour, voilà mon retour d’expérience comme joueur/administrateur système et GM de mmorpg, cet avis sera peut-être déjà acquis pour la plus part:
Point gameplay:
– Le jeu doit être amusant en solo comme un multi, pour ne pas abandonner si peu de personnes viennent
– Seulement recopier un gameplay ne sert à rien, leurs joueurs irons toujours à gameplay égale là où il y a d’autres joueurs. Inovez!
– Avoir un datapack/rates personnalisable, histoire que chaque personne y trouve son compte (histoire spécifique, augmentation des levels à son rythmes)
– Avoir des extensions de protocoles avec une bonne base, pour étendre le gameplay.
Partie performance:
– Beaucoup de dev font du: multiplayer online role-playing game (MORPG) pas du _Massively_ multiplayer online role-playing game (_M_MORPG), il prévoit pour 50 joueurs (pour eux c’est _Massively_, et se plante quand ils ont plus de joueurs)
– Ce qui en résulte, que le petit GM qui veut ouvrir son petit serveur le ferme rapidement car tous les mois il doit claquer des sommes folles en dédié (60€/mois pour avoir une machine correcte chez ovh).
– La personne qui veut mettre son serveur sur sa ligne ADSL ne peuvent en général pas. Car le débit est trop faible (personne ne fait de compression de la connexion tcp, ni ne prévois des options pour minimisé le débit), et à cause des pings. On peut pour la plupart des jeux, faire des protocoles d’auto-correction des latences qui permettent d’éviter que les pings n’ont trop d’importance. Pourtant, héberger chez soit, ou sur un trés petit hébergement est très utile pour démarrer.
– Calcule de complexité, rare sont ceux qui le font, cela ce pose surtout sur les joueurs qui se vois mutuellement, c’est en général: bande passant + cpu = nombre de joueur qui se vois mutuellement ^ 2

– Tout le monde se dit: on verra après pour les performances, hors une fois que tu as 1000 personnes en ligne et un serveur/client complet, personne n’a le courage de le refaire, surtout si il est crade. Résultat, tout le monde ralle car sa rame.

– Les pc ont une puissance qui augmente exponentiellement et le serveur sont exponentiellement plus lent (ce qui fait que depuis des années le nombre général maximum de joueurs reste fixe). Idiot vous direz. La plupart des serveurs ne supportent que <70 joueurs visibles mutuellement et 1000 connectés. Ce qui est très petit (j’ai fait sans problème 500 visibles et 100 000 connectés).

– Pour un petit nombre de joueur (<20), un simple mono coeur atom/arm, quelque centaine de mega de mémoire, une connexion adsl doivent suffire et pour les larges échelles (>10 000), un bon serveur (quad core, 8Go de mémoire, 1000Mbps) doit aussi suffire.
J’ai déjà vu:
– L’utilisation de tous les coeurs en multi-thread avec tellement de mutex qui se gène mutuellement. Cela fait des temps système énorme car sur certain cpu il n’y a pas d’optimisation hardware des mutex. Et qu’un seul cpu était utilisé en gros au final. (Je parle de l2jfree comparé au serveur propriétaire).
– Des serveur qui prennent 10% du cpu à vide sans aucun joueur…(minecraft, l2jfree, …), soit des fois c’est utile (timer et autre), mais pas avec 10% du cpu!
– Blockage, les joueurs s’en fiches que vous utilisez vos 56 coeurs si ça rame, ils veulent que ça ne rame jamais. Le plus efficace est donc de travailler en event, d’isoler les complexités exponentielles et les accés db/disk dans un thread. Idem pour les parties lentes. Dans le multi-thread avec event, essayer de libérer les boucles d’event+thread critique d’un maximum de choses pour gagner en latence.
– Ne sauvegardez pas en continu dans la base de données, faites le à la déconnexion des joueurs, pour les données continues (tel que les déplacements), à intervalle régulier. Bien sûr, les choses ponctuels peuvent être backupé en instantané (mais dans un thread à part).

Donc pour tout le monde (hébergeur, celui qui paye le dédié, les joueurs avec compte payant pour payer le dédié), il est indispensable de soigner certain point tel que les performances, le protocole (ça permet aussi de faire d’autres implémentations), la sécurité, la prévention de bug (personne n’aime quand tout le serveur crash et ça re-roll avec les données d’il y as 1h).
Je ne conseille à personne de faire le noob et de se lancer dans un jeu sans avoir déjà une bonne expérience en programmation (et avec un projet clair et réaliste). Les joueurs font partie des utilisateurs les plus exigeants et ce segment est là où il y a le plus de concurrence. Cela se traduit par déjà un grand projet public ou une solide motivation + y jouer même tout seul.

Les graphismes (je ne suis pas graphiste, mais j’ai quand même un peu d’expérience, manga, pixel art):
– Il ne faut pas les bâcler, car comme moi, beaucoup de joueurs regardent ça pour trier les bons jeux des petits jeux de merde. Donc très important pour avoir de nouveaux joueurs, bien plus que pour les logiciels. Il vaut mieux en avoir peu et bien, que beaucoup et mal. (J’aime bien mars space shooter pour ça)
– Les graphismes personnalisables dans le datapack sont importants.

Les fonctionnalités des bases importantes:
– Toujours prévoir l’envoie du pass en hash (sécurité), beaucoup utilise le même passe partout (dons les visites qu’il visites)
– L’update du datapack (voir client) dans le protocole, c’est assez crade d’avoir un updater à côté de son jeu
– Datapack par serveur, pour avoir des données par serveur et charger soit en fixe (pour les données les – dynamiques) soit à chaud (pour les données les + dynamiques). Important pour la concurrence et minimiser les données transmises et ne pas charger tout le temps les données dynamiques identiques (ratio read/write correcte pour la partie dynamique).
– Définir le nombre max de joueurs en ligne et en db (définir sur 16Bits, 32Bits ou 64bits), et bien proportionner/optimiser son serveur/client.
– Ne pas exclure de joueurs (multi-platforme, ou au moins support sous wine). C’est toujours frustrant (surtout quand on a acheté le jeu), de passer sous windows pour jouer (ou d’être privé du jeu si on a pas windows 😉 ).

– Visibilité correcte, faite en sorte que le joueur voit toujours une proportion correcte de l’écran (zoom adaptatif, …). Quitte à réduire la distance de visibilité si le nombre de joueur est trop grand. Et à ne rien afficher si les calcules à faire sont exagérés (le joueurs préfèrent ne rien voir, que de tout voir et que ça lag tellement qu’ils ne peuvent pas jouer). N’oubliez pas de mettre des hystérésis pour éviter de lag/prendre trop de bande passante près de la limite du serveur.