286 votes

Andrew Bissell avatar

Pourquoi le commutateur Java sur les ints contigus semble-t-il s'exécuter plus rapidement avec des cas supplémentaires ?

Demandé el 25 de Mars, 2013
Quand la question a-t-elle été
7786 affichage
Nombre de visites la question a
5 Réponses
Nombre de réponses aux questions
Résolu
Situation réelle de la question

Je travaille sur un code Java qui doit être hautement optimisé car il sera exécuté dans des fonctions chaudes qui sont invoquées à de nombreux endroits dans la logique principale de mon programme. Une partie de ce code consiste à multiplier double variables par 10 élevé à des valeurs arbitraires non négatives int exponent s. Une façon rapide (edit : mais pas la plus rapide possible, voir Update 2 ci-dessous) d'obtenir la valeur multipliée est de 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);
   }
}

Les ellipses commentées ci-dessus indiquent que les case int Les constantes continuent à s'incrémenter de 1, donc il y a réellement 19 case dans l'extrait de code ci-dessus. Comme je n'étais pas sûr d'avoir besoin de toutes les puissances de 10 dans le code case déclarations 10 à travers 18 j'ai effectué quelques microbenchmarks en comparant le temps nécessaire pour effectuer 10 millions d'opérations avec ce système. switch par rapport à une switch avec seulement case s 0 à travers 9 (avec le exponent limités à 9 ou moins pour éviter de rompre l'esprit d'épuration. switch ). J'ai obtenu un résultat plutôt surprenant (pour moi, du moins !), à savoir que plus la durée de vie de l'appareil est longue, plus il y a de chances que l'appareil soit efficace. switch avec plus case les déclarations ont couru plus vite.

Sur un coup de tête, j'ai essayé d'en ajouter encore plus case qui ne renvoyaient que des valeurs fictives, et j'ai constaté que je pouvais faire fonctionner le commutateur encore plus rapidement avec environ 22-27 valeurs déclarées. case (même si ces cas fictifs ne sont jamais rencontrés pendant l'exécution du code). (Encore une fois, case ont été ajoutés de manière contiguë en incrémentant les valeurs précédentes de l'indicateur case constant par 1 .) Ces différences de temps d'exécution ne sont pas très significatives : pour un échantillon aléatoire de exponent entre 0 y 10 le tampon fictif switch termine 10 millions d'exécutions en 1,49 seconde contre 1,54 seconde pour la version non rembourrée, soit une économie totale de 5ns par exécution. Donc, ce n'est pas le genre de chose qui fait que l'obsession du remplissage d'une instruction switch La déclaration vaut la peine d'être faite du point de vue de l'optimisation. Mais je trouve tout de même curieux et contre-intuitif qu'une instruction switch ne devient pas plus lent (ou, au mieux, maintient une constante O(1) temps) pour exécuter autant de case y sont ajoutés.

switch benchmarking results

Voici les résultats que j'ai obtenus en appliquant diverses limites à l'échantillon généré aléatoirement. exponent valeurs. Je n'ai pas inclus les résultats jusqu'à 1 pour le exponent mais la forme générale de la courbe reste la même, avec une crête autour des 12-17 cas, et une vallée entre 18-28. Tous les tests ont été exécutés dans JUnitBenchmarks en utilisant des conteneurs partagés pour les valeurs aléatoires afin de garantir des entrées de test identiques. J'ai également exécuté les tests dans l'ordre suivant : du plus long au plus court. switch à la plus courte, et vice-versa, pour essayer d'éliminer la possibilité de problèmes de test liés à l'ordre. J'ai mis mon code de test sur un repo github si quelqu'un veut essayer de reproduire ces résultats.

Alors, qu'est-ce qui se passe ici ? Des caprices de mon architecture ou de la construction du micro-benchmark ? Ou est-ce que le Java switch vraiment un peu plus rapide à exécuter dans le 18 à 28 case qu'il ne l'est de 11 jusqu'à 17 ?

Dépôt de test github "switch-experiment".

UPDATE : J'ai nettoyé la bibliothèque d'analyse comparative et j'ai ajouté un fichier texte dans /results avec des résultats pour un plus large éventail de possibilités. exponent valeurs. J'ai également ajouté une option dans le code de test pour ne pas lancer un Exception de default mais cela ne semble pas affecter les résultats.

UPDATE 2 : J'ai trouvé une assez bonne discussion sur ce sujet en 2009 sur le forum xkcd ici : http://forums.xkcd.com/viewtopic.php?f=11&t=33524 . La discussion du PO sur l'utilisation de 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'est pas nécessaire d'effectuer une recherche binaire puisque je sais ce que les entrées du tableau array sont. Il semble fonctionner environ 3 fois plus vite qu'avec l'utilisation de switch évidemment au détriment d'une partie du flux de contrôle qui switch offre. Ce code a été ajouté au repo github également.

Demandé el 25 de Mars, 2013 par Andrew Bissell

1 votes

Avatar de Aniket

La seule explication logique à laquelle je peux penser est que le compilateur Java essaie d'optimiser l'instruction switch avec plus de cas, peut-être en entrant dans une logique O(1) comme la plupart des compilateurs C l'ont fait dans les âges sombres.

Commenté el 25 de Mars, 2013 par Aniket

67 votes

Avatar de asteri

Maintenant, tous les Googlers du monde entier auront précisément 22 cas en tout. switch car c'est clairement la solution la plus optimale :D (Ne montrez pas ça à mon chef, s'il vous plaît.)

