Optimisation programme C

[flavdu44]

Bonjour,

je viens de créer un programme en C qui diminue la taille d'une bitmap par 2 et la resize. Le problème c'est que je dois l'optimiser afin qu'il soit plus rapide. Je pensais utiliser les pointeurs mais je ne vois pas vraiment comment faire. Voici 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
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
#include <stdio.h>
#include <stdlib.h> // malloc
#include <string.h> // memset
#include <stdint.h> // uintxx_t types
 
#include "time_measure.h"
#include "image_utils.h"
 
int basic_data_processing(process_data_t * process_data);
 
 
int init_process_data(process_data_t * process_data, int argc, const char * argv[]) {
	int status = 0, read_fd = -1;
	uint32_t i = 0;
	uint32_t width=0, height=0;
 
	if( process_data != NULL ) {
		memset(process_data, 0, sizeof(process_data_t));
		// affect processing function
		process_data->data_processing_function = basic_data_processing;
 
		switch( argc ) {
			case 2:
				// read BMP file
				read_fd = open(argv[1], O_RDONLY
#ifdef WIN32
											 | O_BINARY
#endif // WIN32
											 );
				if( read_fd != -1 ) {
					status = read_bmp_header(read_fd, &process_data->source_header);
					if( status != -1 ) {
						switch( process_data->source_header.bits_per_pixel ) {
							case 8 :
								status = read_bmp_file_8(read_fd, &process_data->source_header, &process_data->source_bitmap);
								if( status != -1 ) {
                                                                        width=process_data->source_header.width;
                                                                         height= process_data->source_header.height;
                                                                           printf("%d\n", height);
                                                                          printf("%d\n", width);
									status = 0; // status may be positive at this point
									// allocate and initialize destination bitmap
									process_data->destination_bitmap = (uint8_t *) malloc((process_data->source_header.width/2) * (process_data->source_header.height/2) * sizeof(uint8_t));
									if( process_data->destination_bitmap ) {
										process_data->output_file_path = suffixed_filename(argv[1], " (reduced).bmp");
									} else status = -2; // bitmap allocation issue
								} else printf("BMP content read failed\n");
								break;
							default:
								printf("\"%s\" : has %d bits per pixels only 8 bpp is supported\n", argv[1], process_data->source_header.bits_per_pixel);
								break;
						} // switch header.bits_per_pixel
					} else printf("BMP header read failed\n");
				} else printf("open file failed\n");
				break;
			default:
				printf("usage : %s <output BMP file path>\n", argv[0]);
				status = -3;
				break;
		}
	} else status = -1; // parameter issue
 
	return status;
}
 
/***************************Méthode Initiale*************************************/
int basic_data_processing(process_data_t * process_data) {
 
	uint32_t x = 0;
    uint32_t y = 0;
    int32_t pixel, pixel_droit, pixel_bas, pixel_diag, moyenne;
	int status = 0;
	uint32_t width=process_data->source_header.width, height= process_data->source_header.height;
	uint8_t * source_pointer = NULL;
	uint8_t * destination_pointer = NULL;
	uint32_t counter = 0;
 
 
	if( (process_data != NULL) && (process_data->source_bitmap != NULL) && (process_data->destination_bitmap != NULL) ) {
 
		source_pointer = process_data->source_bitmap;
		destination_pointer = process_data->destination_bitmap;
 
       for(y=0; y<height; y++){
                	for(x=0; x<width; x++){
 
                             pixel=source_pointer[x+y*width];
                             pixel_droit=source_pointer[x+1+y*width];
    	                     pixel_bas=source_pointer[x+(y+1)*width];
    	                     pixel_diag=source_pointer[(x+1)+(y+1)*width];
 
                             moyenne=(pixel+pixel_droit+pixel_bas+pixel_diag)/4;
 
                  if( destination_pointer != NULL ) {
 
                     destination_pointer[(x/2)+(y/2)*(width/2)] = moyenne;
 
                   }
                    x++;
              }
              y++;
        }
	} else status = -1; // parameter issue
 
	return status;
}
 
 
int dispose_process_data(process_data_t * process_data) {
	int status = 0;
	uint32_t width=process_data->source_header.width, height=process_data->source_header.height;
 
	if( (process_data != NULL) ) {
		if( process_data->source_bitmap != NULL ) {
			free(process_data->source_bitmap);
			process_data->source_bitmap = NULL;
		}
		if( process_data->destination_bitmap != NULL ) {
			if( process_data->output_file_path ) {
				// save bitmap in BMP format
				process_data->source_header.width = width/2;
                process_data->source_header.height=height/2;
 
				save_bitmap(process_data->output_file_path, &process_data->source_header, process_data->destination_bitmap);
			}
			free(process_data->destination_bitmap);
			process_data->destination_bitmap = NULL;
		}
	} else status = -1; // parameter issue
 
	return status;
}

