Cherche exemple de programme qui s'optimise

Yo la zone,

Je suis en face d’un problème louche.
Je taf sur un compilateur C qui fait des choses très louches. Et parmi ces choses louches optimise des programmes.

Je cherche un exemple de programme pas trop debil, (qui calcule un truc intéressant) qui s’optimise, mais c’est super chaud.
Les deux optimisations considérées sont :

  • Élimination des sous expression commune
    Qui va transformer le programme suivant

a = x + y; b = x + y;
en

a = x + y; b = a;
Car on a déjà calculé x + y

  • Et propagation de constante:
    qui transforme

a =3 b = a + y;
en

a = 3; b = 3 + y;
Vu qu’on connait la valeur de a.

Voila, ces deux optimisations sont classiques, le problème c’est trouver un exemple qui puisse justifier qu’on les as dans notre complio.
On peux pas montrer un exemple avec ca:

a = x + y; b = x + y;
En disant “Oh regarder comme notre complio il optimise votre code debil”

Donc la première idée que j’ai, c’est d’utiliser des macros comme en C, en effet si je met un bon #define SIZE 300
Ya de forte chance que le code optimise des SIZE + 1 en 301.

Vous avez d’autre idées ?

Je paie des bières si vous trouvez des idées qui poutrent

Fraie un programme qui lit la grammaire du C (ou autre). Récupère les variables et fait les optimisations.
(on a fait çà l’année dernière en sujet de master (avec Flex et Bison qui sont des analyseurs grammaticaux)).
Je vois pas de méthodes génériques (pas de bidouilles) qui pourrait le faire =/.

[Hors propos]
Sauf qu’il faut savoir que bien souvent, le compilateur C (standard) optimise de telle sorte à ce que les instructions se passent rapidement, échange de registre etc etc…
a mon avis tu ne gagnera rien, a part perdre du temps en prétraitement.
[/HS]

Edit 1 :
… Erm … Après relecture je suis HS total … je rerédige XD

Edit 2 :
Pourquoi ne pas utiliser un exemple sympa genre : Calcul de suite de fibo / factorielle.

Programme 1 :
A Chaque étape on recalcul du début

Programme optimisé :
Les éléments sont gardés !

Ou un truc du genre ?

Fib et factorielle, sont trop simple pour être optimisés par les deux optimisation décrites. A aucun moment tu vas ecrires deux fois la mêmes opérations, Et pas de propagation de constantes non plus. Je pense qu’il faut plus trouvé un genre de hack. comme les macros

Ou bien trouvé un programme qui s’optimise bien une fois compilé. Mais ça c’est chaud.
Exemple : si on compilait nos tableaux comme en C, en transformant des t[i] en t + i4, je pense qu’on ferai apparaitre plein de i4 qui s’optimiserait avec CSE dans le programme compilé.

Et le problème, vient pas du comment faire les optimisations, mais juste de trouver un exemple cool.

filtre de sobel ou de canny par exemple.

http://fr.wikipedia.org/wiki/D%C3%A9tection_de_contours

Et en quoi ca va bien s’optimiser ton truc ? Juste parce que c’est un gros programme ?

tu travaille sur des images bitmap en réutilisant les mêmes formules (passage en largeur et ensuite en hauteur) et les mêmes valeurs pour des pixels voisins.

Pour ce qui est de la taille du code: j’en ai codé un en assembleur DLX, donc c’est vraiment pas gros.

EDIT: de plus, le filtre de canny nécéssite un parametre souvent noté sigma qui pourrait etre un tres bon exemple pour la propagation de constante.

Yep je comprend, mais au niveau du code, ta même formule tu vas l’écrire une fois, et je suppose qu’elle va être dans une boucles. et si c’est le cas ça rentre pas dans le cadre de mes optimisations. Mais je vais quand même regarder les algo avec des matrices. :slight_smile:

ouais mais non, en fait ^^. A prendre avec des pincettes ce que je vais dire, vu que je parle de mémoire:
pour que l’algo se traine pas trop, tu dois travailler sur plusieurs pixels en même temps. Il me semble que sur une seule boucle, on travaillait sur une sous matrice 3x3 et que plusieurs sous-expressions étaient utiles dans les deux ‘balayages’ (vertical & horizontal). Donc, a ne calculer qu’une fois pour plusieurs utilisations.

J’essayerais de retrouver mon rapport sur le sujet, et pas te dire les choses de mémoire.

Il me semble que pour appliquer un filtre symétrique 3x3 il suffit d’appliquer le filtre 1x3 puis 3x1 … -> linéaire

C’est pas simple de trouver un algo =/

J’ai jamais vraiment programmé, mais il me semblait que

a =3 b = a + y;
était plus rapide a exécuter que :

a = 3; b = 3 + y;

Je me gourre ?
Ca dépend du language ? ( j’avais lu ca a propos du basic du CPC , donc bon)

[quote=“Lukkant, post:10, topic: 39940”]Je me gourre ?
Ca dépend du language ? ( j’avais lu ca a propos du basic du CPC , donc bon)[/quote]

Tu te gourres, en assembleur, une instruction qui prend un registre et une constante, est plus rapide qu’une instruction qui prend deux registres.

J’ai pas tout compris dans le truc mais ca, ca me choque:

mais juste NOWAY on utilise la multiplication ici!! On décale les bits!!

LoneWolf
Decalage de bit FTW

Je comprend pas ton message

Multiplication par 2^i == décalage vers la gauche de i

Binaire tout ça.

Ouai je sais bien, mais c’est quoi le rapport avec le topic ?

Aucun, c’est juste LoneWolf qui tique sur des trucs, rien de grave :slight_smile:

Le problème c’est pas de savoir comment s’optimise le truc, si je compile les tableau avec les multiplication, je oeux avoir une autre passe plus tard, qui va la transformer en décalage de bits,

Mais ça fera toujours apparaitre, des truc qui se feront optimiser par CSE.

IL A BIEN RAISON. Bitshift FTW et pis c’est tout. :slight_smile:

Bon je pense que ca va intéresser personne, mais je donne quand même la solution que j’ai trouvée.

J’ai codé la multiplication de matrice. Et codant les matrices sur un tableau à une case, donc la case i,j de la matrice m devient m[i*p+j].
Et dans le code de la multiplication:

int mult (int * a, int * b, int * c, int m, int n, int p){ int i, j, k; i = 0; while (i < m){ j = 0; while (j < p){ c[i*p+j] = 0; k = 0; while (k < n){ c[i*p+j] = c[i*p+j] + a[i*n+k]*b[k*p+j]; k = k + 1; } j = j + 1; } i = i + 1; } }

Et le i*p+j s’optimise plein de fois, et la fonction calcule un truc intéressant, j’ai prouvé que chaque case de la matrice c, contient bien la bonne valeur.
C’est tout con mais ca à suffit pour écrire un papier.

Voilà