Pourquoi les compilateurs sont-ils si stupides ?

Question

Je me demande toujours pourquoi les compilateurs ne peuvent pas comprendre des choses simples qui sont évidentes pour l'œil humain. Ils font beaucoup d'optimisations simples, mais jamais de choses un tant soit peu complexes. Par exemple, ce code prend environ 6 secondes sur mon ordinateur pour imprimer la valeur zéro (en utilisant java 1.6) :

int x = 0;
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
    x += x + x + x + x + x;
}

System.out.println(x);

Il est tout à fait évident que x ne change jamais, donc peu importe combien de fois vous ajoutez 0 à lui-même, il reste zéro. Le compilateur pourrait donc en théorie remplacer cette expression par System.out.println(0).

Ou encore mieux, cela prend 23 secondes :

public int slow() {
   String s = "x";
   for (int i = 0; i < 100000; ++i) {
       s += "x";
   }
   return 10;
}

Premièrement, le compilateur pourrait remarquer que je crée en fait une chaîne s de 100000 "x", il pourrait donc utiliser automatiquement s StringBuilder à la place, ou encore mieux le remplacer directement par la chaîne résultante puisqu'elle est toujours la même. Deuxièmement, il ne reconnaît pas que je n'utilise pas du tout la chaîne, donc la boucle entière pourrait être rejetée !

Pourquoi, alors que tant de ressources humaines sont consacrées aux compilateurs rapides, ceux-ci sont-ils encore relativement stupides ?

EDIT : Bien sûr, ce sont des exemples stupides qui ne devraient jamais être utilisés nulle part. Mais chaque fois que je dois réécrire un code beau et très lisible en quelque chose d'illisible pour que le compilateur soit content et produise un code rapide, je me demande pourquoi les compilateurs ou un autre outil automatisé ne peuvent pas faire ce travail pour moi.

Answer 1

À mon avis, je ne pense pas que ce soit le rôle du compilateur de corriger ce qui est, honnêtement, un mauvais codage. Vous avez, très explicitement, dit au compilateur que vous voulez que la première boucle soit exécutée. C'est la même chose que :

x = 0
sleep 6 // Let's assume this is defined somewhere.
print x

Je ne voudrais pas que le compilateur supprime mes sleep juste parce qu'il n'a rien fait. Vous pouvez argumenter que l'instruction sleep est une demande explicite de délai alors que votre exemple ne l'est pas. Mais alors vous permettrez au compilateur de prendre des décisions de très haut niveau sur ce que votre code devrait faire, et je pense que c'est une mauvaise chose.

Le code, et le compilateur qui le traite, sont des outils et vous devez être un forgeron si vous voulez les utiliser efficacement. Combien de tronçonneuses de 12 pouces refusent d'essayer d'abattre un arbre de 30 pouces ? Combien de perceuses passent automatiquement en mode marteau si elles détectent un mur en béton ?

Aucun, je le soupçonne, et ce parce que le coût de la conception du produit serait énorme, pour commencer. Mais, plus important encore, vous ne devriez pas utiliser de perceuse ou de tronçonneuse si vous ne savez pas ce que vous faites. Par exemple, si vous ne savez pas ce qu'est le rebond (un moyen très facile pour un débutant de se couper le bras), n'utilisez pas de tronçonneuse avant de le savoir.

Je suis tout à fait d'accord pour permettre aux compilateurs de suggérer des améliorations mais je préfère garder le contrôle moi-même. Ce ne devrait pas être au compilateur de décider unilatéralement qu'une boucle est inutile.

Par exemple, j'ai réalisé des boucles de chronométrage dans des systèmes embarqués où la vitesse d'horloge de l'unité centrale est connue avec précision mais où aucun dispositif de chronométrage fiable n'est disponible. Dans ce cas, vous pouvez calculer précisément le temps que prendra une boucle donnée et l'utiliser pour contrôler la fréquence des événements. Cela ne fonctionnerait pas si le compilateur (ou l'assembleur dans ce cas) décidait que ma boucle est inutile et l'optimisait pour qu'elle n'existe pas.

Ceci étant dit, permettez-moi de vous raconter la vieille histoire d'un compilateur VAX FORTRAN qui a été soumis à un test de performance et dont on a constaté qu'il était beaucoup de des ordres de grandeur plus rapides que son concurrent le plus proche.

Il s'avère que le compilateur a remarqué que le résultat des boucles de référence n'était utilisé nulle part ailleurs et a optimisé les boucles pour qu'elles tombent dans l'oubli.

Answer 2

Oh, je ne sais pas. Parfois les compilateurs sont assez intelligents. Considérez le programme C suivant :

#include <stdio.h>  /* printf() */

int factorial(int n) {
   return n == 0 ? 1 : n * factorial(n - 1);
}

int main() {
   int n = 10;

   printf("factorial(%d) = %d\n", n, factorial(n));

   return 0;
}