Si quelqu'un à des idées je serais ravi.

Merci

[Joker-eph]

Les pointeurs ça "n'optimise" pas, c'est juste un moyen d'exprimer des constructions, "optimiser" c'est d'abord de l'algorithmie, et ensuite une réflexion sur l'architecture visée (hérarchie de cache, blocking des boucles, ...). En tenant compte du fait que tes boucles une fois traitée par le compilateur ne ressemble plus du tout à ce que tu avais en entrée.

Déjà je m'étonne du x++ et y++ ? Est-ce que le code est correct ?

[BufferBob]

comme ça au feeling j'aurais tendance à regarder à partir de la ligne 84 les deux boucles imbriquées, j'imagine que l'essentiel du traitement passe dedans

pour le moins tu peux sans doute éviter le recalcul à chaque ligne de choses comme "y*width", "(y+1)*width" à l'aide de variables intermédiaires/temporaires
l'emploi du type "register" pour x et y peut-être aussi, et ramener les divisions par 2 et par 4 respectivement à des décalages de 1 et 2 bits vers la droite

quelque chose comme ça :

Code c :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
    register uint32 x=0,y=0,yw1=0,yw2=0;
 
    for(y=0; y<height; y++){
        yw1 = y*width;
        yw2 = yw1 + width; /* plutot que de refaire la multiplication (y+1)*width */
        for(x=0; x<width; x++){
            pixel=source_pointer[x+yw1];
            pixel_droit=source_pointer[x+1+yw1];
            pixel_bas=source_pointer[x+yw2];
            pixel_diag=source_pointer[x+1+yw2];
            moyenne=(pixel+pixel_droit+pixel_bas+pixel_diag) >> 2;
            if( destination_pointer != NULL ) {
                destination_pointer[(x>>1)+(y>>1)*(width>>1)] = moyenne;
            }
            x++;
        }
        y++;
    }

mais c'est possiblement que des "bouts de ficelles", à voir si ça suffit à faire une différence significative

[flavdu44]

Bonjour,

Joker-eph, mes x++ et y++ me permettent de passer de 2 lignes en 2 lignes et 2 colonnes en 2 colonnes pour faire ma moyenne.

Merci BufferBob, tes modifications me permettent diminuer légèrement mon temps d'exécution.

[leternel]

Bonjour à toi!

Envoyé par flavdu44

Bonjour,
Joker-eph, mes x++ et y++ me permettent de passer de 2 lignes en 2 lignes et 2 colonnes en 2 colonnes pour faire ma moyenne.

Pour ca, il suffit de mettre x+=2 dans l'instruction d'incrémentation de la boucle

[flavdu44]

Merci, cela ma encore permis d'améliorer mes performances.

Je compte maintenant m'orienter vers des pointeur pour cette partie du code:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
 for(y=0; y<height; y+=2){
        yw1 = y*width;
        yw2 = yw1 + width; 
        for(x=0; x<width; x+=2){
            pixel=source_pointer[x+yw1];
            pixel_droit=source_pointer[x+1+yw1];
            pixel_bas=source_pointer[x+yw2];
            pixel_diag=source_pointer[x+1+yw2];
            moyenne=(pixel+pixel_droit+pixel_bas+pixel_diag) >> 2;
                destination_pointer[(x>>1)+(y>>1)*(width>>1)] = moyenne;
        }  
    }

J'ai essayer plusieurs trucs mai je n'arrive jamais à tomber sur les pixels que je veut.

[diogene]

Dérivé de la dernière version de ton code (et sauf erreur)

