Programme "lent" en c(lecture image)

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:

---

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

As-tu activé les optimisations sur ton compilateur?

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.

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é.

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.

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 ?

OK,

J'ai initialisé le tableau

Code:

---

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

---

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

Merci de vos conseils

Bonjour

Citation:

---

Envoyé par Médinoc

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.

Citation:

---

Envoyé par Médinoc

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.

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:

---

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++; } } } } }

---

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...

Citation:

---

Envoyé par 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...

---

Intéressant

Citation:

---

Envoyé par 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:

---

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

Citation:

---

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.

Code:

---

1 2 3

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

---

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

Citation:

---

Envoyé par sebaaas

..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:

---

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".

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

Citation:

---

Envoyé par wistiti1234

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

---

:whistle: C'est parce que EOF est un entier (<- lien cpluscplus en anglais)
Dans un sens :mrgreen:, 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 :mrgreen:
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.

Citation:

---

Envoyé par wistiti1234

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.

Citation:

---

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.

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 :P.

Citation:

---

Envoyé par 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...

---

Sauf que c'est pour le Intel P4 , P6 et AMD K7 , en gros c'est obsolètes :mrgreen:
Si ces procs fait autant de cycles ,c'est surtout que ce genre de processeur avait une pipeline extrêmement grande (pour atteindre des fréquence élevé notamment) ,du coup a chaque pipeline stall tu te bouffer une trentaines de cycles (même pour une simple addition).
D'ailleurs je prendrais des pincettes sur les chiffres mis sur ce pdf , ça me semble assez fantaisiste.

De nos jours les divisions peuvent atteindre que quelque cycle (voir 1 cycle sur les flottants en utilisant les instructions SSE), la solution d'intel et amd est de multiplier énormément d'ALU (facilement plus de 6) donc la pipeline peut continuer sans se bloquer.
Il faut savoir que théoriquement de nos jours tout peux s’exécuter sur un cycle , voir même plusieurs instruction par cycle.
J'ai fait des test sur des proco modernes (années 2010 et plus) , sur les dernier procs Intel/ryzen ça tourne à 4 IPC , et ça même pour des calculs lourd (comme la multiplications de matrice ou la transformation perspective donc multiplication+division).

Par contre ce que je trouve stupide sur la doc c'est qu'il est bel et bien impossible de prédire la vitesse d'une instruction , cela dépend de l'état de la pipeline et pas des instructions en elle même (le proc ne bloque jamais la pipeline sauf en cas de besoin ).

Citation:

---

Envoyé par Kannagi

Sauf que c'est pour le Intel P4 , P6 et AMD K7 , en gros c'est obsolètes :mrgreen:
Si ces procs fait autant de cycles ,c'est surtout que ce genre de processeur avait une pipeline extrêmement grande (pour atteindre des fréquence élevé notamment) ,du coup a chaque pipeline stall tu te bouffer une trentaines de cycles (même pour une simple addition).
D'ailleurs je prendrais des pincettes sur les chiffres mis sur ce pdf , ça me semble assez fantaisiste.

---

Regarde un petit peu mieux, il s'agit de toutes les architectures core (Haswell, Broadwell, Skylake, etc...). Ca ne me paraît pas particulièrement vieux :mrgreen:
P4 dépasse allègrement les 100 cycles (~150), mais c'est bien les dernières génération Intel (à ~90) que j'avais dans le viseur.
Et de toute façon, on ne peut pas présumé sur quelle plateforme tournera un soft, donc il vaut mieux évoquer les chiffres les plus pessimistes, plutôt que de mettre en avant les beaux scores ZEN...
Par contre je te rejoins pour la qualité de ce pdf. J'ai depuis trouvé d'autres sources qui me paraissent un petit peu plus digne de confiance et où il ne serait plus question que de 30 à 40 cycles, en gros pour toutes les plateformes (sauf rares extrêmes).

Citation:

---

Envoyé par Kannagi

De nos jours les divisions peuvent atteindre que quelque cycle (voir 1 cycle sur les flottants en utilisant les instructions SSE), la solution d'intel et amd est de multiplier énormément d'ALU (facilement plus de 6) donc la pipeline peut continuer sans se bloquer.
Il faut savoir que théoriquement de nos jours tout peux s’exécuter sur un cycle , voir même plusieurs instruction par cycle.
J'ai fait des test sur des proco modernes (années 2010 et plus) , sur les dernier procs Intel/ryzen ça tourne à 4 IPC , et ça même pour des calculs lourd (comme la multiplications de matrice ou la transformation perspective donc multiplication+division).

