C++ embarqué

En modifiant le programme pour permettre de changer la
fonction appelée indirectement:
j = 0x55555555; (ça a l'air d'être la plus mauvaise
valeur)
et dans la boucle:
j = (j >> 31) | (j << 1);
expr[j%2]args;

* si on ne la change pas (expr[0] == [1])
icall0 : time = 7.50e-09 sec, iter = 133333333/sec)
icall1 : time = 5.82e-09 sec, iter = 171821305/sec)
icall2 : time = 6.51e-09 sec, iter = 153609831/sec)
icallR : time = 7.25e-09 sec, iter = 137931034/sec)
icallR1: time = 5.67e-09 sec, iter = 176366843/sec)

* si on la change (expr[0] != [1])
icall0 : time = 1.43e-08 sec, iter = 69930069/sec)
icall1 : time = 1.50e-08 sec, iter = 66800267/sec)
icall2 : time = 1.44e-08 sec, iter = 69492703/sec)
icallR : time = 1.40e-08 sec, iter = 71581961/sec)
icallR1: time = 1.47e-08 sec, iter = 67842605/sec)

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Jean-Marc Bourguet wrote:

Jean-Marc Bourguet <jm@bourguet.org> writes:

Laurent Deniau <Laurent.Deniau@cern.ch> writes:

gcc (direct, indirect) 0 = no arg

call0 : time = 3.03e-09 sec, iter = 330033003/sec)
call1 : time = 3.04e-09 sec, iter = 328947368/sec)
call2 : time = 4.70e-09 sec, iter = 212765957/sec)
callR : time = 3.72e-09 sec, iter = 268817204/sec)
callR1 : time = 3.38e-09 sec, iter = 295857988/sec)
icall0 : time = 4.05e-09 sec, iter = 246913580/sec)
icall1 : time = 6.22e-09 sec, iter = 160771704/sec)
icall2 : time = 4.73e-09 sec, iter = 211416490/sec)
icallR : time = 4.72e-09 sec, iter = 211864406/sec)
icallR1: time = 5.48e-09 sec, iter = 182481751/sec)

Les appels directs sont plus rapide.

Pour info:

Sun-Blade-1500

Avec sparcWorks, -xO3 si j'ai bonne mémoire mais rien de
spécifique au processeur.

call0 : time = 5.24e-09 sec, iter = 190839694/sec)
call1 : time = 6.17e-09 sec, iter = 162074554/sec)
call2 : time = 6.20e-09 sec, iter = 161290322/sec)
callR : time = 5.28e-09 sec, iter = 189393939/sec)
callR1 : time = 6.20e-09 sec, iter = 161290322/sec)
icall0 : time = 1.38e-08 sec, iter = 72202166/sec)
icall1 : time = 1.38e-08 sec, iter = 72254335/sec)
icall2 : time = 1.34e-08 sec, iter = 74571215/sec)
icallR : time = 1.38e-08 sec, iter = 72411296/sec)
icallR1: time = 1.34e-08 sec, iter = 74794315/sec)

Sun-Blade-2500
call0 : time = 4.39e-09 sec, iter = 227790432/sec)
call1 : time = 5.12e-09 sec, iter = 195312499/sec)
call2 : time = 5.09e-09 sec, iter = 196463654/sec)
callR : time = 4.33e-09 sec, iter = 230946882/sec)
callR1 : time = 5.15e-09 sec, iter = 194174757/sec)
icall0 : time = 1.14e-08 sec, iter = 87950747/sec)
icall1 : time = 1.14e-08 sec, iter = 87719298/sec)
icall2 : time = 1.10e-08 sec, iter = 90991810/sec)
icallR : time = 1.14e-08 sec, iter = 87873462/sec)
icallR1: time = 1.10e-08 sec, iter = 90661831/sec)

