Je travaille sur du code Java qui doit être hautement optimisé car il fonctionnera dans des fonctions chaudes qui sont invoquées à de nombreux points dans ma logique de programme principale. Une partie de ce code implique la multiplication des doublevariables par des 10valeurs élevées à des valeurs arbitraires non négatives int exponent. Une façon rapide (edit: mais pas le plus rapide possible, voir Mise à jour 2 ci - dessous) pour obtenir la valeur multipliée est switchle exponent:
double multiplyByPowerOfTen(final double d, final int exponent) {
switch (exponent) {
case 0:
return d;
case 1:
return d*10;
case 2:
return d*100;
// ... same pattern
case 9:
return d*1000000000;
case 10:
return d*10000000000L;
// ... same pattern with long literals
case 18:
return d*1000000000000000000L;
default:
throw new ParseException("Unhandled power of ten " + power, 0);
}
}Les ellipses commentées ci-dessus indiquent que les case intconstantes continuent à augmenter de 1, il y a donc vraiment 19 cases dans l'extrait de code ci-dessus. Puisque je ne suis pas sûr que je réellement besoin de tous les pouvoirs de 10 casedéclarations à 10travers 18, j'ai couru quelques microbenchmarks comparant le temps aux opérations complètes de 10 millions cette switchdéclaration par rapport à un switchavec seulement cases à 0travers 9(avec le exponentlimité à 9 ou moins éviter de casser le pared-down switch). J'ai obtenu le résultat plutôt surprenant (du moins pour moi!) Que le plus long switchavec plus d' caseinstructions s'exécutait plus vite.
Sur une alouette, j'ai essayé d'ajouter encore plus de cases qui viennent de renvoyer des valeurs fictives, et j'ai constaté que je pouvais faire fonctionner le commutateur encore plus rapidement avec environ 22-27 cases déclarés (même si ces cas fictifs ne sont jamais réellement frappés pendant que le code est en cours d'exécution) ). (Encore une fois, les cases ont été ajoutés de manière contiguë en incrémentant la caseconstante précédente de 1.) Ces différences de temps d'exécution ne sont pas très importantes: pour une aléatoire exponententre 0et10 , l' switchinstruction factice remplie termine 10 millions d'exécutions en 1,49 seconde contre 1,54 seconde pour la non remplie version, pour une économie totale de 5 ns par exécution. Donc, pas le genre de chose qui rend obsédant le rembourrage d'unswitchdéclaration vaut l'effort d'un point de vue d'optimisation. Mais je trouve toujours curieux et contre-intuitif qu'un a switchne devienne pas plus lent (ou peut-être au mieux maintienne un temps O (1) constant ) à exécuter car plus de cases y sont ajoutés.
Ce sont les résultats que j'ai obtenus en exécutant avec différentes limites sur les exponentvaleurs générées aléatoirement . Je n'ai pas inclus les résultats jusqu'à 1la exponentlimite, mais la forme générale de la courbe reste la même, avec une crête autour de la marque de cas 12-17 et une vallée entre 18-28. Tous les tests ont été exécutés dans JUnitBenchmarks à l'aide de conteneurs partagés pour les valeurs aléatoires afin de garantir des entrées de test identiques. J'ai également exécuté les tests à la fois du plus long switchau plus court et vice-versa, pour essayer d'éliminer la possibilité de problèmes de test liés à la commande. J'ai mis mon code de test sur un dépôt github si quelqu'un veut essayer de reproduire ces résultats.
Alors, que se passe-t-il ici? Des aléas de mon architecture ou de ma construction de micro-benchmark? Ou est-ce que Java est switchvraiment un peu plus rapide à exécuter dans la plage de 18destination 28 caseque 11jusqu'à 17?
github test repo "switch-experiment"
MISE À JOUR: J'ai nettoyé un peu la bibliothèque de benchmarking et ajouté un fichier texte dans / results avec une sortie sur une plus large gamme de exponentvaleurs possibles . J'ai également ajouté une option dans le code de test pour ne pas lancer Exceptionde default, mais cela ne semble pas affecter les résultats.
MISE À JOUR 2: Trouvé une discussion assez bonne sur ce problème depuis 2009 sur le forum xkcd ici: http://forums.xkcd.com/viewtopic.php?f=11&t=33524 . La discussion de l'OP sur l'utilisation Array.binarySearch()m'a donné l'idée d'une implémentation simple basée sur un tableau du modèle d'exponentiation ci-dessus. Il n'y a pas besoin de la recherche binaire car je sais quelles sont les entrées dans le array. Il semble fonctionner environ 3 fois plus vite que son utilisation switch, évidemment au détriment d'une partie du flux de contrôle switchfourni. Ce code a également été ajouté au dépôt github.
la source
switchdéclarations, car c'est clairement la solution la plus optimale. : D (Ne montrez pas cela à mon avance, s'il vous plaît.)lookupswitchà atableswitch. Le démontage de votre code avecjavapvous montrerait à coup sûr.Réponses:
Comme l'a souligné l'autre réponse , parce que les valeurs de casse sont contiguës (par opposition à rares), le bytecode généré pour vos différents tests utilise une table de commutation (instruction bytecode
tableswitch).Cependant, une fois que le JIT commence son travail et compile le bytecode dans l'assembly, l'
tableswitchinstruction n'aboutit pas toujours à un tableau de pointeurs: parfois la table de commutation est transformée en ce qui ressemble à unelookupswitch(similaire à une structureif/else if).La décompilation de l'assembly généré par le JIT (hotspot JDK 1.7) montre qu'il utilise une succession de if / else si quand il y a 17 cas ou moins, un tableau de pointeurs quand il y en a plus de 18 (plus efficace).
La raison pour laquelle ce nombre magique de 18 est utilisé semble se résumer à la valeur par défaut de l'
MinJumpTableSizeindicateur JVM (autour de la ligne 352 dans le code).J'ai soulevé le problème sur la liste des compilateurs de hotspot et il semble que ce soit un héritage de tests passés . Notez que cette valeur par défaut a été supprimée dans JDK 8 après que d' autres analyses comparatives ont été effectuées .
Enfin, lorsque la méthode devient trop longue (> 25 cas dans mes tests), elle n'est plus alignée avec les paramètres JVM par défaut - c'est la cause la plus probable de la baisse des performances à ce stade.
Avec 5 cas, le code décompilé ressemble à ceci (notez les instructions cmp / je / jg / jmp, l'assembly pour if / goto):
Avec 18 cas, l'assemblage ressemble à ceci (notez le tableau de pointeurs qui est utilisé et supprime le besoin de toutes les comparaisons:
jmp QWORD PTR [r8+r10*1]saute directement à la bonne multiplication) - c'est la raison probable de l'amélioration des performances:Et enfin, l'assemblage avec 30 cas (ci-dessous) ressemble à 18 cas, à l'exception de celui
movapd xmm0,xmm1qui apparaît vers le milieu du code, tel que repéré par @cHao - mais la raison la plus probable de la baisse des performances est que la méthode est trop longtemps pour être aligné avec les paramètres JVM par défaut:la source
Switch - case est plus rapide si les valeurs de case sont placées dans une plage étroite.
Parce que, dans ce cas, le compilateur peut éviter d'effectuer une comparaison pour chaque jambe de cas dans l'instruction switch. Le compilateur crée une table de sauts qui contient les adresses des actions à entreprendre sur différentes jambes. La valeur sur laquelle le changement est effectué est manipulée pour le convertir en index dans le
jump table. Dans cette implémentation, le temps pris dans l'instruction switch est bien inférieur au temps pris dans une cascade d'instructions if-else-if équivalente. Le temps pris dans l'instruction switch est également indépendant du nombre de segments de casse dans l'instruction switch.Comme indiqué dans wikipedia sur l' instruction switch dans la section Compilation.
la source
La réponse réside dans le bytecode:
SwitchTest10.java
Bytecode correspondant; seules les pièces pertinentes sont affichées:
SwitchTest22.java:
Bytecode correspondant; encore une fois, seules les parties pertinentes sont affichées:
Dans le premier cas, avec des plages étroites, le bytecode compilé utilise a
tableswitch. Dans le second cas, le bytecode compilé utilise alookupswitch.Dans
tableswitch, la valeur entière en haut de la pile est utilisée pour indexer dans la table, pour trouver la branche / saut cible. Ce saut / branche est alors effectué immédiatement. Il s'agit donc d'uneO(1)opération.A
lookupswitchest plus compliqué. Dans ce cas, la valeur entière doit être comparée à toutes les clés du tableau jusqu'à ce que la clé correcte soit trouvée. Une fois la clé trouvée, la cible de branche / saut (à laquelle cette clé est mappée) est utilisée pour le saut. La table utilisée danslookupswitchest triée et un algorithme de recherche binaire peut être utilisé pour trouver la clé correcte. Les performances pour une recherche binaire sontO(log n), et tout le processus l'est égalementO(log n), car le saut est toujoursO(1). Ainsi, la raison pour laquelle les performances sont inférieures dans le cas de plages clairsemées est que la clé correcte doit d'abord être recherchée car vous ne pouvez pas indexer directement dans la table.S'il y a des valeurs éparses et que vous n'aviez qu'une
tableswitchà utiliser, la table contiendrait essentiellement des entrées factices qui pointent vers l'defaultoption. Par exemple, en supposant que la dernière entrée dansSwitchTest10.javaétait à la21place de10, vous obtenez:Ainsi, le compilateur crée essentiellement cette immense table contenant des entrées factices entre les espaces, pointant vers la branche cible de l'
defaultinstruction. Même s'il n'y en a pasdefault, il contiendra des entrées pointant vers l'instruction après le bloc de commutation. J'ai fait quelques tests de base, et j'ai trouvé que si l'écart entre le dernier index et le précédent (9) est plus grand que35, il utilise alookupswitchau lieu de atableswitch.Le comportement de l'
switchinstruction est défini dans Java Virtual Machine Specification (§3.10) :la source
lookupswitch?Puisque la question a déjà répondu (plus ou moins), voici quelques conseils. Utilisation
Ce code utilise beaucoup moins IC (cache d'instructions) et sera toujours intégré. Le tableau sera dans le cache de données L1 si le code est chaud. La table de recherche est presque toujours une victoire. (en particulier sur les repères microbiens: D)
Modifier: si vous souhaitez que la méthode soit hot-inline, considérez que les chemins non rapides aiment
throw new ParseException()être aussi courts que minimum ou déplacez-les vers une méthode statique distincte (ce qui les rend courts comme minimum). C'estthrow new ParseException("Unhandled power of ten " + power, 0);une idée faible car elle mange une grande partie du budget en ligne pour le code qui peut être simplement interprété - la concaténation de chaînes est assez verbeuse en bytecode. Plus d'infos et un vrai cas avec ArrayListla source