Réduire le temps de calcul

Bonjour
J'ai essayé de tester le temps de calcul de deux méthodes.
Les voici:

j'ai une fonction principale ou se déroule le calcul.

Code:

---

1 2 3 4

int fonction(double a,double b,double c,double d){ ......... ....Calculs }

---

J'ai une fonction intermédiaire, ou il y a rien dedans, si ce n'est l'appel de la fonction précédente:

Code:

---

1 2 3 4

int fonction2(double x,double y,double z,double u){   fonction (1,2,2,3); }

---

si je fais ca

Code:

---

1 2 3 4 5 6

void main(){   for(long i=1;i<500000;i++){   fonction (1,2,2,3); }

---

alors le temps de calcul sera de, par exemple 9 secondes.

Si maintenant je fais ca:

Code:

---

1 2 3 4 5 6

void main(){   for(long i=1;i<500000;i++){   fonction2(double x,double y,double z,double u) }

---

où les arguments x,y,z,u ont été définis avant,( mais ca a pas d'importance.)
C'est exactement la même chose, il y a juste la fonction2 qui est appelée en plus sur la pile d'appel
Alors le temps de calcul sera par exemple de 14secondes,


Comme vous le voyez, le temps est plus long. Avec 500000 itérations, il y a une différence, alors vous imaginez si j'augmente d'un facteur 10 ou 100 voire 1000 le nb d'itération.

Comment faire pour rendre égale ou diminuer la différence entre les deux méthodes. Si la différence est inhérente à la présence de l'appel de la fonction intérmédiaire, alors je la vire.
Mais j'ai essayé par différents moyens en utilisant par exemple inline, ce qui ne change rien, pas moyen de faire diminuer le temps de calcul.

Que me conseillez vous?
Merci

Tu as bien fait tes tests en mode optimisé / release ?

Parce que tes résultats sont pour le moins étranges.

non, j'ai pas fait de tests en Realese, uniquement en debug.
je viens de le faire en release, ca me donne 0 dans le premier cas,
et 0 dans le second.

Qqn peut il m'expliquer pourquoi ???

Au fait, ca peut changer qqch si je mets inline aux deux fonctions. Mais ca change pas grand chose

Code:

---

1 2 3 4 5 6

void main(){   for(long i=1;i<500000;i++){   fonction (1,2,2,3); }

---

Cette fonction ne fait rien (ni valeur de retour, ni affichage...), le compilateur l'a surement vu et l'a remplacer par une fonction vide, d'où les 0 secondes. Tu peux par exemple utiliser la valeur de retour du main() pour éviter cela :

Code:

---

1 2 3 4 5 6 7

int main(){ int r = 0; for(long i=0;i<500000;i++){ r += fonction (1,2,2,3); } return r; }

---

Citation:

---

Envoyé par Sylvain Togni

Code:

---

1 2 3 4 5 6

void main(){   for(long i=1;i<500000;i++){   fonction (1,2,2,3); }

---

Cette fonction ne fait rien (ni valeur de retour, ni affichage...), le compilateur l'a surement vu et l'a remplacer par une fonction vide, d'où les 0 secondes.

---

Oui, mais...

Citation:

---

Tu peux par exemple utiliser la valeur de retour du main() pour éviter cela :

Code:

---

1 2 3 4 5 6 7

int main(){ int r = 0; for(long i=0;i<500000;i++){ r += fonction (1,2,2,3); } return r; }

---

---

Non...

La valeur de retour de la fonction main a un objectif précis et incontournable: signaler au système l'issue complète de l'exécution du programme.

Les valeurs admises sont

• 0 le programme s'est terminé sans problème
• 1 le programme s'est terminé sur une erreur
• 2 le programme a émis des avertissement (unixoïdes only)

et servent, normalement, lors de la création de script "shell" ou "batch".

Par contre, rien ne t'empêcherait - effectivement - de récupérer une valeur de retour pour en faire quelque chose dans la fonction principale ;) (pourquoi pas un simple affichage :question::)

L'affichage risque de fausser les tests .... enfin l'affichage c'est un des trucs les plus lents...

Citation:

---

Envoyé par LittleWhite

L'affichage risque de fausser les tests .... enfin l'affichage c'est un des trucs les plus lents...

---

Je n'ai jamais dit non plus qu'il fallait le faire à chaque itération ;)

Un affichage unique de la valeur finale avec, pourquoi pas, le temps d'exécution (calculé à l'aide de clock() et consort) peut très bien suffir ;)

Citation:

---

Envoyé par koala01

Les valeurs admises sont

• 0 le programme s'est terminé sans problème
• 1 le programme s'est terminé sur une erreur
• 2 le programme a émis des avertissement (unixoïdes only)

---

Les deux valeurs citées dans le standard sont :
EXIT_SUCCESS (ou 0)
EXIT_FAILURE (valeur non précisée)
(toutes deux définies dans <cstdlib>)

Tout le reste est défini par l'implémentation.

Citation:

---

Cette fonction ne fait rien (ni valeur de retour, ni affichage...), le compilateur l'a surement vu et l'a remplacer par une fonction vide, d'où les 0 secondes.

---

J'ai précisé que cette fonction faisait des calculs.
Je les ai pas mis, mais c'est de calculs de maths.

Mais j'ai +ou- réglé le pb. A ce propos, j'en ai un autre, qui concerne encore le temps de calcul.

Voila en gros quel est mon code:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

double Pochammer(double z,int l){ double res=1; while(l>0){ res=res*(z+l-1); l--;   } return res; } double Fac(int l){ double res=1; while(l>0){ res=res*(l); l--;   } return res; } double Somme(double H,double t, double borne1,double borne2,double a,double b,double c,int n){ double res=0,denom=0,num=0,membre=0; for(int o=0;o<=n;o++){ double result1=0,result2=0; hyperg_2F1_series(-o+b,1+a,a+2,borne1/t,result1); hyperg_2F1_series(-o+b,1+a,a+2,borne2/t,result2); num=-pow(t,H-.5)*Pochammer(a,o)*Pochammer(c-b,o);   denom=1/((1+a)*Donnees::Gamma_c*Pochammer(c,o)*Fac(o));   membre=-pow((double)borne2/t,a)*borne2*result2+pow((double)(borne1)/t,a)*borne1*result1;   res+=num*denom*membre; }   res=res*Donnees::N; return res; }

---

Voici (en gros, pas en détail) pour la fonction main:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

void main(){ double sum2=0,res2=0;   int j=0;   double a=Donnees::H-0.5; double b=0.5-Donnees::H; double c=Donnees::H+0.5;     for(long i=1;i<=Donnees::nb_point;i++) { sum=0; t=(double)i/Donnees::nb_point; tj=(double)0/Donnees::N; tjj=(double)1/Donnees::N;   T=0; while(tjj<=t) { Nombre=3; sum=sum+brownien[T]*Donnees::delta*Somme(Donnees::H,t,tj,tjj,a,b,c,Nombre);   tj=tj+(double)1/Donnees::N; tjj=tjj+(double)1/Donnees::N; T=T+1; } j=j+1;

---

Quand je fais ca:
c'est a dire quand, dans la fonction Somme je supprime la ligne res=+...:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

double Somme(double H,double t, double borne1,double borne2,double a,double b,double c,int n){ double res=0,denom=0,num=0,membre=0; for(int o=0;o<=n;o++){ double result1=0,result2=0; hyperg_2F1_series(-o+b,1+a,a+2,borne1/t,result1); hyperg_2F1_series(-o+b,1+a,a+2,borne2/t,result2); num=-pow(t,H-.5)*Pochammer(a,o)*Pochammer(c-b,o); denom=1/((1+a)*Donnees::Gamma_c*Pochammer(c,o)*Fac(o)); membre=-pow((double)borne2/t,a)*borne2*result2+pow((double)(borne1)/t,a)*borne1*result1;   //res+=num*denom*membre; }   res=res*Donnees::N; return res; }

---

C'est presque AUTOMATIQUE, le temps de calcul est tres faible.

En revanche, quand je fais ca:c'est a dire quand je réactive la ligne,

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

double Somme(double H,double t, double borne1,double borne2,double a,double b,double c,int n){ double res=0,denom=0,num=0,membre=0; for(int o=0;o<=n;o++){ double result1=0,result2=0; hyperg_2F1_series(-o+b,1+a,a+2,borne1/t,result1); hyperg_2F1_series(-o+b,1+a,a+2,borne2/t,result2); num=-pow(t,H-.5)*Pochammer(a,o)*Pochammer(c-b,o); denom=1/((1+a)*Donnees::Gamma_c*Pochammer(c,o)*Fac(o)); membre=-pow((double)borne2/t,a)*borne2*result2+pow((double)(borne1)/t,a)*borne1*result1;   res+=num*denom*membre; }   res=res*Donnees::N; return res; }

---

C'est beaucoup plus long.
Je ne vois pas en quoi le rajout de cette ligne ralenti à ce point le programme (Le programme fait 2000 secondes avec cette ligne).
Pourtant, les calculs ne se font pas avec de gros chiffres.
De l'ordre de 10^5 au maximum.

Savez vous d'ou vient cette différence de calcul?
Ce n'est pas une question de taille de chiffre.

Si je remplace la ligne res+=... par, par exemple:
res+=1000000000000 (ce qui est un gros chiffre),
le temps de calcul sera toujours presque nul.

Il y a trois facteurs:
membre, num,denom.

Pour chacun des trois, je les ai successivement remplacés par 1. C'est le facteur "membre" qui ralentit le plus. Mais tous les trois contribuent à ralentir le programme.


J'ai beau cherché, je ne vois pas.
Je présice que je suis en mode Release.

Merci

Même si les calculs sont longs et compliqués, s'ils ne dépendent d'aucune donnée qui ne sera connue qu'à l'exécution ils peuvent parfaitement être calculés à la compilation par l'optimiseur.

Sauf que le truc, c'est que les compilateurs (enfin, surtout ceux qu'on utilise généralement) ne vont pas forcément précalculer quelque chose à la compilation parce qu'ils ne détectent pas que c'est possible.

Donc au final, ce genre de test, ça ne veut rien dire.

merci pour la réponse. Je comprends pas trop ce que ca signifie, mais en gros, il n'y a rien a faire.

(en plus, les calculs ne sont pas compliqués)

Ben c'est simple, ta fonctions Somme est locale et n'a qu'une seule valeur de retour, res, donc le compilateur ne fait que les calculs dont il a besoin pour évaluer res.

Par exemple quand tu fais :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

double Somme(double H,double t, double borne1,double borne2,double a,double b,double c,int n) { double res=0,denom=0,num=0,membre=0; for(int o=0;o<=n;o++) { /*   Calcul lourd   ...     */   //res+=num*denom*membre; }   res=res*Donnees::N; return res; } }

---

Le compilo supprime complètement la boucle for puisqu'elle ne sert à rien dans l'évaluation de res qui vaut toujours 0 * Données::N.

De même si tu mets res += 1 * denom * 1 alors le compilateur n'a besoin que de denom pour calculer res donc il n'exécute que la ligne denom=1/((1+a)*Donnees::Gamma_c*Pochammer(c,o)*Fac(o)); et supprime le reste.

ahh ok
et ca c'est vrai en release comme en debug, ou uniquement en debug?

Et donc, on ne peut rien faire pour accelerer le code?

Il n'y a pas rien à faire : il suffit de faire en sorte que l'optimisation pure et simple du code ne soit pas possible.

Citation:

---

Il n'y a pas rien à faire : il suffit de faire en sorte que l'optimisation pure et simple du code ne soit pas possible.

---

C'est dans les options du compilateur que ca se règle ca?

Ce que je veux dire, c'est que:
est-ce possible de le rendre bcp plus rapide, malgré les calculs?

Dans tes essais précédents (en mettant des lignes en commentaires) tu n'optimisais pas le calcul, tu faisais tout simplement un calcul différent. Règles de bases pour optimiser tes calculs (à suivre dans l'ordre) :
1/ Fait un code qui marche et c'est tout,
2/ Surtout ne modifie pas un code qui marche avec de petites astuces, le compilateur est meilleur que toi à ce jeu là,
3/ Si vraiment t'as des problèmes dans ton projet, commence par identifier quelles sont les méthodes qui sont les plus gourmandes (instrumente ton code),
4/ Travail sur les algos les + lents.

Y a des rumeurs qui disent ceci:

-moins y a de code, plus ca va vite

-faut toujours privilegier les case switch sur les if

-faut toujours privilégier la récursion (par ex l'appel de fonction récursives) sur les boucles for.


est-ce que tout ceci est vrai?

Citation:

---

Envoyé par deubelte

Y a des rumeurs qui disent ceci:

-moins y a de code, plus ca va vite

---

Non. Un algo en n2 est bien souvent plus simple qu'un algo en nlogn. Pourtant, le second a plus de chance d'être plus performant que le premier.

Citation:

---

Envoyé par deubelte

-faut toujours privilegier les case switch sur les if

---

Pour la lecture du code, certainement. Pour les performances, à voir. Je pense que la plus part du temps, il n'y a pas de gain. Mais c'est plus intuitif qu'étayé comme avis.

Citation:

---

Envoyé par deubelte

-faut toujours privilégier la récursion (par ex l'appel de fonction récursives) sur les boucles for.

---

A bon? Je ne vois pas d'élément à priori pour affirmer cela. D'autant que le récursif peut rapidement être source de problème si on ne maîtrise pas sa profondeur.

Citation:

---

Envoyé par deubelte

-faut toujours privilégier la récursion (par ex l'appel de fonction récursives) sur les boucles for.

---

Une de mes prof travaille dans le domaine de l'imagerie. Elle nous a raconté qu'à l'époque elle avait développé un algorithme de traitement d'image récursif, qui n'allait pas assez vite. Puis elle l'a retravaillé en itératif, et je crois qu'elle avait diminué le temps d'exécution de moitié, ou peut-être plus.
Enfin bon, maintenant, l'exemple date, je ne sais pas si ce serait encore vrai avec nos compilateurs actuels.

Je rejoint 3DArchi...

Pour moi, les trois affirmations sont fausses:

Un algorithme qui fait 100 itérations sera de toutes façons plus rapide qu'un algorithme qui en fait 10000, même s'il effectue plus de tests et /ou d'instructions

Lors de la compilation, le switch case sera de toutes manières remplacer par des test booléens (par contre, du stricte point de vue de la lecture, le gain est énorme ;)), et ceci, sans compter sur le fait qu'un switch case ne peut fonctionner qu'avec des valeurs entières (ou assimilées), ce qui disqualifie le switch case dans une série de cas

L'appel récursif ne sait pas être, dans la plupart des cas, inline (comment le compilateur pourrait-il savoir s'il doit générer le code 10 fois ou.... 10000 fois :question:) et la récursivité implique une série d'appel à la fonction qui prend énormément de temps et de place dans la pile d'appel.

La récursivité doit donc être utilisée quand elle est indispensable, mais les boucles - quelles qu'elles soient, mais en particulier les boucles utilisant un entier incrémenté (ou décrémenté) lors du test afin de savoir si elles doivent être effectuées une fois de plus - s'avèrent bien plus rapides lorsque la récursivité n'est qu'une option parmi d'autres.

Citation:

---

Envoyé par deubelte

-faut toujours privilégier la récursion (par ex l'appel de fonction récursives) sur les boucles for.

---

Plutôt l'inverse en fait. La récursivité est très puissante mais aussi très dangereuse (explosion de la pile d'appel). On cherche la plupart du temps au contraire à dérécursifier des algos pour les optimiser (ce qui se fait facilement quand on a bien compris le but de l'algo en question).
Ce qui est vrai en imperatif (C) ou en objet (c++) ne l'est pas forcément en fonctionnel par exemple (Caml,F#) et vice versa.

Les compilateurs C et C++ font aussi de la tail call optimization hein...
Le problème avec la récursion c'est pas la consommation mémoire, c'est les appels de fonction eux-mêmes.

Citation:

---

C'est dans les options du compilateur que ca se règle ca?

---

Non.
Je l'ai déjà dit cent fois : écris ton code de manière à ce qu'il soit impossible de calculer certaines choses à la compilation. Par exemple en utilisant des variables volatiles ou en prenant une variable depuis l'entrée standard.

c'est bizarre parce qu'en VBA, on m'a toujours dit qu'il fallait utilisé la récursion. Ca semble faux en C.
Mais intuitivement, ca me semblait être plus performant.

Bonjour.

Tu souhaites réduire les temps de calcul. Comme beaucoup de personnes le disent ici, il est difficile de faire mieux que le compilateur de nos jours. Et en tout cas passer en revue des parties de code en assembleur pour gagner quelques nonasecondes est contre-productif.

Mise à part effectivement si tes boucles sont mal conçues, mais ça ne semble pas être le cas, et vu que tu n'utilises pas un algorithme très compliqué, il n'y a peut-être pas de moyen d'augmenter significativement les temps de calcul.

Une méthode à tester et vu que tu utilises des "double" et des fonctions comme "pow", serait d'utiliser les fonctionnalités des processeurs dédiées à ce genre de calcul. Pour les processeurs Intel, tu as le Intel SDK, par exemple.
Par contre ça limite ton programme à un type de processeur. Et d'ailleurs le compilo le fait peut-être déjà pour certains calculs...

Citation:

---

Lors de la compilation, le switch case sera de toutes manières remplacer par des test booléens (par contre, du stricte point de vue de la lecture, le gain est énorme ), et ceci, sans compter sur le fait qu'un switch case ne peut fonctionner qu'avec des valeurs entières (ou assimilées), ce qui disqualifie le switch case dans une série de cas

---

Un gros avantage du switch, c'est que, sur un enum, le compilateur sait vérifier qu'on traite bien tous les cas. Très pratique, surtout lorsqu'on en vient à modifier un enum pour lui rajouter une valeur.

Citation:

---

Envoyé par white_tentacle

Un gros avantage du switch, c'est que, sur un enum, le compilateur sait vérifier qu'on traite bien tous les cas. Très pratique, surtout lorsqu'on en vient à modifier un enum pour lui rajouter une valeur.

---

C'est vrai avec gcc, mais avec Visual Express, non. J'ai pas d'avertissement en ce sens.

Un switch, c'est O(1), une série de tests booléens, c'est O(n)...
Un switch c'est bien évidemment plus rapide oui. Dans le cas où il y a peu de cas, ça génerera probablement des branchements, parce que ça reste plus rapide que des tables même si ça ne passe pas à l'échelle.

Citation:

---

Envoyé par loufoque

Un switch, c'est O(1), une série de tests booléens, c'est O(n)...

---

Tu peux préciser? Parce que, avec Visual Express en release pour un switch de 3 cas, j'ai :

Code:

---

1 2 3 4 5 6 7

sub eax, 0 je SHORT $LN3@main sub eax, 1 je SHORT $LN2@main sub eax, 1 jne SHORT $LN4@main

---

Ca reste du O(n)?

Si tu rajoutes plus de cas, et avec un bon optimiseur, il y a des chances que le compilateur passe par une "jump table" (pas sûr du terme français), qui est donc O(1).

Chose qu'il ne fera probablement jamais avec des if else imbriqués.

Citation:

---

Envoyé par white_tentacle

Si tu rajoutes plus de cas, et avec un bon optimiseur, il y a des chances que le compilateur passe par une "jump table" (pas sûr du terme français), qui est donc O(1).

Chose qu'il ne fera probablement jamais avec des if else imbriqués.

---

Effectivement, en augmentant le nombre de cas, je passe effectivement par une table intermédiaire.