L’Optimisation de vos programmes
Première partie : la théorie
Sans trop rentrer dans les détails, car c’est un sujet très complexe et sans fin, je vais vous donner ici quelques pistes et conseils pour optimiser vos programmes ou scripts.
Et désolé pour l’absence d’illustrations : ni exemples, ni belles images. Juste du texte !
Cependant, si vous avez des idées de codes relativement simples à optimiser pour illustrer ce tuto, vous pouvez me les envoyer par mp pour que je regarde.
Optimisations ? Quelles optimisations ?
Il existe de nombreux aspects qui peuvent être optimisés. Les plus courants sont :
- Le temps d’exécution (s’arranger pour que le programme arrive plus vite au résultat escompté). C’est le sujet que je détaillerai le plus dans ce tuto.
- La mémoire utilisée (diminuer la quantité de mémoire occupée par le programme). Souvent ce n’est pas le point le plus critique dans un bot, aussi on passera à côté de cet aspect. Cependant, il faut savoir que l'utilisation de structures de données optimisées à un impact aussi bien sur la mémoire que sur le temps d'exécution.
- Optimiser la complexité du code (simplifier le programme). C’est souvent une étape nécessaire pour toutes les autres optimisations : un code inutilement complexe est difficilement maintenable, peu performant, gourmand en mémoire…
- Optimiser la maintenabilité (améliorer la lisibilité et la structuration du code pour que votre programme puisse évoluer dans de bonnes conditions sur des longues périodes, et pouvoir être maintenu par plusieurs personnes).
- Optimiser le temps de codage : il s’agit d’atteindre l’objectif fonctionnel du programme (bref, obtenir un programme qui fait ce que l’on veut qu’il fasse) en le moins de temps possible. Cela passe par l’utilisation d’une méthodologie appropriée en fonction du projet pour sa conception et son codage. Cela dépasse nettement le cadre d’un tuto ici, aussi je ne m’étends pas sur le sujet.
- …
Optimisations, est-ce bien utile ?
Pas forcément, et c’est un point important à étudier avant de vouloir optimiser votre programme. Quel est le besoin ? Pourquoi je veux l’optimiser ? Quel objectif je me fixe ?
Ainsi, souvent un programme va réagir à des « stimuli » externes (action de l’utilisateur, arrivée d’un paquet réseau, changement de la couleur d’un pixel…). Donc la question est : combien de temps je mets pour répondre à ce « stimulus » ? Et la question qui vient tout de suite après, c’est : combien de temps faudrait-il que je mette.
La réponse à ces deux questions permettra de déterminer les besoins en optimisation.
Etat des lieux : le Benchmarking
Afin de déterminer précisément la réponse à la première question, vous pouvez adapter votre code pour mesurer et afficher les temps.
Par exemple, avec Autoit, vous pouvez utiliser pour cela les instructions :
_Timer_Init et _Timer_Diff.
Et si vous constatez qu’il faut optimiser votre programme en vitesse, vous devez alors identifier les points noirs de votre code. Avec de l’expérience, une relecture vigilante vous permettra le plus souvent de trouver les parties les plus lentes qui peuvent être optimisées. A défaut, ou pour les programmes complexes, il faut pousser le benchmarking plus loin et découper votre code en tronçons, en mesurant le temps d’exécution de chaque partie, en détaillant de plus en plus les parties les plus lentes. Ainsi vous finissez par identifier la ou les portions de code sur lesquelles doit porter l’optimisation.
Quelques techniques d’optimisation
Une fois que vous savez précisément les points à améliorer et avec en vue le résultat à obtenir, alors il faut trouver les bonnes solutions. Je vais lister ici les principales pistes, toutes n’étant pas forcément applicables dans votre cas.
- Améliorer la complexité de l’algorithme.
C’est plus particulièrement vrai quand il y a des boucles ou des appels récursifs. Réfléchissez à d’autres approches pour atteindre le même résultat, ou un autre résultat acceptable. Par exemple, pouvez-vous éviter une boucle, ou réduire le nombre d’itérations.
La détermination de la complexité d’un algorithme consiste à regarder comment évolue le nombre d’opérations en fonction de la taille du problème. Ainsi, un algorithme en « O(n) » est dit linéaire ou quasi-linéaire : le nombre d’opérations doublera si la taille du problème à traiter double. Si vous avez deux boucles imbriquées, vous pourriez avoir un algorithme avec une complexité en O(n²). Ce qui signifie que le nombre d’instructions va être multiplié par 4 quand le problème double de taille. Ainsi, les meilleurs algorithmes de tri (type quick-sort) ont une complexité en O(n log n).
Donc si vous avez des traitements fortement itératifs, cherchez en premier un moyen de réduire la complexité de votre algorithme.
- Réduisez la taille du problème
Si vous ne pouvez jouer sur la complexité de l’algorithme, peut-être pouvez-vous limiter le nombre d’itérations pour vos boules. Ainsi, par exemple, pour recherche un pixel d’une couleur donnée, déterminez déjà la zone utile de la fenêtre où ce pixel est susceptible d’apparaitre, et limitez la recherche à cette zone.
- Simplifiez les boucles
Quand vous avez un code qui est appelé très souvent (cas d’une boucle par exemple), sortez de la boucle tout ce que vous pouvez. Initialisez vos variables avant d’entrer dans la boule quand c’est possible et évitez dans la boucle tous les traitements qui pourraient n‘être faits qu’une seule fois.
- Trouvez des instructions plus performantes
Si vous utilisez certaines instructions que vous soupçonnez d’être lentes, cherchez-en d’autres plus performantes. Cela peut parfois nécessiter une remise en cause de la façon de faire. Ainsi par exemple, si vous devez lire un fichier (données de configuration par exemple) à chaque passage dans une boucle, voyez si vous ne pouvez pas plutôt mettre les données en mémoire (accès bien plus rapide). Ou encore, si vous devez effectuer des recherches dans des quantités importantes de données, envisagez l’utilisation d’une base de données.
- Traitez les données les plus simples possible
Certaines données sont bien plus rapides à traiter que d’autres. Ainsi, utilisez de préférence des nombres entier pour tous vos traitements, et évitez le plus possible les chaînes de caractères, toujours bien plus fastidieuses à traiter pour le processeur.
- Utilisez les bons outils
En dernier recours, peut-être que vos outils de développement ne sont pas appropriés pour la tâche que vous réalisez. Ainsi Autoit est bien pour les tâches simples, mais si vous avez besoin de performance, il faut envisager d'aller voir ailleurs (cf https://cadernis.com/d/3041)
Seconde partie : cas pratiques
Si vous avez des questions ou suggestions, je suis preneur.
Cas N°1
Allez, un petit cas pratique d'optimisation du code (en C):
Cet exemple est tiré du topic suivant:
Contexte :
Il s'agit de décoder l'identifiant du message, à partir les données du paquet que l'on reçoit (Nécessaire dans un Bot socket).
L'identifiant correspond aux 14 bits de poids fort des deux premiers octets du buffer.
L'idée première était donc de faire une transcription binaire des deux premiers caractères dans une chaine de caractères, puis reconvertir dans l'autre sens en ne concervant que les 14 premiers caractères.
L'implémentation intialement proposée (qui ne marche pas d'ailleurs, mais c'est un détail):
Cliquez pour révéler
Cliquez pour masquer
char* binaire(int n, char* buffer)
{
char* buf = buffer; int rem;
do
{
rem = n%2; n /= 2; if (rem>9) rem+=7;
*buf = 48+(char)rem; buf++;
} while (n>0);
*buf='\0';
strrev(buffer);
return buffer;
}
char *strrev(char *orgString)
{
char *start, *end;
char temp;
start = orgString;
end = orgString + strlen(orgString)-1;
while((start-end)/2 >= 0)
{
temp = *start;
*start++ = *end;
*end-- = temp;
}
return orgString;
}
int getpacketid(char*buffer)
{
char buf[20];
char*id;
sprintf(buf,"%02x%02x",(int)buffer[0],(int)buffer[1]);
id=binaire(atoi(buf),id);
int len=strlen(id);
char ret[20];
sprintf(ret,"%c%c",id[len-2],id[len-1]);
return atoi(ret);
}
On peut constater que le code est :
- illisible, car compliqué et sans commentaires.
- long, très long, trop long.
- conséquence logique sur la fiabilité : code buggé et difficilement maintenable.
- au niveau performance, c'est une catastophe : entre les allocations mémoire, les traitements sur les chaînes... on doit atteindre plusieurs centaines de micro-secondes de temps d'execution.
- au niveau de la mémoire, ce n'est pas mieux. Aussi bien au niveau de la taille du code que des données manipulées, on perd ici pas loin d'un kilo-octet.
Démarche
Pour traiter un tel cas, il faut reprendre le problème à la source et simplifier l'algorithme. Notamment, éviter d'utiliser des chaines (le binaire dans une chaîne, c'est bon pour un humain, mais certainement pas pour un ordinateur).
Fondamentalement, ce que l'on veut c'est :
Trouver la valeur entière correspondant aux deux premiers octets du buffer
Retirer les deux bits de poids faible du résultat.
1er jet
Ce qui peut donner le code suivant :
Cliquez pour révéler
Cliquez pour masquer
// Détermine l'identifiant du premier message contenu dans le paquet dont les données brutes sont passées en paramètre
int getpacketid(char*buffer)
{
int FirstByte = (int)(buffer[0]); // Conversion du premier octet du buffer en valeur entière
int SecondByte = (int)(buffer[1]); // Conversion du second octet du buffer en valeur entière
int Value16Bits = FirstByte * 256 + SecondByte; // Calcul de la valeur sur 16 bits correspondant au deux premiers octets
int Result = Value16Bits / 4; // En divisant par 4, on retire les 2 bits de poids faible
return Result;
}
On constate que ce code est bien plus compact, lisible et commenté.
Il est aussi beaucoup plus performant (à peine plus d'une dizaine de nano-secondes) et la consommation mémoire raisonnable (quelques dizaines d'octets).
Peut-on faire mieux ?
Si vous vous arrétiez là, ce serait déjà très bien, vous avez un code simple, propre, robuste et efficace. Mais dans certains cas (ce n'est pas réellement le cas ici d'ailleurs ^ ^), ou pourrait avoir besoin d'otpimiser encore bien plus le code, si par exemple il est appelé tellement souvent qu'il génère un ralentissement perceptible de l'application.
Donc certainement, on peut faire mieux ! En se mettant à la place du CPU, pour voir comment trouver les instructions les plus appropriées en fonction des données disponibles et du résultat attendu. Cela demande aussi, à ce niveau, de bien maîtriser toutes les subtilités du langage utilisé et idéalement le langage assembleur (les instructions qui seront au final executées par le processeur). A noter qu'il ne servirait à rien d'écrire du code en assembleur (c'est inutile dans la majorité des cas : si vous comprenez comment travaille le compilateur, et optimisez votre code C en conséquence, le code assembleur généré sera aussi rapide - voire plus en raison des optimisations de plus en plus poussées des compilateurs modernes - qu'en tentant d'écrire directement en assembleur).
Démarche pour pousser l'optimisation à l'extrême
Tout d'abord, représentons-nous bien la structure des données transmises en paramètre de cette fonction :
on reçoit un pointeur (donc l'adresse d'une zone mémoire) qui contient les données utiles. Comme ce pointeur est déclaré comme "char *", il désigne à priori une zone mémoire contenant des caractères, ce qui revient à un tableau d'octets (le "char" en C étant codé sur un seul octet).
On peut représenter les 16 bits en question ainsi :
B1 B2 B3 B4 B5 B6 B7 B8 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 D4 D5 D6 D7 D8 ...
B1 à B8 correspondent aux 8 bits du premier octet. C1 à C8 au second octet. D1 à D8 à l'octet suivant... et ainsi de suite jusqu'à la fin du buffer.
Ce que l'on veut au final, c'est un entier sur 32 bits contenant les 14 bits de poids fort, soit (vu que un "int" en C est codé maintenant sur 32 bits pour quasiment tous les compilateurs 32 ou 64 bits) :
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 B1 B2 B3 B4 B5 B6 B7 B8 C1 C2 C3 C4 C5 C6
Aussi, plutôt que de traiter les données du buffer octet par octet, ce serait plus efficace et plus simple de considérer les données 16 bits par 16 bits. En C, un entier non signé sur 16 bits s'appelle "WORD".
Donc il suffit de dire au compilateur que, momentanément, il doit considérer la zone mémoire désignée par le pointeur comme un ensemble de "WORD" et non un ensemble de "char". Ce qui, en C, s'appele un "cast" et s'écrit ainsi :
(WORD *)buffer
Cela signifie : tu dois oublier la définition initiale de buffer, on considérer que c'est ici un pointeur sur un (ou des) WORD
Après, si on veut non plus avoir l'adresse mais la valeur (sur 16 bits donc) stockée à cette adresse, on utilise simplement l'opérateur *. Ce qui pourrait donner :
WORD * New16BitsPointeur = (WORD *)buffer;
WORD My16BitsValue = *New16BitsPointeur;
Mais on peut se passer de ces variables inutiles, et cette valeur sur 16 bits peut être plus simplement donnée par :
*(WORD*)buffer
Ensuite, on veut retirer les 2 bits de poids faible de tout ça, alors pour cela on évite la division (opération lourde, pas explicite et risquée, le résultat ne sera pas toujours ce que vous attendez, notamment avec des nombres négatifs). On lui préfèrera une instruction bas niveau qui fait exactement ce que l'on veut : décaler les bits vers la droite. C'est une instruction très rapide (1 cycle CPU) et "propre".
En C (ou C++, C# et autres dérivés), l'opération se note ">>".
Cela nous donne donc:
(*(WORD*)buffer)>>2
Il se trouve qu'en C, dans le cas présent les parenthèses sont inutiles (>> à la priorité la plus basse dans cetet expression), aussi ce code convient aussi bien :
*(WORD*)buffer>>2
Donc à ce niveau, on à un "WORD" contenant la valeur que l'on veut. Mais notre fonction doit retourner un "int". Comme un WORD (entier non signé sur 16 bits) peut se convertir en int (entier signé sur 32 bits) sans ambiguité ni pertes possibles, aussi la conversion du WORD en int se fera automatiquement sans même un "warning" à la compilation.
Donc notre fonction devient :
int getpacketid(char*buffer)
{
return *(WORD *)buffer>>2;
}
C'est déjà beaucoup mieux, non ?
La touche finale
Et pourtant, on peut encore faire bien plus rapide. En effet, avec le code au-dessus, on conserve l'appel à une fonction. Au niveau des instructions executées en assembleur, cet appel d'une fonction n'est pas anodin : les paramètres et adresse de retour doivent être stockés en mémoire (la pile), puis un saut effectué pour commencer l'execution de la fonction, qui va commencer par récupérer la valeur des paramètres (dans la pile), faire les traitements, mettre le résultat dans la pile et enfin retrouver l'adresse du code appelant pour revenir au code de départ, qui va à son tour récupérer la valeur renvoyée dans la fonction depuis la pile... bref, beaucoup de travail pour au final plus grand chose à faire dans cette fonction.
Pourtant, c'est plus sympa et lisible pour le développeur de conserver une fonction bien délimitée dans son code, qu'il appelle quand c'est utile.
La solution dans ce cas, c'est l'instruction "_inline" à rajouter au début de la déclaration de la fonction. Cela indique au compilateur qu'il doit remplacer tout simplement chaque appel à cette fonction par le code correspondant. C'est comme si on remplaçait par exemple directement dans le code :
int MonIdTantAttendu = getpacketid(LesDonnesDeMonPaquet);
par
int MonIdTantAttendu = *(WORD *)LesDonnesDeMonPaquet>>2;
C'est particulièrement utile dans le cas de fonction très courte et optimisées, qui sont appelées souvent.
C'est d'ailleurs une optimisation qui peut parfois être réalisée automatiquement par certains compilateurs (selon les options de compilation), de considérer comme "_inline" certaines fonctions répondant aux bons critères.
Et voilà ainsi ce que devient la même fonction qu'au début, une fois débuggée, optimisée et commentée...
// Détermine l'identifiant du premier message contenu dans le paquet dont les données brutes sont passées en paramètre
_inline int getpacketid(char*buffer)
{
// On extrait les 14 bits de poids fort des deux premiers octets du buffer,
// en décalant deux fois à droite les 16 premiers bits.
return *(WORD *)buffer>>2;
}
Bilan
Au niveau mémoire, on gagne environ un facteur 100.
Au niveau temps d'execution, on tourne maintenant autour d'une nano-seconde, on est donc quelques centaines de milliers de fois plus rapide que dans le code initial.
Pour la lisibilité, je vous laisse juge en comparant avec le code initial. On fait uniquement les traitements nécessaires, et on explique ce que l'on fait.
D'autres cas ?