Discussion :

[dridri85]

Bonjour,
voilà je faisais tout simplement un code qui calcule la suite de Fibonacci (le but étant de trouver une valeur qui soit pandigital au début et à la fin du nombre).

Bref, j'ai fais ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
int main(void){	
	int* a = (int*)malloc(sizeof(int)*131072);
	int* b = (int*)malloc(sizeof(int)*131072);
	int* c = (int*)malloc(sizeof(int)*131072);
	int* tmp;
	a[0] = 1;
	b[0] = 1;
 
	int i = 0;
	int r = 0;
	int res;
	int j = 0;
	int len = 1;
	for(;;){
		r = 0;
		for(j=0; j<len; j++){
			res = r + a[j] + b[j];
			c[j] = res % 10;
			r = res / 10;
		}
		c[len] = r;
		len += r;
 
		tmp = b;
		b = a;
		a = c;
		c = tmp;
 
		i++;
		if(len > 9 && pandigital(c) && pandigital(c+len-9)){
			printf("Found !\n");
			break;
		}
	}
 
	return 0;
}

Son temps d'exécution est d'environ 240 secondes.

Un ami m'a proposé de le faire de cette façon, qui s'exécute en seulement 100 secondes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
int main(void){
	int* a = (int*)malloc(sizeof(int)*1);
	int* b = (int*)malloc(sizeof(int)*1);
	int* c = NULL;
 
	a[0] = 1;
	b[0] = 1;
 
	int i = 0;
	int r = 0;
	int res;
	int j = 0;
	int len = 1;
	for(;;){
		c = malloc((len+1) * sizeof(int));
		c[len] = 0;
		r = 0;
		for(j=0; j<len; j++){
			res = r + a[j] + b[j];
			c[j] = res % 10;
			r = res / 10;
		}
		c[len] = r;
		len += r;
 
		free(b);
		b = a;
		a = c;
 
		i++;
 
	}
 
	return 0;
}

La différence étant qu'au lieu de faire une rotation des pointeurs, on alloue un nouvel espace pour le prochain nombre et on libère celui qui ne sert plus (la valeur à n-2)

Je n'arrive pas à comprendre comment un malloc et un free peuvent être plus rapide qu'un simple échange de pointeurs.
Je pensais que l'échange prenait peut-être du temps, donc si je mets malloc/free et rotation à la fois le code reste tout de même rapide.

J'ai pensé à un souci d'alignement des buffers, donc j'ai essayé à coup de memalign avec différentes valeurs mais sans résultats...


Si une âme éclairée pouvait passer par là j'aimerai bien comprendre

Merci

[souviron34]

