Optimiser un “while (1);” en C ++ 0x

Est-ce que quelqu’un a une bonne explication de la raison pour laquelle cela était nécessaire?

Oui, Hans Boehm en fournit la justification dans N1528: Pourquoi un comportement indéfini pour les boucles infinies? , bien que ce soit le document WG14, la justification s’applique également à C ++ et le document fait référence à la fois au GT14 et au GT21:

Comme le souligne correctement N1509, le brouillon actuel donne essentiellement un comportement indéfini aux boucles infinies du 6.8.5p6. Un problème majeur pour ce faire est qu’il permet au code de se déplacer à travers une boucle potentiellement non terminale. Par exemple, supposons que nous ayons les boucles suivantes, où count et count2 sont des variables globales (ou dont l’adresse a été prise), et p est une variable locale dont l’adresse n’a pas été prise:

 for (p = q; p != 0; p = p -> next) { ++count; } for (p = q; p != 0; p = p -> next) { ++count2; } 

Ces deux boucles pourraient-elles être fusionnées et remplacées par la boucle suivante?

 for (p = q; p != 0; p = p -> next) { ++count; ++count2; } 

Sans la dispense spéciale du 6.8.5p6 pour les boucles infinies, cela ne serait pas autorisé: si la première boucle ne se termine pas parce que q pointe sur une liste circulaire, l’original n’écrit jamais dans count2. Ainsi, il pourrait être exécuté en parallèle avec un autre thread qui accède ou met à jour count2. Ce n’est plus sûr avec la version transformée qui accède à count2 malgré la boucle infinie. Ainsi, la transformation introduit potentiellement une course aux données.

Dans de tels cas, il est très peu probable qu’un compilateur soit capable de prouver la terminaison de la boucle; il devrait comprendre que q désigne une liste acyclique, qui, à mon avis, dépasse les capacités de la plupart des compilateurs traditionnels et est souvent impossible sans des informations complètes sur le programme.

Les ressortingctions imposées par les boucles sans terminaison sont une ressortingction à l’optimisation des boucles de terminaison pour lesquelles le compilateur ne peut pas prouver la terminaison, ainsi qu’à l’optimisation de boucles réellement non terminées. Les premiers sont beaucoup plus communs que les seconds et souvent plus intéressants à optimiser.

Il existe clairement des boucles for-lo avec une variable de boucle entière dans laquelle il serait difficile pour un compilateur de prouver une terminaison, et il serait donc difficile pour le compilateur de restructurer des boucles sans 6.8.5p6. Même quelque chose comme

 for (i = 1; i != 15; i += 2) 

ou

 for (i = 1; i <= 10; i += j) 

semble indifférent à manipuler. (Dans le premier cas, une théorie des nombres de base est nécessaire pour prouver la terminaison, dans ce dernier cas, nous devons connaître les valeurs possibles de j. Le regroupement des entiers non signés peut compliquer davantage ce raisonnement. )

Ce problème semble s’appliquer à presque toutes les transformations de restructuration de boucle, y compris les transformations de la parallélisation du compilateur et de l’optimisation du cache. Cela semble se transformer en un coût substantiel pour pouvoir écrire des boucles infinies de la manière la plus naturelle possible, d'autant plus que la plupart d'entre nous écrivent rarement des boucles intentionnellement infinies.

La seule différence majeure avec C est que C11 fournit une exception pour contrôler les expressions qui sont des expressions constantes qui diffèrent de C ++ et rend votre exemple spécifique bien défini dans C11.

Pour moi, la justification pertinente est la suivante:

Ceci est destiné à permettre les transformations du compilateur, telles que la suppression des boucles vides, même lorsque la terminaison ne peut pas être prouvée.

Cela est probablement dû au fait qu’il est difficile de prouver que la terminaison est mécanique, et que l’incapacité à prouver la terminaison entrave les transformations, telles que déplacer des opérations indépendantes de la boucle ou inversement. la boucle s’exécute dans un autre, et ainsi de suite. Sans ces transformations, une boucle peut bloquer tous les autres threads pendant qu’ils attendent que le thread termine sa boucle. (J’utilise “thread” pour désigner toute forme de parallel processing, y compris des stream d’instructions VLIW séparés.)