Commenté el 25 de Mars, 2013 par asteri

3 votes

Avatar de Mysticial

Avez-vous un SSCCE plus simple ? Celui-ci ne compile pas pour moi. Aussi faible que je sois avec les performances de Java, je veux essayer de le faire.

Commenté el 25 de Mars, 2013 par Mysticial
Afficher 17 autres commentaires

Réponses

Trop de publicités?

240voto

assylias avatar
assylias Points 102015

Comme indiqué par l'autre réponse parce que les valeurs de cas sont contiguës (par opposition à éparses), 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 en assembleur, le tableswitch n'aboutit pas toujours à un tableau de pointeurs : parfois, le tableau de commutation est transformé en ce qui ressemble à un fichier lookupswitch (semblable à un if / else if structure).

La décompilation de l'assemblage généré par le JIT (hotspot JDK 1.7) montre qu'il utilise une succession de if/else if 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 résulter de la valeur par défaut de l'indicateur de performance de l'utilisateur. MinJumpTableSize drapeau JVM (autour de la ligne 352 du code).

J'ai soulevé le problème sur la liste des compilateurs hotspot et il semble que ce soit un héritage des tests passés . Notez que cette valeur par défaut a été supprimé dans le JDK 8 après davantage d'analyses comparatives ont été effectuées .

Enfin, lorsque la méthode devient trop longue (> 25 cas dans mes tests), elle n'est plus inlined avec les paramètres par défaut de la JVM - c'est la cause la plus probable de la baisse de performance à ce moment-là.

