optimisations des expressions booléennes dans Java

Question

Considérez la méthode suivante en Java:

public static boolean expensiveComputation() { 
    for (int i = 0; i < Integer.MAX_VALUE; ++i); 
    return false; 
} 

Et la principale méthode suivante:

public static void main(String[] args) { 
    boolean b = false; 
    if (expensiveComputation() && b) { 
    } 
} 

conjonction logique (comme & &) est un commutative operation. Alors, pourquoi le compilateur ne pas optimiser le code instruction if à l'équivalent:

if (b && expensiveComputation()) { 
} 

qui a le benefits of using short-circuit evaluation?

De plus, le compilateur essaie-t-il d'effectuer d'autres simplifications logiques ou permutation de booléens afin de générer du code plus rapide? Si non, pourquoi? Certes, certaines optimisations seraient très difficiles, mais mon exemple n'est pas simple? Appeler une méthode devrait toujours être plus lent que de lire un booléen, non?

Merci d'avance.

Answer 1

Cela ne fonctionne pas car la fonctionCalcul() peut avoir des effets secondaires qui modifient l'état du programme. Cela signifie que l'ordre dans lequel les expressions dans les instructions booléennes sont évaluées (costComputation() et b) est important. Vous ne voudriez pas que le compilateur optimise un bug dans votre programme compilé, n'est-ce pas?

Par exemple, si le code était comme celui-ci

public static boolean expensiveComputation() { 
     for (int i = 0; i < Integer.MAX_VALUE; ++i); 
     b = false; 
     return false; 
} 

public static boolean b = true; 
public static void main(String[] args) { 
     if (expensiveComputation() || b) { 
     // do stuff 
     } 
} 

Ici, si le compilateur effectué votre optimisation, le //do stuff courraient quand vous attendez pas à en regardant le code (parce que le b, qui est originellement vrai, est évalué en premier).

Answer 2

Parce que expensiveComputation() peut avoir des effets secondaires.

Puisque Java ne vise pas à être un langage fonctionnellement pur, il n'empêche pas les programmeurs d'écrire des méthodes qui ont des effets secondaires. Ainsi, il n'y a probablement pas beaucoup de valeur dans l'analyse du compilateur pour la pureté fonctionnelle. Et puis, optimisations comme vous posit sont peu susceptibles d'être très précieux dans la pratique, comme expensiveComputation() serait généralement nécessaire d'exécuter de toute façon, pour obtenir les effets secondaires.

Bien sûr, pour un programmeur, il est facile de mettre le b en premier si on s'attend à ce qu'il soit faux et explicitement vouloir éviter le calcul coûteux.

Answer 3

Le compilateur optimisera ceci si vous exécutez le code assez souvent, probablement en insérant la méthode et en simplifiant l'expression booléenne résultante (mais probablement pas en réorganisant les arguments de & &).

Vous pouvez effectuer un test de performances en chronométrant une boucle d'un million d'itérations de ce code à plusieurs reprises. La première itération ou deux sont beaucoup plus lentes que les suivantes.

Answer 4

En fait, certains compilateurs peuvent optimiser les programmes comme celui que vous avez suggéré, il faut juste s'assurer que la fonction n'a pas d'effets secondaires. GCC a une directive de compilation que vous pouvez annoter avec une fonction pour montrer qu'elle n'a pas d'effets secondaires, que le compilateur peut ensuite utiliser lors de l'optimisation. Java peut avoir quelque chose de similaire.

Un exemple classique est

pour (ii = 0; strlen (s)> ii; ii ++) < faire quelque chose>

qui obtient optimisé pour

n = strlen (s); pour (ii = 0; n> ii; ii ++) < faire quelque chose>

par GCC avec le niveau d'optimisation 2, au moins sur ma machine.

Answer 5

La version de Java que j'utilise optimise un dans une expression a && b mais pas avec b. Par exemple, si a est faux, b n'est pas évalué, mais si b était faux, cela n'a pas été le cas. Je l'ai trouvé lorsque je mettais en œuvre la validation dans un formulaire de site Web: J'ai créé des messages à afficher sur la page Web dans une série de méthodes booléennes. Je m'attendais à ce que les champs de la page qui étaient mal entrés soient mis en surbrillance mais, à cause du piratage rapide de Java, le code a été exécuté seulement jusqu'à ce que le premier champ incorrect ait été découvert. Après cela, Java doit avoir pensé quelque chose comme "false & & tout est toujours faux" et a sauté les méthodes de validation restantes.

Je suppose que, en réponse à votre question, si vous faites des optimisations comme celle-ci, votre programme peut tourner plus lentement que possible. Cependant, le programme de quelqu'un d'autre va complètement se casser parce qu'ils ont supposé le comportement non-optimisé comme la chose d'effet secondaire mentionnée dans d'autres réponses.

Malheureusement, il est difficile d'automatiser des décisions intelligentes, en particulier avec des langages impératifs (C, C++, Java, Python, ... c'est-à-dire les langages normaux).