(Dans les deux cas c'est des Sparc IIIi; donc si j'ai bonne memoire
multi-scalaire mais execution dans l'ordre; il me semble que les
Sparc IV ont de l'execution dans le desordre et speculative.)

AMD Athlon(TM) XP1700+ gcc -O3

call0 : time = 9.79e-09 sec, iter = 102145045/sec)
call1 : time = 3.79e-09 sec, iter = 263852242/sec)
call2 : time = 3.37e-09 sec, iter = 296735905/sec)
callR : time = 9.74e-09 sec, iter = 102669404/sec)
callR1 : time = 3.79e-09 sec, iter = 263852242/sec)
icall0 : time = 1.22e-08 sec, iter = 82169268/sec)
icall1 : time = 1.25e-08 sec, iter = 79936051/sec)
icall2 : time = 4.34e-09 sec, iter = 230414746/sec)
icallR : time = 1.19e-08 sec, iter = 83963056/sec)
icallR1: time = 1.24e-08 sec, iter = 80906148/sec)

Le icall2 a l'air suspect...

et en gcc -O3 -mcpu=athlon-xp

call0 : time = 3.78e-09 sec, iter = 264550264/sec)
call1 : time = 4.08e-09 sec, iter = 245098039/sec)
call2 : time = 3.43e-09 sec, iter = 291545189/sec)
callR : time = 3.78e-09 sec, iter = 264550264/sec)
callR1 : time = 4.12e-09 sec, iter = 242718446/sec)
icall0 : time = 4.80e-09 sec, iter = 208333333/sec)
icall1 : time = 5.40e-09 sec, iter = 185185185/sec)
icall2 : time = 4.34e-09 sec, iter = 230414746/sec)
icallR : time = 1.30e-08 sec, iter = 76804915/sec)
icallR1: time = 1.29e-08 sec, iter = 77339520/sec)

A moins que ce ne soit icall0 et icall1.

Je ne me risquerai pas à une interprétation quelconque au
dela de remarquer que les écarts se sont resserés.

Ok. Merci pour ces timings.

a+ ld.

Laurent Deniau wrote:

kanze@gabi-soft.fr wrote:

Laurent Deniau wrote:

kanze@gabi-soft.fr wrote:

[...]

Et si ça conditionne le comportement des programmeurs, il
est temps de changer les programmeurs. Considérer de telles
questions lorqu'on écrit le code, c'est vraiment de
l'optimisation prématurée.

Et pourtant on trouve plus que des templates et les fonctions
inline partout avec des patterns de plus en plus compliquees.

L'utilisation des templates, c'est souvent pour d'autres raisons
que la performance. J'utilise les deux -- des templates et de
l'héritage avec des fonctions virtuelles -- est ce n'est pour
ainsi dire jamais la performance qui joue dans la décision.

beaucoup. Disons que sur une machine généraliste moderne,
je m'attendrais à un rapport entre 1:2 et 1:10. Sur des
machines plus primitives (embarquées ou anciennes), j'ai
déjà vu nettement moins de 1:2.

Jamais vu de tel rapport.

Tu ne t'es jamais servi d'un Sparc moderne ? Où d'une
machine HP Risc ?

uname -a
SunOS sunmta6 5.6 Generic_105181-12 sun4u sparc SUNW,Ultra-1

c'est pas tres moderne, je te l'accorde.

La mienne n'est pas forcément plus moderne, un Ultra-5_10.

Il y a qque semaines, j'ai du me contenter d'un gcc 2.2 (!) et
2.7.2 sur des Sun. Mon code ne passait pas sur 2.2 (pre-c89?)
mais heureusement les deux architectures etaient identiques,
j'ai donc pu utiliser 2.7.2 pour les deux machines...

A priori, pour quelque chose d'aussi simple, je m'attendrais pas
à une grande différence entre les compilateurs. Mais on ne sait
jamais.

Heureusement parce que OOC n'a que des methodes virtuelles.
Je n'aurais jamais fait ca si je n'etais pas convaincu que
virtuel = direct +/- 10% (note que j'ai mesure des appels
virtuel plus rapide que des appels directs).

Je n'ai jamais vu une architecture où le rapport est
seulement de 10%.

Est-ce que tu es sûr que tu ne mésures que la différence de
l'appel même, et pas la différence totale de performance ?
Parce que dans les applications que je connais (même sans
utiliser inline du tout), le temps passés dans les appels
n'en fait qu'une très faible partie du temps d'exécution.

Je ne comprends pas ce que tu dis. De quel temps d'execution
tu parles, si ce n'est pas celui de l'appel? Comme un peu de
code peut-etre plus explicite qu'un long discours, je mets un
test en fin de post.

