Quand, si jamais, c'est la déroulement de la boucle encore utile?

Question

J'ai essayé d'optimiser certains extrêmement critiques des performances de code (un rapide algorithme de tri qui est appelé des millions et des millions de fois à l'intérieur d'une simulation de monte carlo) par le déroulement de la boucle. Voici la boucle interne, je suis en train d'accélérer:

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

J'ai essayé de le 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
}

De ce fait absolument aucune différence, donc je l'ai changé de retour à la forme plus lisible. J'ai eu des expériences similaires d'autres fois, j'ai essayé de déroulement de la boucle. Compte tenu de la qualité de la direction des prédicteurs sur le matériel moderne, quand, si jamais, le déroulement de la boucle est toujours utile d'optimisation?

Answer 1

Déroulement de la boucle de sens que si vous pouvez rompre la dépendance des chaînes. Cela donne un ordre ou d'un super-scalaire du PROCESSEUR possibilité de planifier les choses mieux et ainsi courir plus vite.

Un exemple simple:

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

Ici, la dépendance de la chaîne des arguments est très court. Si vous obtenez un décrochage parce que vous avez un cache-miss sur les données de la matrice de la cpu ne peut rien faire que d'attendre.

Otoh, que 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 cache miss ou d'autres décrochage dans un calcul il y a encore trois autres de la dépendance des chaînes qui ne dépendent pas de la stalle. Un PROCESSEUR peut exécuter ces.

Answer 2

Ceux qui ne serait pas faire une différence parce que vous êtes en train de faire 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 alors il est presque certainement n'a pas d'importance, mais vous êtes en train de faire 50 comparaisons au lieu de 200 (imaginez la comparaison est plus complexe).

Manuel de déroulement de la boucle, en général, est en grande partie un artefact de l'histoire, cependant. C'est un autre de la liste de plus en plus de choses qu'un bon compilateur va faire pour vous quand il le faut. Par exemple, la plupart des gens ne pas s'embêter à écrire x << 1 ou x += x au lieu de x *= 2. Vous venez d'écrire, x *= 2 et le compilateur d'optimiser pour vous à ce qui est meilleur.

Fondamentalement, il y a de moins en moins besoin de deviner votre compilateur.

Answer 3

Indépendamment de la direction de la prévision sur le matériel moderne, la plupart des compilateurs n'déroulement de la boucle pour vous de toute façon.

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

J'ai trouvé Felix von Leitner présentation très éclairante sur le sujet. Je vous recommande de le lire. Résumé: les compilateurs Modernes sont TRÈS intelligents, de sorte que la main d'optimisations sont presque jamais efficace.

Answer 4

Aussi loin que je le comprends, les compilateurs modernes déjà dérouler les boucles, le cas échéant, par exemple, gcc, si elle est adoptée à l'optimisation des drapeaux le manuel dit:

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

Donc, dans la pratique, il est probable que votre compilateur ne les cas triviaux pour vous. C'est à vous donc de faire en sorte que le plus grand nombre possible de vos boucles sont faciles pour le compilateur de déterminer le nombre d'itérations nécessaires.

Answer 5

Déroulement de la boucle, si c'est la main de dérouler ou le compilateur déroulage, peut souvent être contre-productif, en particulier avec les plus récentes les Processeurs x86 (2 Core, Core i7). Bottom line: tester les performances de votre code avec et sans déroulement de la boucle sur tout les Processeurs sur lesquels vous envisagez de déployer ce code sur.