Optimisation: l’ordre des cas dans une instruction switch est-il important?

Envisagez une instruction switch dans la langue de votre choix (par exemple, Java, C, C #, etc.). Bien sûr, l’ordre des déclarations de case est important s’il y a des erreurs, mais supposons que chaque case a une break , l’ordre n’a donc aucune importance sémantique.

L’ordre des instructions de case est-il important lorsque, par exemple, vous envisagez des optimisations? Vaut-il mieux sortinger les cas dans l’ordre croissant ou n’y a-t-il aucun avantage à en ordonner? Quelles optimisations un compilateur peut-il effectuer selon l’ordre des case ? Comme tout compilateur peut choisir ou non de telles optimisations, je ne souhaite pas demander ici un langage ou un compilateur spécifique. La question concerne ce qui pourrait éventuellement arriver.

La réponse dépend non seulement de la langue, mais également du compilateur, et même des parameters de compilateur choisis. Je l’ai vu différer en C ++ en fonction des parameters d’optimisation gcc que j’ai choisis.

En effet, le compilateur peut choisir d’implémenter l’instruction switch en tant que série de tests, tout comme une série d’instructions if / else if, ou il peut choisir d’implémenter l’instruction switch en tant que table de saut. La série de tests sera plus rapide pour les tests précédents, tandis que la table de saut sera généralement aussi rapide quelle que soit la commande.

Si votre compilateur implémente votre instruction switch sous la forme d’une série de tests – et ne les réorganise pas – placer les cas les plus probables plus tôt entraînera un code plus rapide. Autant que je sache, mettre tôt les cas les plus probables ne devrait normalement pas ralentir le code. Par conséquent, si votre code passe beaucoup de temps à exécuter cette instruction switch, rien ne vous empêche de mettre plus tôt les cas plus courants.

Cependant, si vous n’avez pas profilé votre code et que vous ne savez pas que l’instruction switch est un problème de performances, il est préférable de l’écrire en utilisant l’ordre le plus clair pour un être humain qui lit le code.

À en juger par ce critère, cela compte: http://pastebin.com/rJMEunAT

La première méthode a fini à 0,2423 ticks, la seconde à 0,1654

Pour les langages qui interdisent la mise en correspondance de clauses de casse multiples et qui ont des compilateurs avec au moins une optimisation, le fait d’écrire les clauses de casse ne changera certainement pas.

Il existe trois méthodes populaires de compilation des instructions de commutateur:

  • recherche binary codée en dur

  • table de saut indexée

  • table de saut hachée

Tous les trois exigent que le compilateur réorganise les clauses. Le choix dépendra de la langue, du processeur cible, de la dissortingbution des valeurs dans les clauses de cas et éventuellement de la phase de la lune.