Avec 5 cas, le code décompilé ressemble à ceci (remarquez les instructions cmp/je/jg/jmp, l'assemblage pour if/goto) :

[Verified Entry Point]
  # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1'
  # parm0:    xmm0:xmm0   = double
  # parm1:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x00000000024f0160: mov    DWORD PTR [rsp-0x6000],eax
                                                ;   {no_reloc}
  0x00000000024f0167: push   rbp
  0x00000000024f0168: sub    rsp,0x10           ;*synchronization entry
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@-1 (line 56)
  0x00000000024f016c: cmp    edx,0x3
  0x00000000024f016f: je     0x00000000024f01c3
  0x00000000024f0171: cmp    edx,0x3
  0x00000000024f0174: jg     0x00000000024f01a5
  0x00000000024f0176: cmp    edx,0x1
  0x00000000024f0179: je     0x00000000024f019b
  0x00000000024f017b: cmp    edx,0x1
  0x00000000024f017e: jg     0x00000000024f0191
  0x00000000024f0180: test   edx,edx
  0x00000000024f0182: je     0x00000000024f01cb
  0x00000000024f0184: mov    ebp,edx
  0x00000000024f0186: mov    edx,0x17
  0x00000000024f018b: call   0x00000000024c90a0  ; OopMap{off=48}
                                                ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@72 (line 83)
                                                ;   {runtime_call}
  0x00000000024f0190: int3                      ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@72 (line 83)
  0x00000000024f0191: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffffa7]        # 0x00000000024f0140
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@52 (line 62)
                                                ;   {section_word}
  0x00000000024f0199: jmp    0x00000000024f01cb
  0x00000000024f019b: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff8d]        # 0x00000000024f0130
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@46 (line 60)
                                                ;   {section_word}
  0x00000000024f01a3: jmp    0x00000000024f01cb
  0x00000000024f01a5: cmp    edx,0x5
  0x00000000024f01a8: je     0x00000000024f01b9
  0x00000000024f01aa: cmp    edx,0x5
  0x00000000024f01ad: jg     0x00000000024f0184  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x00000000024f01af: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff81]        # 0x00000000024f0138
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@64 (line 66)
                                                ;   {section_word}
  0x00000000024f01b7: jmp    0x00000000024f01cb
  0x00000000024f01b9: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff67]        # 0x00000000024f0128
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@70 (line 68)
                                                ;   {section_word}
  0x00000000024f01c1: jmp    0x00000000024f01cb
  0x00000000024f01c3: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff55]        # 0x00000000024f0120
                                                ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
                                                ;   {section_word}
  0x00000000024f01cb: add    rsp,0x10
  0x00000000024f01cf: pop    rbp
  0x00000000024f01d0: test   DWORD PTR [rip+0xfffffffffdf3fe2a],eax        # 0x0000000000430000
                                                ;   {poll_return}
  0x00000000024f01d6: ret

Avec 18 cas, l'assemblage ressemble à ceci (remarquez 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 :

