Optimisation

Optimisation

> Tutoriel LeekScript

Ici on va parler d'optimisation, l'objectif de l'optimisation est d'améliorer les performances d'un algorithme. En général quand on parle d'optimisation, on parle de temps d’exécution, le but étant de réduire le temps nécessaire pour l’exécution d'une série d'instruction.

En LeekScript, ce temps d'exécution est estimé par un nombre : le nombre d'opérations utilisées par ce calcul. On va donc parler de certaines bonnes pratiques et bons réflexes pour optimiser un programme, quel que soit le langage, ainsi que certaines optimisations plus spécifiques au LeekScript, et intimement liées à la façon dont sont comptées les opérations.

Si ce n'est pas déjà fait, je vous invite à relire l'article du Tutoriel LeekScript : Opérations.

Les bons réflexes

Par exemple, une économie de 500 opérations sur une fonction appelée une seule fois n'économisera que 500 opérations. (logique) En revanche, une économie d'une seule opération, sur une fonction qui est appelée dans une boucle de boucle de boucle peut réduire le coût en opérations de plusieurs dizaines de milliers d'opérations.

Ce qui m'amène au deuxième point :

La moitié du travail d'optimisation d'un code consiste simplement à chercher où partent les opérations (ensuite faut crier fort et leur dire de revenir). Qu'est ce qui coûte cher dans le code ?

Pour ça, pas de secret, on va mesurer !

Dans notre arsenal, le LeekScript fournit une fonction qui va se révéler très utile : getOperations. Cette fonction permet de connaître le nombre d'opérations dépensées jusqu'à maintenant dans le code.

Exemple d'outil simple permettant de mesurer le coût d'une fonction :

global __debug_operation; function startOp(){ __debug_operation = getOperations(); } function stopOp(title){ var ops = getOperations()-__debug_operation - 3; debug("Operations (" + title + ") : " + ops); }

startOp(); stopOp("test à vide"); // test à vide: 0

startOp(); say("hello world"); stopOp("hello world"); // hello world: 30

On peut ainsi confirmer que say coute bien 30 opérations, comme annoncé par la documentation.

Il est possible, et je vous recommande fortement de faire des outils permettant de mesurer d'autres choses dans votre IA, comme le nombre d'appels à une fonction, ainsi que son coût moyen par exemple, ce qui permettra de mieux mesurer l'évolution des coûts dans votre IA, et l'impact de certaines optimisations.

La page Complexité vous aidera à comprendre pourquoi un algorithme coûte cher et comment résoudre le problème. Pour résumer très simplement, on préferera éviter d'imbriquer des boucles entre elles dans la mesure du possible. On cherchera également à limiter la taille de nos boucles, par exemple en ne parcourant que nos cellules accessibles au lieu de parcourir toutes les cellules de la carte. Il est important de noter qu'un algorithme qui a une complexité plus faible utilisera beaucoup moins d'opérations pour un nombre d'éléments à traiter assez grand, pensez-y avant d'essayer de gratter de petites optimisations !

Retirer des boucles ce qui ne va pas changer

Imaginons le code suivant :

var TP = getTP();

// tirer autant de fois que possible sur l'ennemi ! for (var i = 0; i Si nous reprenons l'exemple précédent, cela implique de d'abord vérifier la valeur contenue dans notre tableau avant de l'utiliser:

global WEAPON_MAX_RANGE = [];

var pistolMaxRange;

var weaponMaxRange = WEAPON_MAX_RANGE[WEAPON_PISTOL]; if (weaponMaxRange !== null) { pistolMaxRange = weaponMaxRange; } else { var newMaxRange = getWeaponMaxRange(WEAPON_PISTOL); WEAPON_MAX_RANGE[WEAPON_PISTOL] = newMaxRange; pistolMaxRange = newMaxRange; }

Cela implique un peu plus de d'opérations que de la simple mise en cache lors de la récupération de résultats déjà connu. Mais on évite ainsi de tout calculer en avance, et éventuellement de calculer certaines choses qui ne nous serviront jamais. Cependant, cela reste très lourd à utiliser en terme de code. Heureusement, nous pouvons automatiser ce genre de chose. Il nous suffit de créer une fonction qui prend en argument la fonction à mémoïser, le cache dans lequel mettre les résultats obtenus, et l'argument à passer à la fonction à mémoïser dans le cas où le résultat ne serait pas déjà présent en cache:

function applyMemo(f, mem, x) { var ret = mem[x]; if (ret !== null) { return ret; } else { ret = f(x); mem[x] = ret; return ret; } }

Dans le cas de getWeaponMaxRange(WEAPON_PISTOL), nous avons simplement à utiliser applyMemo de la sorte:

global WEAPON_MAX_RANGE = [];

var pistolMaxRange = applyMemo(getWeaponMaxRange, WEAPON_MAX_RANGE, WEAPON_PISTOL);

Il est possible de rendre cela encore plus simple d'utilisation, en définissant une fonction memoize qui prend en argument une fonction à mémoïser, et qui nous retourne une fonction mémoïsée. (Attention, plus nous rendons facile l'utilisation, plus nous consommons d'opérations. Il est toujours une bonne idée d’estimer quel méthode est préférable selon les besoins de performance et de facilité d'utilisation.)

function memoize(f) { var mem = [];

return function(x) { return applyMemo(f, mem, x); }; }

Dans le cas de getWeaponMaxRange(WEAPON_PISTOL), nous avons simplement à utiliser memoize de la sorte:

global mWeaponMaxRange = memoize(getWeaponMaxRange);

var pistolMaxRange = mWeaponMaxRange(WEAPON_PISTOL);

Il est à noter que les implémentations fournies ici ne sont pas les plus optimisées qui puissent être. Au boulot.

> Note : pour une notation plus concise, on peut utiliser le fait que l'assignation renvoie la valeur assignée :

Se lancer dans le HASH

Très pratique la mémoisation n'est ce pas ? Mais comment utiliser cette méthode pour stocker le résultat d'une fonction qui prend plus de paramètres ?

Le principe d'un hash est d'encoder une information sur une plus petite dimension. D'après wikipedia une fonction de hashage est une fonction particulière qui, à partir d'une donnée fournie en entrée, calcule une empreinte numérique servant à identifier rapidement la donnée initiale

Imaginons qu'on veuille stocker le résultat de la fonction lineOfSight, qui prend 2 paramètres (la cellule de départ et la cellule d'arrivée), on peut simplement faire : Petit rappel : Une cellule peut prendre une valeur de 0 a 612.

Et voila, pas bien compliqué ! Le hash obtenu est un seul nombre qui contient les informations des deux cellules ! Pour cell1 = 13 et cell2 = 310, notre hash vaudra donc 13310; Ici, la multiplication coûte 5 opérations, avec le if qui coûte 1 opération et les accès a 2 opérations, ça nous fait au minimum 11 opérations, sur les 30 que coute lineOfSight.

Mais on peut mieux faire !

Utiliser des opérateurs binaires

Oups j'en vois qui font les gros yeux. Rien de compliqué j'le jure ! Le LeekScript utilise des nombres codés sur 32 bits, c'est-à-dire qu'un nombre est stocké avec 32 0 ou 1. Le but de cette méthode est d'utiliser un peu de cet espace pour mettre nos données. Un exemple vaut 1000 mots, revenons sur la fonction lineOfSight : On va commencer par chercher la puissance de 2 plus élevée que le nombre maximum qu'on cherche a stocker :

2^ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ... | 31 ---|---|---|---|---|---|---|---|---|---|---|----|----|-----|--- Résultat |1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | | 2147483648

Pour notre cellule qui a un maximum de 612, on va donc prendre 1024, c'est a dire 10 bits (2^10 = 1024).

Maintenant il nous suffit d'utiliser des opérateurs de décalage pour stocker tout ça. Il va vous falloir connaître l'utilisation d'au moins deux d'entre eux : | et << (Un p'tit tour sur l'utilisation des opérateurs binaires pour se rafraîchir la mémoire). On part sur une variable vide, égale a 0 par défaut :

var hash = cell1 << 10; //On ajoute la cell1 décalée de 10 bits hash = hash | cell2; //On ajoute la cell2 au début