déjà je ne sais pas si c'est une erreur de reopiage mais l n'y a pas de conditions d'arrêt dans le 2 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
		if(len > 9 && pandigital(c) && pandigital(c+len-9)){
			printf("Found !\n");
			break;

D'autre part, dans quelles condiitons/avec quel outil/fonction as-tu mésuré le temps ??

Je soupçonne pas d'une manière reproductible..

Enfin, ce qui prend du temps dans vos 2 calculs sont les calculs d'adresse et les divisions..

Pour les adresses :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
		for(j=0; j<len; j++){
			res = r + a[j] + b[j];
			c[j] = res % 10;
			r = res / 10;
		}

peut se tansformer aisément en :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
		for(j=0; j<len; j++){
			res = r + *a + *b;
			*c = res % 10;
			r = res / 10;
 
                                      a++, b++, c++ ;
		}

ou tu viens de gagner 3 multiplications par itération.

ensuite, modifier r = res / 0 par r = res * 0.10 (une division coûte beaucoup plus qu"une multiplication)


Mais comme tous les nombres sont des int, les décalages de bits seraient encore mieux...

[aslo92]

Bonjour dridri85,

je voulais essayer de mesurer le temps d'éxécution des 2 codes mais je n'ai pas la définition de la fonction pandigital.

[aslo92]

Tu as dû te tromper lors de ta mesure de temps car mes mesures sur un nombre défini de boucles (pour sortir sans la fonction pandigital) me donne un meilleur temps pour ton code.

Ce qui me parraît normal vu que le malloc prend plus de temps que l'affectation d'une variable.

Sauf erreur de ma part, je pense que si tu fais :

a = b;
b = c;

ça marche encore et tu économises tmp = b et c = tmp qui sont inutiles pour le tour suivant.

Le i++ est inutile aussi.

Il serait aussi souhaitable que tu libères la mémoire utilisée par a, b, c à la fin du programme

[dridri85]

@souviron34: Effectivement j'ai oublié la condition d'arrêt en copiant le second code.

Pour mesurer le temps j'utilise bêtement un GetTickCount() au début et à la fin du programme.
Alors pour la technique du *c au lieu de c[i], je perds en performance, je ne comprends vraiment pas...


La fonction pandigitale n'est pas nécessaire pour les tests, elle ne change pas le temps d'exécution du programme.
aslo92: Tu as quels résultats de temps pour ton nombre d'itération ?
Et sinon, pour le c=tmp, si je en le fait pas je me retrouve avec b et c qui pointent à la même adresse (puisque juste avant on fait b=c).
Et le i++ n'est pas inutile dans le sens où il me permet de connaitre mon résultat final: quel nombre de fibonacci est pandigital au début et à la fin.


En tout cas merci à vous pour vos suggestion

[BlueMonkey]

Bonsoir,

Alors pour la technique du *c au lieu de c[i], je perds en performance, je ne comprends vraiment pas...

Suivant la version de code utilisé, il faut bien faire attention au que les pointeurs a,b,c se déplace dans le cas des *c ... c++.
Ca oblige donc à passer par des pointeurs intermédiaires pour garder l'adresse allouée par le malloc.

Une petite optimisation suplémentaire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
res = r + *a + *b;
*c = res % 10;
r = res / 10;
a++, b++, c++ ;

est équivalent à la suite, en évitant une ligne.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
res = r + *(a++) + *(b++);
*(c++) = res % 10;
r = res / 10;

Maintenant je suis assez surpris des différences de temps obtenu suivant les méthode (c[i] ou *c. Dans mon esprit, un bon compilateur avec les options
d'optimisation activées, le résultat devrait être à peu près le même.

modifier r = res / 10 par r = res * 0.10 (une division coûte beaucoup plus qu"une multiplication)

En théorie c'est vrai. Mais sur ma machine tests montrent que dans ce cas particulier la division sur utilisant des entiers,
reste plus rapide que le produit avec un flottant (perte temps sur les conversion de type implicite ?)

Question : Est-ce que le code exécuté se trouve dans une fonction appelé plusieurs fois?
Parce que le malloc d'un gros bloque mémoire consécutif doit être relativement long. Donc s'il est répété plusieurs fois ...

[souviron34]

Pour mesurer le temps j'utilise bêtement un GetTickCount() au début et à la fin du programme.
Alors pour la technique du *c au lieu de c[i], je perds en performance, je ne comprends vraiment pas...

D'une part, pour aavoir des mesures correctes, il faut faire des moyennes sur un grand nombre : boucler 1000, 10 000 ou 100 000 fois, et en tirer la moyenne.

D'autre part, c'est juste autour de la fonction qu'il faut entourer par le calcul.

Enfin, il faut s'assurer que cela se passe dans les mêmes conditions : qu'il n'y a rien d'autre qui tourne en // (style une interface, un soft de fond...) qui pourraiy gêner la mesure en ayant une activité parallèle, en "déloadant" ou "reloadant" une partie du programme..

[dridri85]

Cette fonction n'est appelée qu'une seule fois.
Bien sûr j'exécute toujours dans les mêmes conditions, mais même si il y a un peu d'écart je passe quand même là de 240 à 100 secondes.

J'ai bien sûr essayé toutes les techniques que vous proposez, mais j'en reviens toujours au même résultat : le second code (utilisant malloc est free) est beaucoup plus rapide que le premier (qui inverse simplement les pointeurs).
Je comprends vraiment pas là...

[diogene]

le second code (utilisant malloc est free) est beaucoup plus rapide que le premier (qui inverse simplement les pointeurs).

Avec le même compilateur, les mêmes options de compilation, la même machine et en ayant vérifié que les résultats (valeurs finales de i, len , du début et de la fin du tableau des valeurs) sont les mêmes ?

[souviron34]

Cette fonction n'est appelée qu'une seule fois.

je ne parle pas de ça : je dis qu'il faut l'appeler 10 000 ou 100000 fois et faire la moyenne du delta de temps pour avoir une estimation correcte..

En ne l'appelant qu'une fois il y a d'autres trucs qui peuvent rentrer en ligne de compte (des threads, des chargements de partie de prog..)

[BlueMonkey]

Salut,

Je crois qu'il y a méprise.

dridri85Cette fonction n'est appelée qu'une seule fois.

répond à

BlueMonkey post#6: Question : Est-ce que le code exécuté se trouve dans une fonction appelé plusieurs fois?
Parce que le malloc d'un gros bloque mémoire consécutif doit être relativement long. Donc s'il est répété plusieurs fois ...

[dridri85]

Oui il y a petite confusion

Hum en fait j'ai pas fait 100 000 tests, mais à chaque fois le résultat est strictement identique à 0.1s près (j'ai un processeur multi-coeurs donc il est rarement à court de ressources)


diogene@: Bien sûr j'utilise le même compilateur, en fait j'utilise le même code en commentant l'une ou l'autre méthode.

[souviron34]

Si une âme éclairée pouvait passer par là j'aimerai bien comprendre

J'ai regardé d'un peu plus près le code..

Et...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
         len = 1 ;
	for(;;){
		for(j=0; j<len; j++){
                          ...
		}
		len += r;                        ...
		if(len > 9 )
	              break;
	}

implique que on ne fait pas plus de 9 fois la boucle (au grand max, à condtion que r soit toujours 1 au plus)


D'autre part (2ième algo) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	int* a = (int*)malloc(sizeof(int)*1);
	int* b = (int*)malloc(sizeof(int)*1);
            ....
	for(;;){
		c = malloc((len+1) * sizeof(int));
                         ....
		for(j=0; j<len; j++){
			res = r + a[j] + b[j];
			c[j] = res % 10;
			r = res / 10;
		}
		c[len] = r;
		len += r;
                          ...
		b = a;
		a = c; 

  }

me semble totalement faux : d'abord tu stockes dans c[1] au premier coup, et non je pense c[0]... Ensuite :

* par exemple au premier tour on a a[0] = b[0] = 1, donc res=2, c[1] = 0, et r=0 et len finit toujours à 1.

* au 2ième tour, on a b[0] = ancien a[0] = 1, et a[0] = ancien c[0] = indéfini (non affecté), disons xxxxx, donc res = xxxxx%10, c[1] = xxxxx (vraisemblablement n'importe quoi) , et r = xxxxx/10, et len finit toujours avec xxxxx+1, avec vraisemblablement xxxxx > 9, donc on s'arrête.

Alors je ne sais pas trop ce que ça fait au total, je suppose que c'est pour ça que ça va plus vite, tu ne dois tourner que 2 fois..

Essaye déjà d'affecter c[0] à l'initialisation..


D'autre part, avec ce 2ième algo, dès la 2ième boucle, si ton r peut être supérieur à 0, tu débordes en mémoire..

[dridri85]

Juste pour être clair, les deux codes s'exécutent sans rencontrer la moindre erreur et leur résultat est strictement identique : i est égal à 131000 et quelques.

D'abord la condition n'est pas
if(len > 9 )
mais
if(len > 9 && pandigital(c) && pandigital(c+len-9))
Ce qui n'est pas le cas avant la 131000 et quelques nièmes boucle.


Et niveau algorithme je vois pas bien ce qui pose problème : Au premier tour c'est bien c[0] qui est affecté et non c[1] =>
c[j] = res % 10; // avec j=0
Et sinon r n'est jamais supérieur à 1 car les additions se font forcément avec des valeurs comprises entre 0 et 9

[souviron34]

Juste pour être clair, les deux codes s'exécutent sans rencontrer la moindre erreur et leur résultat est strictement identique : i est égal à 131000 et quelques.

Ce qui ne veut rien dire : un code qui a l'air de tourner sans erreur peut en conteni..

D'abord la condition n'est pas
if(len > 9 )
mais
if(len > 9 && pandigital(c) && pandigital(c+len-9))
Ce qui n'est pas le cas avant la 131000 et quelques nièmes boucle.

C'est toi qui a dit que ça n'avait pas d'importance (post #5)

Et niveau algorithme je vois pas bien ce qui pose problème : Au premier tour c'est bien c[0] qui est affecté et non c[1] =>
c[j] = res % 10; // avec j=0

Sans doute mais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
	int len = 1;
	for(;;){
		c = malloc((len+1) * sizeof(int));
		c[len] = 0;
		r = 0;
		for(j=0; j<len; j++){
			res = r + a[j] + b[j];
			c[j] = res % 10;
			r = res / 10;
		}
		c[len] = r;

[aslo92]

Bonjour,

J'utilise l'instruction assembleur rdtsc pour mesurer le temps. Cette instruction permet de lire le compteur clock du processeur. La précision de la mesure dépend donc de la fréquence du processeur.

J'ai refait le test sur plusieurs boucles et cette fois je trouve des résultats différents:

Ton programme : 23667585 coups d'horloge cpu
Le programme de ton ami: 16084982 coups d'horloge cpu
Ton programme modifié: 3273034 coups d'horloge cpu

Je crois que j'ai l'explication de la différence de performance que tu observes:

Dans ton programme, tu alloues 3 blocs de 131072 octets * sizeof(int).
Dans le programme de ton ami, au démarrage, on n'alloue que 1 * sizeof(int).

Je pense que la différence de temps vient de l'utilisation du cache par le processeur.

En effet dans ton cas, les buffers sont gros et les chances de cache miss sont donc plus importantes, ce qui entraine des pénalités (rechargement, déchargement du cache)

Dans le cas de ton ami, son programme débute avec des buffers ne contenant qu'un entier. Au début de l'éxécution, les chances de cache miss sont nulles. Par la suite, la taille des buffers augmentent et le temps d'exécution et le nombre de cache miss devrait augmenter.

Pour valider cette interprétation, il faudrait pouvoir utiliser l'outil VTUNE d'Intel que j'ai déjà utilisé mais que ne n'ai pas actuellement.

J'ai toutefois modifié ton programme pour essayer de faire mieux en partant de cette hypothèse.
Je suppose que le processeur met dans le cache la pile du programme pour accéder rapidement aux variables locales.
J'ai donc alloué les buffers sur la pile en créant un tableau d'entier de taille 3 * 131072. Mon buffer est donc alloué sur le tas local au lieu du tas global (malloc) et il est libéré automatiquement à la sortie de la fonction.

Ensuite, j'ai divisé ce tableau en 3 zones a, b, c.
Pour améliorer encore les choses, j'ai modifié le contenu de ta boucle j pour éliminer les divisions. Je les ai donc remplacées par un test sur la présence ou non de la retenue (res >= 10).

Mes mesures me donnent une accélération d'un facteur 5.
Voici le programme que je te propose:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
int main(void){	
    int  mem[131072 * 3];
    int* a = mem;
    int* b = a + 131072;
    int* c = b + 131072;
    int* tmp;
    a[0] = 1;
    b[0] = 1;
 
    int i = 0;
    int r = 0;
    int res;
    int j = 0;
    int len = 1;
    for(;;){
        r = 0;
        for(j=0; j<len; j++){
            c[j] = r + a[j] + b[j];
            if (c[j] >= 10)
            {
                c[j] -= 10;
                r = 1;
            }
            else
            {
                r = 0;
            }
        }
        c[len] = r;
        len += r;
 
        tmp = b;
        b = a;
        a = c;
        c = tmp;
 
        i++;
        if(len > 9 && pandigital(c) && pandigital(c+len-9)){
            printf("Found !\n");
            break;
        }
     }
 
     return 0;
}

Dis-moi ce que tu en penses et s'il donne toujours le bon résultat ?

[diogene]

Il n'y a chez moi aucune différence de temps significative entre les deux codes (différence < 0.5%) en faisant tourner les codes en remplaçant le test if(len > 9 && pandigital(c) && pandigital(c+len-9))... par un if (i == 135000) break; .

Remarque :
A la fin, j'ai len à 28214. Pourquoi fais-tu une alloc de 131072

Se peut-il qu'il y ait des problèmes de cache chez toi avec des tableaux aussi gros ?

[dridri85]

Niveau résultat je me suis trompé c'est dans les 330xxx et non 131xxx

aslo92: merci pour tes tests, je croyais avoir fait le tour des possibilités mais c'est vrai que le cache est une part importante.
Mais dans mon cas je n'ai pas d'accélération x5, car ton code s'exécute en 226 secondes (contre 240 pour l'original). Je ne connais pas l'assembleur x86 du coup je vois pas trop comment utiliser rdtsc
Sinon pour le test de la retenue, j'aurai cru qu'une division et un modulo consommeraient moins de cycles processeur que des tests et des jumps.

[diogene]

Niveau résultat je me suis trompé c'est dans les 330xxx et non 131xxx

C'est pas spécialement comique, car ça nous fait perdre du temps. Il faut qu'on soit sûr des conditions dans lesquelles on travaille.
Peux-tu donner la valeur finale de i et len ainsi que les 10 premières valeurs de c[] à la fin du calcul?
Pendant que tu y es, donne aussi le code de pandigital() que tu utilises, parce qu'une bonne partie du temps de calcul doit être passé dans cette fonction.

[dridri85]

Mince je croyais avoir donné le code de pandigital dans un de mes posts..

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
int pandigital(int* s){
	int m = 0, i;
	for (i=0; i<9; i++) m |= 1 << (s[i]-1);
	return m == 0x1FF;
}

Les dix premières valeurs sont tout simplement celles de la suite de Fibonacci :
1
1
2
3
5
8
13
21
34
55
Fn = F(n-1) + F(n-2)

La valeur finale exacte de i est donc 329468, qui est la valeur correcte j'ai bien vérifié, avec une longueur de 68855 chiffres.