Code :

1
2
3
4
5
6
7
8
for(y=0; y<height; y+=2){
       uint8_t * p1 = source_pointer+y*width;
       uint8_t * p2 = p1+ width;
       uint8_t * pd = destination_pointer + (y>>1)*(width>>1);
       for(x=0; x<width; x+=2){
                pd[(x>>1)] = (p1[x]+p1[x+1]+p2[x]+p2[x+1]) >> 2;
       }  
 }

[flavdu44]

Merci diogene,

Ca fonctionne nikel et a bien optimisé mon code

[flavdu44]

Est-ce qu'il serait possible d'optimiser les boucles for ?

[transgohan]

En partant de la version de diogene on peut paralléliser le traitement (exécuter le traitement en le découpant et l'exécutant dans plusieurs threads).
Mais cela ne se fait pas sans une bonne compréhension de la parallélisation de tâche.
Surtout que suivant la taille de tes tableaux la parallélisation n'apportera pas forcement un gain de performance.

[leternel]

D'une manière générale, le meilleur principe d'optimisation est le suivant:
"la plus rapide manière de faire un calcul, c'est encore de ne pas le faire".
Autrement dit, la tache est environ optimisée si les seuls calculs sont les calculs utiles.
Le code de diogene est en ce sens optimal.

Tu veux réaliser remplir une image de taille N/2*M/2, et tu as N/2*(M+3)/2 affectation. Je ne vois pas qu'optimiser de plus.

Tu peux éventuellement modifier les affectations de pointeurs, il est possible que sur certaines architectures, tu gagnes quelques cycles… mais tu peux aussi perdre… c'est à voir.

Code :

1
2
3
4
5
6
7
8
9
10
11
uint8_t * p1 = source_pointer;
uint8_t * p2 = p1+ width;
uint8_t * pd = destination_pointer;
for(y=0; y<height; y+=2){
       p1 += y*width;
       p2 += y*width;
       pd += width>>1;
       for(x=0; x<width; x+=2){
                pd[(x>>1)] = (p1[x]+p1[x+1]+p2[x]+p2[x+1]) >> 2;
       } 
}

[Joker-eph]

Envoyé par leternel

D'une manière générale, le meilleur principe d'optimisation est le suivant:
"la plus rapide manière de faire un calcul, c'est encore de ne pas le faire".
Autrement dit, la tache est environ optimisée si les seuls calculs sont les calculs utiles.

Le "environ" laisse ouvert beaucoup de choses... Quid des caches par exemple ? Y a plein de raison qui font qu'il y a beaucoup à gagner même en "ne faisant que des calculs utiles".

Optimiser les boucles "for" ça peut être du tiling, de la vectorisation, du multithreading, du pipeline (peut-être pas ici...), ou une combinaison de tout ça. Mais ne pas oublier que le compilateur fait déjà plein de choses (à moins de compiler en -O0).

[leternel]

pour faire mieux, il faut connaitre précisément les caractéristiques techniques du processeur, dont: la taille des caches, le jeu d'instructions, le nombre de registres, et d'autre trucs qu'un compilo fera de toute facon bien mieux que toi…
à moi d'être implémenteur de compilateur, bien évidemment.

Mon "environ" optimal signifie que l'algorithme ne peux pas faire mieux. Il ne reste que le gagne-petit, et l'artillerie lourde (multithread, assembleur…)

[transgohan]

Le compilateur n'a pas accès à toutes les informations de ton matériel. Il ne sait pas quel type de cache est implémenté (ton OS ne le sait pas non plus d'ailleurs), à savoir si c'est un pass-through ou non par exemple ce qui peut énormément changer la donne.
Et on doit bien trouver d'autres paramètres qui peuvent changer la donne, mais je pense que déjà celui-ci est le plus flagrant.

Pour ceux qui n'ont pas envie de se potasser de la doc pour comprendre ce concept : un cache implémentant une politique de pass-through ne va pas charger une donnée en cache L1, elle va transiter directement en cache L2 lors de son écriture. Si cette donnée venait à être demandée en lecture elle sera rapatriée dans le cache L1 et y restera (pour utilisation en lecture ou écriture).

[Joker-eph]