EDIT: Exemple muet:

 while (complicated_condition()) { x = complicated_but_externally_invisible_operation(x); } complex_io_operation(); cout << "Results:" << endl; cout << x << endl; 

Ici, il serait plus rapide pour un thread de faire la complex_io_operation tandis que l'autre effectue tous les calculs complexes dans la boucle. Mais sans la clause que vous avez citée, le compilateur doit prouver deux choses avant de pouvoir faire l'optimisation: 1) que complex_io_operation() ne dépend pas des résultats de la boucle, et 2) que la boucle se terminera . Prouver 1) est assez facile, prouvant 2) est le problème majeur. Avec la clause, elle peut supposer que la boucle se termine et obtenir un gain de parallélisation.

J'imagine aussi que les concepteurs ont considéré que les cas où des boucles infinies se produisent dans le code de production sont très rares et sont généralement des choses comme les boucles événementielles qui accèdent aux E / S d'une certaine manière. En conséquence, ils ont pessimisé le cas rare (boucles infinies) en faveur de l'optimisation du cas le plus courant (boucles non infinies, mais difficiles à prouver mécaniquement non-finies).

Cela signifie toutefois que les boucles infinies utilisées dans les exemples d’apprentissage en souffriront, ce qui entraînera des pièges dans le code du débutant. Je ne peux pas dire que c'est entièrement une bonne chose.

EDIT: en ce qui concerne l'article perspicace que vous liez maintenant, je dirais que "le compilateur peut supposer X à propos du programme" est logiquement équivalent à "si le programme ne satisfait pas X, le comportement n'est pas défini". Nous pouvons montrer ceci comme suit: supposons qu’il existe un programme qui ne satisfait pas à la propriété X. Où le comportement de ce programme serait-il défini? La norme définit uniquement le comportement en supposant que la propriété X est vraie. Bien que la norme ne déclare pas explicitement le comportement non défini, elle l'a déclaré non défini par omission.

Considérons un argument similaire: "le compilateur peut supposer qu'une variable x n'est affectée qu'au plus une fois entre les points de séquence" équivaut à "assigner à x plus d'une fois entre les points de séquence n'est pas défini".

Je pense que l’interprétation correcte est celle de votre édition: les boucles infinies vides sont un comportement indéfini.

Je ne dirais pas que c’est un comportement particulièrement intuitif, mais cette interprétation a plus de sens que l’autre, à savoir que le compilateur est autorisé arbitrairement à ignorer les boucles infinies sans invoquer UB.

Si les boucles infinies sont UB, cela signifie simplement que les programmes non-terminants ne sont pas considérés comme significatifs: selon C ++ 0x, ils n’ont aucune sémantique.

Cela a aussi un certain sens. Ils constituent un cas particulier, où un certain nombre d’effets secondaires ne se produisent plus (par exemple, rien n’est jamais renvoyé de main ) et un certain nombre d’optimisations du compilateur sont entravées par la nécessité de conserver des boucles infinies. Par exemple, déplacer des calculs sur la boucle est parfaitement valide si la boucle n’a pas d’effets secondaires, car le calcul sera finalement effectué dans tous les cas. Mais si la boucle ne se termine jamais, nous ne pouvons pas réorganiser le code en toute sécurité, car nous pourrions simplement modifier les opérations réellement exécutées avant que le programme ne se bloque. Sauf si nous traitons un programme suspendu comme UB.

Je pense que cela va dans le sens de ce type de question , qui fait référence à un autre fil . L’optimisation peut parfois supprimer des boucles vides.

Le problème est que le compilateur est autorisé à réorganiser le code dont les effets secondaires ne sont pas en conflit. L’ordre d’exécution surprenant pourrait se produire même si le compilateur produisait un code machine sans fin pour la boucle infinie.

