Bonjour.

Souvent, on parle de "branch (mis)prediction" pour parler du comportement du processeur lorsqu'il rencontre une condition if : http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array/11227902#11227902
Il "précharge" la suite des instructions qui lui semble la plus probable, et il les change si sa prédiction quant au résultat du if était fausse. C'est ce "rattrapage de dernière minute" qui peut diminuer la vitesse d’exécution d'un programme.

Lorsque je travaille sur un projet où les performances sont importantes, j'essaye donc de diminuer mon usage de if / else branches, quitte à faire quelques calculs en plus.

Par exemple, ce code aurait une très mauvaise prédiction de branche :

int n = rand() % 10;
if (n > 5) {
    ...
}

Cependant, je me demandais... Qu'en est-il des boucles for / while ? De ce que j'imagine, le processeur aura tout autant de mal à précharger les instructions que pour un if s'il ne connaît pas la valeur de la condition d'arrêt.

int n = rand() % 10;
for (int i = 0; i < n; i++) {
    ...
}

int n = rand() % 10;
while (n--) {
    ...
}

Après tout, le if est implicite dans ces boucles, mais il me semble être bien présent.

Est-on d'accord que ce type de boucle est aussi "mauvais" qu'un simple if ?

Dans le cas de tes boucles a la fin tu as bien un if pour savoir si il faut faire un jump a la premiere instruction de la boucle ou juste continuer (que ce soit un while ou un for, au final c'est juste du syntax sugar).

MAIS, il s'agit d'un if bien plus previsible que dans le 1er cas ou tu as une chance sur deux de te tromper.
Dans une boucle la condition est sur la valeur de n qui decroit petit a petit. Mettons que n soit egal a 5, la condition sera vraie 5 fois puis fausse une fois. C'est le meilleur cas possible en matiere de prediction puisqu'il y a tres peu de variation. Surtout qu'avec une valeur si petite le compilo risque meme de faire sauter completement la boucle en faisant du loop unrolling

De plus ton premier cas n'est vraiment penalisant que si il se trouve dans une boucle repetee plusieurs fois. 1 erreur de prediction ponctuelle n'a jamais tue personne.

le compilateur ne traduit pas systématiquement une structure de contrôle vers des branchements; les architectures modernes ont des instructions pour que le flot de contrôle soit statique même avec une condition.

par exemple les instructions CMOVxx avec x86 (conditional move).

if (rand() > 5)
  n = 1;
else
  n = 2;

naïvement

    call rand         ; appelle rand()
     cmp eax, 5       ; compare la valeur de retour a 5
      jg .greater5    ; si supérieur, branche vers .greater5
     mov [n], 2       ; n := 2
.greater5:
     mov [n], 1       ; n := 1

avec cmov, sans branchement

       mov [n], 2     ; n := 2
      call rand       ; appelle rand()
       cmp eax, 5     ; compare la valeur de retour a 5
    cmovjg [n], 1     ; si supérieur,  n := 1

au niveau de la micro-architecture, il peut y avoir de la prédication de branchement, les branchement possibles sont exécutés en parallèle mais seules les effets de la branche valide sont appliqués. Je doute que ce soit le cas avec les cpu x86, la prédication demande un jeu d'instructions adapté.

Qu'en est-il des boucles for / while ? De ce que j'imagine, le processeur aura tout autant de mal à précharger les instructions que pour un if s'il ne connaît pas la valeur de la condition d'arrêt.

Normalement, au niveau du code machine, il n'y a plus de if, de else, de while, ... qui sont explicites mais que des instructions de branchements semblables. Cependant, les micro-architectures modernes (< 8 ans) peuvent détecter les boucles d'une certaine taille pour mettre en cache les instructions dans un tampon afin d’améliorer la prédiction.

En moyenne la prediction de branchement se passe bien sur tous les codes avec un intel moderne. Je ne m'inquieterai pas de ca. Je fais de l'optimization performance dans la vie et je pense que j'ai tracke un probleme de performance important a probleme de prediction de branchement deux fois en 10 ans. Donc mon conseil: ne te fait pas chier avec ca.

Les problemes de perf les plus classique que je vois:
-probleme d'algo (les plus classique: programmation dynamique et hashage)
-probleme de langage (un calcul bien baveu fait en matlab, python, java, ou je sais pas quoi)
-utilisation d'objet a outrance
-code qui est execute mais qui ne sert a rien (souvent c'est un code qui fait plus que ce qu'il n'a a faire. Comme trier pour extraire le max)
-convertion de type a outrance (particulierement typique en python ou les gens stockent les donne dans des chaines et les cast en float pour faire les calcul et les recast en string apres. pourquoi? je sais pas... mais je le vois tout le temps)

Apres ca, il y a les moins classique
-pas d'utilisation de tous les cores
-I/O faite par petit block
-trop de transfert memoire (cache trashing ou IO a outrance)

Quand on a passer ca, ca devient un code raisonnable mais encore on finit par se taper:
-pas d'utilisation de la vectorization
-pas d'alignement memoire
-trop de mutex
-false sharing
-loop unrolling
-representation de donne (SoA vs AoS)

Si on en est la, le code est en general pas mal, mais on peut encore regarder
-optimization de tlb
-optimization du cached'instruction
-mix d'instruction sous optimal
-cache bypassing

Et si vraiment on veut plus:
-latence d'instruction
-prediction de branchement
-minimization du nombre de registre

Donc, en bref quand on commence a s'inquieter de la prediction de branchement, c'est qu'il n'y a plus grand chose a gagner.

Sans compter que plus on avance dans la liste (tres complete :D ) que tu proposes, moins le rapport "temps de dev" / "gain de perf" est important. Et a partir d'un certain stade on commence avoir un trade-off entre "maintenabilite" du code et "performance". L'optimisation precoce de code a souvent des effets negatifs a moyens termes.

Du coup j'aurais tendance a recommender de ne s'interesser, en cours de dev, qu'aux elements "haut niveau" (archi du framework adaptee au projet, bon outils/langages pour la situation, algos utilises intensivement non-naifs, etc.). Et ne s'attaquer aux choses plus fines que lorsque le moment est venu (les structure de donnees sont definitives, pas de changement majeur de features a prevoir, etc.) et s'aider d'outils profiler pour passer du temps la ou c'est utile.

Ne pas oublier non plus que generalement seule une petite partie du codebase contribue aux perfs constatees par l'utilisateur. Un algo un peu sous-optimal qui n'a utilise qu'une fois en demarrage d'application ne presente aucun interet en termes d'optimisation. Donc ne faire de l'opti que pour des problemes constates et averes.

godrik, y a pas aussi une histoire avec les cœurs jumeaux ?

chaque cœurs a un cache L1
deux cœurs partagent un cache L2
tous les cœurs partagent le cache L3

si deux cœurs qui ne partagent pas le même cache l2 communiquent on a

L1 -> L2 -> L3 -> L2 -> L1

alors qu'avec deux cœurs jumeaux

L1 -> L2 -> L1

oui, il y a les histoire de hierarchie de cache. Et aussi hyperthreading et numa effect. Mais c'est rare que les gens aient vraiment ce genre de probleme. Mais ca arrive en effet.

Super, merci beaucoup pour vos avis et retours d'expériences.

Je n'ai pas grande connaissance du comportement bas niveau du processeur, les erreurs de prédiction de branche semblent être bien amorties d'après ce que vous dites, donc je vais arrêter de trop les prendre en considération, et me focaliser sur les autres éléments importants cités par godrik.