[Verified Entry Point]
  # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1'
  # parm0:    xmm0:xmm0   = double
  # parm1:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x000000000287fe20: mov    DWORD PTR [rsp-0x6000],eax
                                                ;   {no_reloc}
  0x000000000287fe27: push   rbp
  0x000000000287fe28: sub    rsp,0x10           ;*synchronization entry
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@-1 (line 56)
  0x000000000287fe2c: cmp    edx,0x13
  0x000000000287fe2f: jae    0x000000000287fe46
  0x000000000287fe31: movsxd r10,edx
  0x000000000287fe34: shl    r10,0x3
  0x000000000287fe38: movabs r8,0x287fd70       ;   {section_word}
  0x000000000287fe42: jmp    QWORD PTR [r8+r10*1]  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x000000000287fe46: mov    ebp,edx
  0x000000000287fe48: mov    edx,0x31
  0x000000000287fe4d: xchg   ax,ax
  0x000000000287fe4f: call   0x00000000028590a0  ; OopMap{off=52}
                                                ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@202 (line 96)
                                                ;   {runtime_call}
  0x000000000287fe54: int3                      ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@202 (line 96)
  0x000000000287fe55: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe8b]        # 0x000000000287fce8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@194 (line 92)
                                                ;   {section_word}
  0x000000000287fe5d: jmp    0x000000000287ff16
  0x000000000287fe62: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe86]        # 0x000000000287fcf0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@188 (line 90)
                                                ;   {section_word}
  0x000000000287fe6a: jmp    0x000000000287ff16
  0x000000000287fe6f: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe81]        # 0x000000000287fcf8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@182 (line 88)
                                                ;   {section_word}
  0x000000000287fe77: jmp    0x000000000287ff16
  0x000000000287fe7c: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe7c]        # 0x000000000287fd00
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@176 (line 86)
                                                ;   {section_word}
  0x000000000287fe84: jmp    0x000000000287ff16
  0x000000000287fe89: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe77]        # 0x000000000287fd08
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@170 (line 84)
                                                ;   {section_word}
  0x000000000287fe91: jmp    0x000000000287ff16
  0x000000000287fe96: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe72]        # 0x000000000287fd10
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@164 (line 82)
                                                ;   {section_word}
  0x000000000287fe9e: jmp    0x000000000287ff16
  0x000000000287fea0: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe70]        # 0x000000000287fd18
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@158 (line 80)
                                                ;   {section_word}
  0x000000000287fea8: jmp    0x000000000287ff16
  0x000000000287feaa: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe6e]        # 0x000000000287fd20
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@152 (line 78)
                                                ;   {section_word}
  0x000000000287feb2: jmp    0x000000000287ff16
  0x000000000287feb4: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe24]        # 0x000000000287fce0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@146 (line 76)
                                                ;   {section_word}
  0x000000000287febc: jmp    0x000000000287ff16
  0x000000000287febe: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe6a]        # 0x000000000287fd30
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@140 (line 74)
                                                ;   {section_word}
  0x000000000287fec6: jmp    0x000000000287ff16
  0x000000000287fec8: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe68]        # 0x000000000287fd38
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@134 (line 72)
                                                ;   {section_word}
  0x000000000287fed0: jmp    0x000000000287ff16
  0x000000000287fed2: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe66]        # 0x000000000287fd40
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@128 (line 70)
                                                ;   {section_word}
  0x000000000287feda: jmp    0x000000000287ff16
  0x000000000287fedc: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe64]        # 0x000000000287fd48
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@122 (line 68)
                                                ;   {section_word}
  0x000000000287fee4: jmp    0x000000000287ff16
  0x000000000287fee6: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe62]        # 0x000000000287fd50
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@116 (line 66)
                                                ;   {section_word}
  0x000000000287feee: jmp    0x000000000287ff16
  0x000000000287fef0: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe60]        # 0x000000000287fd58
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@110 (line 64)
                                                ;   {section_word}
  0x000000000287fef8: jmp    0x000000000287ff16
  0x000000000287fefa: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe5e]        # 0x000000000287fd60
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@104 (line 62)
                                                ;   {section_word}
  0x000000000287ff02: jmp    0x000000000287ff16
  0x000000000287ff04: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe5c]        # 0x000000000287fd68
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@98 (line 60)
                                                ;   {section_word}
  0x000000000287ff0c: jmp    0x000000000287ff16
  0x000000000287ff0e: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe12]        # 0x000000000287fd28
                                                ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
                                                ;   {section_word}
  0x000000000287ff16: add    rsp,0x10
  0x000000000287ff1a: pop    rbp
  0x000000000287ff1b: test   DWORD PTR [rip+0xfffffffffd9b00df],eax        # 0x0000000000230000
                                                ;   {poll_return}
  0x000000000287ff21: ret

Et enfin, l'assemblage avec 30 cas (ci-dessous) ressemble à celui avec 18 cas, à l'exception de l'addition de movapd xmm0,xmm1 qui apparaît vers le milieu du code, repéré par @cHao - Cependant, la raison la plus probable de la baisse de performance est que la méthode est trop longue pour être inlined avec les paramètres par défaut de la JVM :

