Optimisation des ruptures du pipeline - Page 1

Bonjour,

J'ai cherché un peu sur google et n'ai pas trouvé ce qui est sans doute évident pour ceux qui connaissent bien les processeurs modernes et les versions de GCC récentes.

Soit l'alternative if (c) then A else B. Connaissant le comportement du programme pour les données le plus souvent traitées, je sais que, la plupart du temps, c sera faux et B exécuté. Serait-il plus efficace en moyenne d'écrire if (not c) then B else A ?

En assembleur 68k, j'avais l'habitude de choisir la première écriture, car elle génère
- la plupart du temps : seulement 1 branchement pour aller en B
- quelquefois : 1 branchement non exécuté pour poursuivre en A + 1 branchement pour éviter B
Alors que la seconde écriture aurait généré
- la plupart du temps : 1 branchement non exécuté pour poursuivre en B + 1 branchement pour éviter A
- quelquefois : 1 branchement pour aller en A


Mais qu'en est-il sur un processeur moderne ? On suppose que A et B sont petits, j'imagine que ca permet de ne pas s'occuper de l'influence des défauts de cache.

Sans être expert du sujet, il me semble que la prédiction des branchements va lancer l'exécution du cas le plus fréquent, en fonction des stats qu'il a fait la dernière fois qu'il est passé par cette instruction. Du coup j'imagine que toute optimisation manuelle est inconséquente (voire parfois néfaste).

Après il y a peut-être des techniques sioux de l'espace au delà du principe que je connais ^^

Sans être un expert en processeurs modernes, je pense que tu devrais te documenter sur la prédiction des branchements.
À priori aujourd'hui, ce qui prend du temps ce n'est pas le branchement ou non branchement, mais la non-validité de la prédiction faite par le CPU. (Contrairement à l'époque ou tu pouvais calculer précisément un nombre de cycles pris par un branchement)

En l'occurrence je ne pense pas que c soit plus prévisible que "not c", en revanche tu économiseras quand même un branchement (inconditionnel) en choisissant ta première condition ^^

Au final ce qui va compter c'est la prédictibilité de c pour le CPU. Et encore, si ce n'est pas exécuté dans une boucle critique, ce n'est sans doute pas important de s'attarder dessus.
À priori, GCC te permet d'aider le CPU avec __builtin_expect(,) mais ça n'a pas l'air possible avec Visual C++ par exemple (vu que ta question mentionne GC,C je suppose que ça ira )

D'autres t'en diront sans doute plus (PpHd, bearbecue ?)

[cross]

Merci spectras pour cette info qui nous oriente dans le bon sens

GoldenCrystal : Merci.

En l'occurrence je ne pense pas que c soit plus prévisible que "not c"

Pour simplifier et donner une image forte, disons que cette condition teste si l'objet traité est un sommet ou une arête dans un graphe complet Donc on sait à l'avance que la probabilité de tomber sur une arête tend vers 1 quand l'ordre du graphe augmente.

Le tout est traité dans un algorithme très complexe (des tonnes de branchements répartis dans plusieurs Mo de code), si bien que je pense que le processeur écrase parfois son cache de statistiques entre deux exécutions de ce passage. Donc peut-être que, en placant l'alternative la plus probable là où va le processeur quand il n'a pas de stats, on réduirait les ruptures du pipeline ?

Bien sûr, c'est l'ensemble du programme qui peut être accéleré, et non-pas une petite condition perdue quelque part, car la plupart des conditions de l'algo ont une probabilité estimable à l'avance

Je ne suis pas sur qu'on se soit bien compris
Ma phrase (que tu as cité) aborde le problème d'un point de vue logique et indépendant de ton problème particulier. Je ne parle pas de la probabilité que tu as pu estimer à partir de ton problème, mais de la "prévisibilité" pour le CPU. (i.e. P(c) est aussi facile à obtenir que P(not c) c'est le sens de ma phrase)

Pour le reste, oui c'est ça il faut juste que le CPU arrive à prévoir juste... (Après la différence entre les deux formes est, je pense, quasi-négligeable, et en plus ça pourrait varier d'un CPU à l'autre)
Tu n'as qu'à essayer le truc que j'ai indiqué dans mon post (Jamais utilisé perso, en même temps je fais peu de C ^^)

c'est très utilisé dans linux, donc avec gcc

http://stackoverflow.com/questions/109710/likely-unlikely-macros-in-the-linux-kernel

#define likely(x)	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)

si tu sais que C sera souvent faux, alors

if(unlikely(c)) {/*truc rare*/} else { /*truc fréquent*/ }

Tiens, intéressant, merci.
Il y a un équivalent pour VC++ ?

d'après ./3, la réponse est non.

Génial !