Envoyé par leternel

pour faire mieux, il faut connaitre précisément les caractéristiques techniques du processeur, dont: la taille des caches, le jeu d'instructions, le nombre de registres, et d'autre trucs qu'un compilo fera de toute facon bien mieux que toi…
à moi d'être implémenteur de compilateur, bien évidemment.

Mon "environ" optimal signifie que l'algorithme ne peux pas faire mieux. Il ne reste que le gagne-petit, et l'artillerie lourde (multithread, assembleur…)

Je disconviens respectueusement
Sans connaitre ces paramètres, il y a des motifs qui sont constant. Par exemple à algorithme égal tu peux toujours l'écrire d'une manière qui favorise l'utilisation d'un cache, comme parcourir des tableaux à deux dimensions suivant les lignes et non les colonnes...
Ensuite tu peux déjà faire un blocking pour une taille de L1 que tu sais inférieur à ton cache L1 (en général 32k sur un proc intel).
Enfin il y a la vectorisation et la parallélisation, voir les options de gcc (ou icc).
Bref, sinon voir les papiers sur le compilateur source-à-source à source Pluto, qui traite ce genre de code en appliquant toutes ces optimisations et en te régénérant un code C à passer à gcc.

Et pour info voilà ce que l'OS peut me dire sur mon cache :