[Verified Entry Point]
  # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1'
  # parm0:    xmm0:xmm0   = double
  # parm1:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x0000000002524560: mov    DWORD PTR [rsp-0x6000],eax
                                                ;   {no_reloc}
  0x0000000002524567: push   rbp
  0x0000000002524568: sub    rsp,0x10           ;*synchronization entry
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@-1 (line 56)
  0x000000000252456c: movapd xmm1,xmm0
  0x0000000002524570: cmp    edx,0x1f
  0x0000000002524573: jae    0x0000000002524592  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x0000000002524575: movsxd r10,edx
  0x0000000002524578: shl    r10,0x3
  0x000000000252457c: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe3c]        # 0x00000000025243c0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@364 (line 118)
                                                ;   {section_word}
  0x0000000002524584: movabs r8,0x2524450       ;   {section_word}
  0x000000000252458e: jmp    QWORD PTR [r8+r10*1]  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x0000000002524592: mov    ebp,edx
  0x0000000002524594: mov    edx,0x31
  0x0000000002524599: xchg   ax,ax
  0x000000000252459b: call   0x00000000024f90a0  ; OopMap{off=64}
                                                ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@370 (line 120)
                                                ;   {runtime_call}
  0x00000000025245a0: int3                      ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@370 (line 120)
  0x00000000025245a1: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe27]        # 0x00000000025243d0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@358 (line 116)
                                                ;   {section_word}
  0x00000000025245a9: jmp    0x0000000002524744
  0x00000000025245ae: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe22]        # 0x00000000025243d8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@348 (line 114)
                                                ;   {section_word}
  0x00000000025245b6: jmp    0x0000000002524744
  0x00000000025245bb: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe1d]        # 0x00000000025243e0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@338 (line 112)
                                                ;   {section_word}
  0x00000000025245c3: jmp    0x0000000002524744
  0x00000000025245c8: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe18]        # 0x00000000025243e8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@328 (line 110)
                                                ;   {section_word}
  0x00000000025245d0: jmp    0x0000000002524744
  0x00000000025245d5: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe13]        # 0x00000000025243f0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@318 (line 108)
                                                ;   {section_word}
  0x00000000025245dd: jmp    0x0000000002524744
  0x00000000025245e2: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe0e]        # 0x00000000025243f8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@308 (line 106)
                                                ;   {section_word}
  0x00000000025245ea: jmp    0x0000000002524744
  0x00000000025245ef: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe09]        # 0x0000000002524400
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@298 (line 104)
                                                ;   {section_word}
  0x00000000025245f7: jmp    0x0000000002524744
  0x00000000025245fc: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe04]        # 0x0000000002524408
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@288 (line 102)
                                                ;   {section_word}
  0x0000000002524604: jmp    0x0000000002524744
  0x0000000002524609: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdff]        # 0x0000000002524410
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@278 (line 100)
                                                ;   {section_word}
  0x0000000002524611: jmp    0x0000000002524744
  0x0000000002524616: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdfa]        # 0x0000000002524418
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@268 (line 98)
                                                ;   {section_word}
  0x000000000252461e: jmp    0x0000000002524744
  0x0000000002524623: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffd9d]        # 0x00000000025243c8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@258 (line 96)
                                                ;   {section_word}
  0x000000000252462b: jmp    0x0000000002524744
  0x0000000002524630: movapd xmm0,xmm1
  0x0000000002524634: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe0c]        # 0x0000000002524448
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@242 (line 92)
                                                ;   {section_word}
  0x000000000252463c: jmp    0x0000000002524744
  0x0000000002524641: movapd xmm0,xmm1
  0x0000000002524645: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffddb]        # 0x0000000002524428
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@236 (line 90)
                                                ;   {section_word}
  0x000000000252464d: jmp    0x0000000002524744
  0x0000000002524652: movapd xmm0,xmm1
  0x0000000002524656: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdd2]        # 0x0000000002524430
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@230 (line 88)
                                                ;   {section_word}
  0x000000000252465e: jmp    0x0000000002524744
  0x0000000002524663: movapd xmm0,xmm1
  0x0000000002524667: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdc9]        # 0x0000000002524438
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@224 (line 86)
                                                ;   {section_word}

[etc.]

  0x0000000002524744: add    rsp,0x10
  0x0000000002524748: pop    rbp
  0x0000000002524749: test   DWORD PTR [rip+0xfffffffffde1b8b1],eax        # 0x0000000000340000
                                                ;   {poll_return}
  0x000000000252474f: ret
Répondu el 25 de Mars, 2013 par assylias (102015 Points )

1 votes

Avatar de Aniket

@Abu c'est une source plus fiable. - Démontage.

Commenté el 25 de Mars, 2013 par Aniket