Dans mon cas, je me suis servi d'une charpente de test existant
qui est un peu trop pour poster:-(. Et qui, d'après mes
expériences, introduit du jitter dans les mesures.

[...]

Ce qui n'est pas forcément une mauvaise chose. En fin de compte,
ce qui compte, ce n'est pas le coût d'un appel, c'est le temps
d'exécution totale du programme. Et le fait qu'un appel
virtuelle coûte 10 fois plus qu'un appel non-virtuelle n'est pas
forcément significatif. D'abord, ils font des choses
différentes, et aussi, quel pourcentage du temps de l'exécution
se passe réelement dans les appels -- si ce n'est qu'un ou deux
pour cent, une facteur dix dans le temps d'exécution n'a pas
d'impact sur le temps d'exécution du programme. C'est le genre
de benchmark que j'ai fait par curiosité, pour m'amuser, mais
qui n'a pas le moindre impact sur la façon que je code.

Par ce que tu as de l'experience...

Mais il ne faut pas oublier les decisions qui ont ete prises
pour C++. Le but etait d'avoir le meme degre d'efficacite que
le C (probablement pour facilite la transition psychologique
des programmeur C vers le C++).

Pas seulement pour des raisons psychologiques, je crois. Quand
on a besoin des performances, on en a besoin. Seulement, à
quelques exceptions près (du genre vector<>::operator[]), on ne
sait qu'on a besoin qu'une fois qu'on a du code, et alors, le
profiler ne dit où il faut s'attaquer.

Je vois encore pas mal d'articles et de propositions (tout
plus complexe les unes que les autres) sur les multi-methodes
en C++ alors qu'un double (ou N) appel virtuel resout le
probleme. Je ne connais pas la raison, mais cela semble
etroitement lie au coup des appels virtuels.

Je ne suis pas sûr de quoi tu parles. S'il s'agit des
propositions du langage, l'intérêt n'est pas la performance (un
double appel virtuel serait probablement plus rapide), mais la
facilité d'écriture -- actuellement, pour faire le double appel,
il faut que la classe de base connaît les classes dérivées, ce
qui introduit un couplage souvent indésirable.

[...]

De même, j'ai utilisé une charpente de benchmark qui n'a pas
été conçu pour mesurer des choses aussi petites. Il donne de
très bons résultats quand la durée de ce qu'on mesure
dépasse la durée d'un appel virtuel par une facteur de deux
ou de trois, mais quand la durée devient plus petite, le
code qui enlève le coût du au charpente introduit trop de
jitter -- pour des choses vraiment rapides, il m'arrive à
avoir des résultats négatifs. (Mais comment faire avec
précision pour de telles durées ? Parce que c'est
précisement avec de telles durées que le coût de la gestion
de la boucle, etc., pèse le plus.)

Il suffit de les eliminer.

C'est ce qu'essaie de faire ma charpente. Je ne suis pas
convaincu que ce n'est pas ces essaies qui introduit le jitter.

De l'autre côté, il faut le comparer à ce qu'on fait dans
la fonction. Dès qu'il y a une multiplication ou une
division entière, avec des termes non constantes, le temps
de l'appel devient négligeable. Sur ma machine... on ne
peut pas faire de généralités.

On ne parle que du cout de l'appel, le reste est speculatif.

Mais comment mesures-tu le coût de l'appel, sans mesurer
aussi le coût du retour, le coût de la gestion de la boucle,
etc. ?

Le cout du retour est inclu biensur. Pour moi un appel c'est
un aller-retour. Le cout de la boucle peut se retirer, cf code
ci-dessous.

D'accord. C'était juste pour être sûr qu'on parlait de la même
chose.

Et en ce qui concerne le temps nécessaire à incrémenter le
compteur et à le tester ? (Sur un Sparc, une incrémentation, une
comparaison et un saut conditionnel pourrait bien prendre plus
de temps qu'un appel sans paramètres et son rétour.)

Sans parler du coût des indirections supplémentaires
nécessaire pour tromper l'optimisateur.

Compilation separee.

C'est sans doute la meilleur solution dans ce cas-ci. En
supposant qu'elle suffit. (Autant que je sache, elle suffit
encore pour g++ et Sun CC. Pour combien de temps, je ne sais
pas.)