$ grep . /sys/devices/system/cpu/cpu0/cache/index*/*
/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size:64
/sys/devices/system/cpu/cpu0/cache/index0/level:1
/sys/devices/system/cpu/cpu0/cache/index0/number_of_sets:64
/sys/devices/system/cpu/cpu0/cache/index0/physical_line_partition:1
/sys/devices/system/cpu/cpu0/cache/index0/shared_cpu_list:0
/sys/devices/system/cpu/cpu0/cache/index0/shared_cpu_map:00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000001
/sys/devices/system/cpu/cpu0/cache/index0/size:32K
/sys/devices/system/cpu/cpu0/cache/index0/type:Data
/sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity:8
/sys/devices/system/cpu/cpu0/cache/index1/coherency_line_size:64
/sys/devices/system/cpu/cpu0/cache/index1/level:1
/sys/devices/system/cpu/cpu0/cache/index1/number_of_sets:64
/sys/devices/system/cpu/cpu0/cache/index1/physical_line_partition:1
/sys/devices/system/cpu/cpu0/cache/index1/shared_cpu_list:0
/sys/devices/system/cpu/cpu0/cache/index1/shared_cpu_map:00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000001
/sys/devices/system/cpu/cpu0/cache/index1/size:32K
/sys/devices/system/cpu/cpu0/cache/index1/type:Instruction
/sys/devices/system/cpu/cpu0/cache/index1/ways_of_associativity:8
/sys/devices/system/cpu/cpu0/cache/index2/coherency_line_size:64
/sys/devices/system/cpu/cpu0/cache/index2/level:2
/sys/devices/system/cpu/cpu0/cache/index2/number_of_sets:4096
/sys/devices/system/cpu/cpu0/cache/index2/physical_line_partition:1
/sys/devices/system/cpu/cpu0/cache/index2/shared_cpu_list:0-1
/sys/devices/system/cpu/cpu0/cache/index2/shared_cpu_map:00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000003
/sys/devices/system/cpu/cpu0/cache/index2/size:6144K
/sys/devices/system/cpu/cpu0/cache/index2/type:Unified
/sys/devices/system/cpu/cpu0/cache/index2/ways_of_associativity:24

[Ngork]

En suivant ce fil de discussion, tout-à-fait passionnant, j'ai eu envie de me pencher à nouveau sur l'optimisation en faisant un certain nombre de tests systématiques (compilation avec gcc -O2).

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
int main()
{
  unsigned long long int s=0;
  unsigned int i,j;
 
 
  for (i=0; i<1000000000; i++)
    {
      for (j=1; j<i; j++)
        {
          s+=i;
        }
    }
 
  printf("%llu",s);
 
  return 0;
}

Cela donne un temps moyen de 4,2 secondes sur ma bécane ...

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
unsigned int i,j;
unsigned long long int s=0;
 
int main()
{
  for (i=0; i<1000000000; i++)
    {
      for (j=1; j<i; j++)
        {
          s+=i;
        }
    }
 
  printf("%llu",s);
 
  return 0;
}

Celui-ci, en sortant les déclarations de variables de la fonction main, ne prend plus que 2,8 secondes en moyenne !

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
unsigned int i,j,n=0;
unsigned long long int s=0;
 
int main()
{
  for (i=0; i<1000000000; i++)
    {
      for (j=1; j<n; j++)
        {
          s+=n;
        }
 
      n++;
    }
 
  printf("%llu",s);
 
  return 0;
}

Enfin, ce code avec une variable de plus, a priori superflue, produit un temps d'exécution de 1,9 secondes en moyenne !!!

Si vous avez une idée pour expliquer ces résultats bizarres, je suis preneur !

[Kirilenko]

Bonsoir,

Pour effectuer ce genre de comparatifs, il est souvent de mise de jeter un coup d'œil au code ASM généré, ainsi que de préciser la version du compilateur. Chez moi, avec les mêmes codes et les mêmes options de compilation, j'ai des résultats exactement inverses.

Bonne soirée !

[Ngork]

Oui, bien sûr que j'ai regardé le code assembleur, ce qui m'a évidemment confirmé que le code généré est plus rapide mais ne répond pas à ma question, qui est : pourquoi un compilateur C comme gcc avec l'option O2 a-t-il produit un code plus rapide et mieux optimisé avec ces modifications qui selon toute logique devraient produire un code plus lent (le code avec la variable superflue est deux fois plus rapide dans mes tests que celui sans variable superflue) ?

Je serais d'autant plus intéressé par une réponse sur ce sujet que j'ai obtenu peu après des résultats un peu différents avec gcc (MinGW) en version 4.7.2 sous Windows 7 par rapport à gcc en version 4.6.3 sur une distrib Mageia :

gcc 4.6.3 sous Linux : 4,2 s / 2,8 s / 1,9 s
gcc 4.7.2 sous Windows 7 : 3,7 s / 3,9 s / 2,4 s

L'introduction de la variable superflue conduit donc encore à une meilleure optimisation mais de moindre importance, alors que le passage des variables locales en variables globales ralentit cette fois l'exécution (ce qui pour le coup me paraît plus logique ...).
Au delà de ça, ce qui m'étonne et m'inquiète un tantinet, c'est la grande disparité de ces résultats d'une version de compilo à l'autre, particulièrement en tenant compte des résultats exactement inverses obtenus par Kirilenko !

Car si une optimisation, voire un simple style de programmation, peut induire des écarts de vitesse du simple au double puis les inverser selon la version du compilo, quel est alors l'intérêt de l'optimisation (hors l'optimisation algorithmique qui n'est pas ici en cause) ?
Exemple : j'écris mon code puis, comme la vitesse est un point essentiel du logiciel que je veux produire, j'optimise soigneusement les parties gourmandes du source avec un compilo x en version 1.1, réussissant à multiplier par trois la vitesse d'exécution.
Deux ans plus tard, j'ai besoin de modifier ce prog, ce que je fais, puis je le recompile avec le compilo x maintenant passé en version 1.3, voire avec un nouveau compilo y, et là ... patatras, mon programme super rapide devient une grosse limace !

Je suis vraiment le seul à trouver ça gênant ?

[Joker-eph]

Amusant avec GCC 4.4 aucune différence de perf, et avec 4.6 je passe de 1.39s à 2s en remplaçant i par n.

[transgohan]

Mais dites moi... Vous tournez sur une configuration faite pour les benchmarks ?
Non parce que vous savez faire tourner des tests de performance sur un OS de bureautique et qui plus est non temps réel et s'étonner de différences de l'ordre de la centaine de milliseconde c'est du n'importe quoi...

Et de plus la moyenne n'apporte pas grand chose comme résultat, elle doit être comparée avec l'écart type au minimum.

La tolérance sur ce genre de configuration est de l'ordre de 1-5 secondes pour des traitements long (et on peut descendre à l'ordre de 300-800 ms en sachant ce que l'on fait : fermer / couper tout ce que l'on peut, et c'est pas une mince affaire sur un OS de bureautique...).