Pourquoi fact_res_1 est-elle plus rapide que fact_res_2 ?

Version imprimable

Bonjour.
A l'occasion d'un exo sur la récursivité, je code la traditionnelle fonction factoriel.
Voulant tester sa rapidité, je compare 2 façons de la coder :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned long fact_rec_1(int n) {
	if (n == 1) 
		return 1;
	 else 
		return n * fact_rec_1(n - 1);
}
 
unsigned long fact_rec_2(int n) {
	if (n != 1)
		return n * fact_rec_2(n - 1);
	else
		return 1;
}

J'obtiens

Citation:

fact_rec_1 : 63 millisecondes
fact_rec_2 : 69 millisecondes

et je suis surpris que fact_res_1() où le test

Code:

if (n == 0)

est False le plus souvent soit plus rapide que fact_res_2 ou

Code:

if (n !=0)

est True le plus souvent et n'oblige donc pas la fct à passer au

Code:

else

Merci pour vos éclaircissements !

Le code complet pour ceux qui voudraient tester :

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
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
unsigned long fact_rec_1(int n) {
	if (n == 1) {
		return 1;
	} else {
		return n * fact_rec_1(n - 1);
	}
}
 
unsigned long fact_rec_2(int n) {
	if (n != 1)
		return n * fact_rec_2(n - 1);
	else
		return 1;
}
 
int main(void) {
	unsigned long res = 0;
	time_t begin = clock();
	time_t end = clock();
 
	begin = clock();
	for (int n = 0; n < 100000; n++) {
		for (int i = 15; i < 25; i++) {
			res = fact_rec_1(i);
		}
	}
	end = clock();
	printf("fact_rec_1 : %ld millisecondes\n",
			(end - begin) * 1000 / CLOCKS_PER_SEC);
 
	begin = clock();
	for (int n = 0; n < 100000; n++) {
		for (int i = 15; i < 25; i++) {
			res = fact_rec_2(i);
		}
	}
	end = clock();
	printf("fact_rec_2 : %ld millisecondes\n",
			(end - begin) * 1000 / CLOCKS_PER_SEC);
	return EXIT_SUCCESS;
}

Presque pareil

Bonjour,

Les deux tests (n== 0 et n != 0=) sont équivalents une comparaison suivi d'un saut conditionnel (les divers sauts conditionnels sont, d'une part, équivalents et, d'autre part, ils seront bien prédits ici) .
Une vue de l'assembleur possible peut faire comprendre ce qui se passe :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ; Code : if(n== 0) cmp n, 0 jnz _Else ;...then return 1... jmp _End_if ; qui ne sert à rien à cause du return et sera peut être supprimé _Else: ;...else fact_1... _End_if: ; Code : if(n!= 0) cmp n, 0 jnz _Else ;...then fact_2......' jmp _End_if _Else: ;...else return 1...' _End_if:
Comme on le voit, la branche "then" a un jmp en plus c'est ce qui fait la différence. Sinon il n'yen a pas, la prédiction de branchement rend les deux sauts conditionnels équivalents vers le même cas le plus fréquent (!= 1).
Certains compilateurs peuvent être assez astucieux pour permuter les cas. Mais pas tous 8-)

Mea culpa :oops: : à cause des return mon explication ne tient pas.

Salutations

19/09/2022, 19h57
Sve@r

Bonjour

Des benchs de ce genre ne sont pas facile à interpréter car tu as ta machine qui fait d'autres trucs qui peuvent interférer. A titre d'information, Python possède un module de bench (timeit) qui fonctionne de la façon suivante: on lui donne un repeat (ex 10) et un number (ex 500). Il lance alors la fonction à tester 500 fois et chronomètre le temps que prend ces 500 appels. Et il fait ça 10 fois. Et au bout des 10 chronos il te donne le plus court, le plus long et la moyenne. Pour essayer de te donner un bench le plus impartial possible en lissant au mieux les interférences éventuelles.

Plus le compilateur qui rajoute parfois sa sauce en faisant des optimisations qui font que le code généré ne correspond pas au code écrit. Perso je n'aime pas car pour moi un compilateur c'est un traducteur qui n'a pas à prendre d'initiatives sur mon code mais que peut-on y faire et surtout qu'est-ce que cela entraine sur un bench tel que tu l'as écrit...?