Par contre ce que je trouve stupide sur la doc c'est qu'il est bel et bien impossible de prédire la vitesse d'une instruction , cela dépend de l'état de la pipeline et pas des instructions en elle même (le proc ne bloque jamais la pipeline sauf en cas de besoin ).

---

Alors là tu m'intéresses. Tu as des sources solides pour appuyer tous ça?

Moi j'ai plutôt l'habitude de travailler sur de petits micros. Et initialement, j'imaginais effectivement que nos gros CPU modernes devaient être capable de calculer une simple division en un battement de cil.
Mais ce n'est absolument pas ce que j'ai trouvé jusqu'à présent. Bien au contraire.
Non seulement la division semble toujours s'exécuter entre 20 à 40 cycles suivant la plateforme, que ce soit en entier ou en flottant (et de toute façon peu importe, ce n'est pas parce que la div float serait plus rapide à calculer qu'une div int, que le compilo réorientera la div int vers le FPU!!),
mais en plus, comme tu l'as évoqué, si plusieurs instructions simples (comme l'addition) peuvent être calculé en parallèle, simultanément sur le même cœur, ce n'est pas le cas de la division, qui bénéficie de la double peine (très longue à calculé, et un par un à la queue leu-leu).

De tout ce que j'ai trouvé jusqu'à présent, il semblerait qu'il n'y ait eut encore aucun génie qui n'ait réussis à nous pondre la formule magique pour calculer une division en un seul cycle d'horloge.
J'ai été étonné et déçu de le découvrir, mais au fond, ça peut se comprendre.
C'est comme les divisions qu'on réalise à la main: il faut un cycle par bit.

Pardon je rectifie:
Zen subit la double peine: 46 cycles en 64 bits, et une division après l'autre.
Core par contre a effectivement multiplié les unités de calcul (4 visiblement, pour 35 à 88 cycles en 64bits).
Mais comme il en est de même pour l'addition, le rapport addition / division restera toujours aussi important.

C'est une info intéressante à garder à l'esprit. Surtout quant on écrit une boucle.

Je me répète , mais tes chiffres sont faux (en plus complètement absurde de donner des chiffres précis) , tu ne peux pas donner de chiffre précis sur un processeur moderne , comme je te l'ai dit , toutes les instructions peuvent s’exécuter sur 1 cycle (division comprise) pour être exact depuis plus de 20 ans les instructions s’exécute en double (de nos jours un proc actuel peut théoriquement gérer 6 instructions/cycles)
De plus c'est impossible de donner un chiffre précis , le out of order ,superscalaire , le renommage des registres etc etc , donne un coté très peu précis sur la vitesse des instructions , cela dépend de l'optimisation interne des proco et il est quasi impossible de savoir précisément ce qu'il fait !
(et elle dépend de l'état de la pipeline si rien ne bloque ta division , ton addition , ta multiplication etc etc, elle ne te coûtera rien ).
donc la vitesse réel d'une instruction dépend plus de son contexte.

Citation:

---

Alors là tu m'intéresses. Tu as des sources solides pour appuyer tous ça?

---

La doc officiel Intel , AMD , autre et l'architecture des ordis depuis les années 2000 :mrgreen:

Les sources pour les calculs, mes test perso (enfin de plusieurs cobayes pour être précis):

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

Matrix x Matrix PS 1 : 27 3.704 Matrix x Matrix PS 2 : 21 4.762 Matrix x Matrix SS : 43 4.186 Matrix x Matrix int : 40 5.000 Transform Perspective SS : 27 1.852 Raster : 2777 3.961 Matrix x Matrix SS flush : 398 0.452 Matrix x Matrix PS 1 flush : 423 0.236 Matrix x Matrix PS 2 flush : 418 0.239 Mov cache : 0 inf /31.701 Mov flush : 137 0.080 /1.393 time 0.801371 s frq 1799.699219 MHz   Thinkad 580, Ubuntu 18.04, Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz   AMD Ryzen 7 2700X Matrix x Matrix PS 1 : 43 2.326 Matrix x Matrix PS 2 : 20 5.000 Matrix x Matrix SS : 42 4.286 Matrix x Matrix int : 55 3.636 Transform Perspective SS : 34 1.471 Raster : 6237 1.764 Matrix x Matrix SS flush : 941 0.191 Matrix x Matrix PS 1 flush : 845 0.118 Matrix x Matrix PS 2 flush : 786 0.127 Mov cache : 0 inf /27.721 Mov flush : 306 0.036 /0.627 time 0.775116 s frq 3694.184082 MHz

---

Je dois avoir une cinquantaine de test comme ça, par contre le raster qui possède plusieurs division , tu remarque que l'IPC est de plus de 1 ! ;)
Et donc on bien a moins d'un cycle de division (la transformation perspective à un IPC de 1,4 / 1,8 donc c'est un mul + div)
Et je viens de test c'est quasi pareil pour la transformation perspective avec des int (donc on est loin de 20 , 40 ou autre chiffre fantaisiste pour la division :mrgreen: )