C'est l'argument des utilisateurs d'Objective-C qui clame
que le message dispatch (bien que tres lent, 800% pour gcc)
est suffisament rapide en raison du code de la fonction. Et
quand tu demandes comment faire une classe Complex efficace
(je te rappelle que les data membres ne sont accessible que
par des methodes), ils te repondent que Objective-C n'est
pas fait pour ca...

Et si tu leur démandes pourquoi Objective-C n'est pas fait
pour ça... ils répondent que c'est parce que les appels de
fonction sont trop lents ? :-)

Les appels de method, oui. Facteur 8 (dans le meilleur des
cas) quand meme. Pour un getter sur un Array, ca peut etre
critique.

Tout à fait. Comme j'ai dit, vector<>::operator[] est
probablement quelque chose que je ferais non-virtuel d'office,
sans attendre le profileur.

Encore que... Barton et Nackman avait un truc là, qui me servait
dans les classes de tableau pré-norme.

[...]

Si tu as le temps, tu peux executer le code ci-dessous sur les
architectures que tu as. La version C++ est facile deduire du code
ci-dessous.

Attention ! En voyant ton code, je ne crois pas que tu dupliques
réelement ce que font les appels virtuels. En tout cas,
j'explique bien la différence de nos mesures.

Dans ma charpente, j'utilise (pour des raisons plus ou moins
historiques -- ce n'est pas une solution idéale ici) une
fonction virtuelle pour isoler le code à tester, et tromper
l'optimisateur. Grosso modo, ma boucle de test est :

for ( unsigned int count = N ; count != 0 ; == count ) {
f() ;
}

où f() est une fonction virtuelle. J'exécute la boucle une fois
avec une fonction f() vide, et j'en soustrait le résultat des
mesures avec les fonctions f() réeles. (A priori, ça doit
tromper même les optimisateurs capables de faire de
l'optimisation entre plusieurs unités de compilation.)

Dans notre cas, je mets dans f l'appel d'une autre fonction,
avec affectation de la valeur de rétour (probablement pas
nécessaire -- mais note bien que ça réduit le rapport des
temps). Selon le cas, cette fonction est :

-- inline non-member
-- non-inline non-membre (définie dans une autre module)
-- inline membre
-- non-inline membre (non-virtuel, définie dans une autre module)
-- membre virtuel

Mais je crois ce qui est importante ici, par rapport à ce que tu
mésures, c'est que chaque fois, j'exécute la fonction dans une
contexte nouvelle -- la seule chose que le compilateur a
« préchargé » dans les régistres, c'est le pointeur this (dans
i0).

//-------------------speed_f.h
#ifndef SPEED_H
#define SPEED_H

void do_nothing0(void);
void do_nothing1(unsigned a);
void do_nothing2(unsigned a, unsigned b);
unsigned do_nothingR(void);
unsigned do_nothingR1(unsigned a);

extern void (*p_do_nothing0) (void);
extern void (*p_do_nothing1) (unsigned);
extern void (*p_do_nothing2) (unsigned, unsigned);
extern unsigned (*p_do_nothingR) (void);
extern unsigned (*p_do_nothingR1)(unsigned);

#endif

//-------------------speed_f.c
#include "speed_f.h"

void do_nothing0(void) {}
void do_nothing1(unsigned a) { (void)a; }
void do_nothing2(unsigned a, unsigned b) { (void)a; (void)b; }
unsigned do_nothingR(void) { return 0; }
unsigned do_nothingR1(unsigned a) { return a; }

void (*p_do_nothing0) (void) = do_nothing0;
void (*p_do_nothing1) (unsigned) = do_nothing1;
void (*p_do_nothing2) (unsigned, unsigned) = do_nothing2;
unsigned (*p_do_nothingR) (void) = do_nothingR;
unsigned (*p_do_nothingR1)(unsigned) = do_nothingR1;

//-------------------call_speed.c
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

#include "speed_f.h"