Bonsoir Sve@r, j'ai essayé de reproduire le test que tu as décris :

Avec 10 tests répétés 1000000 fois, j'obtiens toujours le même résultat étonnant :

Citation:

fact_rec_1_min : 107 millisecondes
fact_rec_1_max : 114 millisecondes
fact_rec_1_moy : 111.900002 millisecondes

fact_rec_2_min : 122 millisecondes
fact_rec_2_max : 126 millisecondes
fact_rec_2_moy : 124.000000 millisecondes

J'ai essayé d'inverser l'ordre des tests, d’abord rec_2 puis rec_1 , cela ne chance rien au résultat.

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define REPETITION 10
#define NOMBRE 1000000
 
unsigned long fact_rec_1(int n);
unsigned long fact_rec_2(int n);
unsigned long tab_min(unsigned long *tab, int taille);
unsigned long tab_max(unsigned long *tab, int taille);
float tab_moy(unsigned long *tab, int taille);
 
int main(void) {
	unsigned long res = 0;
	unsigned long fact_rec_1_res[REPETITION] = { 0 };
	unsigned long fact_rec_2_res[REPETITION] = { 0 };
	time_t begin = clock();
	time_t end = clock();
	int n, i;
 
	for (n = 0; n < REPETITION; n++) {
		begin = clock();
		for (i = 0; i < NOMBRE; i++) {
			res = fact_rec_1(25);
		}
		end = clock();
		fact_rec_1_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
 
		begin = clock();
		for (i = 0; i < NOMBRE; i++) {
			res = fact_rec_2(25);
		}
		end = clock();
		fact_rec_2_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
	}
 
	printf("fact_rec_1_min : %ld millisecondes\n",
			tab_min(fact_rec_1_res, REPETITION));
	printf("fact_rec_1_max : %ld millisecondes\n",
			tab_max(fact_rec_1_res, REPETITION));
	printf("fact_rec_1_moy : %f millisecondes\n",
			tab_moy(fact_rec_1_res, REPETITION));
	puts("");
	printf("fact_rec_2_min : %ld millisecondes\n",
			tab_min(fact_rec_2_res, REPETITION));
	printf("fact_rec_2_max : %ld millisecondes\n",
			tab_max(fact_rec_2_res, REPETITION));
	printf("fact_rec_2_moy : %f millisecondes\n",
			tab_moy(fact_rec_2_res, REPETITION));
 
	return EXIT_SUCCESS;
}
 
unsigned long fact_rec_1(int n) {
	if (n == 1)
		return 1;
	else
		return n * fact_rec_1(n - 1);
}
 
unsigned long fact_rec_2(int n) {
	if (n != 1)
		return n * fact_rec_2(n - 1);
	else
		return 1;
}
 
unsigned long tab_min(unsigned long *tab, int taille) {
	unsigned long res = tab[0];
	for (int i = 0; i < taille; i++) {
		if (tab[i] < res) {
			res = tab[i];
		}
	}
	return res;
}
 
unsigned long tab_max(unsigned long *tab, int taille) {
	unsigned long res = tab[0];
	for (int i = 0; i < taille; i++) {
		if (tab[i] > res) {
			res = tab[i];
		}
	}
	return res;
}
 
float tab_moy(unsigned long *tab, int taille) {
	float res = 0;
	for (int i = 0; i < taille; i++) {
		res += tab[i];
	}
	return res / (float) taille;
}

20/09/2022, 07h03
foetus
Le seul truc que je vois c'est le nombre de possibilités pour rentrer dans le if :mrgreen: :
- if (n == 1), 1 seule
- if (n != 1), 1 infinité
On peut penser raisonnablement que la première solution peut être transformée en switch (avec 1 seul cas et le else qui devient le cas par défaut).
Le switch étant [légèrement] + efficace parce qu'il utilise 1 table de sauts

En testant vite fait avec 1 switch (mais il faut garder les return dans les case et ne pas créer de variable locale), on arrive [quasi] au même résultat que le code avec if (n == 1).
Code:

1 2 3 4 5 6 7 8 9 10 unsigned long fact_rec_3(int n) { switch(n) { case 1: return 1; break; default: return (n * fact_rec_3(n - 1)); break; } }
Mais cela interroge :koi: parce que j'ai toujours entendu dire qu'il faut mettre le cas qui a l'occurence la + élevée dans le if (ici le code avec if (n != 1)).
Mais cela veut dire que le compilateur ne va pas y toucher et il ne va pas l'optimiser :koi:
:whistle: après remplacer 1 if par 1 switch c'est très souvent trivial et tout le monde sait que le switch est [légèrement] + efficace
20/09/2022, 09h21
Bktero

Dans des cas comme ça, il faut regarder l'assembleur généré pour les 2 (ou 3) fonctions, par exemple avec https://compiler-explorer.com/

Bien penser à mettre une option pour le niveau d'optimisation (comme -O2), sinon les comparaisons n'ont pas de sens.

Après, c'est pas forcément facile de comprendre pourquoi ça donne ça, mais c'est toujours mieux que de faire des suppositions sur ce que ça donne.
20/09/2022, 09h50
dalfab

Je dirais plutôt que les 2 fonctions sont totalement identiques. L'optimiseur devrait voir cela.
Il faudrait voir les 2 codes assembleurs.
Selon moi, la fonction 1 fait l'appel récursif en toute dernière action, et donc est facilement convertible en un traitement non récursif faisant gagner du temps. Mais encore une fois, les fonctions sont identiques, l'optimiseur fait mal son boulot!
20/09/2022, 10h17
-Eks-