Aucune idée de la confiance qu'on peut avoir en ce document, mais il dit (page 57) que GCC place B en premier et repousse A plus loin, potentiellement très loin, genre après tout le reste des instructions de la fonction (le schéma en bas de page sera plus clair que moi). De cette manière, on a une exécution parfaitement linéaire le plus souvent. C'est encore mieux que l'astuce décrite dans le post ./1

ah oui carrément?

bon sinon tu fais un coup de gcc -S sur le fichier qui t'intéresse, t'auras la réponse

./9 ah, oué
Dommage

(en 68k, faut choisir celui de beq ou de bne qui est le plus rapide (je sais plus lequel d'ailleurs ))

C'est pas le même nombre de cycles ?

Ce qui est sûr en tout cas, c'est qu'il faut choisir le sens de façon à ce qu'il n'y ait pas de saut dans le cas le plus courant (et c'est vrai pour la plupart des processeurs de la même époque : comme il n'y a pas de prédiction de branchement, exécuter le saut est toujours plus long que de continuer à l'instruction suivante)

ben, il y a toujours au moins un saut s'il y a un else, non ?

; // machin ; } ; else ; { ; // truc ; } ; // suite; ; return; tst.l d0 beq truc ; machin suite: ; suite rts truc: ; truc bra suite

Non. Tu peux mettre 2 sauts pour ton else (un conditionnel au début, et un inconditionnel à la fin), et du coup ne pas en avoir pour le if : ; if (d0 != 0)
; {

Ah oué, tiens. Tout simple, mais fallait y penser

cross edit : oué oué, j'avais compris

Voilà, et d'après le document d'Ulrich Drepper, cité dans le ./10, c'est ce que GCC génère quand on utilise les astuces de Golden Crystal et squalyl.

En plus du builtin_expect, tu peux faire un profile build, qui te permet plus ou moins de faire calculer ses prévisions par le compilateur.
En gros, tu fais un build, puis un run. Là le run va instrumenter les branches les plus critiques (c'est le même mécanisme que pour la mesure de couverture).
Tu refais un run avec ses infos, et ca te génère un build optimisé (voir fprofile-generate ou http://stackoverflow.com/questions/4365980/how-to-use-profile-guided-optimizations-in-g )
Ca marche aussi avec msvc. http://msdn.microsoft.com/en-us/library/xct6db7f%28v=vs.80%29.aspx

Tu peux aussi faire du link-time-optimization avec les dernières versions de gcc (comme avec msvc):
http://gcc.gnu.org/onlinedocs/gccint/LTO.html

Très intéressant. Ca devrait être mieux connu.

je crois que c'est bien le cas dans la spec du C.

true n'existe pas dans la spéc du C, c'est du C++

Le standard dit que &&, || et ! renvoient toujours 0 et 1, donc !! est la manière la plus rapide à écrire de convertir zéro/non-zéro en 0/1.

./22 > Pas également en C99 ?

Il y a des booléens natifs en C99 et en C++, mais il est clairement spécifié que lors de la conversion en entiers, true est converti en 1.

Ah oui tiens, ils ont rajouté ça dans le C99, j'avais pas fait attention.

Permettez-moi de m'incruster, mais je cherche à optimiser ça :

;========================================================
;
;       GetArchiveHandle
;
;       Return the handle of the archive to process
;
;       input   a0      Archive name (C-string)
;       ouput   d0.w    Handle of the archive if ERROR_CODE(a6) == AR_NO_ERROR. ERROR_CODE(a6) is set at the right value
;       destroy std
;========================================================

GetArchiveHandle:
        pea     (a0)
        moveq.l #$FFFFFFF8,d0                   ; OTH_TAG
        lea     ArchiveSignature(pc),a1
        jsr     CHECK_FILE_TYPE(a6)
        movea.l (sp)+,a0
        moveq.l #AR_NOT_AN_ARCHIVE,d1
        tst.w   d0
        beq.s   \ArchiveFound
                bpl.s   \Quit
                        moveq.l #AR_ARCHIVE_NOT_FOUND,d1
                        bra.s   \Quit

\ArchiveFound:
        jsr     GET_FILE_HANDLE(a6)
        moveq.l #AR_NO_ERROR,d1

\Quit:  move.w  d1,ERROR_CODE(a6)
        rts

C'est ce que j'ai écrit spontanément, j'aimerais savoir si votre manière d'optimiser les sauts s'appliquerait ici : on a trois possibilités pour d0, valeur de retour de CHECK_FILE_TYPE :
- < 0 si le fichier n'existe pas
- > 0 si le fichier existe, mais n'a pas le bon type
- = 0 si le fichier existe, a le bon type, et éventuellement un signature custom valide.

Merci d'avance.

Que veux-tu optimiser? En place, cette méthode ne permet pas de gagner quoi que ce soit. En vitesse, il faut savoir quel(s) cas tu veux optimiser, et prévoir une exécution linéaire pour ces cas.

Saint Folco, patron de la microoptimisation, priez pour nous

(tu ne crois pas que tu pousses un peu le bouchon, sérieusement ? )