#define RUN_TEST(expr)
{
clock_t t[4];
unsigned i;

t[0] = clock();
for (i = 0; i < loop; i++) {
expr;

Et c'est ici où il y a la différence, à mon avis. Dans le cas
des appels indirects, c'est un jeu d'enfant au compilateur de
reconnaître que p_do_nothing (une variable locale, n'est-ce
pas), ne varie pas, et de le garder dans un régistre pendant la
boucle. Du coup, tu compares un appel indirect sur régistre avec
un appel direct -- d'après ce que je peux voir, j'ai bien
l'impression que sur un Sparc, il n'y a pas réelement une
différence. (D'après ce qu'on m'a dit, ce n'est pas le cas sur
les PA Risc de HP. Mais ça a pu évoluer depuis qu'on m'a raconté
ça.)

Note bien que dans mon code, au moment de l'appel de la
fonction, la seule chose que le compilateur a à sa disposition,
c'est le pointeur this. Il est donc bien obligé à 1) lire le
vptr de l'objet, et 2) lire l'adresse de la fonction à partir du
vptr. C-à-d deux accès mémoire. Et ce sont ces accès mémoire,
couplé au fait qu'il est impossible à la logique de prédiction
du branchement de déviner l'adresse que je lit du vtbl, et donc,
d'avancer les choses, qui explique le coût en temps.

En somme, on mésurait bien deux choses différentes. Maintenant,
je ne sais pas ce que tu voulais réelement mesurer. C'est à toi
de savoir. Il faut dire qu'effectivement, mes mesures sont
particulièrement pessimiste ; je n'exclurais pas que si
j'appelais la fonction virtuelle directement de la boucle, le
compilateur réussirais à « cacher » le pointeur à la fonction
dans un régistre. Je n'ai pas fait l'essai.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Jean-Marc Bourguet wrote:

En modifiant le programme pour permettre de changer la
fonction appelée indirectement:
j = 0x55555555; (ça a l'air d'être la plus mauvaise
valeur)
et dans la boucle:
j = (j >> 31) | (j << 1);
expr[j%2]args;

Cette expression est presente une fois ou trois fois dans la deuxieme
boucle? Pour eliminer les "couts parasites", il faut qu'elle soit
presente qu'une fois dans chaque boucle, sinon la regle du 1-3 ne sert
plus a rien.

* si on ne la change pas (expr[0] == [1])
icall0 : time = 7.50e-09 sec, iter = 133333333/sec)
icall1 : time = 5.82e-09 sec, iter = 171821305/sec)
icall2 : time = 6.51e-09 sec, iter = 153609831/sec)
icallR : time = 7.25e-09 sec, iter = 137931034/sec)
icallR1: time = 5.67e-09 sec, iter = 176366843/sec)

* si on la change (expr[0] != [1])
icall0 : time = 1.43e-08 sec, iter = 69930069/sec)
icall1 : time = 1.50e-08 sec, iter = 66800267/sec)
icall2 : time = 1.44e-08 sec, iter = 69492703/sec)
icallR : time = 1.40e-08 sec, iter = 71581961/sec)
icallR1: time = 1.47e-08 sec, iter = 67842605/sec)

Ca laisserait suppose une evaluation speculative de l'indirection dans
le premier cas et qui ne marche plus dans le deuxieme cas, non?

Sur mon pentium-M, j'ai effectivement la meme chose (gcc 3.3.5):

static double
NcallR1_speed(unsigned loop)
{
clock_t t[4];
unsigned i, j;
unsigned (*R1[2])(unsigned) = { do_nothingR11, do_nothingR12 };

t[0] = clock();
for (i = 0; i < loop; i++) {
j = i & 1;
R1[j](i);
}
t[1] = clock();

t[2] = clock();
for (i = 0; i < loop; i++) {
j = i & 1;
R1[j](i);
R1[j](i);
R1[j](i);
}
t[3] = clock();

return test_unit_time(t, loop);
}

donne:

NcallR1: time = 2.32e-08 sec, iter = 43159257/sec)

Il semble donc que les appels indirects aleatoires (du point de vue du
processeur ;-) ) comme ci-dessus ne marche pas bien (facteur 4), mais
les appels indirects deterministes marche bien. Hors la ou on a besoin
que les appels soient rapides, c'est en general dans le cas
deterministe. Un cas typique, c'est un getter virtuel de conteneur
utilise dans une boucle. Le conteneur ne change pas dans la boucle, mais
il peut changer d'un appel a l'autre de la fonction qui l'utilise.

a+, ld.

Laurent Deniau <Laurent.Deniau@cern.ch> writes:

Le icall2 a l'air suspect...