7 votes

Avatar de assylias

@syb0rg Pour être honnête, je ne comprends pas non plus les petits détails ;-)

Commenté el 25 de Mars, 2013 par assylias

4 votes

Avatar de asteri

+1 pour une excellente réponse ! Pourriez-vous démonter quelque chose avec plus de 30 cas pour comparer le moment où la performance sort du "creux" dans le graphique de l'OP ?

Commenté el 25 de Mars, 2013 par asteri
Afficher 19 autres commentaires

46voto

Vishal K avatar
Vishal K Points 9232

Cas Switch est plus rapide si les valeurs sont placées dans une fourchette étroite, par exemple. 

case 1:
case 2:
case 3:
..
..
case n:

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 en un indice dans l' jump 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 l'instruction switch dans la Compilation de la section.

Si la plage de valeurs d'entrée est indéniablement "petits" et n'a qu'un quelques lacunes, certains compilateurs qui intègrent un optimiseur peut effectivement mettre en œuvre l'instruction switch comme une branche de la table ou un tableau de indexé pointeurs de fonction au lieu d'une longue série de conditionnel les instructions. Cela permet à l'instruction switch pour déterminer instantanément la branche d'exécuter sans avoir à passer par une liste de comparaisons.

Répondu el 25 de Mars, 2013 par Vishal K (9232 Points )

4 votes

Avatar de Aniket

Ce n'est pas correct. Il sera plus rapide, que les valeurs des cas soient étroites ou larges. C'est O(1) - l'écart entre les valeurs des cas ne devrait pas avoir d'importance.

Commenté el 25 de Mars, 2013 par Aniket

0 votes

Avatar de Aniket

Je pense que le compilateur Java a quelque chose à voir avec l'augmentation des performances. Mais je ne sais pas trop comment.

Commenté el 25 de Mars, 2013 par Aniket

6 votes

Avatar de Vishal K

@Aniket : Lisez cet article de wikipedia. fr.wikipedia.org/wiki/Branch_table

Commenté el 25 de Mars, 2013 par Vishal K
Afficher 12 autres commentaires

31voto

Vivin Paliath avatar
Vivin Paliath Points 40975

La réponse se trouve dans le bytecode :

SwitchTest10.java

public class SwitchTest10 {

    public static void main(String[] args) {
        int n = 0;

        switcher(n);
    }

    public static void switcher(int n) {
        switch(n) {
            case 0: System.out.println(0);
                    break;

            case 1: System.out.println(1);
                    break;

            case 2: System.out.println(2);
                    break;

            case 3: System.out.println(3);
                    break;

            case 4: System.out.println(4);
                    break;

            case 5: System.out.println(5);
                    break;

            case 6: System.out.println(6);
                    break;

            case 7: System.out.println(7);
                    break;

            case 8: System.out.println(8);
                    break;

            case 9: System.out.println(9);
                    break;

            case 10: System.out.println(10);
                    break;

            default: System.out.println("test");
        }
    }       
}

Bytecode correspondant ; seules les parties pertinentes sont indiquées :

public static void switcher(int);
  Code:
   0:   iload_0
   1:   tableswitch{ //0 to 10
        0: 60;
        1: 70;
        2: 80;
        3: 90;
        4: 100;
        5: 110;
        6: 120;
        7: 131;
        8: 142;
        9: 153;
        10: 164;
        default: 175 }

SwitchTest22.java :

public class SwitchTest22 {

    public static void main(String[] args) {
        int n = 0;

        switcher(n);
    }

