techniques optimisations ? - Page 1

Salut à tous,

Edit : les réponses déjà apportées sont en gras.

J'ai plusieurs questions en vrac (et en C) à vous soumettre, surtout concernant l'optimisation d'un programme.
Nos chères petites TI ne sont pas des bêtes de courses, nous le savons bien. Il faut donc veiller à optimiser le code au maximum pour les progs/jeux exigeants.
1) Existe-t-il à qq part un document/site qui propose les techniques d'optimisation du code les plus courantes ? Les pièges à éviter qui font perdre du temps à l'execution d'un programme ? [Liens fournis dans ce post]
2) Manipuler un double est-il plus lent que manipuler un entier ? [Oui] Si oui, y'a-t-il moyen d'optimiser le code en ne travaillant par exemple qu'avec des entier et en effectuant une division par 10 (pour une précision de 1 décimale) au moment de l'exploitation de cette variable ? Ou une autre technique ?[Utilisation des nombres en virgule fixe]
3) Un modulo est-il une opération qui prend du temps ? Peut-elle être optimisée ?
[Oui si x mod n avec n multiple de 2. Optimisation implicite par GCC]
4) La longueur d'un bloc de code influe-elle sur la vitesse du programme à squizzer ce code (ex : un bloc if qui contiendrait 1000 lignes mais dont le test d'entrée ne serait pas vérifié, serait-il plus long à sauter qu'un même bloc qui ne contiendrait qu'une seule ligne de code ?) [Non]
5) caster un double en int est-il lent (ex : int i = (int) d; ) ? peut-on optimiser ceci ? [Lent]

Voilà c'est à peu près tout pour le moment, il est possible que j'en trouve d'autres entre temps

Merci !

Martial Demolins (./2) :
Un modulo n avec n==x^2 (x entier évidemment) peut être très rapide en assembleur, mais je sais pas si gcc sait optimiser ça.

Bien sûr que si Ce serait grave sinon. Il suffit que l'opérande de gauche soit non signée.

je me permets de mettre à jour le post initial avec vos réponses au fur et à mesure.

djflex (./2) :
y'a-t-il moyen d'optimiser le code en ne travaillant par exemple qu'avec des entier et en effectuant une division par 10 (pour une précision de 1 décimale) au moment de l'exploitation de cette variable ? Ou une autre technique ?

Oui, mais pas par 10. Utilise plutot des puissances de deux, car les divisions se transforment en décalage. Cherche "virgule fixe" sur google, c'est utilisé très souvent.

djflex (./2) :
La longueur d'un bloc de code influe-elle sur la vitesse du programme à squizzer ce code (ex : un bloc if qui contiendrait 1000 lignes mais dont le test d'entrée ne serait pas vérifié, serait-il plus long à sauter qu'un même bloc qui ne contiendrait qu'une seule ligne de code ?)

Non. A un ou deux cycles d'horloge près, mais tu sentiras pas la différence.

djflex (./2) :
aster un double en int est-il lent (ex : int i = (int) d; ) ? peut-on optimiser ceci ?

A mon avis (je sais jamais, pour cette question) tu obtiendras pas ce que tu veux, mais le codage du nombre flottant sous forme d'un entier. A moins que ça marche? a confirmer.


sinon, pas bête, la liste des réponses dans le post 0

Utilise plutot des puissances de deux, car les divisions se transforment en décalage. Cherche "virgule fixe" sur google, c'est utilisé très souvent.

Je vais regarder.

A mon avis (je sais jamais, pour cette question) tu obtiendras pas ce que tu veux, mais le codage du nombre flottant sous forme d'un entier. A moins que ça marche? a confirmer.

J'ai toujours fait comme ça en tout cas pour tronquer un nombre à virgule en entier. Je n'ai pas vu de disfonctionnements pour l'instant.

sinon, pas bête, la liste des réponses dans le post 0

N'est ce pas ?

djflex (./1) :
1) Existe-t-il à qq part un document/site qui propose les techniques d'optimisation du code les plus courantes ? Les pièges à éviter qui font perdre du temps à l'execution d'un programme ?

