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

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?

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.

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.

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.

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.

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.

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.

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)

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.

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.