Optimisation des ruptures du pipeline - Page 2

C'est votre technique exposée plus haut que j'ai pas bien comprise, j'ai du mal à voir la correspondance du if/else en C.

Je voulais juste savoir comment appliquer votre optimisation à mon code, sur le plan théorique, pas pour optimiser 2 cycles ^^

Ben en gros le cas le plus commun s'exécute en un flot d'instructions continu (aucun saut), tandis que le cas le moins commun s'exécute beaucoup plus loin avec un saut (conditionnel) pour y entrer, et un saut (inconditionnel) pour en sortir.

Après, j'aurais dit pareil que Kevin.

Vu que tu n'as pas précisé pour quel tu aurais voulu "optimiser" (faut compter le nombre de cycles, à priori sur 68k, un saut .b non exécuté coute moins cher qu'un saut .b exécuté), c'est difficile de te démontrer une "technique d'optimisation" "sans optimiser".

Dans ton cas, en supposant que tu veuilles "optimiser" pour le cas =0, ça reviendrait à remplacer le beq \ArchiveFound par un bne \ArchiveNotFound, et à déplacer le code qui suit le beqne plus loin (à la fin, quoi) et le préfixer du label \ArchiveNotFound.
(Mais attention à ne pas transformer un saut relatif 8 bits en saut relatif 16 bits en faisant ça…)

Ah, ok, merci.

Aller pour le plaisir :;======================================================== ; ; 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
T'es un amour Bob

C'est le même code non ?

(notes au passagela mise en forme... ça ressemble à un test pour vérifier que ça marche quand on poste)

Folco (./31) :
C'est votre technique exposée plus haut que j'ai pas bien comprise, j'ai du mal à voir la correspondance du if/else en C.

Je voulais juste savoir comment appliquer votre optimisation à mon code, sur le plan théorique, pas pour optimiser 2 cycles ^^

De ce que je me rappelle, ce dont ils parlent sur ce topic ne te sert à rien sur un 68k comme celui de la TI car la rupture de pipeline n'a pas d'importance. (en fait, il y a moins de choses à se soucier pour optimiser : pas de cache, pas de prédiction de saut, pas d'instructions conditionnelles, pas de waitstate, etc.)

Il y a une légère différence toutefois au niveau du timing entre un saut conditionnel emprunté et non emprunté. (Mais seulement en .b ?)

vince : Ah oui en effet J'ai cru qu'il voulait montrer la version suggérée par GoldenCrystal. Pas mal du tout cette coloration. C'est généré à chaque affichage ou mis en cache ?

Folco : Pour compléter la réponse de Brunni avec mon peu de connaissances, le pipeline c'est le système qui consiste, sur les processeurs modernes, à paralléliser les 4 étapes successives qui sont nécessaires pour exécuter une instruction (de mémoire : lecture, décodage, exécution, écriture). Chaque instruction passe successivement dans ces 4 modules, donc nécessite au moins 4 cycles pour s'exécuter comme sur 68k, mais, pendant qu'une instruction est traitée par un module, le module précédent traite l'instruction suivante. Il y a donc une instruction qui rentre dans le pipeline et une instruction qui se termine à chaque cycle, ainsi le temps d'exécution moyenné d'une instruction n'est plus que de 1 cycle. Le problème de ce système intelligent, c'est qu'un saut conditionnel introduit un doute sur les instructions qui suivront, donc sur les instructions à charger dans le pipeline. En cas de mauvaise prédiction, il faut annuler le travail des 3 premiers modules et leur donner successivement les nouvelles instructions, donc aucun résultat ne sort du processeur durant les 4 cycles suivants.

Dans un code qui comporte beaucoup d'alternatives, mal prédire peut tendre à diviser par 4 la vitesse d'exécution. Il doit probablement exister des tels cas d'école, mais je crois que les programmes réels sont plutôt bien prédits.

Il me semble que le 68K a bien un pipeline. Il faut d'ailleurs s'en méfier lorsqu'on modifie le code à la volée.

Il y a effectivement un pipeline tout court, qui se limite au prefetch des instructions dans le cache d'instructions. Il n'y a pas les autres étapes d'un pipeline moderne.

./39 > C'est encore bien plus compliqué que ça, malheureusement
Le pipeline peut être bien plus profond que juste 4 instructions, et pour rentabiliser au mieux le CPU, l'exécution est effectuée dans le désordre (OOE: Out of Order Execution), d'où (entre autres) la nécessité de bien placer ses barrières mémoire dans du code parallèle.
Une mauvaise prédiction de branchement va annuler toutes les opérations déjà effectuées (potentiellement certaines instructions suivant le saut pourraient déjà avoir été exécutées "entièrement"...).
Mais en plus de ça, une erreur de prédiction peut aussi provoquer un cache miss, donc engendrer un surcoût supplémentaire...

Je recommande ca à ceux qui se demandent comment sont prédits les branchements :
www.siteduzero.com/tutoriel-3-620252-les-branchements-viennent-mettre-un-peu-d-ambiance.html

Il y a probablement mieux (j'ai repéré plusieurs petites erreurs), mais on apprend quand même beaucoup de choses.

(pas encore lu) mémoire associative PC <-> saut pris/pas pris, j'ai bon?

edit: (lu) pas mal l'itanium

[cross] Ils disent qu'un cache associatif est souvent utilisé pour retenir les adresses des branchements. Pour la prédiction, ils donnent des méthodes assez sympa

ah oui y'a plein de méthodes en fait.

Bon j'arrive un peu apres la bataille

./3>
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 ?)

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

non, pas d'equivalent sous VC++, principalement parceque la plupart des architectures pour lesquelles VC++ compile n'ont pas d'encoding specifique des hints de branchements au niveau des instructions asm directement.
contrairement, par exemples, aux PPC, ou tu peux directement ecrire un truc comme:

jge+ _Label	# dit au CPU de supposer que le jump sera execute
jge- _Label	# dit au CPU de supposer que le jump ne sera pas execute

le hint donne a GCC, sur les architectures qui supportent ca, va souvent directement se traduire par un flagging de l'instruction generee par la backend. Alors que sur les architectures ne le supportant pas (x86-64 par exemple), ca aura pour effet de convertir, lorsque les bon flags d'optimisation sont actives:

if (unlikely(condition))
	B();
else
	A();

en:

if (!condition)
	A();
else
	B();

dans visual, il faut le faire a la main, mais c'est _beaucoup_ moins genant de pas avoir ce genre de hints sur les x86 recents, du a la prediction dynamique des branchement (cf le Branch-Target-Buffer dans un des derniers liens postes. C'est en gros un historique des dernieres branches prises, on peut voir ca comme une sorte de hashmap qui mappe des addresses d'instructions de branchements avec un petit historique des derniers jumps effectues, et qui se sert de cet historique pour predire les branchements suivants. (il y a d'autres subtilites dans la prediction, mais, pour resumer, le CPU se demmerde vraiment tres bien, lorsque les jumps suivent un pattern pas trop complexe)).

