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 exponents. 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 cases 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 cases 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 cases 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é cases (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, cases 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 cases y sont ajoutés.

Pourquoi Java interrupteur sur contiguë ints semblent courir plus vite avec ajout de cas?

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 à un tableswitch. Démontage de votre code avec javap 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 compiler tableswitch à un lookupswitch 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 un double[] à 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 un Exception si les clients d'essayer de le dépasser. Votre idée d'utiliser double pour la exponent 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.}; et return 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