Citation:

---

Non seulement la division semble toujours s'exécuter entre 20 à 40 cycles suivant la plateforme, que ce soit en entier ou en flottant (et de toute façon peu importe, ce n'est pas parce que la div float serait plus rapide à calculer qu'une div int, que le compilo réorientera la div int vers le FPU!!)

---

Cela existe depuis bien longtemps la PS2 pouvait le faire (techniquement elle ne fait que 7 cycles , mais si tu optimise la pipeline elle ne te coûte que 1 cycle ) , avec le même principe elle pouvait faire même 4 addition et/ou 4 multiplication par cycle , et c'est un proc qui date des années 2000 ;)
Donc sur 7 cycles tu pouvait avoir une transformation 3D complète d'un vecteur ! (1 div et 5 x 4mul+4add + convert int to float avec load/store compris)

Pour ma part le souci de l'IPC (sur l'archi x86) sur les proco des années 2010 et plus est largement résolu , par contre une plus grande optimisation actuelle se trouve sur celle de la mémoire cache parce que là c'est un coût de plus d'une centaine de cycles (avec peu d optimisation possible ) alors que la division est largement optimisation niveau pipeline.
Il est plus intéressant d'optimiser la mémoire cache que les instructions vraiment (qui de toute façon n'est pas prédictible en terme de vitesse), on est plus dans les années 80 :p

Les deux seuls proco qui résolu le souci de la mémoire cache est l'Emotion Engine et le processeur CELL , ce sont les deux seuls qui donne des outils au programmeurs pour ne pas en avoir (mais comme ils sont dénué de fonction automatique pour le faire , c'est le programmeur qui doit le faire lui même , en version simple faut y aller en asm :mrgreen: ).

Tu as une vision assez faussé du fonctionnement des processeurs moderne (j'ai l'impression que tu me parle d'un processeur des années 80), quand un processeur tombe sur une division , il va continuer l'exécutions des instructions , il se bloquera quand celle ci est pleine (et avec 4 ou plus ALU , AGU , BRU , FPU , SSE etc etc ) , il faut beaucoup beaucoup d'instruction pour qu'elle se bloque (bloque = que les instructions te coûtera plus que 1 cycle).

Citation:

---

Envoyé par Kannagi

Je me répète , mais tes chiffres sont faux (en plus complètement absurde de donner des chiffres précis) , tu ne peux pas donner de chiffre précis sur un processeur moderne ...

---

Pourtant ce Professeur me paraît être quelqu'un de très expérimenté (au regard des autres volumes qu'il a rédigé), et sa méthodologie, plutôt rigoureuse (expliqué en page 4).
Mais si tu crois mieux savoir...

Citation:

---

Envoyé par Kannagi

... comme je te l'ai dit , toutes les instructions peuvent s’exécuter sur 1 cycle (division comprise) pour être exact depuis plus de 20 ans les instructions s’exécute en double (de nos jours un proc actuel peut théoriquement gérer 6 instructions/cycles)

---

Excuses-moi de ne pas te croire ta sainte parole, mais la technique de division en un cycle, ça semble être un secret encore mieux gardé que la recette coca-cola.:mouarf:
J'ai beau cherché encore et encore, je n'est trouvé aucun papier, aucune documentation, aucun brevet, aucune discussion ou sujet de forum qui tendrait à montrer cela réalisable.
Bien au contraire, j'ai trouver de très bon papier montrant toute la complexité de la chose (ici, là, ou encore là, mais je ne vais pas innonder...).

