Discussion :

[sebaaas]

Bonjour,

J'ai un petit programme qui lit un fichier image PGM de 720 x 560 que je met dans un tableau de 9 x 8.
Voici le 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
#include <stdio.h>
#include <stdlib.h>
 
int main(int argc, char *argv[])
{
    FILE* fichier = NULL;
    int tableau9x8[9][8];
    int i = 0;
    int j = 0;
    int k = 0;
    int l = 0;
 
    fichier = fopen("1.pgm", "r");//ouverture du fichier
    fseek(fichier, 15, SEEK_SET); // placement du curseur après l'entête du fichier PGM
 
    if (fichier != NULL)
    {
      //remplir le PGM dans un tableau
       for (j = 0; j < 560 ; j++)
       {
           for (i = 0; i < 720 ; i++)
           {
            k=i/80;
            l=j/70;
              tableau9x8[k][l]=tableau9x8[k][l]+ fgetc(fichier);
 
           }
       }
      // fermeture du fichier
        fclose(fichier);
 
    }
 
    return 0;
}

Or je trouve le programme assez lent. Est-ce du fait que je lise les caractère 1 par 1 (fgetc)?
Voyez vous un moyen d'accélérer la manœuvre ?

Merci

[Médinoc]

As-tu activé les optimisations sur ton compilateur?

[Kannagi]

optimisation ou pas du compilateur , la lecture du disque dur est très très lente.
Tu peux augmenter un peu la lecture en faisant une lecture avec fread et donc de faire ta boucle sur le buffer de ton image.

[Médinoc]

Mais de mémoire, fgetc() est déjà bufferisée.
Personnellement je commencerais par sortir le calcul de l de la boucle intérieure, mais n'importe quel optimiseur doit déjà en être capable, pour peu qu'il soit activé.

[Bousk]

Ton tableau n'est pas initialisé, tu vas avoir des résultats différents à chaque appel.
Ensuite, qu'entends-tu par lent ? La lecture depuis disque est lente, la seule façon de l'améliorer est de posséder un SSD.

[dalfab]

Le résultat obtenu n'est qu'un tableau aléatoire car non initialisé.
Avant d'optimiser, il est préférable de faire quelque chose qui ait un sens.
Tel que tu le lis, le fichier serait un fichier texte d'au moins 430215 caractères est-ce bien le cas? Lire au delà de la taille max d'un fichier peut peut-être ajouter les longueurs, mais version debug ou optimisé, ça ne devrait être sous la milliseconde.
Qu'entends-tu par lent ?

[sebaaas]

OK,

J'ai initialisé le tableau

Code :

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

int tableau9x8[9][8] = {{0}};

Afin d'accélérer le tout je vais mettre les fichiers en diskram.

Merci de vos conseils

[Sve@r]

Bonjour

Mais de mémoire, fgetc() est déjà bufferisée.

C'est vrai que la lecture disque est toujours bufferisée. Mais même bufferisée, lire n fois 1 caractère sera toujours plus lent que lire 1 fois n caractères. Dans le premier cas, il y a n fois appel de fonction avec n fois tout ce qui va avec et ça, même si c'est invisible et transparent, ce n'est pas gratuit.
De fait j'avais fait il y a quelques années des tests benchmark de ce type et globalement les fonctions style fgets ou fread donnaient de meilleurs résultats que fgetc. Bien sûr il y a aussi des effets liés à la taille de la zone lue qui peuvent parfois être contre intuitifs (par exemple ce n'est pas parce qu'on multiplie la taille de la zone à lire par 10 que ça va améliorer les performances x10 et parfois ça peut même les baisser) mais malgré tout ça reste préférable.

Personnellement je commencerais par sortir le calcul de l de la boucle intérieure, mais n'importe quel optimiseur doit déjà en être capable, pour peu qu'il soit activé.

Personnellement je pense qu'aucun optimiseur ne peut remplacer la réflexion et l'analyse personnelle. Il vaut mieux d'abord réfléchir et (comme tu le dis) sortir les traitements lourds des boucles si le fait de calculer dans la boucle n'apporte rien au résultat.
Une fois ce travail fait, si ensuite l'optimiseur peut faire des trucs en plus c'est cadeau.

[wistiti1234]

