Quand, le cas échéant, le déroulement de boucle est-il encore utile?

93

J'ai essayé d'optimiser un code extrêmement critique pour les performances (un algorithme de tri rapide appelé des millions et des millions de fois dans une simulation de Monte Carlo) en déroulant une boucle. Voici la boucle intérieure que j'essaie d'accélérer:

// Search for elements to swap.
while(myArray[++index1] < pivot) {}
while(pivot < myArray[--index2]) {}

J'ai essayé de dérouler quelque chose comme:

while(true) {
    if(myArray[++index1] < pivot) break;
    if(myArray[++index1] < pivot) break;
    // More unrolling
}


while(true) {
    if(pivot < myArray[--index2]) break;
    if(pivot < myArray[--index2]) break;
    // More unrolling
}

Cela n'a fait absolument aucune différence, alors je l'ai changé pour une forme plus lisible. J'ai eu des expériences similaires d'autres fois, j'ai essayé le déroulement de boucle. Compte tenu de la qualité des prédicteurs de branche sur le matériel moderne, quand, le cas échéant, le déroulement de boucle est-il encore une optimisation utile?

dsimcha
la source
1
Puis-je vous demander pourquoi vous n'utilisez pas les routines de tri rapide de bibliothèque standard?
Peter Alexander
14
@Poita: Parce que les miennes ont des fonctionnalités supplémentaires dont j'ai besoin pour les calculs statistiques que je fais et sont très bien adaptées à mes cas d'utilisation et donc moins générales mais mesurables plus rapidement que la bibliothèque standard. J'utilise le langage de programmation D, qui a un vieil optimiseur de merde, et pour les grands tableaux de flottants aléatoires, je bat toujours le tri C ++ STL de GCC de 10 à 20%.
dsimcha

Réponses:

122

Le déroulement en boucle a du sens si vous pouvez rompre les chaînes de dépendances. Cela donne à un CPU hors service ou super-scalaire la possibilité de mieux planifier les choses et donc de fonctionner plus rapidement.

Un exemple simple:

for (int i=0; i<n; i++)
{
  sum += data[i];
}

Ici, la chaîne de dépendance des arguments est très courte. Si vous obtenez un blocage parce que vous avez un manque de cache sur le tableau de données, le processeur ne peut rien faire d'autre que d'attendre.

D'autre part ce code:

for (int i=0; i<n; i+=4)
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;

pourrait courir plus vite. Si vous obtenez un échec de cache ou un autre blocage dans un calcul, il y a encore trois autres chaînes de dépendances qui ne dépendent pas du blocage. Une CPU hors service peut les exécuter.

Nils Pipenbrinck
la source
2
Merci. J'ai essayé le déroulement en boucle dans ce style dans plusieurs autres endroits de la bibliothèque où je calcule des sommes et des choses, et dans ces endroits, cela fonctionne à merveille. Je suis presque sûr que la raison est que cela augmente le parallélisme des niveaux d'instruction, comme vous le suggérez.
dsimcha
2
Belle réponse et exemple instructif. Bien que je ne vois pas comment les blocages sur les échecs de cache pourraient affecter les performances pour cet exemple particulier . Je suis venu m'expliquer les différences de performances entre les deux morceaux de code (sur ma machine le deuxième morceau de code est 2 à 3 fois plus rapide) en notant que le premier désactive tout type de parallélisme au niveau des instructions dans les voies en virgule flottante. Le second permettrait à un processeur super-scalaire d'exécuter jusqu'à quatre ajouts en virgule flottante en même temps.
Toby Brull
2
Gardez à l'esprit que le résultat ne sera pas numériquement identique à la boucle d'origine lors du calcul d'une somme de cette façon.
Barabas
La dépendance portée par la boucle est un cycle , l'addition. Un noyau OoO fera l'affaire. Ici, le déroulement peut aider SIMD en virgule flottante, mais ce n'est pas à propos de OoO.
Veedrac
2
@Nils: Pas beaucoup; Les processeurs x86 OoO grand public sont toujours assez similaires aux Core2 / Nehalem / K10. Le rattrapage après un échec de cache était encore assez mineur, masquer la latence FP était toujours le principal avantage. En 2010, les processeurs capables de faire 2 charges par horloge étaient encore plus rares (juste AMD car SnB n'était pas encore sorti), donc plusieurs accumulateurs étaient certainement moins précieux pour le code entier que maintenant (bien sûr, c'est du code scalaire qui devrait auto-vectoriser , alors qui sait si les compilateurs transformeront plusieurs accumulateurs en éléments vectoriels ou en plusieurs accumulateurs vectoriels ...)
Peter Cordes
25