Mais n’hésites surtout pas à reposter, si jamais tu arrives a trouver une source qui confirmerait tes convictions.
Et n'hésites pas à en informer AMD, les pauvres, eux qui en sont toujours réduits à calculer 2 bits par cycles (2.10.2) sur leur petit ZEN (d'où les 14-46 cycles en 64bits, avec les sorties prématurés...), je suis suis sûr qu'ils seraient ravie d'apprendre ta technique (histoire de finir d'enterrer INTEL :ptdr:).

Citation:

---

Envoyé par Kannagi

La doc officiel Intel , AMD , autre et l'architecture des ordis depuis les années 2000 :mrgreen:

---

C'est de celle-ci que tu veux parler? (tu pensais peut-être que j'allais pas vérifier?)
Je te laisse vérifier l'appendix C, pour voir de combien s'est planté l'Université du Danemark, moi j'ai pas eu le courage de le faire...

Pour le reste, je n'ai aucun doute que nos CPU doivent bénéficier de tous un tas d'optmisiation pour masquer le plus possible les engorgement dans le pipeline (avec de la prédicion, et d'autres technique que je ne connais pas).
Mais comme toutes ces optimisations bénéficieront tout autant à l'addition qu'à la division, on se retrouve à nouveau à la case départ: la division restera toujours l'instruction de base la plus lente, par rapport à la multiplication et les autres...

Citation:

---

Envoyé par wistiti1234

Pourtant ce Professeur me paraît être quelqu'un de très expérimenté (au regard des autres volumes qu'il a rédigé), et sa méthodologie, plutôt rigoureuse (expliqué en page 4).
Mais si tu crois mieux savoir...

---

C'est pas une question de croyance , c'est le principe même de la pipeline , mais les processeurs actuel qu'on peut nommer superscalaire out of order rend bien plus complexe et fluctuant une mesure précise.

Citation:

---

Envoyé par wistiti1234

Excuses-moi de ne pas te croire ta sainte parole, mais la technique de division en un cycle, ça semble être un secret encore mieux gardé que la recette coca-cola.:mouarf:
J'ai beau cherché encore et encore, je n'est trouvé aucun papier, aucune documentation, aucun brevet, aucune discussion ou sujet de forum qui tendrait à montrer cela réalisable.
Bien au contraire, j'ai trouver de très bon papier montrant toute la complexité de la chose (ici, là, ou encore là, mais je ne vais pas innonder...).

---

Ce n'est pas une question de croyance , j'ai posté quelque calcul que j'ai fait sur un vrai processeur (avec mul et division) donc ça confirme ce qui se dit , je t'ai dit aussi que c'était le cas sur des processeurs que j'ai personnellement programmé (sur PS2 entre autre).

Citation:

---

Envoyé par wistiti1234