    public static void switcher(int n) {
        switch(n) {
            case 0: System.out.println(0);
                    break;

            case 1: System.out.println(1);
                    break;

            case 2: System.out.println(2);
                    break;

            case 3: System.out.println(3);
                    break;

            case 4: System.out.println(4);
                    break;

            case 5: System.out.println(5);
                    break;

            case 6: System.out.println(6);
                    break;

            case 7: System.out.println(7);
                    break;

            case 8: System.out.println(8);
                    break;

            case 9: System.out.println(9);
                    break;

            case 100: System.out.println(10);
                    break;

            case 110: System.out.println(10);
                    break;
            case 120: System.out.println(10);
                    break;
            case 130: System.out.println(10);
                    break;
            case 140: System.out.println(10);
                    break;
            case 150: System.out.println(10);
                    break;
            case 160: System.out.println(10);
                    break;
            case 170: System.out.println(10);
                    break;
            case 180: System.out.println(10);
                    break;
            case 190: System.out.println(10);
                    break;
            case 200: System.out.println(10);
                    break;
            case 210: System.out.println(10);
                    break;

            case 220: System.out.println(10);
                    break;

            default: System.out.println("test");
        }
    }       
}

Bytecode correspondant ; à nouveau, seules les parties pertinentes sont indiquées :

public static void switcher(int);
  Code:
   0:   iload_0
   1:   lookupswitch{ //23
        0: 196;
        1: 206;
        2: 216;
        3: 226;
        4: 236;
        5: 246;
        6: 256;
        7: 267;
        8: 278;
        9: 289;
        100: 300;
        110: 311;
        120: 322;
        130: 333;
        140: 344;
        150: 355;
        160: 366;
        170: 377;
        180: 388;
        190: 399;
        200: 410;
        210: 421;
        220: 432;
        default: 443 }

Dans le premier cas, avec des gammes étroites, le bytecode compilé utilise un tableswitch . Dans le second cas, le bytecode compilé utilise un fichier lookupswitch .

Sur tableswitch la valeur entière en haut de la pile est utilisée pour indexer dans la table, pour trouver la cible du branchement/saut. Ce saut/branchement est ensuite exécuté immédiatement. Il s'agit donc d'un O(1) fonctionnement.

A lookupswitch est plus compliqué. Dans ce cas, la valeur entière doit être comparée à toutes les clés de la table jusqu'à ce que la clé correcte soit trouvée. Une fois la clé trouvée, la cible de branchement/saut (à laquelle cette clé est associée) est utilisée pour le saut. La table qui est utilisée dans lookupswitch est triée et un algorithme de recherche binaire peut être utilisé pour trouver la bonne clé. Les performances d'une recherche binaire sont O(log n) et l'ensemble du processus est également O(log n) parce que le saut est toujours O(1) . La raison pour laquelle les performances sont plus faibles dans le cas de plages éparses est que la clé correcte doit d'abord être recherchée parce que vous ne pouvez pas indexer directement 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 fictives qui pointeraient vers la default option. Par exemple, si l'on suppose que la dernière entrée de la rubrique SwitchTest10.java était 21 au lieu de 10 vous obtenez :

public static void switcher(int);
  Code:
   0:   iload_0
   1:   tableswitch{ //0 to 21
        0: 104;
        1: 114;
        2: 124;
        3: 134;
        4: 144;
        5: 154;
        6: 164;
        7: 175;
        8: 186;
        9: 197;
        10: 219;
        11: 219;
        12: 219;
        13: 219;
        14: 219;
        15: 219;
        16: 219;
        17: 219;
        18: 219;
        19: 219;
        20: 219;
        21: 208;
        default: 219 }

Ainsi, le compilateur crée essentiellement cette énorme table contenant des entrées fictives entre les espaces, pointant vers la cible de branchement de l'élément de commande de l'élément de commande. default l'instruction. Même s'il n'y a pas de default il contiendra des entrées pointant vers l'instruction après le bloc d'interrupteurs. J'ai fait quelques tests de base, et j'ai constaté que si l'écart entre le dernier indice et le précédent ( 9 ) est supérieure à 35 il utilise un lookupswitch au lieu d'un tableswitch .

Le comportement de la switch est définie dans Spécification de la machine virtuelle Java (§3.10) :