A moins que ce ne soit icall0 et icall1.

Rien dans le code généré ne me semble suspect, mais j'ai pas
tout examiné en détail. J'ai même pas cherché après la doc
pour être capable de le faire: j'ai arrêté au moment de
l'introduction du Pentium d'essayer de comprendre un
processeur suffisemment en détail pour être capable de
savoir quand je peux le programmer en assembleur plus
efficacement qu'avec un compilateur. Je me contente
maintenant d'avoir une vision de plus haut niveau de la
structure des processeurs -- sans être sûr de ceux qui
utilisent les techniques en question.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

kanze@gabi-soft.fr wrote:

Laurent Deniau wrote:

Il y a qque semaines, j'ai du me contenter d'un gcc 2.2 (!) et
2.7.2 sur des Sun. Mon code ne passait pas sur 2.2 (pre-c89?)
mais heureusement les deux architectures etaient identiques,
j'ai donc pu utiliser 2.7.2 pour les deux machines...

A priori, pour quelque chose d'aussi simple, je m'attendrais pas
à une grande différence entre les compilateurs. Mais on ne sait
jamais.

Je parlais d'un autre code (environ 50000 lignes), pas du test ;-)

Je vois encore pas mal d'articles et de propositions (tout
plus complexe les unes que les autres) sur les multi-methodes
en C++ alors qu'un double (ou N) appel virtuel resout le
probleme. Je ne connais pas la raison, mais cela semble
etroitement lie au coup des appels virtuels.

Je ne suis pas sûr de quoi tu parles. S'il s'agit des
propositions du langage, l'intérêt n'est pas la performance (un
double appel virtuel serait probablement plus rapide), mais la
facilité d'écriture -- actuellement, pour faire le double appel,
il faut que la classe de base connaît les classes dérivées, ce
qui introduit un couplage souvent indésirable.

Mais les propositions en question sont aussi tres contraignante, comme
celle de AA dans modern C++ design (ch11).

De même, j'ai utilisé une charpente de benchmark qui n'a pas
été conçu pour mesurer des choses aussi petites. Il donne de
très bons résultats quand la durée de ce qu'on mesure
dépasse la durée d'un appel virtuel par une facteur de deux
ou de trois, mais quand la durée devient plus petite, le
code qui enlève le coût du au charpente introduit trop de
jitter -- pour des choses vraiment rapides, il m'arrive à
avoir des résultats négatifs. (Mais comment faire avec
précision pour de telles durées ? Parce que c'est
précisement avec de telles durées que le coût de la gestion
de la boucle, etc., pèse le plus.)

Il suffit de les eliminer.

C'est ce qu'essaie de faire ma charpente. Je ne suis pas
convaincu que ce n'est pas ces essaies qui introduit le jitter.

Une methode approximative et simple, c'est la regle du 1-3. Tu peux
changer en N-M si tu as des doutes sur les optimisations faites sur 1.

Le principe est de considerer le cout X que tu cherches a mesurer plus
un surcout constant C que tu ne connait pas mais tu connais la somme des
2 soit T. Ca donne:

X + C = T1

si tu evalues 3 fois l'expression que tu cherches a mesurer dans une
boucle indentique:

3X + C = T3

ce qui nous donne X = (T3-T1)/2/NLOOP; et ce quelque soit les couts
*constants* que tu ne connais pas necessairement. Par exemple, la boucle
elle-meme est un coup constant (inclue dans C), et il est important de
l'enlever quand tu mesures des couts aussi faible qu'un appel de
fonction par rapport a la boucle elle-meme...

De l'autre côté, il faut le comparer à ce qu'on fait dans
la fonction. Dès qu'il y a une multiplication ou une
division entière, avec des termes non constantes, le temps
de l'appel devient négligeable. Sur ma machine... on ne
peut pas faire de généralités.

On ne parle que du cout de l'appel, le reste est speculatif.

Mais comment mesures-tu le coût de l'appel, sans mesurer
aussi le coût du retour, le coût de la gestion de la boucle,
etc. ?

Le cout du retour est inclu biensur. Pour moi un appel c'est
un aller-retour. Le cout de la boucle peut se retirer, cf code
ci-dessous.

D'accord. C'était juste pour être sûr qu'on parlait de la même
chose.

