Créer une table coûte cher...

Pour mon serveur de logs, j'ai utilisé le système suivant pour écrire un message dans la base Postgresql:

• Ouvrir la transaction


• Créer une table temporaire qui sera détruite automatiquement à la fin de la transaction (on commit drop)


• Remplir la table avec les éléments de mon message


• Appeler la fonction qui va cŕeer les entrées dans les tables, à partir de la table temporaire


• Fermer la transaction, causant la destruction de la table temporaire.

Pour tester un peu tout ceci, j'ai envoyé 10000 messages de log d'un coup. Grosse déception, les performances étaient vraiment ridicules, à environ 60 messages par seconde.

J'ai ensuite réessayé en changeant le mécanisme pour la table temporaire: cette fois-ci, je créé la table une seule fois, au tout début, et je dis à Postgres de se contenter de tronquer la table à la fin de la transaction (on commit delete rows).

Surprise, la base de données s'en trouve beaucoup mieux, et pédale à 600 transactions par seconde!

Autant qu'il soit agréable qu'il ait été si simple de décupler ainsi les performances, je ne suis pas tout à fait satisfait par cette solution. Le problème principal est de gérer les reconnections: comment détecter que la table a disparu, et comment la recréer?

J'ai donc changé mon code de manière à appeler, pour chaque transaction, une fonction qui va détecter si la table existe déjà, et si non la créé. Vivement les blocks anonymes (DO $$ ... $$), mais ce sera pour Postgresql 8.5 (ou plutôt, Postgresql 9.0, puisque c'est ainsi que la prochaine version s'appelle désormais).

Verdict: 400 transactions par secondes. Et une routine qui sera imperméable aux déconnections. Ça me va!

C++ - Insertion dans une map et hints

Vous est-il déjà arrivé d'insérer des éléments dans une map, en sachant qu'ils étaient déjà ordonnés? Quelle perte de temps, dans ce cas, de payer une insertion logarithmique lorsque l'on sait déjà où l'élément doit aller. Cela tombe bien, std::map fournit la possibilité d'indiquer où l'élément se situe, via un "hint", et d'insérer en temps constant amorti. La documentation n'est cependant pas très précise sur le sujet. Voyons donc ce que ça donne, aidé de notre fidèle nano-horloge (attention, pour Linux seulement).

#include <iostream>
#include <ctime>
#include <vector>
#include <map>

int main()
{
  timespec t1, t2, t3;

  std::vector<int> keys;
  for(int i = 0; i < 100000; i++)
  {
    keys.push_back(i);
  }

  std::map<int, int> m1;
  std::map<int, int> m2;

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t1);

  for(int i = 0; i < keys.size(); i++)
  {
    m1.insert(m1.begin(), std::make_pair(i, i));
  }

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t2);

  for(int i = 0; i < keys.size(); i++)
  {
    m2.insert(std::make_pair(i, i));
  }

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t3);

  std::cout << "m1: " << t2.tv_nsec - t1.tv_nsec << std::endl;
  std::cout << "m2: " << t3.tv_nsec - t2.tv_nsec << std::endl;

  return 0;
}

Voilà comment réduire fortement le temps d'insertion (dans la réalité, l'on pourrait avoir à copier quelque chose d'un peu plus lourd qu'un entier, et les gains seraient plus réduits, mais quand même!). Scénario improbable, me direz-vous? Pas tant que ça. Par exemple, sérialisation / désérialisation vers un fichier, ou un format réseau: si l'on contrôle la sérialisation, l'on peut simplement écrire les éléments dans l'ordre du conteneur, et utiliser les hints au moment de la désérialisation. Facile, et fournissant un gain immédiat!

Développer son MMORPG - Architecture

5ème partie, où je soutiens que faire "comme les grands" peut avoir des avantages inattendus.

Je ne dirais pas que le plus grand risque du développeur de fond est d'abandonner son projet, mais plutôt de se laisser perdre dans l'exploration de solutions techniques. Ainsi, l'on se retrouve à démarrer bille en tête sur de la 3D, tout jeter pour passer à la 2D quand les difficultés deviennent insurmontables, puis revenir en 3D lorsque l'on vient juste de découvrir un nouveau moteur graphique, puis décider de passer à un moteur de jeu complet, puis se rendre compte de ses faiblesses et revenir à la 2D...

Il est malheureusement difficile d'échapper à ce genre de cycles, et c'est pour cela qu'il faut s'y préparer et développer en gardant en tête que l'on aura sûrement à changer quelques fondamentaux dans un futur proche. Et avoir de bonnes bibliothèques bien génériques est un pas dans la bonne direction.

Il est très peu probable qu'une refonte, même massive, change beaucoup le code de sérialisation, ou l'authentification, ou les logs, ou les utilitaires de bases de données, etc. Mettre ce code dans des bibliothèques bien séparées (et si possible bien testées), c'est l'assurance d'avoir déjà beaucoup de bon code lorsque l'on sonde de nouvelles possibilités.

Mais l'on peut pousser plus loin: l'on peut séparer de grands ensembles du tronc commun, et construire des services entiers qui soient réutilisables partout. Autant les MMORPGs commerciaux distribuent l'authentification, les logs, les données statiques du monde pour des raisons de performance, autant l'amateur peut construire ces mêmes services comme étant des blocs solides dans une architecture instable, lesquels tourneront d'ailleurs gentiment sur la même machine. Et si le succès est au rendez-vous, il sera d'autant plus simple de distribuer.

Un serveur de logs - C'est pas comme si écrire dans un fichier ou une base de données était très dépendant des fonctionnalités du jeu. Une application indépendante qui tourne en tâche de fond, une API, et basta, voilà une belle brique sur laquelle se poser.