Cela ne ferait aucune différence parce que vous faites le même nombre de comparaisons. Voici un meilleur exemple. Au lieu de:

for (int i=0; i<200; i++) {
  doStuff();
}

écrire:

for (int i=0; i<50; i++) {
  doStuff();
  doStuff();
  doStuff();
  doStuff();
}

Même dans ce cas, cela n'aura presque certainement pas d'importance, mais vous faites maintenant 50 comparaisons au lieu de 200 (imaginez que la comparaison est plus complexe).

Cependant, le déroulement manuel de la boucle est en grande partie un artefact de l'histoire. C'est une autre de la liste croissante de choses qu'un bon compilateur fera pour vous quand cela compte. Par exemple, la plupart des gens ne prennent pas la peine d'écrire x <<= 1ou à la x += xplace x *= 2. Vous venez d'écrire x *= 2et le compilateur l'optimisera pour vous à ce qui est le mieux.

Fondamentalement, il est de moins en moins nécessaire de remettre en question votre compilateur.

cletus
la source
1
@Mike Désactiver l'optimisation est certainement une bonne idée quand on est perplexe, mais cela vaut la peine de lire le lien publié par Poita_. Les compilateurs deviennent extrêmement bons dans ce domaine.
dmckee --- ex-moderator chaton
16
@Mike "Je suis parfaitement capable de décider quand ou quand ne pas faire ces choses" ... J'en doute, sauf si vous êtes surhumain.
Mr. Boy
5
@John: Je ne sais pas pourquoi tu dis ça; les gens semblent penser que l'optimisation est une sorte d'art noir que seuls les compilateurs et les bons devineurs savent faire. Tout se résume aux instructions et aux cycles et aux raisons pour lesquelles ils sont dépensés. Comme je l'ai expliqué à maintes reprises sur SO, il est facile de dire comment et pourquoi ces sommes sont dépensées. Si j'ai une boucle qui doit utiliser un pourcentage de temps significatif et qu'elle passe trop de cycles dans la boucle, par rapport au contenu, je peux la voir et la dérouler. Idem pour le levage de code. Il ne faut pas un génie.
Mike Dunlavey
3
Je suis sûr que ce n'est pas si difficile, mais je doute toujours que vous puissiez le faire aussi vite que le compilateur. Quel est le problème avec le compilateur qui le fait pour vous de toute façon? Si vous ne l'aimez pas, désactivez simplement les optimisations et brûlez votre temps comme en 1990!
M. Boy
2
Le gain de performances dû au déroulement de la boucle n'a rien à voir avec les comparaisons que vous enregistrez. Rien du tout.
bobbogo
14

Indépendamment de la prédiction de branche sur le matériel moderne, la plupart des compilateurs effectuent de toute façon un déroulement en boucle pour vous.

Il serait intéressant de savoir combien d'optimisations votre compilateur fait pour vous.

J'ai trouvé la présentation de Felix von Leitner très éclairante sur le sujet. Je vous recommande de le lire. Résumé: Les compilateurs modernes sont TRÈS intelligents, donc les optimisations manuelles ne sont presque jamais efficaces.

Peter Alexander
la source
7
C'est une bonne lecture, mais la seule partie que je pensais être sur la marque était où il parle de garder la structure des données simple. Le reste était exact mais repose sur une hypothèse géante et non déclarée - que ce qui est exécuté doit l' être. Dans le réglage que je fais, je trouve que les gens s'inquiètent des registres et des échecs de cache lorsque des quantités massives de temps passent dans des montagnes inutiles de code d'abstraction.
Mike Dunlavey
3
"Les optimisations manuelles ne sont presque jamais efficaces" → Peut-être vrai si vous êtes complètement nouveau dans la tâche. Tout simplement pas vrai autrement.
Veedrac
En 2019, j'ai encore effectué des déroulements manuels avec des gains substantiels par rapport aux tentatives automatiques du compilateur ... donc ce n'est pas si fiable de laisser le compilateur faire tout cela. Il semble ne pas se dérouler si souvent. Au moins pour c # je ne peux pas parler au nom de toutes les langues.
WDUK
2

