Discussion :

[aslo92]

faudrait voir comment tu viens de foutre en l'air ton cache pour toute les opérations suivantes maintenant. Même si le cosinus lui même est plus long a calculer, si ta table de cosinus n'était pas déjà dans le cache (ce qui ne se voit pas sur un benchmark) ou si tu viens de decharger une ligne de cache qui aurait été utile deux instructions plus bas (ce qu'un benchmark ne permet pas de mesurer non plus) alors au final tu y perds.

Pour prouver ce que tu avances, il faudrait utiliser VTUNE sur le code à optimiser.

Tout dépend de la précision dont tu as besoin pour ton calcul. Si tu as besoin de 10 décimales, je suis d'accord avec toi, c'est pas jouable car le tableau de cosinus sera trop gros.

Par contre si 2 décimales suffisent ton tableau de cosinus occupera 315*8=2520 octets ce qui est suffisamment petit pour ne pas perturber des données présentes même dans le cache L1.

[souviron34]

Par contre si 2 décimales suffisent ton tableau de cosinus occupera 315*8=2520 octets ce qui est suffisamment petit pour ne pas perturber des données présentes même dans le cache L1.

Voir plus haut...

Ce genre de choses n'est à faire qu'en dernier recours, lorsque TOUTES les optimisations des algorithmes et du code ont été faites..

D'après les posts, je pense que nous en sommes très très très loin, et que par conséquent ces questions n'ont pas lieu d'être...

[screetch]

une precision de 0.01 en entrée ne donnera pas un résultat cosinus correct a 0.01 je pense.

Pour prouver ce que tu avances, il faudrait utiliser VTUNE sur le code à optimiser.

et pourquoi il faudrait prouver ce que j'avance? pourquoi toi tu pourrais pas prouver ce que tu avances a la place? je veux dire, c'est quand même pas moi qui veut remplacer une instruction ASM par un lookup dans une table et cradoquer mon code (ou pire, le code des autres). Alors pourquoi je devrais aller justifier (malgré tout j'ai deja foutu pas mal d'explications ici) que le code devrait rester propre au lieu de saloper tout avec des cosinus imprécis et a peine plus rapides sans même savoir si il y avait un problème de ce coté?

non, TOI tu sors VTune et tu me prouves que la solution a base de tableaux elle pourrit pas son cache plutôt

[Neckara]

cosinus imprécis...

Dans les matières comme la physique il est inutile d'avoir 300 chiffres significatifs.
On n'utilise pas de valeurs exacte (d'ailleurs l'ordinateur ne sais pas calculé de valeur exacte mais seulement des valeur approchées).
Le tout est de savoir de combien de chiffre significatif, le degré de précision dont on a besoin.

Sinon, je ne vois pas l'utilité d'un tel débat ici.
On a vu dans les posts précédents que finalement, les processeurs s'étaient amélioré et qu'aujourd'hui, la fonction cos(x) est assez rapide.

Ensuite, entre cos(x) ou cos[x] je pense que chacun est libre de choisir.
On est pas dans le cas d'un programme à optimiser à 200%.

cos[x] prend de la place mémoire donc il ne faut pas l'utiliser pour un degré trop grand de précision.
cos(x) serait apparemment encore un petit peu moins rapide que cos[x], mais ce n'est pas significatif ici.

Après, chacun code comme il veut.

[Sve@r]

...d'ailleurs l'ordinateur ne sais pas calculé de valeur exacte mais seulement des valeur approchées

Salut

Attention à la façon de dire les choses. S'il est vrai que le codage des flottants (avec mantisse et exposant) n'est pas toujours exact, il existe d'autres façon de coder les décimaux. Le COBOL, par exemple, avec sa déclaration PIC 99V999 te donnera un nombre à 3 décimales en précision absolue. Le module decimal de Python te donnera lui aussi des décimaux parfaits. Et sûrement d'autres librairies dans d'autres langages font la même chose...

[Neckara]

Bien sûr, quand la fonction est un polynôme, l'ordinateur peut nous donner une valeur exacte.

Mais dans le cas de fonctions exponentielle, cosinus et autres, l'ordinateur passe par une formule de Taylor si je ne dit pas de bêtise.

L'ordinateur calculera donc une valeur approchée au voisinage d'un point connu.
Il peut arriver que la valeur approchée soit égale à la valeur exacte, mais ce n'est pas toujours le cas.
Au mieux il pourra donner une expression, mais c'est impossible de donner une valeur exacte d'un nombre ayant une infinité de chiffres décimaux.

[anacharsis]

Mais dans le cas de fonctions exponentielle, cosinus et autres, l'ordinateur passe par une formule de Taylor si je ne dit pas de bêtise.

tu ne dis pas de bêtise ! mais l'algorithme est un peu plus compliqué : on divise l'argument par 2 jusqu'à obtenir un argument assez petit (pour que Taylor soit assez précis), puis on utilise Taylor sur ce petit argument, puis un opérateur de différences finies (sur des polynômes de degré 2) pour évaluer la fonction du double du petit argument et on répète jusqu'à retrouver l'argument initial (en fait on compte les étapes de division par 2, et on applique autant d'étapes dans la multiplication par 2 sans évaluer l'argument).
les publications faites autour des calculatrices HP-65 des années 74-75 donnaient pas mal de détails sur ces questions, et bien que, depuis, les processeurs soient passés de 4 bits à 64 bits, les algorithmes n'ont pas beaucoup changé.
PS pour ceux qui sont réellement au fait de ces algorithmes, je sais que la réalité est un peu plus compliquée, puisque les coefficients de Taylor sont pré-calculés et sont parfois pris en compte dans l'opérateur de différences finies.

A+

[souviron34]

ce qui fait que je doute extrêmement fortement de la mesure donnée en fin de première page qu'il faudrait 220 opérations/cycles pour calculer un cosinus..

[aslo92]

c'est quand même pas moi qui veut remplacer une instruction ASM par un lookup dans une table

Je ne vois pas très bien quelle est l'instruction ASM magique dont on parle. Si c'est FCOS, ça fait bien longtemps que ça n'est plus utilisé.
En traçant le code de cos(x) on obtient ç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
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
73B2E7B8  movlpd      xmm0,qword ptr [esp+4]  
73B2E7BE  pextrw      eax,xmm0,3  
73B2E7C3  and         ax,7FFFh  
73B2E7C7  sub         ax,3030h  
73B2E7CB  cmp         ax,10C5h  
73B2E7CF  ja          73B2E917  
73B2E7D5  movlpd      xmm1,qword ptr ds:[73B2F190h]  
73B2E7DD  mulsd       xmm1,xmm0  
73B2E7E1  movlpd      xmm2,qword ptr ds:[73B2F198h]  
73B2E7E9  cvtsd2si    edx,xmm1  
73B2E7ED  addsd       xmm1,xmm2  
73B2E7F1  movlpd      xmm3,qword ptr ds:[73B2F1B0h]  
73B2E7F9  subsd       xmm1,xmm2  
73B2E7FD  movapd      xmm2,xmmword ptr ds:[73B2F1A0h]  
73B2E805  mulsd       xmm3,xmm1  
73B2E809  unpcklpd    xmm1,xmm1  
73B2E80D  add         edx,1C7610h  
73B2E813  movsd       xmm4,xmm0  
73B2E817  and         edx,3Fh  
73B2E81A  movapd      xmm5,xmmword ptr ds:[73B2F180h]  
73B2E822  lea         eax,ds:[73B2E950h]  
73B2E828  shl         edx,5  
73B2E82B  add         eax,edx  
73B2E82D  mulpd       xmm2,xmm1  
73B2E831  subsd       xmm0,xmm3  
73B2E835  mulsd       xmm1,mmword ptr ds:[73B2F1B8h]  
73B2E83D  subsd       xmm4,xmm3  
73B2E841  movlpd      xmm7,qword ptr [eax+8]  
73B2E846  unpcklpd    xmm0,xmm0  
73B2E84A  movsd       xmm3,xmm4  
73B2E84E  subsd       xmm4,xmm2  
73B2E852  mulpd       xmm5,xmm0  
73B2E856  subpd       xmm0,xmm2  
73B2E85A  movapd      xmm6,xmmword ptr ds:[73B2F160h]  
73B2E862  mulsd       xmm7,xmm4  
73B2E866  subsd       xmm3,xmm4  
73B2E86A  mulpd       xmm5,xmm0  
73B2E86E  mulpd       xmm0,xmm0  
73B2E872  subsd       xmm3,xmm2  
73B2E876  movapd      xmm2,xmmword ptr [eax]  
73B2E87A  subsd       xmm1,xmm3  
73B2E87E  movlpd      xmm3,qword ptr [eax+18h]  
73B2E883  addsd       xmm2,xmm3  
73B2E887  subsd       xmm7,xmm2  
73B2E88B  mulsd       xmm2,xmm4  
73B2E88F  mulpd       xmm6,xmm0  
73B2E893  mulsd       xmm3,xmm4  
73B2E897  mulpd       xmm2,xmm0  
73B2E89B  mulpd       xmm0,xmm0  
73B2E89F  addpd       xmm5,xmmword ptr ds:[73B2F170h]  
73B2E8A7  mulsd       xmm4,mmword ptr [eax]  
73B2E8AB  addpd       xmm6,xmmword ptr ds:[73B2F150h]  
73B2E8B3  mulpd       xmm5,xmm0  
73B2E8B7  movsd       xmm0,xmm3  
73B2E8BB  addsd       xmm3,mmword ptr [eax+8]  
73B2E8C0  mulsd       xmm1,xmm7  
73B2E8C4  movsd       xmm7,xmm4  
73B2E8C8  addsd       xmm4,xmm3  
73B2E8CC  addpd       xmm6,xmm5  
73B2E8D0  movlpd      xmm5,qword ptr [eax+8]  
73B2E8D5  subsd       xmm5,xmm3  
73B2E8D9  subsd       xmm3,xmm4  
73B2E8DD  addsd       xmm1,mmword ptr [eax+10h]  
73B2E8E2  mulpd       xmm6,xmm2  
73B2E8E6  addsd       xmm5,xmm0  
73B2E8EA  addsd       xmm3,xmm7  
73B2E8EE  addsd       xmm1,xmm5  
73B2E8F2  addsd       xmm1,xmm3  
73B2E8F6  addsd       xmm1,xmm6  
73B2E8FA  unpckhpd    xmm6,xmm6  
73B2E8FE  addsd       xmm1,xmm6  
73B2E902  sub         esp,10h  
73B2E905  addsd       xmm4,xmm1  
73B2E909  movlpd      qword ptr [esp+4],xmm4  
73B2E90F  fld         qword ptr [esp+4]  
73B2E913  add         esp,10h  
73B2E916  ret

On est bien loin d'une instruction assembleur qui fait le travail en un claquement de doigt... C'est peut-être la formule de Taylor dont parle Neckara ?

Pour info, voici le code généré pour lire la valeur du cosinus dans une table:

Code :

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

1
2
0125143E  mov         eax,dword ptr [t_cos]  
01251441  fld         qword ptr [eax+2F98h]

On se demande bien pourquoi c'est plus rapide non ?

Alors pourquoi je devrais aller justifier (malgré tout j'ai deja foutu pas mal d'explications ici) que le code devrait rester propre au lieu de saloper tout avec des cosinus imprécis et a peine plus rapides

Est-ce que le code est moins lisible en faisant: a = t_cos[x] au lieu de a = cos(x) ? J'avoue que là, j'ai un peu de mal à comprendre !

Concernant le fait que ce soit à peine plus rapide, je pense qu'un facteur 5 est loin d'être à peine plus rapide. C'est comme si je vendais une 2CV au prix d'une Ferrari à peine plus rapide (facteur 3).

[souviron34]

'fin, tu fais comme tu veux, hein...

C'est juste que, comme dit plus haut, ça n'a aucun intérêt dans 99.9999999999999% des cas...

Alors, tu fais comme tu veux, hein.. Tu peux chercher à réinventer toutes les fonctions et de maths, et diverses et variées.. Je suis certain que tu peux même refaire un système d'exploitation...

Mais je suis certain que si je te vois arriver demander un boulot, je ne prend pas dans mon équipe

Et que je n'ai pas envie d'avoir à reprendre un code que tu aurais fait..

[anacharsis]

comme tu peux le constater, le débat devient un peu houleux. il est grand temps de le clore car : tu veux calculer une position toutes les 100 millisecondes et ce, pendant 10 secondes. d'où pour toi, environ 100 calculs.

pour obtenir un cosinus par lecture d'une table, avec une précision de 2 chiffres après la virgule il te faudra une table d'un peu plus de 150 valeurs (tu peux le vérifier avec n'importe quel tableur). pour la remplir, il te faudra donc calculer 150 cosinus et ensuite en lire 100.

si tu trouves ça très à ton goût, fais le !

[Bktero]

J'ai lu de ces trucs dans ce sujet

Sans vous vexez, j'ai vu un benchmark fait avec 10 calculs et une seule configuration, quelqu'un dire que ce n'est pas à lui de prouver que ça perturbe le cache alors que son contradicteur a essayé de faire une démonstration, j'ai appris qu'on n'utilisait pas les valeurs exactes et que l'ordinateur n'en calculait pas.... mais quand on utilise pi comment avoir des valeurs exactes ? Enfin, concernant le gain en cycle CPU, je dirais que quand j'ai une mémoire flash de quelques ko pour stocker mon programme, je vais vraiment réfléchir au gain en vitesse contre la perte de mémoire à stocker mes cosinus dans un tableau.

Une personne ici a tellement raison, c'est souviron34 ! Il y a tellement d'optimisations à faire dans nos algorithmes et nos codes (les miens les premiers !) pour ne se préoccuper du cosinus qu'en dernier recours

[aslo92]

Je suis désolé si j'ai froissé certaines personnes. Ce n'était pas le but !
J'ai peut-être trop fait de temps réel et ce n'est apparemment pas le but à atteindre dans cette discussion ?

Bonne journée à tous

[Bktero]

En fait le but du message original ne parle absolument pas d'optimisation du calcul du cosinus, on s'est juste lancé dans un long débat à cause de Neckara ( )

Si tu as une vision temps réel, dans ce cas je comprends mieux ton raisonnement. Pour toi, gagner des cycles CPU pour que ta tâche se termine dans les temps est important. Je pense que ta remarque et celle de souviron se rejoignent d'une certaine façon : en règle générale, ce n'est pas utile car il y beaucoup d'optimisations à faire avant celle-là ; dans certains cas, on a besoin des dernières optimisations pour répondre à certaines contraintes.

[souviron34]

Je suis désolé si j'ai froissé certaines personnes. Ce n'était pas le but !
J'ai peut-être trop fait de temps réel et ce n'est apparemment pas le but à atteindre dans cette discussion ?

Bonne journée à tous

Désolé que tu l'aies pris comme ça : tu n'as froissé personne (enfin, je pense) ici..

Ce qu'on en dit, c'est que c'est peu important en général.

J'ai par contre trouvé un lien qui peut t'intéresser :

How does C computes sin and other math functions, où, de manière générale, il est dt que cela dépend à 100% des implémentations et de la bibliothèque et du compilateur, avec appel éventuel aux fonctions du processeur (et donc très nettement plus rapides que tout algo),, et vers le bas de la page, tu trouveras aussi une autre méthode rapide..