Le plus probable est que ypcman compilait sans optimisations (sans passer l'option -O de gcc comme rappelé par Bktero, avec -O2 ou -O3 par exemple).

En tout cas, il n'indique pas qu'elles étaient ses options de compilation, ni le compilateur utilisé.

j'ai utilisé le lien pour voir l'assembleur généré et effectivement, l'assembleur est identique pour les 2 fonctions, identique aussi avec celle employant un switch/case

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fact_rec_1(int):
        push    rbp
        mov     rbp, rsp
        push    rbx
        sub     rsp, 24
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 1
        jne     .L2
        mov     eax, 1
        jmp     .L3
.L2:
        mov     eax, DWORD PTR [rbp-20]
        movsx   rbx, eax
        mov     eax, DWORD PTR [rbp-20]
        sub     eax, 1
        mov     edi, eax
        call    fact_rec_1(int)
        imul    rax, rbx
.L3:
        mov     rbx, QWORD PTR [rbp-8]
        leave
        ret

Je suis sous gcc (GCC) 11.3.1 20220421 (Red Hat 11.3.1-2)
Effectivement je compilais en -O0. En passant à -O2, les différences de durées deviennent négligeables.

Merci pour vos réflexions !

20/09/2022, 11h29
WhiteCrow

Bonjour,

Durée nulle = optimisation, toutes tes boucles ont élé opt out car elles n'avaient aucun effet →passe ta variable res en volatile pour éviter cela avec des optimisations poussées (ou fait quelque chose avec le résultat calculé).
Et surtout, surtout utilise des outils comme godbolt.

J'imagine, et là il faudrait qu'un expert confirme, que dans le premier cas le code qui est déjà dans le pipeline d'exécution se trouve exécuté la majorité du temp, alors que dans le second cas le processeur devra invalidé le pipeline d'exécution et recommencer.

J'ai justement utilisé godbolt !

Citation:

Envoyé par WhiteCrow

Bonjour,

Durée nulle = optimisation, ....

En fait, je testais toujours fact(25) un million de fois. Or avec l'optimisation, fact(25) n'étais plus recalculé d'où les durées nulles. J'ai modifié mon code pour calculer un fact(rand()%26) et les durées sont redevenues non nulles mais en revanche quasi identiques et sans l'une systématiquement plus faible que l'autre :

Citation:

fact_rec_1_min : 122 millisecondes
fact_rec_1_max : 126 millisecondes
fact_rec_1_moy : 124.800003 millisecondes

fact_rec_1_plus_min : 120 millisecondes
fact_rec_1_plus_max : 127 millisecondes
fact_rec_1_plus_moy : 124.900002 millisecondes

fact_rec_2_min : 122 millisecondes
fact_rec_2_max : 126 millisecondes
fact_rec_2_moy : 124.800003 millisecondes

fact_rec_2_plus_min : 121 millisecondes
fact_rec_2_plus_max : 128 millisecondes
fact_rec_2_plus_moy : 125.099998 millisecondes

Voici le code si ça intéresse

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define REPETITION 10
#define NOMBRE 10000000
 
unsigned long fact_rec_1(int n);
unsigned long fact_rec_1_plus(int n);
unsigned long fact_rec_2(int n);
unsigned long fact_rec_2_plus(int n);
unsigned long tab_min(unsigned long *tab, int taille);
unsigned long tab_max(unsigned long *tab, int taille);
float tab_moy(unsigned long *tab, int taille);
 
int main(void) {
	unsigned long res = 0;
	unsigned long fact_rec_1_res[REPETITION] = { 0 };
	unsigned long fact_rec_2_res[REPETITION] = { 0 };
	unsigned long fact_rec_1_plus_res[REPETITION] = { 0 };
	unsigned long fact_rec_2_plus_res[REPETITION] = { 0 };
	time_t begin = clock();
	time_t end = clock();
	int n, i;
	int val = 26;
	srand(time(NULL));
	for (n = 0; n < REPETITION; n++) {
 
		begin = clock();
		for (i = 0; i < NOMBRE; i++) {
			res = fact_rec_1_plus(rand() % val);
		}
		end = clock();
		fact_rec_1_plus_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
 
		begin = clock();
		for (i = 0; i < NOMBRE; i++) {
			res = fact_rec_2_plus(rand() % val);
		}
		end = clock();
		fact_rec_2_plus_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
 
		begin = clock();
		for (i = 0; i < NOMBRE; i++) {
			res = fact_rec_1(rand() % val);
		}
		end = clock();
		fact_rec_1_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
 
		begin = clock();
		for (i = 0; i < NOMBRE; i++) {
			res = fact_rec_2(rand() % val);
		}
		end = clock();
		fact_rec_2_res[n] = (end - begin) * 1000 / CLOCKS_PER_SEC;
 
	}
 
	printf("fact_rec_1_min : %ld millisecondes\n",
			tab_min(fact_rec_1_res, REPETITION));
	printf("fact_rec_1_max : %ld millisecondes\n",
			tab_max(fact_rec_1_res, REPETITION));
	printf("fact_rec_1_moy : %f millisecondes\n",
			tab_moy(fact_rec_1_res, REPETITION));
	puts("");
	printf("fact_rec_1_plus_min : %ld millisecondes\n",
			tab_min(fact_rec_1_plus_res, REPETITION));
	printf("fact_rec_1_plus_max : %ld millisecondes\n",
			tab_max(fact_rec_1_plus_res, REPETITION));
	printf("fact_rec_1_plus_moy : %f millisecondes\n",
			tab_moy(fact_rec_1_plus_res, REPETITION));
	puts("");
	printf("fact_rec_2_min : %ld millisecondes\n",
			tab_min(fact_rec_2_res, REPETITION));
	printf("fact_rec_2_max : %ld millisecondes\n",
			tab_max(fact_rec_2_res, REPETITION));
	printf("fact_rec_2_moy : %f millisecondes\n",
			tab_moy(fact_rec_2_res, REPETITION));
	puts("");
	printf("fact_rec_2_plus_min : %ld millisecondes\n",
			tab_min(fact_rec_2_plus_res, REPETITION));
	printf("fact_rec_2_plus_max : %ld millisecondes\n",
			tab_max(fact_rec_2_plus_res, REPETITION));
	printf("fact_rec_2_plus_moy : %f millisecondes\n",
			tab_moy(fact_rec_2_plus_res, REPETITION));
	return EXIT_SUCCESS;
}
 
unsigned long fact_rec_1(int n) {
	if (n == 1)
		return 1;
	else
		return n * fact_rec_1(n - 1);
}
 
unsigned long fact_rec_1_plus(int n) {
	switch (n) {
	case 1:
		return 1;
		break;
	default:
		return n * fact_rec_1(n - 1);
		break;
	}
}
 
unsigned long fact_rec_2(int n) {
	if (n != 1)
		return n * fact_rec_2(n - 1);
	else
		return 1;
}
 
unsigned long fact_rec_2_plus(int n) {
	if (!(n == 1))
		return n * fact_rec_2(n - 1);
	else
		return 1;
}
 
unsigned long tab_min(unsigned long *tab, int taille) {
	unsigned long res = tab[0];
	for (int i = 0; i < taille; i++) {
		if (tab[i] < res) {
			res = tab[i];
		}
	}
	return res;
}
 
unsigned long tab_max(unsigned long *tab, int taille) {
	unsigned long res = tab[0];
	for (int i = 0; i < taille; i++) {
		if (tab[i] > res) {
			res = tab[i];
		}
	}
	return res;
}
 
float tab_moy(unsigned long *tab, int taille) {
	float res = 0;
	for (int i = 0; i < taille; i++) {
		res += tab[i];
	}
	return res / (float) taille;
}

20/09/2022, 12h01
Sve@r

Citation:

Envoyé par ypcman

J'ai modifié mon code pour calculer un fact(rand()%26)

Si tu veux un rand plus uniforme, il est conseillé de demander un rand() / RAND_MAX * 26
20/09/2022, 12h13
ypcman

Citation:

Envoyé par Sve@r

Si tu veux un rand plus uniforme, il est conseillé de demander un rand() / RAND_MAX * 26

Ok, mais ce ne serait pas plutôt

Code:

26*(double)rand()/(double)RAND_MAX;

Sinon, ça renvoie toujours 0, non ?
20/09/2022, 12h26
-Eks-

Citation:

Envoyé par ypcman

Ok, mais ce ne serait pas plutôt

Code:

26*(double)rand()/(double)RAND_MAX;

Sinon, ça renvoie toujours 0, non ?

Oui.

Tu peux aussi le faire en castant seulement le numérateur ou le dénominateur de la division. Il n'est pas nécessaire de caster les deux.
20/09/2022, 12h26
Sve@r

Citation:

Envoyé par ypcman

Sinon, ça renvoie toujours 0, non ?

Exact, il faut diviser en double (me pensais en Python). Mais un seul cast suffit, une opération impliquant 2 opérandes se faisant toujours dans le type le plus large des deux 8-). A toi de choisir lequel tu veux caster.
20/09/2022, 14h42
Guesset