Un serveur d'authentification - Encore un service on ne peut plus générique. Un compte, des permissions sur des applications, des permissions plus précises au sein de ces applications... Au fur et à mesure que l'on développe son jeu, l'on peut enrichir le serveur d'authentification avec des fonctionnalités de type rôles, création de compte via un serveur Web, accumulation de statistiques... qui pourront rester stables au fur et à mesure que l'on travaille sur les modules plus proches du gameplay.

Et autres - Peut-être un serveur qui fournit des données statiques? Peut-être des éléments de GUI?

A vrai dire, l'on pourra sans doute changer de langage en cours de route, ces services resteront (pour peu que les communications soient raisonnablement portables).

Bien sûr, il faut éviter de perdre son temps à généraliser du code, mais si un effort mesuré augmente ses chances d'être encore là après deux ou trois itérations, ça vaut le coup.

OMake et fichiers générés

J'ai tout une série de classes C++ générées à partir d'un petit programme ocaml. Comment s'assurer que le bon vieux OMake génère tout dans le bon ordre? Malgré quelques subtilités, c'est plus facile qu'il n'y parait.

Voilà mon fichier OMakefile:

LIBFILES[] =
 RequestMsg

GENERATEDFILES[] = 
 MsgId.h
 RequestMsg.h
 RequestMsg.cpp

CGeneratedFiles($(GENERATEDFILES))

LIB = ../lib/libmessages

.DEFAULT: $(StaticCLibrary $(LIB), $(LIBFILES))

.PHONY: clean
clean:
 rm -f *~ *.o adh

.PHONY: gch
gch:
 $(CXX) -c $(CXXFLAGS) All.h

$(GENERATEDFILES): messages.xml ../bin/dsgen
 ../bin/dsgen messages.xml

En premier, la liste des fichiers pour construire la bibliothèque, comme dans tout OMakefile qui se respecte.

Ensuite, la première subtilité. Je liste tous les fichiers qui seront générés par l'application (l'on peut probablement créer la liste à partir de la première liste de fichiers). Puis l'on indique via la commande CGeneratedFiles que ces fichiers sont générés. OMake va donc chercher dans l'ensemble des make files la règle qui lui indiquera comment construire ces fichiers. Ça tombe bien, tout en bas (au milieu, c'est du standard), il y a une règle qui dit que les fichiers dans $(GENERATEDFILES) peuvent être générés à partir de ma description xml et du programme de génération, et donne la commande à faire tourner pour les construire.

Deuxième subtilité, vu que le programme pour construire lesdits fichiers est lui-même créé par un autre make file du même groupe, j'indique le programme comme dépendance, ce qui veut dire qu'il cherchera à compiler le programme d'abord s'il ne peut pas le trouver.

Ansi, tout changement aussi bien dans mon fichier de description de classes (le "messages.xml") que dans le programme qui génère le code forcera une regénération. Et comme OMake se base sur un hash des fichiers pour déterminer si il y a eu changement, une modification cosmétique du générateur, par exemple, qui ne changerait pas le format de fichiers, se traduira par une execution du générateur, et c'est tout: les fichiers n'ayant pas changé, il est inutile de recompiler la bibliothèque, de lier les exécutables...

Taille d'une base de données Postgresql

C'est pourtant facile!

select datname, pg_size_pretty(pg_database_size(datname)) 
from pg_database

Valgrind

J'expérimente un petit peu avec Valgrind, et notamment avec callgrind, lequel génère le graphe des appels de fonctions, avec le nombre d'instructions passées dans chaque. C'est très instructif, et fondamental lorsque l'on essaie d'optimiser son programme. Et en plus, le magnifique kcachegrind est l'application graphique qui permet de visualiser les résultats.

Lançons donc un beau test:

valgrind --tool=callgrind ./unittests

Ceci génère un fichier callgrind.out., que l'on charge dans kcachegrind.

kcachegrind callgrind.out.16532

Et voilà le travail!


En regardant par exemple une de mes fonctions les plus coûteuses, la bien nommée geom::isCollision, l'on voit qu'en dehors d'elle même, elle a principalement passé son temps à récupérer les listes d'axes et de vertex pour les cylindres. La collision de cylindres coûte cher, n'en doutons pas!

Collisions - Un peu d'UML

Dans ma folle jeunesse, j'avais une haine farouche d'UML, et je craignais le jour où je commencerais à bosser et à devoir l'utiliser tout le temps. Heureusement, je me suis rendu compte que dans l'industrie (du moins dans la mienne), personne n'utilise UML. Au mieux, l'on dessinera un petit croquis avec trois cases et deux flèches pour s'expliquer.

C'est pourquoi, en doses homéopathiques, j'ai fini par apprécier le sous-ensemble d'UML qui me permet juste de mettre quelques idées à plat. En plus, je trouve ça généralement joli.

Voilà donc ma hiérarchie de classes pour la gestion des collisions!



La partie en bas à droite (en dessous de BasicShape) est implémentée et testée. La partie CompoundShape me permettra d'effectuer des collisions entre des solides plus complexes unions de solides simples, comme par exemple un château fort et ses tours fait à partir d'un pavé et de 4 cylindres. La collision des objets complexes sera un bête calcul bourrin de recherche de collisions entre les solides simples.

Enfin, la classe mère Shape fournira une interface renvoyant la boite englobante alignée sur les axes, qui sera la clé de voûte de mon octree (d'ailleurs, il n'y a pas l'air d'avoir de traduction d'octree, même Wikipedia l'utilise... Que pensez-vous d'octarbre?).