Les buffers utilisé par les fichiers sont contrôlé (activation, taille) par les commandes setbuf() / setvbuf().

Après, si la mémoire n'est pas un problème dans le programme, moi je lirais tous le fichier d'un seul coup dans un buffer temporaire et je travaillerait directement dessus. En plus de supprimer le morcellement des accès disque, ça éviterait également les quelques 720 x 560 appels/retour de fonctions de lecture (avec gestion de contexte, etc...).
Et puis, suivant l'algorithme qu'on va écrire derrière, ça faciliterait les accès non séquentielle à ces données (vs les multiples "seek()", si on voulait faire la même chose directement sur le fichier).

Par ailleur, il n'y a pas que le "l=j/70;" qui est redondant. On se rend bien compte que le "k=i/80;" aussi, aboutit 80% du temps au même résultat. Et celui-là, je suis pas certain que les optimiseurs savent en faire quelque chose.
Or, parmi les opérateurs de bases sur les entiers, la division est de très loin la plus coûteuse. Ca va dépendre des architectures, et je ne suis pas sûr de ce qu'il en est sur x86, mais '+', '-', '*' se règles généralement en un seul cycle d'horloge, tandis que la division peut en demander une bonne vingtaine ou quarantaine, suivant la plateforme.


Bon bien-sûr, sur PC, on n'a généralement pas besoin de se préoccuper de ce genre de détails et il est préférable de privilégier d'autres considération (réutilisation du code, lisibilité, maintenance, ...). Mais si un goulot d'étranglement critique a réellement été identifié, et en restant sur des boucles for, moi j'aurai proposé quelque chose comme ça:

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
char buf[720*560];
int tableau9x8[9][8] = {{0}};
 
 
size_t ret = fread(buf, 1, 720*560, fichier);
 
if( ret == (720*560) ){
    char *bufPtr = buf;
    for(int row=0; row!=8; row++){
        for(int r=70; r!=0; r--){
            for(int col=0; col!=9; col++){
                for(int c=80; c!=0; c--){
                    tableau9x8[col][row] += *bufPtr++;
                }
            }
        }
    }
}

[wistiti1234]

Pardon, sur x86, on dirait que la division peut approcher les 100 cycles! Probablement parce que l'ALU est taillé pour travailler en 64 bits, donc plus de bits à traiter...

[sebaaas]

Pardon, sur x86, on dirait que la division peut approcher les 100 cycles! Probablement parce que l'ALU est taillé pour travailler en 64 bits, donc plus de bits à traiter...

Intéressant

[sebaaas]

Les buffers utilisé par les fichiers sont contrôlé (activation, taille) par les commandes setbuf() / setvbuf().

Après, si la mémoire n'est pas un problème dans le programme, moi je lirais tous le fichier d'un seul coup dans un buffer temporaire et je travaillerait directement dessus. En plus de supprimer le morcellement des accès disque, ça éviterait également les quelques 720 x 560 appels/retour de fonctions de lecture (avec gestion de contexte, etc...).
Et puis, suivant l'algorithme qu'on va écrire derrière, ça faciliterait les accès non séquentielle à ces données (vs les multiples "seek()", si on voulait faire la même chose directement sur le fichier).

Par ailleur, il n'y a pas que le "l=j/70;" qui est redondant. On se rend bien compte que le "k=i/80;" aussi, aboutit 80% du temps au même résultat. Et celui-là, je suis pas certain que les optimiseurs savent en faire quelque chose.
Or, parmi les opérateurs de bases sur les entiers, la division est de très loin la plus coûteuse. Ca va dépendre des architectures, et je ne suis pas sûr de ce qu'il en est sur x86, mais '+', '-', '*' se règles généralement en un seul cycle d'horloge, tandis que la division peut en demander une bonne vingtaine ou quarantaine, suivant la plateforme.


Bon bien-sûr, sur PC, on n'a généralement pas besoin de se préoccuper de ce genre de détails et il est préférable de privilégier d'autres considération (réutilisation du code, lisibilité, maintenance, ...). Mais si un goulot d'étranglement critique a réellement été identifié, et en restant sur des boucles for, moi j'aurai proposé quelque chose comme ça:

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
char buf[720*560];
int tableau9x8[9][8] = {{0}};
 
 
size_t ret = fread(buf, 1, 720*560, fichier);
 