Lionel avait écrit un petit document à ce sujet.
!call Lionel Debroux
--- Call : Lionel Debroux appelé(e) sur ce topic ...
Sinon, tu dois pouvoir trouver les trucs bateau d'optimisation sur Internet. Il faut s'y prendre de "haut en bas" pour optimiser, c'est-à-dire commencer par mesurer la complexité en temps et espace de ton algorithme, puis ensuite penser à optimiser l'implémentation.

5) caster un double en int est-il lent (ex : int i = (int) d; ) ? peut-on optimiser ceci ?

Comme toutes les opérations sur les nombres flottants, c'est sûrement un peu lourd.

djflex (./1) :
1) Existe-t-il à qq part un document/site qui propose les techniques d'optimisation du code les plus courantes ? Les pièges à éviter qui font perdre du temps à l'execution d'un programme ?

Il y en a pas mal. Le 68000 est un processeur très courant, employé sur les ordinateurs Amiga, Atari et Macintosh dans les années 80 et 90, donc tu peux trouver plein de choses intéressantes dans les documents de cette époque.
Par exemple : http://linux.cis.monroeccc.edu/~paulrsm/doc/trick68k.htm

Et pour le C(++) :
http://www.custard.org/~andrew/optimize.php
http://www.gamedev.net/reference/programming/features/performance/
etc.

Le premier ne me parle pas trop (j'y connais rien en asm).
Les deux suivants m'ont l'air pas mal du tout !

Disons quand même que de manière générale, le compilateur s'en sort bien pour optimiser ton code, et que de toute façon c'est parfois préférable de conserver un code un poil moins performant mais lisible.

Sur TI, à par les nombre flottants qui sont vraiment lents, je ne vois pas d'autre truc spécifique auquel tu devrais faire attention. Peut-être pourrais-tu préciser la nature de ton programme et les parties qu'il est nécessaire que tu optimises pour qu'on puisse te conseiller plus précisément.

Thibaut (./3) :

Martial Demolins (./2) :
Un modulo n avec n==x^2 (x entier évidemment) peut être très rapide en assembleur, mais je sais pas si gcc sait optimiser ça.

Bien sûr que si Ce serait grave sinon. Il suffit que l'opérande de gauche soit non signée.

Attention, cette limitation (nombre non signé (unsigned)!) est importante, c'est moins efficace avec des nombres signés (il y a des opérations en plus à faire, parce que le modulo d'un nombre négatif par un nombre positif est toujours négatif ou nul en C). Donc je conseille de toujours écrire &(x-1) pour les modulos par une puissance de 2 (x=2^k étant la puissance de 2). Dans beaucoup de cas (routines de sprites par exemple), &(x-1) (et >>k pour la division qui va avec) a des chances d'être ce que tu veux réellement d'ailleurs, la définition C du modulo est un peu bizarre.

djflex (./1) :
4) La longueur d'un bloc de code influe-elle sur la vitesse du programme à squizzer ce code

Il y a 3 longueurs de saut possibles: <128 octets (.s), >=128 et <32768 octets (.w) et >=32768 octets (.l). Entre .s et .w, la différence est minime: pour un branchement effectué ou pour un appel de fonction (bsr), ça n'a aucune importance (10 cycles pour le branchement effectué dans les 2 cas, 18 pour le bsr), pour un branchement conditionnel qui n'est pas effectué (condition non satisfaite), le .s prend 8 cycles, le .w 12. Les sauts .l sont plus coûteux: jmp (saut non conditionnel) prend 12 cycles, jsr (appel de fonction) prend 20 cycles et les sauts conditionnels sont particulièrement coûteux parce qu'il faut un saut conditionnel .s + un jmp, ce qui fait 20 cycles pour un branchement effectué (le bra.s ne sera pas effectué, le jmp le sera) et 10 pour un branchement non effectué (bra.s effectué, jmp sauté).