Sur ma version de CCG (4.3.2 sur Debian ), lorsqu'ils sont compilés sans optimisation, ou -O1 il génère du code pour factorial() comme on pourrait s'y attendre, en utilisant un appel récursif pour calculer la valeur. Mais le -O2 il fait quelque chose d'intéressant : Il se compile en une boucle fermée :

    factorial:
   .LFB13:
           testl   %edi, %edi
           movl    $1, %eax
           je  .L3
           .p2align 4,,10
           .p2align 3
   .L4:
           imull   %edi, %eax
           subl    $1, %edi
           jne .L4
   .L3:
           rep
           ret

Assez impressionnant. L'appel récursif (même pas récursif en queue) a été complètement éliminé, de sorte que la factorielle utilise maintenant O(1) d'espace de pile au lieu de O(N). Et bien que je n'aie qu'une connaissance très superficielle de l'assemblage x86 (en fait AMD64 dans ce cas, mais je ne pense pas que les extensions AMD64 soient utilisées ci-dessus), je doute que vous puissiez écrire une meilleure version à la main. Mais ce qui m'a vraiment époustouflé, c'est le code qu'il a généré sur -O3 . L'implémentation de la factorielle est restée la même. Mais main() changé :

    main:
   .LFB14:
           subq    $8, %rsp
   .LCFI0:
           movl    $3628800, %edx
           movl    $10, %esi
           movl    $.LC0, %edi
           xorl    %eax, %eax
           call    printf
           xorl    %eax, %eax
           addq    $8, %rsp
           ret

Voir le movl $3628800, %edx ligne ? gcc est pré-informatique factorial(10) au moment de la compilation. Il n'appelle même pas factorial() . Incroyable. Je tire mon chapeau à l'équipe de développement de GCC.

Bien sûr, tous les avertissements habituels s'appliquent, il s'agit juste d'un exemple de jouet, l'optimisation prématurée est la racine de tous les maux, etc, etc, mais il illustre que les compilateurs sont souvent plus intelligents que vous ne le pensez. Mais il illustre le fait que les compilateurs sont souvent plus intelligents que vous ne le pensez. Si vous pensez que vous pouvez faire un meilleur travail à la main, vous avez presque certainement tort.

(Adapté d'un publier sur mon blog .)

Answer 3

En parlant d'un point de vue C/C++ :

Votre premier exemple sera optimisé par la plupart des compilateurs. Si le compilateur java de Sun exécute vraiment cette boucle, c'est la faute du compilateur, mais croyez-moi, n'importe quel compilateur C, C++ ou Fortran datant d'après 1990 élimine complètement une telle boucle.

Votre deuxième exemple ne peut pas être optimisé dans la plupart des langages car l'allocation de mémoire est un effet secondaire de la concaténation des chaînes de caractères. Si un compilateur optimisait le code, le modèle d'allocation de mémoire changerait, ce qui pourrait entraîner des effets que le programmeur tente d'éviter. La fragmentation de la mémoire et les problèmes qui y sont liés sont des problèmes auxquels les programmeurs embarqués sont confrontés tous les jours.

Dans l'ensemble, je suis satisfait des optimisations que les compilateurs peuvent réaliser de nos jours.

Answer 4

Les compilateurs sont conçus pour être prévisible . Cela peut les faire paraître stupides de temps en temps, mais ce n'est pas grave. Les objectifs de l'auteur du compilateur sont

• Vous devriez être en mesure de regarder votre code et de faire des prédictions raisonnables sur ses performances.

• De petits changements dans le code ne devraient pas entraîner de différences spectaculaires dans les performances.

• Si le programmeur pense qu'une petite modification devrait améliorer les performances, elle devrait au moins ne pas les dégrader (à moins que des choses surprenantes ne se produisent dans le matériel).

Tous ces critères militent contre les optimisations "magiques" qui ne s'appliquent qu'aux cas particuliers.

---

Vos deux exemples ont un variable mise à jour dans une boucle mais non utilisée ailleurs . Ce cas est en fait assez difficile à détecter, à moins d'utiliser une sorte de framework qui peut combiner l'élimination du code mort avec d'autres optimisations comme la propagation des copies ou la propagation des constantes. Pour un simple l'optimiseur de flux de données, la variable ne semble pas morte. Pour comprendre pourquoi ce problème est difficile à résoudre, voir la page article de Lerner, Grove et Chambers dans POPL 2002 qui utilise précisément cet exemple et explique pourquoi c'est difficile.

Answer 5

Le compilateur JIT de HotSpot n'optimise que le code qui a été exécuté pendant un certain temps. Au moment où votre code est chaud, la boucle a déjà été lancée et le compilateur JIT doit attendre la prochaine entrée de la méthode pour chercher des moyens d'optimiser la boucle. Si vous appelez la méthode plusieurs fois, vous obtiendrez peut-être de meilleures performances.

Ce sujet est traité dans le FAQ sur le HotSpot sous la question "J'ai écrit une boucle simple pour chronométrer une opération simple et c'est lent. Qu'est-ce que je fais mal ?