OVH Cloud OVH Cloud

Beuuurk !

87 réponses
Avatar
Cyrille Szymanski
En me balladant tranquillement dans les sources de la libc de
FreeBSD, j'ai rencontré un petit bout de code effrayant au
détour de malloc.c :

/* If it's empty, make a page more of that size chunks */
if (!page_dir[j] && !malloc_make_chunks(j))
return 0;

C'est pas très beau ça quand même, mais on dirait que ça
fonctionne... pour combien de temps ?

--
cns

7 réponses

5 6 7 8 9
Avatar
talon
Marc Espie wrote:

Ah ? c'est plus lent ?
Moi qui croyais que les deux algo pouvaient avoir les memes performances.
Ma memoire me jouerait des tours ?


En tout cas la division entière sur processeur alpha est censée être
beaucoup plus lente que la multiplications entière. Je parle bien sûr de
ce qui est cablé sur le chip.


--

Michel TALON

Avatar
pornin
According to Marc Espie :
[division entière par rapport à multiplication entière]
Ah ? c'est plus lent ?
Moi qui croyais que les deux algo pouvaient avoir les memes performances.
Ma memoire me jouerait des tours ?


Oui, ta mémoire est joueuse. On ne connaît pas d'algorithme efficace
pour faire des divisions (plus efficace qu'une division chiffre à
chiffre à la Euclide), alors qu'on en connaît pour les multiplications
(on sait faire des multiplieurs avec des circuits dont la profondeur est
2*log n, où n est la taille en bits des opérandes). Je parle bien sûr de
circuits en taille P(n) (si on se permet des tailles exponentielles, on
peut tabuler, mais ce n'est pas raisonnable pour n = 32 par exemple).

On peut néanmoins "truander" en rajoutant des bits de précisions et
en faisant des interpolations polynômiales ; c'est ce que font les
coprocesseurs arithmétiques pour les nombres flottants. Mais ça reste
nettement plus lent que les multiplications.


Dans la pratique, sur un Pentium IV récent, une multiplication entière
est bouclée en 10 cycles alors que pour une division, c'est entre 66 et
80 cycles. De plus, la multiplication est très bien pipelinée (on peut
en envoyer une nouvelle à chaque cycle) contrairement à la division (une
division tous les 30 cycles). Sur le coprocesseur arithmétique, avec des
"doubles" (64 bits dont 53 bits de mantisse), c'est 8 cycles pour la
multiplication, 40 pour la division.

Sur Alpha, c'est plus simple : le processeur n'a tout simplement pas de
division entière. Quand on fait une division, le compilateur C produit
un appel à une fonction ad hoc. Quant à la multiplication (sur 64 bits),
c'est 12 cycles sur un 21164a (une multiplication tous les 8 cycles).


Ceci étant, si le diviseur est connu à la compilation, on peut optimiser
les choses : outre les cas simples (divisions par une puissance de 2,
remplaçables par un décalage(*)), on peut gérer le cas général avec
des multiplications. Il y a un article de Granlund et Montgomery qui
décrit ça : "Division by Invariant Integers using Multiplication".
cf http://portal.acm.org/citation.cfm?id8249&dl¬M&coll=portal

En regardant l'évolution des processeurs, notamment les différences
entre les deux générations successives de Pentium IV (eh oui, il y a
plusieurs modèles), on voit que les multiplications sont de plus en plus
rapides (14 -> 10) alors que les divisions sont de plus en plus lentes
(56/70 -> 66/80). Cela traduit le fait que les divisions entières sont
en fait très rares dans le code "usuel".


--Thomas Pornin


(*) Un détail qui peut avoir son importance : la sémantique du C
impose que (-1)/2 vaille 0 ; avec un décalage à droite (même en
préservant le signe), on n'obtient _pas_ le bon résultat. Alors
qu'avec des nombres non signés, le décalage est valide. Aussi,
quand on n'a que des nombres positifs, l'usage de types "unsigned"
peut accélérer les choses. Par exemple, soit le code suivant :

int foo(int x)
{
return x / 2;
}

unsigned bar(unsigned x)
{
return x / 2;
}

À la compilation (sur PC), ça donne le code assembleur suivant
(gcc 3.3.4, flags -O3 -march=athlon -fomit-frame-pointer) :

foo:
movl 4(%esp), %eax
movl %eax, %ecx
shrl $31, %ecx
addl %ecx, %eax
sarl %eax
ret
(...)
bar:
movl 4(%esp), %eax
shrl %eax
ret

où l'on voit que la variante "unsigned" est beaucoup plus efficace,
aussi bien en taille de code qu'en vitesse d'exécution.

Avatar
pornin
According to Michel Talon :
Le point de vue du physicien, c'est qu'il se fout royalement de ce
pourquoi, il mesure combien de temps prend la multiplication, combien
la division, et ils est très content de ce résultat.


Le physicien est type "j'apprends par coeur". Il fait sa mesure, mais
comme il ne sait pas pourquoi c'est ainsi, il ne peut pas étendre
cette connaissance à d'autres configuration (ou pire, il le fait et se
plante...). Ça lui demande aussi un plus grand effort de mémoire.

Un exemple : supposons que le physicien fasse une mesure sur un 80386.
Il voit la multiplication entre 38 cycles et la division en 41 cycles.
Il se dit que c'est kif-kif. Il extrapole sur un Pentium IV, ou pire, un
Alpha, et il se vautre.

L'informaticien (de type "matheux") qui regarde en profondeur peut
obtenir ainsi avec un effort mémoriel moindre des connaissances valides
sur plus de configurations. Il est donc plus efficace. Voilà pourquoi
je prétends que cet informaticien a adopté une méthode meilleure que le
physicien.