En taille de code, un saut .s prend 2 octets, un saut .w prend 4 octets, un saut non conditionnel .l prend 6 octets + 1 relogement et un saut conditionnel .l prend un saut .s + un saut non conditionnel .l, donc 8 octets + 1 relogement.

Sasume parle en ./8 de http://lionel.debroux.free.fr/S1P9/tutorial.html .
Le tutorial est quand même nettement orienté TI-68k, même si certaines techniques s'appliquent un peu partout.

Très bon lien aussi que ce dernier.
Juste pour être sûr, par rapport au modulo, comment écririez vous (de manière optimisée) le test pour savoir si le modulo d'un nombre x par 16 est égal à 0 (x % 16 == 0) ?
Merci

x & 15 == 0

(unsigned)x % 16 == 0 me paraît être la solution la plus claire.

pourquoi, unsigned? pour le fun, non?

Regarde le code généré si x est signé, tu verras bien.

x % 16 == 0 me paraît être la solution la plus claire.

C'est sûr mais on peut toujours mettre un commentaire à côté pour expliquer..

Ok je vais essayer avec x & 15 == 0 (ou !(x&15) en fait, c'est pas plus rapide ?)

Merci à tous.

J'écrirais effectivement !(x&15), mais normalement (x&15)==0 devrait donner exactement le même code (mais c'est plus long, donc beurk! ).

C'est plus lisible, donc plus maintenable tout en évitant le risque d'erreur dans l'implémentation... Donc c'est mieux

djflex (./20) :

x % 16 == 0 me paraît être la solution la plus claire.

C'est sûr mais on peut toujours mettre un commentaire à côté pour expliquer..

Un code clair est un code qui n'a pas besoin de commentaire justement.

(unsigned)x % 16 == 0 donne le même code, la même rapidité que !(x&15), tout en ne requiérant pas de commentaire

Un code clair est un code qui n'a pas besoin de commentaire justement.

Sauf si on est limité par la puissance de la machine sur laquelle on l'execute et qu'on doive bidouiller pour augmenter la rapidité d'execution, quitte à nuire à la lisibilité du code. C'est sur que personne n'écrirait ça aujourd'hui dans un programme en .NET ou en C++ sur PC.

x % 16 == 0 donne le même code, la même rapidité que !(x&15), tout en ne requiérant pas de commentaire

Dans ce cas là aucun pb, j'utiliserai x % 16 == 0.

Le "(unsigned)" indiqué par Thibaut est important

Effectivement. Un nombre signé % 16, c'est lent parce que le modulo se comporte bizarrement avec les nombres négatifs en C (et le compilateur ne peut pas savoir si le nombre peut être négatif quand il est signé).

Personnellement, je conseille !(x&15) tout simplement, il vaut mieux écrire ce qu'on pense vraiment (ce qu'on pense vraiment étant qu'on veut du code rapide et compact ) que faire confiance au compilateur, et on ne risque pas de se tromper avec les histoires de signé ou non.

Lionel Debroux (./25) :
Le "(unsigned)" indiqué par Thibaut est important

Oui, pourquoi tu l'enlèves à chaque fois djflex ? Sans ça, on se retrouve avec un code lent.

Ou alors on écrit &15 tout simplement et on n'a pas ce problème.

c'est pas très intéressant les nb négatifs dans ce cas, c'est pas très certains qu'il en ait dans son cas, et x est peut être déja unsigned!

forcer en unsigned un nombre signed, ça va foutre la bzz je pense, même si le modulo se calcule, le résultat sera t il correct?

en général on aura un assert (x>0) avant je pense

squalyl (./29) :
forcer en unsigned un nombre signed, ça va foutre la bzz je pense, même si le modulo se calcule, le résultat sera t il correct?

Pour une puissance de 2 (ce pour quoi cette optimisation s'applique), il sera toujours correct. (Démonstration: Si x congru à y mod 2^{8 sizeof(unsigned)} alors x congru à y mod 2ⁿ pour tout entier naturel n<=8 sizeof(unsigned).)