Et n'hésites pas à en informer AMD, les pauvres, eux qui en sont toujours réduits à calculer 2 bits par cycles (2.10.2) sur leur petit ZEN (d'où les 14-46 cycles en 64bits, avec les sorties prématurés...), je suis suis sûr qu'ils seraient ravie d'apprendre ta technique (histoire de finir d'enterrer INTEL :ptdr:).

---

Au mieux cette doc nous dis que la division à une longueur de pipeline de 4-32 cycles pas que la division te coûtera autant (c'est une nuance assez importante).
Dire que la division fait 16 cycles , c'est dire quel le processeur passera 16 cycles à faire ça et rien d'autre .
Avoir une pipeline de 16 cycles, ça veut dire qu'il faut 16 cycles pour qu'elle se termine , mais laissera le soin au processeur d’exécuter d'autre instruction en parallèle , tu la vois la nuance ?
Je vais pousser le raisonnement plus loin si tu as arrive à paralléliser ces 16 cycles , alors ta division aura un coût équivalent de 1 cycle.
Pour ça que je le dis et répète que tu ne peux pas dire combien coûte une division (ou tout autre instruction ) , ça n'a rien n'a voir avec une croyance , c'est le principe même de la pipeline (paralléliser les instructions) , si tu la parallélise suffisamment bien alors tu atteint donc que la fréquence = nombre d'instruction , et si le proc est superscalaire alors tu peux avoir un IPC au delà de un.
Rien de magique ,c'est un principe que tous les processeurs ont acquis depuis plus de 20 ans.

Je ne te cacherai pas que les test que j'ai fait m'ont un peu étonné , je me doutais pas qu'un proc actuel arriverai à paralléliser suffisamment les instructions pour éviter tout les blocage de pipeline et donc avoir une moyenne de 3 instruction par cycle (division et multiplication comprise).
Mais d'un coté cela ne m'étonne pas vraiment la PS2 arrivait a atteindre les 2 instructions/cycles (avec div + instruction SIMD donc pas des petits calculs).
Donc Intel et AMD ont réussi a bien travailler dans ce domaine c'est indéniable (mais pas étonnant dans un sens).

Citation:

---

Mais comme toutes ces optimisations bénéficieront tout autant à l'addition qu'à la division, on se retrouve à nouveau à la case départ: la division restera toujours l'instruction de base la plus lente, par rapport à la multiplication et les autres...

---

Je que je tente de souligner c'est que c'est contre productive de raisonner de cette façon , la vitesse des instructions ne sont pas prédictible à l'avance.
Donc non ce n'est pas vrai , si une addition bloque la pipeline et que la division non , alors l'addition te coûtera plus de cycle que la division , et inversement.
De même que la prédiction de branchement (une condition ou une boucle) si le processeur se loupe sur la prédiction ça te coûtera bien plus que qu'une division ;)
Donc non on est loin de la case de départ , mais dans quelque chose de bien plus complexe.

Citation:

---

Mais n’hésites surtout pas à reposter, si jamais tu arrives a trouver une source qui confirmerait tes convictions.

---

Si mes convictions sont "que tout peux te coûter 1 cycle même la division" alors je reste sans voix fasse a autant de dédains , surtout que je pense que je connais un peu mieux le sujet que toi.

Faisant un peu d'histoire , dans les années 80 les processeurs fonctionnait avec des instructions avec un taux fixe de cycle (l'addition fait 3 cycles la division 80 et j'y passe)
A partir des années 95 est venu sur le marché (pour le PC et pour les consoles) des processeurs avec une pipeline donc pouvoir paralléliser les instructions entre elle et atteindre leur nombre théorique ( fréquence = nombre d'instruction).
Il y'a eu deux voies , une quand nomme in order est une version manuelle de cette optimisation , ce qu'on appelle out of order est une version automatique.
Puis on a voulu exécuter plusieurs instruction en même temps pareil la version automatique est appelé superscalaire et la version manuelle VLIW.

Pour cela que tu ne peux pas savoir combien fait exactement le nombre de cycle d'une instruction sur un proc superscalaire out of order (le x86) parce qu'il fait cette optimisation en interne et que tu ne connais pas précisément la taille exact de cette pipeline , ni même comment il la gère.
Ce n'est pas pour rien que des failles comme spectre et meltdown ont était découvert si tardivement ,c'est bien que ce genre de processeur est une vrai boite noire sur la façon de comment il gère les instructions !

Mais si tu programme sur un proc in order VLIW (comme le CELL) , c'est à toi de gerer la pipeline et les instructions que tu exécute en double ,tu peux en lisant le code source savoir où et quand il y'a un blocage et dire "tiens la division ici me prend 3 cycles et là elle me prend 8 cycles et dans une autre 1 cycle" (ben oui suivant où se trouve les blocages de cette pipeline , cela fluctue beaucoup sur combien de cycle ça te prend).

Donc merci de ne pas me parler de "croyance" ou de "conviction" quand je ne fais qu’énumérer le fonctionnement des processeurs !

Pour rejoindre ce que dit Kannagi :

Citation:

---

Le nombre d'instructions par seconde d'un processeur peut être déterminé en multipliant l'IPC par la fréquence d'horloge (mesuré en cycles par seconde ou Hertz) du microprocesseur en question. Le nombre d'instructions par seconde est un indicateur approximatif des performances d'un microprocesseur.

---

Citation:

---

Le nombre d'instructions exécutées par cycle n'est pas une constante pour un processeur donné; il dépend de la manière dont le logiciel en cours d'exécution interagit avec le microprocesseur, et évidemment de l'ensemble de la machine, et en particulier de la hiérarchie mémoire. Cependant, certaines fonctions d'un microprocesseur ont pour effet d’accroitre les valeurs d'IPC au-dessus de la moyenne ; la présence de multiples unités arithmétiques et logiques (une ALU est une unité d'un microprocesseur qui peut effectuer des opérations élémentaires d’arithmétique et logique), et un court pipeline.

---

Citation:

---

Un processeur CISC exécute la plupart des instructions élémentaires (addition, multiplication, tests, etc.) en une période d'horloge, tandis qu'il faut généralement quatre périodes d'horloge à un processeur RISC pour obtenir le même résultat. Cependant, le système de pipeline dans les architectures RISC permet d'optimiser l'exécution d'instructions, rendant d'autant plus délicat le lien entre le nombre de MIPS et la performance réelle du processeur.

---

sources Wikipedia.


Par ailleurs, les CPU Intel intègrent 3 niveaux de cache L1, L2, et L3. Les caches ont une importance primordiale car la mémoire est un goulot d'étranglement pour le CPU. Ton CPU passera probablement autant de temps à charger les deux opérandes et retourner en mémoire le résultat qu'à faire la division.

Et dans le cas d'exemple d'ici, le temps le plus important sera les accès I/O, encore plus "lents" que les accès mémoire.

Citation:

---

Envoyé par chrtophe

Par ailleurs, les CPU Intel intègrent 3 niveaux de cache L1, L2, et L3. Les caches ont une importance primordiale car la mémoire est un goulot d'étranglement pour le CPU. Ton CPU passera probablement autant de temps à charger les deux opérandes et retourner en mémoire le résultat qu'à faire la division.

Et dans le cas d'exemple d'ici, le temps le plus important sera les accès I/O, encore plus "lents" que les accès mémoire.

---

Je ne peux que être d'accord à 200% !
Et j'aurais bien voulu expliquer plus cette problématique là (que de la vitesse des instructions).

Sur me mes différents tests (que j'ai du exécuter 1 millions de fois ) pour avoir l'éfficasité du processeurs à traiter un groupe d'instruction (parce qu'on on ne peut pas parler de la vitesse d'une instruction sur un processeur superscalaire) , cela donne un aperçu de la vitesse du proc (je voualit surtout savoir si il arrivait bien a paralléliser correctement les instructions).
Et la réponse est oui , mais d'un coté c'est pas étonnant Intel ou AMD outre qu'ils ont du rajouter beaucoup (beaucoup) d'unité de calcul , ils ont aussi 192 registres interne (pour le renommage de registre qui sert notamment a éviter les dépendance entre les instructions).
Je trouve que c'est une version bazooka de résoudre ce souci , mais bon on va dire qu'elle marche.

Bien sur comme tu le dit , les caches sont bien plus contraignant (3 caches miss sur un ryzen te coûte presque 1000 cycles).
Et c'est pour ma part la différence entre un AMD et un Intel , Intel a un IPC moindre mais gère mieux les cache (les cache miss sont plus rapide) que ceux d'AMD qui ont un avantage sur l'IPC.
D'ailleurs il faut savoir que les compilo tente d’optimiser ce cache vu que les caches miss sont peu parallélisable , et le plus gros gain quand peut avoir sur un proc actuelle se trouve sur ça.
Il faut être conscient que sur un proco moderne cela peut être 50% du temps de calcul perdu , c'est assez énorme.

Le seul truc que je n'ai pas réussi à "mesurer" , c'est la latence du au boucle et aux comparaisons , bref mesurer la vitesse de la prédiction des branchements , mais ça revient à faire les failles meltdown et spectre et de mesurer ensuite le nombre de cycle (et encore meme pas sur que le nombre qu'on aura est fiable), mais bon je pense que avec mes nombreux test , j'ai une vision assez précise de combien prend a peu près chaque partie en terme de cycle.

Citation:

---

Et c'est pour ma part la différence entre un AMD et un Intel , Intel a un IPC moindre mais gère mieux les cache (les cache miss sont plus rapide) que ceux d'AMD qui ont un avantage sur l'IPC.

---

Ca je peux pas dire, je n'ai pas testé, et pas étudié vraiment la question.

L'architecture CPU x sera pour un traitement meilleure sur un modèle pour telle chose et moins bonne pour une autre par rapport à l'architecture y à puissance équivalente.
Globalement les processeurs PowerPC G3/G5 avait une puissance équivalente à un Intel de l'époque à fréquence plus faible.

Ce qui est important ici, c'est de savoir que temps de chargement des valeurs à diviser peut dépasser le temps du calcul lui-même (en vulgarisant), dans ce cas précis, il ne sert pas à grand-chose de dire que le calcul prendra x cycles. On est sur un problème C à la base (et dans le forum C, pas assembleur), pas sur un problème assembleur. Savoir qu'une division est couteux en temps CPU suffit.

Le problème est ici en priorité un problème d'algorithme, avant d'être un problème d'optimisation de compilation.