Et en ce qui concerne le temps nécessaire à incrémenter le
compteur et à le tester ? (Sur un Sparc, une incrémentation, une
comparaison et un saut conditionnel pourrait bien prendre plus
de temps qu'un appel sans paramètres et son rétour.)

cf l'explication ci-dessus.

Sans parler du coût des indirections supplémentaires
nécessaire pour tromper l'optimisateur.

Compilation separee.

C'est sans doute la meilleur solution dans ce cas-ci. En
supposant qu'elle suffit. (Autant que je sache, elle suffit
encore pour g++ et Sun CC. Pour combien de temps, je ne sais
pas.)

Franchement, si elle ne suffit plus, il n'y a plus de probleme ;-)

Mais je crois ce qui est importante ici, par rapport à ce que tu
mésures, c'est que chaque fois, j'exécute la fonction dans une
contexte nouvelle -- la seule chose que le compilateur a
« préchargé » dans les régistres, c'est le pointeur this (dans
i0).

[...]

#define RUN_TEST(expr)
{
clock_t t[4];
unsigned i;

t[0] = clock();
for (i = 0; i < loop; i++) {
expr;

Et c'est ici où il y a la différence, à mon avis. Dans le cas
des appels indirects, c'est un jeu d'enfant au compilateur de
reconnaître que p_do_nothing (une variable locale, n'est-ce
pas)

non elle est externe. Et rien n'empeche do_nothing(), la fonction
pointee, de changer la valeur de p_do_nothing() a chaque appel.

, ne varie pas, et de le garder dans un régistre pendant la
boucle. Du coup, tu compares un appel indirect sur régistre avec
un appel direct -- d'après ce que je peux voir, j'ai bien

En ce qui concerne mon test, ce n'est pas le cas. Il suffit de mettre 6
fonction dans la boucle (plus que le nombre de registre disponible sur
IA32) et voir que le temps ne change effectivement pas.

l'impression que sur un Sparc, il n'y a pas réelement une
différence. (D'après ce qu'on m'a dit, ce n'est pas le cas sur
les PA Risc de HP. Mais ça a pu évoluer depuis qu'on m'a raconté
ça.)

Note bien que dans mon code, au moment de l'appel de la
fonction, la seule chose que le compilateur a à sa disposition,
c'est le pointeur this. Il est donc bien obligé à 1) lire le
vptr de l'objet, et 2) lire l'adresse de la fonction à partir du
vptr. C-à-d deux accès mémoire. Et ce sont ces accès mémoire,
couplé au fait qu'il est impossible à la logique de prédiction
du branchement de déviner l'adresse que je lit du vtbl, et donc,
d'avancer les choses, qui explique le coût en temps.

Les tests que j'avais fait pour verifier que OOC fonctionne a des
vitesses raisonnable comportaient la meme chose. Je cherchais
effectivement a mesurer . Je n'y ai pas vu de difference avec gcc 2.95.
Je devrais peut-etre recommencer mes tests avec la serie 3. Mais
globalement, ca ne peut pas etre pire, donc ca me satisfait d'avance ;-)

En somme, on mésurait bien deux choses différentes. Maintenant,
je ne sais pas ce que tu voulais réelement mesurer. C'est à toi
de savoir. Il faut dire qu'effectivement, mes mesures sont
particulièrement pessimiste ; je n'exclurais pas que si
j'appelais la fonction virtuelle directement de la boucle, le
compilateur réussirais à « cacher » le pointeur à la fonction
dans un régistre. Je n'ai pas fait l'essai.

Mais meme s'il le fait, c'est une mesure significative et representative
quand meme. Tu peux avoir dans ton code des trucs du genre:

SumResult sum;
for(int i = 0; i < beaucoup; i++)
sum += vect[i];

ou operator+= et operator[] sont virtuels... J'ai utilise ce genre de
code pour pourvoir remplacer toutes mes variables flottantes ou
complexes par des variables aleatoires (flottantes ou complexes) et
estimer la propagation des incertitudes.

On peut aussi considerer par exemple que plus tu as de fonctions
virtuelles utilisees dans la boucle moins leur cout d'appel est
important parce que comme tu le dis, elles contiennent elle-meme du code
et renvoie probablement qqchose sur lequel on applique un traitement, etc...

a, ld.

Jean-Marc Bourguet wrote:

Laurent Deniau <Laurent.Deniau@cern.ch> writes:

Le icall2 a l'air suspect...

A moins que ce ne soit icall0 et icall1.

Rien dans le code généré ne me semble suspect, mais j'ai pas
tout examiné en détail. J'ai même pas cherché après la doc
pour être capable de le faire: j'ai arrêté au moment de
l'introduction du Pentium d'essayer de comprendre un

Quand je disais ca, c'etait juste a la lumiere de:

icall0 : time = 1.22e-08 sec, iter = 82169268/sec)
icall1 : time = 1.25e-08 sec, iter = 79936051/sec)
icall2 : time = 4.34e-09 sec, iter = 230414746/sec)