./10>
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

Ca, c'est pas pour economiser un jump statique (qui est en gros gratuit sur les architectures recentes), mais pour separer le "code froid" du "code chaud". Avoir plein de if/else avec un seul des blocs execute la plupart du temps et l'autre quasiment jamais, ca produit des "bulles" de code froid au milieu du code chaud.

Et ca a pour effet d'augmenter enormement le nombre d'octets inutiles par cache-line dans l'Instruction cache. donc plus de cache misses inutiles
sans ce genre d'optimisations, le ratio instructions executee / nombre de cache-lines fetch dans l'instruction cache peut vite devenir assez bas, et sous-optimal.
avec ces optims, la plupart du temps, toutes les instructions dans les lignes de cache fetchees sont du code utile.
et de temps en temps, l'execution saute dans une zone "froide", loade une cache-line, s'execute, et retourne au code chaud.

./39>Folco : Pour compléter la réponse de Brunni avec mon peu de connaissances, le pipeline c'est le système qui consiste, sur les processeurs modernes, à paralléliser les 4 étapes successives qui sont nécessaires pour exécuter une instruction (de mémoire : lecture, décodage, exécution, écriture). Chaque instruction passe successivement dans ces 4 modules, donc nécessite au moins 4 cycles pour s'exécuter comme sur 68k, mais, pendant qu'une instruction est traitée par un module, le module précédent traite l'instruction suivante. Il y a donc une instruction qui rentre dans le pipeline et une instruction qui se termine à chaque cycle, ainsi le temps d'exécution moyenné d'une instruction n'est plus que de 1 cycle

./42>

c'est _BEAUCOUP_ plus complexe que 4 etapes successives.
les pipelines modernes peuvent avoir des profondeurs qui depassent les 30 cycles/"etapes".
une seule misprediction de branchement, et ca flushe tout le pipeline.
sachant que certaines instructions peuvent etre schedulees entre deux et 4 fois PAR CYCLE, je te laisse imaginer l'impact que ca peut avoir sur les perfs
(bon c'est pas aussi violent que "4*30 instructions de penalite" hein , il y a des interactions plus complexes entre les differents ports d'execution et autres trucs marrants dans le pipeline qui font que t'as jamais autant d'instructions en meme temps en cours de traitement dans ton pipeline)

Et sur les CPUs hyper-threades (genre les core-i7, ou des core2-quad HT, qui n'ont que 2 vrais cores), il y a encore des trucs en plus, les unites d'execution sont partagees dans les deux threads hardware, mais chaque hyper-thread a son propre bout de silicium pour fetch et decoder les instructions, donc les interactions peuvent devenir extremement complexes, voire pas calculables du tout, vu que la performance de ton bout d'asm micro-optimise aux petits oignons va dependre de quel autre process est schedule sur l'autre hyper-thread de ton core.

bref... ^^

c'est pour ca que ca sert souvent a grand chose de compter les cycles sur les CPUs modernes (ie: c'est pas toujours faisable), et qu'il vaut mieux profiler le code dans son cas reel d'utilisation