--Thomas Pornin

Avatar
Thierry Thomas
Jeudi 29 avril 2004 à 06:19 GMT, Cyril Guibourg a écrit :
Thierry Thomas writes:

Euh, non, mais j'en ai écrit moi-même...


Façon dba ? ;-)


Joker...
--
Th. Thomas.


Avatar
mips
On Thu, 29 Apr 2004 08:07:32 +0000 (UTC)
(Thomas Pornin) wrote:

Pour bien connaître l'assembleur avec les performances et
optimisations possibles, ça aide beaucoup de savoir comment ça
marche au niveau en-dessous. On peut avoir une connaissance
empirique (de type "par coeur") de ces données, mais c'est mieux de
comprendre ce qui se passe. Par exemple, on peut apprendre par coeur
qu'une division entière prend beaucoup plus de temps sur un
processeur moderne qu'une multiplication entière avec des opérandes
de même taille -- mais c'est mieux de savoir pourquoi.


Sauf que l'interet n'est peut-etre pas si evident sur du code qui est
cense etre portable autant sur des vieilles machines, que sur des
recentes et voire sur celles qui ne sont pas encore sorties.

mips

Avatar
mips
On Wed, 28 Apr 2004 10:16:24 +0200
Marwan Burelle wrote:

Oui et dans certains il faut aussi prendre la precaution de la
relire au cas ou ...


Oui, toujours, mais bon, si tu lis bien linéairement, c'est
relativement clair ....


C'est aussi relativement "long" ;)

On ne parle pas de lire des centaines de lignes en une seule
passe. Par contre, une trentaine ... mais bien sûr, si tous les
cas où l'on


Quand je fais de la maintenance de code, c'est rare que je n'ai
que 30 lignes de code a consulter. Et quand je dit rare je suis
genereux.


Hé, mipsounet, quand je parle de 30 lignes, je parle de bloc de 30
lignes. Je doute que tu sois capable de te taper en une seule passe
des fichier C de plusieures centaines de lignes (sinon, je veux bien
t'embaucher pour corriger les projets de mes étudiants, ah merde
c'est pas en C ;)


SuperMips c'est moi !
(Notez bien le superbe clin d'oeil a la sexualite d'Arnaud)

n'est pas forcément plus lisible (en plus dans le cas du double
if, on se retrouve avec une hierarchie de "if" suffisament
ambigue, pour justement rendre les choses moins lisible.)


La par contre je te suis plus.


Ben, je suis désolé, mais un :

if (truc1)
if (truc2)
.... ;

Je trouve ça moins lisible que :

if (truc1 && truc2)
.... ;

Surtout s'il traine d'autre if imbriqués dans le coin ...


Desole mais je te suis toujours pas :))

Le truc, c'est que dans les constructions if, la fin du if n'est pas
toujours clair, imagine quelque chose du genre :

if (truc)
if (truc1)
if (truc2)
e1 ;
else e2 ;

Il n'est pas toujours facile de voir à quoi se rapporte le "else",
même avec la bonne indentation (d'ailleur, le "if ..."/"if ... else
..." est le cas classsique de shift/reduce conflict en yacc ... )


Normal c'est ecrit comme un goret la :)
Et comme je l'ai deja dit je critique une certaine facon de coder le C
en general pas seulement certaines utilisations des operateurs
logiques.

Maintenant, comme je l'ai dit, ça dépend de ce que tu utilises.
Typiquement, le while (--i) pour savoir ce qui se passe ... en
une seule passe ...


Pourtant ca saute aux yeux !!! ;)


i = 0 ;
...
while (--i) { ... }

En fonction de ce que tu as dans les premiers "...", ça peut devenir
conton de se demander pourquoi se code boucle à l'infini ... surtout
que l'on a pas forcément "i = 0" explicitement ... alors que
[...]


Le but de cette boutade etait de montrer le point de vue inverse dans
cette discussion. Pour moi lisible ca veut dire du code suffisemment
clair pour etre lu rapidemment tout en restant explicite (et donc peu
ou pas sujet a erreur d'interpretation).

Enfin bon je crois qu'il est temps de fermer ce thread :)

mips



Avatar
pornin
According to mips :
Sauf que l'interet n'est peut-etre pas si evident sur du code qui est
cense etre portable autant sur des vieilles machines, que sur des
recentes et voire sur celles qui ne sont pas encore sorties.


Au contraire, au contraire... Quand on comprend suffisamment ce qui
se passe "en-dessous", on est plus à même de savoir comment ça a évolué
dans le passé, et aussi d'anticiper ce qui va se passer dans l'avenir.

Par ailleurs, il ne faut pas confondre portabilité et optimisation.
Faire du code qui tourne _correctement_ partout, et faire du code qui
tourne _vite_ partout, ce n'est pas le même boulot. Mon approche
habituelle est de faire du code :
-- qui tourne à peu près partout ;
-- qui indique clairement (à la compilation et par une erreur, si
possible) quand on est en train de l'essayer là où il ne peut pas
tourner(*) ;
-- qui tourne _suffisamment_ vite sur une ou quelques architectures
spécifiques, celles que j'ai sous la main en général. J'insiste sur
le "suffisamment", parce qu'une grande partie de mes productions n'a
pas de problème de vitesse, et un simple "-O" en ligne de commande
suffit amplement.


--Thomas Pornin

(*) C'est-à-dire :

#include <limits.h>
#if CHAR_BIT != 8
#error This code requires 8-bit bytes.
#endif

5 6 7 8 9