🚀 go-pugleaf

Charlie Gordon a �crit :


>> [...] j'ai du mal � 
>> comprendre comment un do/while peut-�tre moins efficace qu'un while
>> ou un for, alors qu'il fait une comparaison en moins...
> 
> Elle fait une comparaison en moins, mais le corps de la boucle est
> execut� une fois de plus avec le do/while dans le cas ou l'�l�ment �
> ins�rer est d�j� � sa place en fin de liste.

Dans le morceau de code que j'ai fourni, le corps de la boucle est
toujours effectu� une fois, m�me si je place le while en t�te. C'est
pour �a que je l'ai mis � la fin. On est dans un cas similaire � �a :

int i, j, n;
n = 42;
for (i = 2; i < n; ++i) {
    for (j = 1; j < i; ++j) {
        /* corps */
    }
}

Comme la valeur de i va de 2 � n, quand j vaut 1, il est n�cessairement
inf�rieur � i, et la premi�re comparaison est inutile. Le do/while
suivant constitue donc une optimisation possible :

for (i = 2; i < n; ++i) {
    j = 1;
    do {
        /* corps */
        ++j;
    } while (j < i);
}

Aujourd'hui, il est possible que les compilateurs savent traduire un for 
en do/while quand il le faut, mais sans doute pas � l'�poque o� j'ai 
�crit ce code.


>>> Mais encore faudrait-il que la routine de tri repr�sente une part
>>> significative du temps de calcul, as-tu fait un peu de profiling ?

>> Actuellement, la part de cette fonction est d'environ 1.5% d'apr�s 
>> gprof, mais :
> 
> cela semble indiquer que tu concentres tes efforts sur le mauvais
> cheval.

Je ne me concentre plus tellement l� dessus. Et le 1.5%, c'est apr�s 
avoir �carter les solutions plus lentes...


>> 1) gprof marche mal. Entre deux impl�mentations, l'une rendant le 
>> programme globalement 1% plus rapide que l'autre, gprof trouve la
>> m�me part d'utilisation de 1,5%.
> 
> C'est vrai, mais la difference de perf pourrait aussi s'expliquer par
> les effets de bord que la modif de cette routine peut avoir sur le
> reste du code : par exemple changements d'alignement dans d'autres
> fonctions deont le code pourtant identique a ete d�cal� � cause des
> modifs...

Le code profil� n'�tant pas le m�me que le code normalement ex�cut�, les 
effets de bord sont omnipr�sents. Beaucoup trouvent que gprof marche 
mal, et utilise des alternatives home-made, p.ex :
http://www.squid-cache.org/mail-archive/squid-dev/200009/0101.html


>> 2) j'en suis aux micro-optimisations depuis un moment. Pourcent par
>>  pourcent, j'ai gagn� un facteur 5 en vitesse depuis 5 ans.
> 
> A conditions constantes je suppose?

Bien s�r.


> parce que c'est le rapport moyen
> de performances obtenu en suivant betement l'evolution du hard �
> logiciel constant. Donc en changeant de machine (pour un prix modique
> d'ailleurs) tu devrais avoir un facteur 25.

En gros oui.


>> 3) le taux d'utilisation de cette fonction pourrait �tre sup�rieur
>> si elle �tait plus efficace.
> 
> Ca depend de ce que tu entends par l� : - tu ferais plus usage de
> cette fonction, dans d'autres parties de l'algorithme, ou plus
> souvent au cours de l'analyse des coups.

Oui.


> Alors oui, l'optimisation 
> paierait, mais vu qu'elle ne represente que 1.5% aujourd'hui, tu
> pourrais deja mettre cette demarche en pratique.

C'est difficile. Dans le tri complet, il y a aussi le calcul des valeurs 
� trier, qui est assez long. Le taux d'utilisation est � peu pr�s 
optimal aujourd'hui.

-- 
Richard