Il y a pas mal de temps, j’etait un membre actif de DOLServer qui est un emulateur de serveur DAOC entièrement ecris en C#.
Dans un soft server on a souvent a faire attention au performance. Il faut dire que l’on est parti avec un server qui pouvait acceuillir 30 personnes et qui prennais 100% du CPU et 900 Mo de ram et que l’on a fini à une utilisation normal du CPU et de la memoire (je n’ai pu les chiffres en tête) et surtout du coup la capacité d’avoir sur une machine classique jusqu’a 300 personnes sans problème. On a aussi améliorer le temps de lancement en passant de 6 minutes a 30 secondes…
Tout cela, n’est pas un miracle… cela vient surtout d’optimisation de plusieurs modules clés. En l’ocurance l’access à la Database qui est souvent ce qui ralentit le plus. La gestion des packets de données recu et émis. Ces 2 systemes on été grandement améliorés par l’utilisation de cache et le banissement de relation au niveau des requetes qui nous faisait faire n+1 select. Problème souvent rencontré dans hibernate. Je ne m’etends pas la dessus cependant on fait souvent cela sans s’en rendre compte et pas que dans hibernate.
Je sais que meme en construisant une requete, on est souvent appelé a prendre tout ce qui n’est pas déjà dans une autre table et on fait un “not in” et la les performance chute. En effet, en fait le “not in”/”in” dans une requete fait qu’il va relancer la requete pour chaque passage. Je suis passer de 30 a 0.75 secondes sur une seul requete comme ca.
select * from ma_table
where id not in (select id from ma_table_d_archive)
devient
select * from ma_table t,(select id from ma_table minus select id from ma_table_d_archive) a
where t.id = a.id
ou encore avec le “not exists”/”exists”
select * from ma_table t
where NOT EXISTS (select ‘1′ from ma_table_d_archive a WHERE t.id = a.id)
ou par la création d’une table temporaire:
create table temp as (select id from ma_table minus select id from ma_table_d_archive).
Tout cela n’a pour but que d’eviter le recalcule de la 2eme requete a chaque passage dans la première.
Une autre astuce: est de créé des index pour améliorer la recherche et les forcer a l’utilisation si le SGBD prends le mal ( voir le plan d’execution)
Une autre astuce (bis): Si vous faite beaucoup d’insertion dans une DB, on supprime les index et on les recré après.
On aussi fait un thread spécialement dédié à la sauvegarde qui tourne en boucle et sauve toute les 10 minutes. Cela évite de sauver toutes les 5 secondes parcequ’un joueur change de position. Bref, pensez à quel champs/table doivent etre en base en continue car critique et quel champs peuvent perdre 10 minutes de temps en cas de crash.
Après bien sûr pour le code il n’y a pas de règle sauf une testé, testé et encore testé!! Et oui il faut testé et c’est bien souvent comme ca que l’on voit ce qui est lent dans le code. Comme j’ai déjà fait le travail dessus. Les delegates sont super lent en .NET 1.1 (beaucoup plus rapide en .NET 2.0) et les locks peuvent conduire a des grosses perte de temps car cela fait dormir un thread en attendant qu’un autre est fini.
Pour le reste des modules, nous avons le WorlManager qui s’occupe de retrouver une personne ou un objet dans le monde et très souvent on veux tout ce qui se trouve dans une aire circulaire autour du joueur qui est plus ou moins grande (quand il parle, pour mettre a jour les items, quand il change de vetement,…). Ce module était clé car il est appelé souvent et il est surtout très lent. Je ne vais pas vous faire tout l’historique cependant voici ce qu’on avait a l’origine:
un systeme qui testait 1 par 1 tous les objets et qui calculait la distance entre notre joueur et les objets de la carte.
Nous avons commencer par séparer les objet du monde par type ( item, joueur, porte, …)
Puis nous avons fait uniquement les test dans la zone du joueur (et les zones adjacentes) .
Puis nous avons fait un systeme de sous zone ou on testait les zone non vide. Ce qui bien plus rapide car on ne test que les 2 coins de la zone. Donc, dés qu’il y a plus de 2 joueurs dans la zone c’est top.
Ce systeme fonctionne en fait par dicotomie.
Nous avons aussi redeveloppé notre propre system de hashtable qui fonctionnait aussi par dicotomie. Un entier servant de flag pour les 32 prochaines places. Je m’explique, nous avions en plus de notre collection d’objet une collection de int. Et chaque bit du int servais a indiquer si la place correspondante etait vite ou non. Ce qui permet de trouver vite les place libre avant de faire grossir sa collection pour rien. Ici on aurait pu utilise 2 liste chainé ( une pour le plein et l’autre pour le vide).
En fait tout cela rejoint une notion très importante que je cachais sous l’utilisation de dicotomie et qui est la complexité.
La complexité qu’est ce que c’est et bien c’est une notion mathematique qui dit de combien d’evenement maximum vous aller faire pour faire ce que vous voulez.
Par exemple, vous rechercher un nombre dans une suite de nombre (1 a 10 par exemple). Quel est la meilleur facon d’avoir le resultat rapidement?
Au première abord on fait comme suit:
Est ce que c’est 1?
Est ce que c’est 2?
Est ce que c’est 3?
.
.
Est ce que c’est n?
On dit alors qu’il faut parcourir n fois au maximum la list pour trouver notre nombre. Donc c’est une complexité d’ordre n (grand Tau de n mais bon on fait l’abus de language…)
Autre methode maintenant je pose un autre type de question:
Est ce que c’est supérieur a n/2 ?
Est ce que c’est supérieur n/4 (respectivement 3n/4) ?
.
.
On voit bien vite que notre problème sera résolue plus rapidement avec 10 la première fois 10 iteration avec la 2eme methode (en 3 ou 4 fois c’est plié). Ici on dit que la complexité est de type log (n).
D’ailleur en therme probabiliste,pour 10, l’esperance de gain est de 11/2 (=Sum(1,10,1/10)) pour la premiere methode et de 17/5 (=3 x 6/10 + 4 x 4/10) pour la 2eme. Or 17/5 >11/2. Donc déjà pour 10 on va netement plus vite…
Sans s’en rendre compte on vient en fait de testé les arraylists toute betes et les arbre AVL. Personnelement, j’ai utilisé des splay tree qui sont presque la meme chose que les arbres AVL et c’est vrais que le gain de performance a la recherche est impressionnant.
Pour résumer voila les diferrentes complexités:
| Notation |
Type de complexité |
Exemple |
| O(1) |
complexité constante (indépendante de la taille de la donnée) |
une liste a 1 seul element |
| O(log(n)) |
complexité logarithmique |
arbre avl, splay tree, arbre binaire en e generale… |
| O(n) |
complexité linéaire |
itération sur une liste simple d’objet (arraylist, array d’objet ),… |
| O(nlog(n)) |
complexité quasi-linéaire |
- |
| O(n2) |
complexité quadratique |
tout ce qui est trie (sortlist ou list.sort par exemple),produit cartésien de 2 table en BDD,… |
| O(n3) |
complexité cubique |
- |
| O(np) |
complexité polynomiale |
- |
| O(nlog(n)) |
complexité quasi-polynomiale |
- |
| O(2n) |
complexité exponentielle |
- |
| O(n!) |
complexité factorielle |
- |
remarque: l’hashtable n’est pas de rang n je pense car elle utilise une table de hashage pour retrouver plsu vite ses element et je ne sais pas si il n’y a pas quelquechose genre splay tree pour la table de hashage…
On notera que la complexité est vallable pour les listes avec beaucoup d’element car on néglige des thermes qui quand on a peu d’element devienne plus trop négligeable.
- Retravailler vos requetes et specialement les jointures (2 selectAll que l’on raccroche coté code valent mieux qu’un produit cartésien n*m selects)
- jamais de in/no in dans une requete en base
- créé des index
- quand on ajoute beaucoup d’élements, on supprime les index pour les recréé après.
- penser par dicotomie et spécialement a toujours avoir une compléxité en log (n) sur les modules clés
- testé la rapidité de vos codes
- utilisé des listes appropriés (listDictionnary pour les petites listes et hashtable pour les grosses par exemple en C#)
- testé
- et encore testé