if( ret == (720*560) ){
    char *bufPtr = buf;
    for(int row=0; row!=8; row++){
        for(int r=70; r!=0; r--){
            for(int col=0; col!=9; col++){
                for(int c=80; c!=0; c--){
                    tableau9x8[col][row] += *bufPtr++;
                }
            }
        }
    }
}

Avec ma version le temps d'exécution était de +/- 0.0033
En déplaçant la /70 => 0.0032
En optimisant ("gcc -O3 -Wall - o test.o -c test.c" et "gcc -O3 -o test test.o") => 0.0019
Avec le code de wistiti1234 => 0.0013
Avec le code de wistiti1234 + optimisation => 0.00025
=> le programme tourne 13 x plus vite.
Merciiiiiiiiii à tous

[chrtophe]

Pardon, sur x86, on dirait que la division peut approcher les 100 cycles! Probablement parce que l'ALU est taillé pour travailler en 64 bits, donc plus de bits à traiter...

Une division c'est couteux en temps CPU, mais le compilateur peut utiliser les fonctions SIMD qui permettent la parallélisation de plusieurs calculs.

[sebaaas]

Code :

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

1
2
3
unsigned char buf[720*560];
....
unsigned char *bufPtr = buf;

..sinon, j'obtenais des nombres négatifs

[Sve@r]

..sinon, j'obtenais des nombres négatifs

Pas tout à fait. Que ce soit en signed ou unsigned, un nombre a toujours la même valeur binaire. Mais simplement en signed, le premier bit est pris comme bit de signe. Toutefois tant que tu ne changes pas de plage de valeurs, ça n'a absolument aucun impact dans les calculs. Mais si ensuite tu copies un signed short dans un signed long dont le bit de signe vaut 1 alors ce 1 est étendu au long pour conserver la valeur négative.
Exemple: tu définis un char qui vaut 0x7F (0111 1111). Tu lui ajoutes 1 il passe alors à 0x80 (1000 0000). Et ça, ça reste vrai en signed et unsigned.
Mais si ce char est unsigned et que tu le copies dans un short, le short vaudra 0x0080 (0000 0000 1000 0000).
Et si ce char est signed et que tu le copies dans un short, alors le short vaudra 0xFF80 (1111 1111 1000 0000).
Et tu remarqueras qu'on ne se préoccupe absolument pas de la caractéristique du short (signed/unsigned) dans cette transaction. Cette caractéristique ne prendra son sens que si on copie plus tard ce short dans un long.

Ensuite, au delà de la caractéristique signed/usigned de ton char (qui vaut toujours 0x80), il reste le souci de l'affichage.
Si tu l'affiches "%d" alors il est converti et affiché en signed int. Mais cette conversion dépend de sa nature signed/unsigned. S'il est signed le bit de signe s'étend ce qui donne 0xFFFF FF80 et affiché en signed int (avec complément à 2 et etc) ça redonne -128. Et s'il est unsigned il n'y a pas de bit de signe à étendre ce qui donne 0x0000 0080 soit 128.
Et si tu l'affiches "%u" alors il est converti et affiché en unsigned int. Et là encore cette conversion ne change pas ; ce qui change c'est juste l'affichage du résultat.
Donc s'il est signed le bit de signe s'étend ce qui donne 0xFFFF FF80 mais là affiché en unsigned int ça donne 4294967168. Et s'il est unsigned il n'y a pas de bit de signe à étendre ce qui donne donc toujours 0x0000 0080 soit 128.

Et si ensuite tu lui enlèves 1, que ce soit en sgned ou en unsigned il repasse à 0x7F (0111 1111)=127

De fait, ce petit programme d'exemple produit exactement ce résultat

Code c :

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
#include <stdio.h>
 
int main() {
	signed char sc=0x7F;
	unsigned char uc=0x7F;
 
	printf("uc=%d, sc=%d\n", uc, sc);
	printf("uc=%u, sc=%u\n", uc, sc);
	sc++;
	uc++;
	printf("uc=%d, sc=%d\n", uc, sc);
	printf("uc=%u, sc=%u\n", uc, sc);
	sc--;
	uc--;
	printf("uc=%d, sc=%d\n", uc, sc);
	printf("uc=%u, sc=%u\n", uc, sc);
}