Lorsque les cas de commutation sont peu nombreux, la représentation en tableau de l'instruction tableswitch devient inefficace en termes d'espace. L'instruction lookupswitch peut être utilisée à la place. L'instruction lookupswitch associe des clés int (les valeurs des étiquettes de cas) à des décalages cibles dans une table. Lorsqu'une instruction lookupswitch est exécutée, la valeur de l'expression du switch est comparée aux clés du tableau. Si l'une des clés correspond à la valeur de l'expression, l'exécution se poursuit à l'offset cible associé. Si aucune clé ne correspond, l'exécution se poursuit à la cible par défaut. [...]

Répondu el 25 de Mars, 2013 par Vivin Paliath (40975 Points )

1 votes

Avatar de assylias

J'ai compris de la question que les nombres sont toujours contigus mais que la plage est plus ou moins longue - c'est-à-dire que dans un exemple les cas vont de 0 à 5 alors que dans un autre exemple ils vont de 0 à 30 - et aucun des exemples n'utilise de valeurs éparses.

Commenté el 25 de Mars, 2013 par assylias

0 votes

Avatar de Vivin Paliath

@assylias Hmm, intéressant. Je suppose que j'ai mal compris la question. Laissez-moi faire quelques expériences supplémentaires. Donc vous êtes en train de dire que même avec un contiguës allant de 0 à 30, le compilateur utilise une valeur de lookupswitch ?

Commenté el 25 de Mars, 2013 par Vivin Paliath

0 votes

Avatar de Andrew Bissell

@VivinPaliath : Oui, dans mes tests, les constantes de cas sont toujours contiguës, donc je teste essentiellement les interrupteurs sur [0, 1], [0, 1, 2], [0, 1, 2, 3] ... etc.

Commenté el 25 de Mars, 2013 par Andrew Bissell
Afficher 3 autres commentaires

19voto

bestsss avatar
bestsss Points 6403

Puisque la question a déjà reçu une réponse (plus ou moins), voici un conseil. Utilisez

private static final double[] mul={1d, 10d...};
static double multiplyByPowerOfTen(final double d, final int exponent) {
      if (exponent<0 || exponent>=mul.length) throw new ParseException();//or just leave the IOOBE be
      return mul[exponent]*d;
}

Ce code utilise beaucoup moins d'IC (cache d'instructions) et sera toujours inlined. Le tableau sera dans le cache de données L1 si le code est chaud. La table de consultation est presque toujours une victoire. (en particulier sur les microbenchmarks :D )

Edit : si vous souhaitez que la méthode soit "hot-inline", considérez les chemins non rapides tels que throw new ParseException() pour qu'elles soient aussi courtes que possible ou les déplacer vers une méthode statique distincte (ce qui les rendrait aussi courtes que possible). C'est-à-dire que throw new ParseException("Unhandled power of ten " + power, 0); est une idée faible car elle consomme une grande partie du budget d'inlining pour du code qui peut être simplement interprété - la concaténation de chaînes de caractères est assez verbeuse en bytecode . Plus d'informations et un cas réel avec ArrayList

Répondu el 27 de Mars, 2013 par bestsss (6403 Points )

0voto

LifeH2O avatar
LifeH2O Points 1588

Sur la base de javac source vous pouvez écrire switch de manière à ce qu'il utilise tableswitch .

Nous pouvons utiliser le calcul de la source javac pour calculer le coût pour votre deuxième exemple.

lo = 0
hi = 220
nlabels = 24

table_space_cost = 4 + hi - lo + 1
table_time_cost = 3
lookup_space_cost = 3 + 2 * nlabels
lookup_time_cost = nlabels

table_cost = table_space_cost + 3 * table_time_cost // 234
lookup_cost = lookup_space_cost + 3 * lookup_time_cos // 123

Ici le coût du tableswitch est plus élevé (234) que celui du lookupswitch (123) et donc le lookupswitch sera sélectionné comme opcode pour cette instruction de commutation.

Répondu el 20 de Avril, 2021 par LifeH2O (1588 Points )

Questions connexes

Questions en vedette

Top Tags

Dans notre réseau

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

Yandex
X