d'ailleurs a propos des cycles des instructions, il y a deux metriques bien distinctes:
- le throughput : le nombre de cycles a attendre avant que le pipeline du CPU puisse accepter une autre instruction de ce type (ca peut etre < 1 cycle : plusieurs instructions displatchees par cycle)
- la latence: le nombre de cycles que tu dois attendre avant de pouvoir utiliser le resultat d'une instruction. (le vrai "cout" en cycles de l'instruction, mais on ne peut pas se baser uniquement la dessus, vu que des instructions qui s'executent sur un autre port d'execution peuvent etre executees en parallele, du moment qu'elles n'ont pas besoin du resultat pour faire leurs calculs)


Si ca t'interesse, je te conseille d'aller jeter un oeil ici, c'est le meilleur doc sur le sujet que je connaisse:

http://www.agner.org/optimize/
http://www.agner.org/optimize/optimization_manuals.zip

(hors consoles, evidemment )

bearbecue (./47) :
c'est pour ca que ca sert souvent a grand chose de compter les cycles sur les CPUs modernes (ie: c'est pas toujours faisable), et qu'il vaut mieux profiler le code dans son cas reel d'utilisation

De toute façon, même avec des vieux processeurs il fallait déjà se méfier de tout ces mangeurs de cycles

bearbecue (./47) :
Et sur les CPUs hyper-threades (genre les core-i7, ou des core2-quad HT, qui n'ont que 2 vrais cores), il y a encore des trucs en plus, les unites d'execution sont partagees dans les deux threads hardware, mais chaque hyper-thread a son propre bout de silicium pour fetch et decoder les instructions, donc les interactions peuvent devenir extremement complexes, voire pas calculables du tout, vu que la performance de ton bout d'asm micro-optimise aux petits oignons va dependre de quel autre process est schedule sur l'autre hyper-thread de ton core.

bref... ^^

c'est pour ca que ca sert souvent a grand chose de compter les cycles sur les CPUs modernes (ie: c'est pas toujours faisable), et qu'il vaut mieux profiler le code dans son cas reel d'utilisation

Bref, vive -Os, au moins c'est une métrique déterministe et facile à quantifier!

plutot vive -O3 /o/
(de toutes facons, autant que je sache, GCC ne sait pas optimiser en prenant en compte l'HyperThreading ^^ (en tout cas je vois pas comment il pourrait faire ))

Bearbecue, tu répètes ce qui a déjà été dit, mais merci pour tes développements, c'est intéressant.

bearbecue (./50) :
plutot vive -O3 /o/

Bah non, l'optimisation en vitesse ne peut être qu'approximative, l'optimisation en taille est clairement définie et modélisable.

et alors ?

Il vaut mieux optimiser quelque chose où les effets sont immédiatement quantifiables que de faire de la devinette.

Ben si le programme est 2x plus rapide avec -O3, c'est parfaitement quantifiable : Il est 2x plus rapide…

(et on est pas à cent octets près)

Kevin : Oui la taille des binaires est le critère prioritaire. C'est pour ça que GTC est préférable à GCC -Os et le mode kernel recommandé.

KK ./52> ./54> "tiens je planterais bien des patates . hmm mais il y a un risque pour que ca pousse pas , alors que si je les jette, je suis sur que c'est clairement quantifiable, ca poussera jamais "
#jette les patates germees# /o/
#va a velo acheter des patates a l'epicerie bio#



(ok les patates peuvent aussi pousser dans la poubelle suivant le temps qu'elles y restent, mais bon c'est a peu pres equivalent a un -Os qui sera plus rapide "avec un peu de bol" )
et tfacons Kevin, t'es off-topic, la question c'est clairement l'optimisation en vitesse, et pour le coup entre -Os et -O3 le moins clairement quantifiable c'est bien -Os


sinon, je suis d'accord qu'optimiser en taille est bon aussi, reduire la taille du code a loader dans l'I-Cache ne peut pas etre mauvais ^^

Perso j'optimise certaines parties en vitesse ou en taille effectivement, en fonction de la fréquence d'accès et la taille (estimée) de la boucle. Mais c'est toujours assez délicat ce genre de choses, ça change avec le temps (proço, compilo ou code mis à jour).

Et KK c'est juste parce que comme ses dépôts qui doivent tout contenir doivent rester gratuits et libres, il faut que les binaires soient le plus petit possible c'est tout (et comme sous Linux la seule place est prise par le code, pas par les ressources, ça a du sens de compiler en -Os).

Perso j'optimise certaines parties en vitesse ou en taille effectivement, en fonction de la fréquence d'accès et la taille (estimée) de la boucle. Mais c'est toujours assez délicat ce genre de choses, ça change avec le temps (proço, compilo ou code mis à jour).

ouais c'est pour ca que l'optim sur consoles c'est bien cool
le hardware change pas et tu peux faire de l'optim ultra-specifique.