ou il parait bizarre que icall2 soit 3 fois plus rapide que icall1 et de
la suite:

icall0 : time = 4.80e-09 sec, iter = 208333333/sec)
icall1 : time = 5.40e-09 sec, iter = 185185185/sec)
icall2 : time = 4.34e-09 sec, iter = 230414746/sec)

qui semble un peu plus coherente mais toujours pas tres claire...

processeur suffisemment en détail pour être capable de
savoir quand je peux le programmer en assembleur plus
efficacement qu'avec un compilateur. Je me contente

Je ne m'interesse plus non plus a l'assembleur depuis 15 ans ;-)

a+, ld.

Laurent Deniau <Laurent.Deniau@cern.ch> writes:

Jean-Marc Bourguet wrote:

En modifiant le programme pour permettre de changer la
fonction appelée indirectement:
j = 0x55555555; (ça a l'air d'être la plus mauvaise
valeur)
et dans la boucle:
j = (j >> 31) | (j << 1);
expr[j%2]args;

Cette expression est presente une fois ou trois fois dans la deuxieme
boucle?

Trois fois dans la deuxième boucle, comme dans la première:
Au moins pour la prédiction des sauts conditionnels, il y a
des implémentations qui font de la corrélation. Je ne
voulais pas rendre la chose possible ici (j'ai essayé des
variations sur l'initialisation de j, 0x55555555 était la
plus défavorable pour le prédicteur).

Ca laisserait suppose une evaluation speculative de
l'indirection dans le premier cas et qui ne marche plus
dans le deuxieme cas, non?

Mettre cet effet en évidence était l'objectif de
l'expérience. Rien que pour montrer que les processeurs
(même pas trop récent comme mon Athlon-XP 1700) ne sont pas
si facile que ça à prédire...

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Laurent Deniau <Laurent.Deniau@cern.ch> writes:

Jean-Marc Bourguet wrote:

Laurent Deniau <Laurent.Deniau@cern.ch> writes:

Le icall2 a l'air suspect...

A moins que ce ne soit icall0 et icall1.
Rien dans le code généré ne me semble suspect, mais j'ai pas

tout examiné en détail. J'ai même pas cherché après la doc
pour être capable de le faire: j'ai arrêté au moment de
l'introduction du Pentium d'essayer de comprendre un

Quand je disais ca, c'etait juste a la lumiere de:

icall0 : time = 1.22e-08 sec, iter = 82169268/sec)
icall1 : time = 1.25e-08 sec, iter = 79936051/sec)
icall2 : time = 4.34e-09 sec, iter = 230414746/sec)

ou il parait bizarre que icall2 soit 3 fois plus rapide que icall1 et de la
suite:

icall0 : time = 4.80e-09 sec, iter = 208333333/sec)
icall1 : time = 5.40e-09 sec, iter = 185185185/sec)
icall2 : time = 4.34e-09 sec, iter = 230414746/sec)

qui semble un peu plus coherente mais toujours pas tres claire...

Je suis d'accord, c'est pour ça que j'ai été voir
l'assembleur et ai un peu joué avec (eh oui, je suis en
congé...) mais mes mesures sont reproductibles et je
n'arrive pas à les expliquer.

processeur suffisemment en détail pour être capable de
savoir quand je peux le programmer en assembleur plus
efficacement qu'avec un compilateur. Je me contente

Je ne m'interesse plus non plus a l'assembleur depuis 15 ans ;-)

Ce n'est pas que ça ne m'intéresse pas, j'ai pas le temps à
y consacré pour que ce soit utile...

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org