Pour autant que je sache, les compilateurs modernes déroulent déjà des boucles le cas échéant - un exemple étant gcc, si vous passez les indicateurs d'optimisation, le manuel dit qu'il le fera:

Déroulez les boucles dont le nombre d'itérations peut être déterminé au moment de la compilation ou lors de l'entrée dans la boucle.

Donc, en pratique, il est probable que votre compilateur s'occupe des cas triviaux pour vous. C'est donc à vous de vous assurer que le plus grand nombre possible de vos boucles est facile pour le compilateur de déterminer combien d'itérations seront nécessaires.

Rich Bradshaw
la source
Les compilateurs juste à temps ne font généralement pas de déroulement de boucle, les heuristiques sont trop chères. Les compilateurs statiques peuvent y consacrer plus de temps, mais la différence entre les deux méthodes dominantes est importante.
Abel
2

Le déroulement en boucle, qu'il s'agisse du déroulement manuel ou du déroulement du compilateur, peut souvent être contre-productif, en particulier avec les processeurs x86 plus récents (Core 2, Core i7). En bout de ligne: comparez votre code avec et sans déroulement de boucle sur les processeurs sur lesquels vous prévoyez de déployer ce code.

Paul R
la source
Pourquoi en particulier sur les processeurs recet x86?
JohnTortugo
7
@JohnTortugo: Les processeurs x86 modernes ont certaines optimisations pour les petites boucles - voir par exemple Détecteur de flux de boucle sur les architectures Core et Nehalem - dérouler une boucle pour qu'elle ne soit plus assez petite pour tenir dans le cache LSD annule cette optimisation. Voir par exemple tomshardware.com/reviews/Intel-i7-nehalem-cpu,2041-3.html
Paul R
1

Essayer sans savoir n'est pas la manière de le faire.
Ce tri prend-il un pourcentage élevé du temps total?

Tout ce que fait le déroulement de la boucle, c'est de réduire la surcharge de la boucle d'incrémentation / décrémentation, de comparaison pour la condition d'arrêt et de saut. Si ce que vous faites dans la boucle prend plus de cycles d'instructions que la surcharge de la boucle elle-même, vous n'allez pas voir beaucoup d'amélioration en pourcentage.

Voici un exemple de la façon d'obtenir des performances maximales.

Mike Dunlavey
la source
1

Le déroulement en boucle peut être utile dans des cas spécifiques. Le seul gain n'est pas de sauter certains tests!

Cela peut par exemple permettre un remplacement scalaire, une insertion efficace de la prélecture logicielle ... Vous seriez surpris de son utilité (vous pouvez facilement obtenir une accélération de 10% sur la plupart des boucles même avec -O3) en déroulant agressivement.

Comme cela a été dit auparavant, cela dépend beaucoup de la boucle et le compilateur et l'expérience sont nécessaires. Il est difficile de faire une règle (ou l'heuristique du compilateur pour le déroulement serait parfaite)

Kamtchatka
la source
0

Le déroulement de la boucle dépend entièrement de la taille de votre problème. Cela dépend entièrement de la capacité de votre algorithme à réduire la taille en groupes de travail plus petits. Ce que vous avez fait ci-dessus ne ressemble pas à ça. Je ne sais pas si une simulation de Monte Carlo peut même être déroulée.

Un bon scénario pour le déroulement de la boucle serait de faire pivoter une image. Puisque vous pouvez faire pivoter des groupes de travail séparés. Pour que cela fonctionne, vous devez réduire le nombre d'itérations.

jwendl
la source
Je déroulais un tri rapide qui est appelé depuis la boucle interne de ma simulation, pas la boucle principale de la simulation.
dsimcha
0

Le déroulement de boucle est toujours utile s'il y a beaucoup de variables locales à la fois dans et avec la boucle. Pour réutiliser davantage ces registres au lieu d'en enregistrer un pour l'index de boucle.

Dans votre exemple, vous utilisez une petite quantité de variables locales, sans abuser des registres.

La comparaison (à la fin de la boucle) est également un inconvénient majeur si la comparaison est lourde (c'est-à-dire nontest instruction), surtout si elle dépend d'une fonction externe.

Le déroulement en boucle permet également de sensibiliser le processeur à la prédiction de branche, mais cela se produit quand même.

LiraNuna
la source