Je crois que c’est la bonne approche. La spécification de langage définit des moyens pour appliquer l’ordre d’exécution. Si vous voulez une boucle infinie qui ne peut pas être réorganisée, écrivez ceci:

 volatile int dummy_side_effect; while (1) { dummy_side_effect = 0; } printf("Never prints.\n"); 

Je pense que le mieux serait peut-être d’énoncer le problème comme suit: «Si un morceau de code ultérieur ne dépend pas d’un élément de code antérieur et que le code précédent n’a aucun effet secondaire sur une autre partie du système, la sortie du compilateur peut exécuter le dernier morceau de code avant, après ou mélangé avec l’exécution du premier, même si le premier contient des boucles, sans tenir compte du moment ou du fait que le code précédent serait réellement complet .

 void testfermat (int n)
 {
   int a = 1, b = 1, c = 1;
   while (pow (a, n) + pow (b, n)! = pow (c, n))
   {
     si (b> a) a ++;  sinon si (c> b) {a = 1;  b ++};  sinon {a = 1;  b = 1;  c ++};
   }
   printf ("Le résultat est");
   printf ("% d /% d /% d", a, b, c);
 }

comme

 void testfermat (int n)
 {
   if (fork_is_first_thread ())
   {
     int a = 1, b = 1, c = 1;
     while (pow (a, n) + pow (b, n)! = pow (c, n))
     {
       si (b> a) a ++;  sinon si (c> b) {a = 1;  b ++};  sinon {a = 1;  b = 1;  c ++};
     }
     signal_other_thread_and_die ();
   }
   sinon // Deuxième thread
   {
     printf ("Le résultat est");
     wait_for_other_thread ();
   }
   printf ("% d /% d /% d", a, b, c);
 }

Généralement pas déraisonnable, même si je crains que:

   int total = 0;
   pour (i = 0; num_reps> i; i ++)
   {
     update_progress_bar (i);
     total + = do_something_slow_with_no_side_effects (i);
   }
   show_result (total);

deviendrait

   int total = 0;
   if (fork_is_first_thread ())
   {
     pour (i = 0; num_reps> i; i ++)
       total + = do_something_slow_with_no_side_effects (i);
     signal_other_thread_and_die ();
   }
   autre
   {
     pour (i = 0; num_reps> i; i ++)
       update_progress_bar (i);
     wait_for_other_thread ();
   }
   show_result (total);

En ayant un processeur qui gère les calculs et un autre qui gère les mises à jour de la barre de progression, la réécriture améliore l’efficacité. Malheureusement, cela rendrait les mises à jour des barres de progression moins utiles qu’elles ne le devraient.

Il n’est pas décidable pour le compilateur pour les cas non sortingviaux s’il s’agit d’une boucle infinie.

Dans différents cas, il peut arriver que votre optimiseur atteigne une classe de complexité supérieure pour votre code (par exemple, il s’agit de O (n ^ 2) et vous obtenez O (n) ou O (1) après l’optimisation).

Donc, inclure une telle règle interdisant de supprimer une boucle infinie dans le standard C ++ rendrait impossible de nombreuses optimisations. Et la plupart des gens ne veulent pas cela. Je pense que cela répond parfaitement à votre question.

Autre chose: je n’ai jamais vu d’exemple valable où vous ayez besoin d’une boucle infinie qui ne fait rien.

Le seul exemple dont j’ai entendu parler est un hack moche qui devrait être résolu autrement: il s’agissait de systèmes embarqués où le seul moyen de déclencher une réinitialisation était de geler le périphérique pour que le watchdog le redémarre automatiquement.

Si vous connaissez un exemple valable / bon où vous avez besoin d’une boucle infinie qui ne fait rien, s’il vous plaît dites-le moi.

Je pense qu’il est utile de souligner que les boucles qui seraient infinies, à l’exception du fait qu’elles interagissent avec d’autres threads via des variables non-volatiles et non-synchronisées, peuvent désormais entraîner un comportement incorrect avec un nouveau compilateur.

En d’autres termes, rendre vos globales volatiles – ainsi que les arguments transmis à une telle boucle via un pointeur / référence.