Youppie !

Bonjour,

A la lecture de l'assembleur, mon explication initiale redevient valide :ccool:.

En effet, les return ne sont pas exécutés in situ car seule la valeur de retour est préparée là où ils apparaissent (dans eax ou rax) pour être traitée seulement en fin de fonction. Le jmp systématique de fin du "then" pèse alors effectivement plus car plus fréquent dans la seconde fonction. Ceci d'autant plus que la ribambelle de call qui précèdent casse un peu le potentiel d'anticipation du jmp par le processeur.

Salutations
20/09/2022, 15h02
Sve@r
Citation:

Envoyé par ypcman

J'ai modifié mon code pour calculer un fact(rand()%26)

Désolé de revenir sur ce détail, mais pour être le plus impartial possible, il faudrait que les deux fonctions calculent les mêmes choses...

Accessoirement, pourquoi prendre la factorielle comme exemple? Ton but tel que tu l'exprimes c'est regarder comment se comporte if (truc_le_moins_probable) vs if (truc_le_plus_probable). Pourquoi ne pas écrire une fonction style
Code:

1 2 3 4 5 6 7 8 9 10 11 void fct1(int n) { if (n == 0) n=5; else n=10; sleep(1); } void fct2(int n) { if (n != 0) n=10; else n=5; sleep(1); }
Après si le sleep() change la donne sur les chronos, on peut le remplacer par autre chose (une boucle), l'essentiel est que les effets induits par la récursivité soient supprimés...
20/09/2022, 15h09
ypcman

Tu as raison. C'est juste que j'étais en train de coder une fct factoriel récursive lorsque j'ai voulu tester les 2 versions du if().
Pour le rand() aussi mais à relativiser car je boucle un grand nombre de fois :

Code:

define NOMBRE 10000000
20/09/2022, 17h45
Guesset

Factorielle récursive vs performances
Bonjour,

Coder une factorielle en récursif pour comprendre la récursivité pourquoi pas. Faire des mesures de performances dessus n'est pas loin de la perversité :D (il suffit de comparer à une simple boucle).

En outre le codage n'est pas très fiable car l'argument est déclaré comme int il peut donc être négatif ou nul. Badaboum ! : boucle infinie heureusement arrêtée (salement mais arrêté quand même) par la saturation de la pile.
Même en passant en unsigned, il est préférable d'écrire :
Code:

1 2 3 4 unsigned long fact_rec_1(int n) { if (n < 2) return 1; return n * fact_rec_1(n - 1); }
Salutations