Donc récapitulatif: tu travailles en signed/unsigned selon la plage de valeur que doivent prendre tes variables (et ça c'est très bien d'y penser car une copie signed, avec extension du bit de signe, prendra un poil plus de temps qu'une copie unsigned).
Et tu les affiches avec le format correspondant à la caractéristique que tu veux au résultat. C'est là qu'il faut connaitre ses formats printf "%d", "%u", "%ld", "%lu", "%hd", "%hu", "%o", "%x".

[wistiti1234]

C'est ce qui ce passait, chaque octets étant au final accumulé dans un int.
Mea-culpa, j'avais bêtement cru que le 'fgetc()' d'origine retournait un 'char'. Je pensais avoir respecté les types original, mais non non, il est bien définit en int

[foetus]

Mea-culpa, j'avais bêtement cru que le 'fgetc()' d'origine retournait un 'char'. Je pensais avoir respecté les types original, mais non non, il est bien définit en int

C'est parce que EOF est un entier (<- lien cpluscplus en anglais)
Dans un sens , il fallait que cette valeur soit différente d'une valeur d'1 char.


Édit : suite à la réponse de mon V.D.D. (voisin du dessous) je vais répondre à la question que tu te poses
L'encodage ASCII a des valeurs dans une plage entre 0x00 et 0x7F : donc tu n'auras pas la valeur 0xFF. Mais d'autres encodages MBCS et UTF-8 étendent l'ASCII et peuvent éventuellement avoir comme valeur 0xFF.
Sinon, si ce n'est pas du texte mais des données (comme des couleurs par exemple), on ne peut pas supposer que la valeur 0xFF soit utilisée ou pas.

[Sve@r]

Mea-culpa, j'avais bêtement cru que le 'fgetc()' d'origine retournait un 'char'. Je pensais avoir respecté les types original, mais non non, il est bien définit en int

Pour compléter la succinte mais exacte réponse de foetus, c'est pour arriver à différencier la valeur -1 (0xFFFF) renvoyée par fgetc() quand elle ne lit plus rien, du caractère ascii 255 (0xFF) éventuellement présent dans le fichier et donc lu comme tout autre caractère. Si tu stockes le retour de fgetc() dans un char, dans les deux cas tu vois 0xFF. Et si tu le stockes dans un int, alors quand tu lis le caractère ascii 255 tu obtiens 0x00FF (qui pourra être utilisé ensuite comme char sans souci grâce au cast implicite) et quand la fonction renvoie -1, alors tu récupères 0xFFFF.

Il y a aussi ce même genre d'astuce (jouer sur les emplacements des valeurs dans une variable) avec la fonction wait(). Elle attend la mort d'un fils et quand ledit fils meurt elle remplit une variable int indiquant la cause de la mort. S'il est mort de mort naturelle via exit(n) (n étant compris entre 0 et 255) alors la variable vaut simplement n (ce qui place "n" dans les 8 derniers bits de la variable). Et s'il a été tué via kill(m) (m étant là compris entre 1 et 255), alors la variable vaux m * 256 (ce qui place "m" dans les 8 premiers bits).
Ensuite ne reste qu'à regarder si les 8 premiers bits valent 0 (fin par exit()) ou pas (fin par kill()) et jouer avec les décalages pour récupérer la bonne valeur. Et il y a même des macros qui font tout ça à ta place.

[chrtophe]

fgetc() reads the next character from stream and returns it as an unsigned char cast to an int, or EOF on end of file or error.

Cela résume les explications données et aussi le temps de traitement lors de la lecture caractère par caractère.

Le format PGM est simple.

Tu as tout intérêt à lire avec les fonctions chaine, vu qu'en C, une chaine est un tableau de char. Comme tu connais la "largeur" de chaque ligne de l'image (et le nombre de lignes correspondant à la hauteur), tu n'auras qu'une seule boucle for à faire pour lire chaque ligne. Tu n'auras pas de conversion implicite en int.
Tu pourras la faire au besoin.

Dernier point, contrôles la signature du fichier .pgm (et sa validité). C'est une habitude qu'il faut prendre pour éviter les failles.

[wistiti1234]

Effectivement, je m'étais posé la question de la raison de ce int. En cherchant, j'ai vu que c'était à cause de cette 257ième valeur EOF .