Si on simplifie ce code, ça nous donne var hash = cell1 << 10 | cell2;, ce qui ne consomme que 3 opérations ! Pour cell1 = 13 et cell2 = 310, notre hash vaudra 13622. Notre variable hash contient donc un nombre binaire, avec 10 bits réservés a cell1 et 10 bits pour cell2.

Notre fonction finale ne consomme plus que 7 opérations, une petite amélioration, non négligeable cependant.

La vrai force des hash binaire se révèle quand on veut stocker plus d'informations dedans :

Mémoïser les cases accessibles

De quelles informations aurait on besoin pour mémoïser les cases accessibles ? La position de départ, les points de mouvement (MP) disponibles et disons l'id du poireau (pourquoi pas !)

Pour commencer il faut définir combien de bits chaque élément pourra utiliser :

Et bien il suffit de prendre un nombre suffisamment grand pour ne pas le dépasser ! Au hasard, quelque chose comme 20 MP. Il nous faudra donc 5 bits.

Quoi que quoi ?? Ils n'ont rien a voir avec le nombre de bits qu'on vient de décider là, si ? Et bien si c'est très simple :

Attention à bien vérifier que le nombre total de bits que vous utilisez ne dépasse pas les 64, sinon ils partiront dans le néant ! Ici on a 10 + 6 + 5 = 21 bits, on est large !

Pour ne pas se tromper, on peut utiliser une feuille de papier et noter notre méthode :

Donnée | cell | id | mp | -------|------|----|----| Taille (bits) | 10 | 6 | 5 Décalage | 6 + 5 = 11 | 5 + 0 = 5 | 0

Essayez maintenant de stocker 2 cellules et une arme/puce ! Si vous y arrivez, vous maitrisez maintenant l'art du hash binaire.

Faire de la bouillie

Comment gérer le cas où la taille de nos données à stocker dépasse les 64 bits ? Quand on a par exemple a un tableau de cellules, on ne pourra pas hasher tout ça avec notre intelligence binaire.

Heureusement un programmeur n'est jamais a court d'options : On va faire de la bouillie. L'avantage de notre méthode binaire est qu'on peut récupérer les informations stockées si le besoin s'en fait sentir. Ici, on va abandonner tout espoir de récupération.

Pour un tableau, on peut utiliser une formule magique :

Le principe est simplement de modifier le hash en le multipliant par un nombre assez grand par rapport à element. Attention, cette fonction fonctionne (hum) mais l'unicité de son résultat est loin d'être garanti, il faut croire en notre bonne chance pour être sur que le résultat en sortie sera toujours différent si l'entrée est différente. (Elle ne m'a jamais fait défaut)

A garder en tête quand on utilise cette fonction:

Sacrifier la lisibilité

Parfois, il faut sacrifier la lisibilité du code pour améliorer ses performances. Cette section est réservée aux méthodes bien crasseuses pour les gratteurs d'opérations, à vos risques et périls ! Il est recommandé de n'utiliser ces méthodes que dans des fonctions bas niveau qui sont appelées très souvent.

remplacer floor

Le fonction floor renvoie l'arrondi bas d'un nombre. Par exemple floor(0.9) = 0, floor(199.724) = 199, ... Il se trouve que les opérateurs binaires convertissent les nombres en entier pour seulement une opération ! En utilisant nombre | 0, on transforme donc nombre en entier (arrondi bas par défaut), ce qui nous donne le même comportement que floor !

Ca ne coute qu'une opération, une opération de gagnée !

Faire une moyenne entière

La moyenne de deux valeurs peut être calculée par

Pour un total de 6 opérations. Make it 2 avec la syntaxe suivante:

On utilise l'opérateur binaire de décalage pour faire la division par deux. Attention ! Le résultat sera équivalent a floor((value1 + value2) / 2) a cause de la conversion implicite. (Merci a Kavaliov)

Gratter les comparaisons

Les opérateurs == et != coûtent 1 opération chacun, c'est une opération de trop !

On va exploiter ici les conversions en arrière plan, comme pour la simplification du if. Il se trouve que if(null) et if(0) donnent tout deux false, c'est-à-dire que la condition suivant ce if ne s'exécutera pas. Si on est sûr que notre table ne contiendra pas de 0, de null ou de booléens, on peut simplement ne pas mettre le ==.