Pourquoi Java interrupteur sur contiguë ints semblent courir plus vite avec ajout de cas?
Je suis en train de travailler sur certains de code Java qui doit être hautement optimisé comme il se déroulera à chaud des fonctions qui sont appelées à un grand nombre de points de mon programme principal de la logique. Une partie de ce code implique de multiplier double
variables par 10
soulevées à l'arbitraire, non négatives int
exponent
s. Un moyen rapide (edit: mais pas de la manière la plus rapide possible, voir mise à Jour 2 ci-dessous) pour obtenir la valeur multipliée est à switch
sur le 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);
}
}
Le commentaire ellipses ci-dessus indiquent que le case
int
constantes incrémenter de 1, donc il y a vraiment 19 case
s dans l'extrait de code ci-dessus. Comme je n'étais pas sûr de savoir si j'ai réellement besoin de toutes les puissances de 10 dans case
états 10
thru 18
, j'ai couru quelques microbenchmarks de comparer le temps d'exécution de 10 millions d'opérations avec cette switch
énoncé par rapport à un switch
avec seulement case
s 0
thru 9
(avec le exponent
limitée à 9 ou moins pour éviter de casser le épurée switch
). J'ai eu le plutôt surprenant (pour moi, au moins!) résultat le plus switch
avec plus case
déclarations en fait, couru plus vite.
Sur une alouette, j'ai essayé d'ajouter encore plus de case
s qui revient tout juste des valeurs factices, et constaté que je pouvais obtenir le commutateur à courir encore plus vite, avec près de 22 à 27 déclaré case
s (même si le mannequin cas ne sont jamais réellement touché tandis que le code est en cours d'exécution). (Encore une fois, case
s ont été ajoutés dans une zone contiguë de la mode en incrémentant l'avant case
constante par 1
.) Ces temps d'exécution différences ne sont pas très importantes: pour un aléatoire exponent
entre 0
et 10
, le mannequin collier de switch
instruction se termine 10 millions d'exécutions dans 1.49 secondes contre 1.54 secondes pour le unpadded version, pour un grand total de l'épargne de 5ns par l'exécution. Donc, pas le genre de chose qui rend obsédés par le rembourrage d'un switch
déclaration de la valeur de l'effort à partir d'un point de vue de l'optimisation. Mais je trouve qu'il est curieux et contre-intuitif qu'un switch
n'est pas devenu plus lent (ou peut-être, au mieux, le maintien constant de la O(1) temps) à réaliser que la plus case
s y sont ajoutés.
Ce sont les résultats que j'ai obtenus de l'exécution avec les différentes limites sur le générés aléatoirement exponent
valeurs. Je ne comprend pas les résultats de tous les chemin vers le bas pour 1
pour la exponent
limite, mais la forme générale de la courbe reste la même, avec un rebord autour de la 12-17 cas, et une vallée entre 18-28. Tous les tests ont été exécutés dans JUnitBenchmarks de l'utilisation partagée des conteneurs pour les valeurs aléatoires pour s'assurer identiques tests d'entrées. J'ai également fait des tests à la fois dans l'ordre de la plus longue switch
déclaration à la plus courte, et vice-versa, pour essayer d'éliminer la possibilité de commander liés à problèmes de test. J'ai mis mon code de test sur un dépôt github si quelqu'un veut essayer de reproduire ces résultats.
Donc, ce qui se passe ici? Certains caprices de mon architecture ou micro-benchmark de la construction? Ou est la Java switch
vraiment un peu plus rapide à s'exécuter dans le 18
à 28
case
que c'est à partir de 11
jusqu'à 17
?
github test repo "switch-expérience"
Mise à JOUR: j'ai nettoyé l'analyse comparative de la bibliothèque tout à fait un peu et ajouté un fichier texte dans /résultats avec une sortie dans un large éventail de possibles exponent
valeurs. J'ai aussi ajouté une option dans le code de test et de ne pas jeter un Exception
de default
, mais cela ne semble pas affecter les résultats.
Mise à JOUR 2: Trouvé une assez bonne discussion de cette question à partir de l'arrière, en 2009, sur le xkcd forum ici: http://forums.xkcd.com/viewtopic.php?f=11&t=33524. L'OP de l'analyse de l'utilisation Array.binarySearch()
m'a donné l'idée de faire un tableau simple basée sur la mise en œuvre de l'exponentiation schéma ci-dessus. Il n'est pas nécessaire pour le binaire de recherche depuis que je sais ce que les entrées dans la array
sont. Il semble environ 3 fois plus rapide que l'utilisation switch
, évidemment au détriment d'une partie du flux de contrôle qui switch
offre. Ce code a été ajouté le dépôt github aussi.
- La seule explication logique à laquelle je pense est un compilateur Java est en essayant d'optimiser l'instruction switch plus de cas, peut-être d'aller dans un O(1) logique que la plupart des compilateurs C fait dans les âges sombres.
- Maintenant, tous les Googlers de partout ont précisément 22 cas dans tous les
switch
états, comme c'est clairement la solution la plus optimale. 😀 (Ne pas montrer ça à mon chef, s'il vous plaît.) - Avez-vous un simple SSCCE? Celui-ci ne compile pas pour moi. Faible comme je suis avec la performance Java, je veux prendre une photo à ce.
- Référence sans dépendances serait utile.
- Vous trouverez peut-être la section "permet de faire passer dans la JVM" dans ma réponse à propos de chaîne à base de cas, utile. Je pense que ce qui se passe ici, c'est que vous êtes de commutation à partir d'un
lookupswitch
à untableswitch
. Démontage de votre code avecjavap
serait de vous montrer pour vous. - oui @erickson je me suis souvenu de votre réponse a tout à l'arrière - fait assez pour la recherche. Merci
- Je pensais que trop, mais il est toujours
tableswitch
. - J'ai ajouté la dépendance des pots à l' /lib dans le dossier des pensions. @Mysticial Désolé, j'ai déjà passé trop de temps à descendre ce trou de lapin! Si vous prenez le "s'étend AbstractBenchmark" hors les classes de test et de se débarrasser de la "com".carrotsearch" les importations, vous pouvez jouer seulement avec JUnit de la dépendance, mais le carrotsearch des choses est assez agréable pour filtrer une partie du bruit de l'équipe et des périodes de chauffe. Malheureusement, je ne sais pas comment faire pour exécuter ces tests JUnit en dehors de l'Ide, si.
- J'ai réussi à reproduire les résultats avec beaucoup plus simple indice de référence. La direction générale contre la table pour le petit vs taille moyenne de la performance était un peu évident à deviner. Mais je n'ai pas de meilleure idée que n'importe qui d'autre sur le dip va dans 30 cas...
- Merci pour la reproduire! Certains détails de la réelle pratique d'utilisation pour le commutateur a une fuite dans la tester un peu, je vais probablement tenter de faire passer ces si cette question continue de camionnage. 😉
- En fait tous les tests de la compilation de
tableswitch
au niveau du compilateur; mais pour certaines raisons, l'équipe semble compilertableswitch
à unlookupswitch
lorsque le nombre de cas est faible. - Liés à la réponse à une autre question stackoverflow.com/questions/10287700/...
- Noter que (i) votre nouveau bloc statique peut être écrite:
ARRAY_32[i] = Math.pow(1, i);
au lieu de la succession de if/else et (ii)1000000000000000000L * 10;
et les suivants sont des nombres négatifs en raison des Longs débordement - vous devez utiliser undouble[]
à la place. - Je savais que quelqu'un allait m'appeler sur le trop-plein. 🙂 Je ne voulais pas avoir l'esprit qu'il y une fois l'objectif changé à "jeter beaucoup de choses au niveau de l'interrupteur et de voir comment il se comporte." Une fois que j'ai la déplacer dans la production (probablement avec un tableau de mise en œuvre) je vais probablement juste de mettre une limite supérieure de 14 ou 15 ans sur le
exponent
et jeter unException
si les clients d'essayer de le dépasser. Votre idée d'utiliserdouble
pour laexponent
valeurs est intéressant, car il peut économiser les frais d'une conversion de l'opération. Je vais vous laisser savoir ce que je trouve dans l'essai. - Alors pourquoi ne pas se débarrasser de l'affaire, tous ensemble, et il suffit de faire quelque chose comme:
final long[] pow = {1, 10, 100, 1000, 10000, etc.};
etreturn d * pow[exponent];
- C'est la solution décrite dans la mise à JOUR 2 (mais on pourrait l'exception de la JVM pour déjà faire quelque chose de similaire avec un interrupteur).
- vous avez besoin d'un couple d'options JVM d'être aussi bonne, à savoir:- XX:+PrintAssembly et +XX:+PrintFlagsFinal - puis le traiter comme C. Mais le cas habituel est le manque de inline qui est trivial de voir dans l'assemblée.
- Comme votre question est plus précisément sur le commutateur cas, ce n'est pas une réponse, mais sur le sujet de la performance de la pow() opération avez-vous envisagé un rapprochement? Je trouve sympa cette article: martin.ankerl.com/2007/10/04/...
- Une brève mise à jour par commentaire, ce problème a été déposée dans l'Oracle de bugs de la base de données: bugs.sun.com/bugdatabase/view_bug.do?bug_id=8010941
- Oracle ingénieurs ont réduit la taille minimale de HotSpot généré sauter tables de 10 sur x86 et 5 sur SPARC: hg.openjdk.java.net/jdk8/jdk8/hotspot/rev/34bd5e86aadb
Vous devez vous connecter pour publier un commentaire.
Cas Switch est plus rapide si les valeurs sont placées dans une fourchette étroite, par exemple.
Parce que, dans ce cas, le compilateur peut éviter d'effectuer une comparaison de tous les cas de la jambe dans l'instruction switch. Le compilateur de faire un saut de la table qui contient les adresses des mesures à prendre sur les différents pieds. La valeur sur laquelle l'interrupteur est en cours d'exécution est manipulé pour le convertir dans un index à la
saut de la table
. Dans cette mise en œuvre , le temps pris dans l'instruction switch est beaucoup moins que le temps pris dans un équivalent si-sinon-si la déclaration cascade. Aussi le temps pris dans l'instruction switch est indépendant du nombre de cas de jambes en l'instruction switch.Comme indiqué dans wikipédia à propos de instruction switch dans la Compilation de la section.
1
:-/La réponse se trouve dans le bytecode:
SwitchTest10.java
Correspondant bytecode; seules les parties pertinentes montré:
SwitchTest22.java:
Correspondant bytecode; encore une fois, seules les parties pertinentes montré:
Dans le premier cas, avec d'étroites plages, le code compilé utilise un
tableswitch
. Dans le second cas, le code compilé utilise unlookupswitch
.Dans
tableswitch
, la valeur entière sur le dessus de la pile est utilisée pour les index dans la table, afin de trouver la succursale la/saut de cible. Ce saut/branche est ensuite effectuée immédiatement. Donc, c'est unO(1)
opération.Un
lookupswitch
est plus compliqué. Dans ce cas, la valeur de l'entier doit être comparé à l'encontre de toutes les clés de la table jusqu'à ce que la clé se trouve. Après la clé est trouvée, la branche/de saut à la cible (que cette clé est mappé) est utilisé pour le saut. La table qui est utilisée danslookupswitch
est triée et binaire de l'algorithme de recherche peut être utilisé pour trouver la bonne clé. Performance pour une recherche binaire estO(log n)
, et l'ensemble du processus est égalementO(log n)
, parce que le saut est encoreO(1)
. Donc, la raison de la performance est plus faible dans le cas des rares plages est que la clé correcte doit d'abord être regardé, parce que vous ne pouvez pas l'index dans la table directement.Si il existe peu de valeurs et vous n'aviez qu'un
tableswitch
à utiliser, table contiennent essentiellement factice entrées qui pointent à l'default
option. Par exemple, en supposant que la dernière entrée dansSwitchTest10.java
était21
au lieu de10
, vous obtenez:De sorte que le compilateur fondamentalement crée cette immense table contenant mannequin d'entrées entre les lacunes, pointant vers la direction de la cible de la
default
instruction. Même si il n'y a pas undefault
, il contient des entrées pour le pointage de l'instruction après le bloc de commutateurs. J'ai fait quelques tests de base, et j'ai trouvé que si l'écart entre la dernière et l'indice précédent (9
) est plus grande que35
, il utilise unlookupswitch
au lieu d'untableswitch
.Le comportement de la
switch
déclaration est définie dans La Machine Virtuelle Java Specification (§3.10):lookupswitch
?Depuis que la question est déjà une réponse (plus ou moins), voici quelques conseil.
Utilisation
Que le code utilise beaucoup moins d'IC (cache d'instructions) et sera toujours inline. Le tableau sera en L1 cache de données si le code est chaud. La table de recherche est presque toujours une victoire. (esp. sur microbenchmarks 😀 )
Edit: si vous souhaitez la méthode à chaud-inline, considèrent que le non-vite les chemins comme
throw new ParseException()
être aussi courte que le minimum ou les déplacer pour séparer méthode statique (donc les rendant court comme minimum). C'estthrow new ParseException("Unhandled power of ten " + power, 0);
est une faible idée b/c il mange beaucoup de l'inlining budget de code qui peut être simplement interprétée - concaténation de chaîne est très longue dans le bytecode . Plus d'infos et un cas réel w/liste de tableaux