Dlaczego Java z włączonymi ciągłymi intami wydaje się działać szybciej z dodanymi przypadkami?

276

Pracuję nad kodem Java, który musi być wysoce zoptymalizowany, ponieważ będzie działał w gorących funkcjach, które są wywoływane w wielu punktach mojej logiki programu głównego. Część tego kodu polega na pomnożeniu doublezmiennych przez 10podniesione do dowolnych nieujemnych int exponent. Jeden szybki sposób (edit: ale nie najszybsze, patrz Aktualizacja 2 poniżej), aby uzyskać wartość zwielokrotniony jest switchna 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);
   }
}

Skomentowane elipsy powyżej wskazują, że case intstałe nadal zwiększają się o 1, więc casew powyższym fragmencie kodu są naprawdę 19 s. Ponieważ nie byłem pewien, czy ja rzeczywiście trzeba wszystkie siły 10 w casesprawozdaniu 10thru 18, wpadłem kilka microbenchmarks porównanie czasu do ukończenia 10 milionów operacji z tym switchstwierdzeniem kontra switchz tylko cases 0thru 9(z exponentograniczona do 9 lub mniej unikaj łamania zredukowanego switch). Miałem dość zaskakujący (przynajmniej dla mnie!) Wynik, że im dłużej switchz większą liczbą caseinstrukcji faktycznie działało szybciej.

Na sroku próbowałem dodać jeszcze więcej cases, które właśnie zwróciły wartości pozorne, i odkryłem, że mogę sprawić, aby przełącznik działał jeszcze szybciej z około 22-27 zadeklarowanymi wartościami cases (nawet jeśli te fałszywe przypadki nigdy nie są trafiane podczas działania kodu ). (Ponownie, cases zostały dodane w sposób ciągły poprzez zwiększenie poprzedniej casestałej o 1.) Te różnice w czasie wykonania nie są bardzo znaczące: dla losowego exponentmiędzy 0i 10, manekinowa switchinstrukcja kończy 10 milionów wykonań w 1,49 sekundy w porównaniu do 1,54 sekundy w przypadku niewypełnionego wersja, dla wielkich całkowitych oszczędności 5ns na wykonanie. Więc nie jest to rzecz, która sprawia, że ​​obsesja na punkcie wyrzuceniaswitchoświadczenie warte wysiłku z punktu widzenia optymalizacji. Ale nadal uważam za ciekawe i sprzeczne z intuicją, że a switchnie staje się wolniejsze (lub w najlepszym razie utrzymuje stały czas O (1) ) do wykonania, gdy casedodaje się do niego więcej s.

zmienić wyniki testów porównawczych

Są to wyniki, które uzyskałem, stosując różne limity losowo generowanych exponentwartości. I nie obejmują wyników całą drogę w dół do 1za exponentgranicę, ale ogólny kształt krzywej pozostaje taka sama, z grzbietu wokół znaku 12-17 przypadek i dolinie między 18-28. Wszystkie testy zostały uruchomione w JUnitBenchmark przy użyciu wspólnych kontenerów dla losowych wartości, aby zapewnić identyczne dane wejściowe testowania. Testy przeprowadziłem także w kolejności od najdłuższego switchwyrażenia do najkrótszego i odwrotnie, aby spróbować wyeliminować możliwość wystąpienia problemów z testowaniem związanym z porządkowaniem. Umieściłem mój kod testowy na repozytorium github, jeśli ktoś chce spróbować odtworzyć te wyniki.

Co się tu dzieje? Jakieś kaprysy mojej architektury lub konstrukcji z mikroprocesorem? Lub Java jest switchnaprawdę trochę szybciej wykonać w 18celu 28 casezakresie niż jest to od 11do 17?

repozytorium testowe github „Switch-Experiment”

AKTUALIZACJA: Wyczyściłem trochę bibliotekę testów porównawczych i dodałem plik tekstowy do / results z pewnymi danymi wyjściowymi w szerszym zakresie możliwych exponentwartości. Dodałem również opcję w kodzie testowym, aby nie wyrzucać Exceptionz default, ale nie wydaje się to wpływać na wyniki.

AKTUALIZACJA 2: Znalazłem całkiem niezłą dyskusję na ten temat z 2009 roku na forum xkcd tutaj: http://forums.xkcd.com/viewtopic.php?f=11&t=33524 . Dyskusja OP dotycząca użycia Array.binarySearch()dała mi pomysł na prostą implementację powyższego wzorca potęgowania w oparciu o tablicę. Wyszukiwanie binarne nie jest potrzebne, ponieważ wiem, jakie są wpisy array. Wygląda na to, że działa około 3 razy szybciej niż przy użyciu switch, oczywiście kosztem pewnego przepływu sterowania, który switchzapewnia. Ten kod został również dodany do repozytorium github.

Andrew Bissell
źródło
64
Teraz wszyscy pracownicy Google będą mieli dokładnie 22 przypadki we wszystkich switchstwierdzeniach, ponieważ jest to zdecydowanie najbardziej optymalne rozwiązanie. : D (Nie pokazuj mi tego, proszę).
asteri
2
Czy masz prostszy SSCCE? Ten nie kompiluje się dla mnie. Choć jestem słaby, jeśli chodzi o wydajność Javy, chcę spróbować.
Mysticial
5
Pomocna może być sekcja „Przełączniki w JVM” w mojej odpowiedzi na temat przypadków opartych na łańcuchach. Myślę, że dzieje się tutaj to, że zmieniasz z a lookupswitchna a tableswitch. Demontaż kodu za pomocą javappokazałby na pewno.
erickson,
2
Dodałem słoiki zależności do folderu / lib w repozytorium. @Mysticial Niestety, spędziłem już za dużo czasu, schodząc do tej króliczej nory! Jeśli usuniesz „extends AbstractBenchmark” z klas testowych i pozbędziesz się importu „com.carrotsearch”, możesz uruchomić tylko z zależnością JUnit, ale funkcja wyszukiwania marchewek jest całkiem niezła do odfiltrowywania części szumu z JIT i okresy rozgrzewki. Niestety nie wiem, jak uruchomić te testy JUnit poza IntelliJ.
Andrew Bissell
2
@AndrewBissell Udało mi się odrzucić wyniki za pomocą znacznie prostszego testu porównawczego. Rozgałęzienie vs. tabela dla małych i średnich wyników było dość oczywiste. Ale nie mam lepszego wglądu niż ktokolwiek inny na temat zanurzenia się w 30 przypadkach ...
Mysticial

Odpowiedzi:

228

Jak wskazano w drugiej odpowiedzi , ponieważ wartości przypadków są ciągłe (w przeciwieństwie do rzadkich), wygenerowany kod bajtowy dla różnych testów używa tablicy przełączników (instrukcja kodu bajtowego tableswitch).

Jednak gdy JIT rozpocznie pracę i skompiluje kod bajtowy w asemblerze, tableswitchinstrukcja nie zawsze daje tablicę wskaźników: czasami tablica przełączników jest przekształcana w coś, co wygląda lookupswitch(podobne do struktury if/ else if).

Dekompilacja zestawu wygenerowanego przez JIT (hotspot JDK 1.7) pokazuje, że wykorzystuje on ciąg if / else, jeśli jest 17 przypadków lub mniej, tablicę wskaźników, gdy jest ich więcej niż 18 (bardziej wydajna).

Powód, dla którego używana jest ta magiczna liczba 18, sprowadza się do domyślnej wartości MinJumpTableSizeflagi JVM (wokół linii 352 w kodzie).

Podniosłem ten problem na liście kompilatorów hotspotów i wydaje się, że jest to dziedzictwo poprzednich testów . Zauważ, że ta wartość domyślna została usunięta w JDK 8 po przeprowadzeniu większej liczby testów porównawczych .

Wreszcie, gdy metoda staje się zbyt długa (> 25 przypadków w moich testach), nie jest już uwzględniana przy domyślnych ustawieniach JVM - jest to najbardziej prawdopodobna przyczyna spadku wydajności w tym momencie.


W 5 przypadkach zdekompilowany kod wygląda następująco (zwróć uwagę na instrukcje cmp / je / jg / jmp, zestaw dla 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    

W 18 przypadkach zestaw wygląda tak (zwróć uwagę na tablicę używanych wskaźników i eliminuje potrzebę wszystkich porównań: jmp QWORD PTR [r8+r10*1]przeskakuje bezpośrednio do właściwego mnożenia) - jest to prawdopodobny powód poprawy wydajności:

[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    

I wreszcie zestaw z 30 przypadkami (poniżej) wygląda podobnie do 18 przypadków, z wyjątkiem dodatkowego, movapd xmm0,xmm1który pojawia się w połowie kodu, jak zauważył @ cHao - jednak najbardziej prawdopodobną przyczyną spadku wydajności jest to, że metoda jest zbyt tęsknię za wprowadzeniem domyślnych ustawień 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    
assylias
źródło
7
@ syb0rg Szczerze mówiąc, nie rozumiem też drobnych szczegółów ;-)
assylias
4
+1 za świetną odpowiedź! Czy możesz zdemontować coś z ponad 30 skrzyniami do porównania, gdy wydajność wychodzi z „zapadu” na wykresie PO?
asteri
4
@VivinPaliath stackoverflow.com/questions/1503479/…
assylias
2
@AndrewBissell Domyślam się, że różne zachowanie opiera się na (i) testach wydajności między architekturami, które wykazały, że tablica wskaźników jest skuteczna tylko wtedy, gdy liczba przypadków jest większa niż 18, lub (ii) kod jest profilowany jako jest uruchamiany, a profiler określa, które podejście jest lepsze w czasie wykonywania. Nie mogę znaleźć odpowiedzi.
assylias,
3
Demontaż 30 skrzynek i 18 skrzynek wygląda prawie tak samo. Różnice wydają się w większości ograniczone do dodatkowego tasowania rejestru po około 11 przypadku. Nie mogę powiedzieć, dlaczego JITter to robi; wydaje się niepotrzebny.
cHao
46

Przełączanie wielkości liter jest szybsze, jeśli wartości wielkości liter są umieszczone w wąskim zakresie np.

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

Ponieważ w tym przypadku kompilator może uniknąć wykonania porównania dla każdego etapu sprawy w instrukcji switch. Kompilator tworzy tabelę skoków, która zawiera adresy działań, które należy wykonać na różnych nogach. Wartość, na której dokonywany jest przełącznik, zostaje zmanipulowana w celu przekształcenia go w indeks w celu jump table. W tej implementacji czas potrzebny na instrukcję switch jest znacznie krótszy niż czas równoważnej kaskadzie instrukcji if-else-if. Również czas poświęcony instrukcji switch jest niezależny od liczby odnóg liter w instrukcji switch.

Jak stwierdzono w wikipedii o instrukcji switch w sekcji Kompilacja.

Jeśli zakres wartości wejściowych jest identyfikowalnie „mały” i ma tylko kilka luk, niektóre kompilatory zawierające optymalizator mogą faktycznie zaimplementować instrukcję switch jako tabelę rozgałęzień lub tablicę indeksowanych wskaźników funkcji zamiast długiej serii instrukcji warunkowych. Pozwala to instrukcji switch na natychmiastowe określenie, którą gałąź wykonać, bez konieczności przeglądania listy porównań.

Vishal K.
źródło
4
to nie jest poprawne. Będzie szybciej, niezależnie od tego, czy wartości przypadków są wąskie czy szerokie. Jest to O (1) - nie powinno mieć znaczenia, jak różne są wartości wielkości liter.
Aniket Inge
6
@Aniket: Przeczytaj ten artykuł wikipedii. en.wikipedia.org/wiki/Branch_table
Vishal K
14
@Aniket: To nie jest O (1), jeśli zakres jest szeroki i rzadki. Istnieją dwa rodzaje przełączników, a jeśli zakres jest zbyt rozproszony, Java skompiluje go do „przełącznika wyszukiwania” zamiast „przełącznika tabel”. Pierwszy wymaga porównania gałęzi do znalezienia, podczas gdy drugi nie.
cHao
4
Wikipedia jest przyzwoitym miejscem do wyszukiwania odniesień, ale nie powinna być uznawana za wiarygodne źródło. Wszystko, co tam czytasz, to najlepsze informacje z drugiej ręki.
cHao
6
@Aniket: Szczerze mówiąc, deasemblacja jest specyficzna dla danego JVM na konkretnej platformie. Inni mogą to tłumaczyć inaczej. Niektórzy mogą w rzeczywistości użyć tablicy skrótów do wyszukiwania. Nadal nie będzie działał tak dobrze jak przełącznik stołowy, ale może przynajmniej być blisko. Zajmie to więcej czasu dla JIT i wymaga zastosowania algorytmu mieszającego do danych wejściowych. Więc chociaż wynikowy kod asemblera może być pouczający, nie jest on również autorytatywny, chyba że mówisz konkretnie o Hotspot v1.7. Cokolwiek na Windows x86_64.
cHao
30

Odpowiedź leży w kodzie bajtowym:

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");
        }
    }       
}

Odpowiedni kod bajtowy; pokazano tylko odpowiednie części:

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");
        }
    }       
}

Odpowiedni kod bajtowy; ponownie pokazane tylko odpowiednie części:

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 }

W pierwszym przypadku, przy wąskich zakresach, skompilowany kod bajtowy używa a tableswitch. W drugim przypadku skompilowany kod bajtowy używa lookupswitch.

W tableswitchpolu wartość całkowita na górze stosu służy do indeksowania tabeli, aby znaleźć cel rozgałęzienia / skoku. Ten skok / gałąź jest następnie wykonywany natychmiast. Dlatego jest to O(1)operacja.

A lookupswitchjest bardziej skomplikowane. W takim przypadku wartość całkowitą należy porównać ze wszystkimi kluczami w tabeli, dopóki nie zostanie znaleziony prawidłowy klucz. Po znalezieniu klucza do skoku używany jest cel rozgałęzienia / skoku (na który mapowany jest ten klucz). Używana tabela lookupswitchjest sortowana, a algorytm wyszukiwania binarnego może zostać użyty do znalezienia właściwego klucza. Wydajność wyszukiwania binarnego jest O(log n)taka sama, jak cały proces O(log n), ponieważ skok nadal trwa O(1). Dlatego przyczyną niskiej wydajności w przypadku rzadkich zakresów jest to, że najpierw należy sprawdzić poprawny klucz, ponieważ nie można bezpośrednio indeksować tabeli.

Jeśli istnieją rzadkie wartości i miałbyś tylko tableswitchdo użycia, tabela zasadniczo zawierałaby pozorne wpisy wskazujące na defaultopcję. Na przykład, zakładając, że ostatni wpis SwitchTest10.javabył 21zamiast 10, otrzymujesz:

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 }

Tak więc kompilator zasadniczo tworzy ogromną tabelę zawierającą pozorne wpisy między przerwami, wskazując na rozgałęziony cel defaultinstrukcji. Nawet jeśli nie ma default, będzie zawierać wpisy wskazujące instrukcję po bloku przełącznika. Zrobiłem kilka podstawowych testów i odkryłem, że jeśli różnica między ostatnim indeksem a poprzednim ( 9) jest większa niż 35, to używa on lookupswitchzamiast a tableswitch.

Zachowanie switchinstrukcji jest określone w specyfikacji wirtualnej maszyny Java (§3.10) :

Tam, gdzie przypadki przełącznika są rzadkie, reprezentacja tabelowa instrukcji tablewitch staje się nieefektywna pod względem przestrzeni. Zamiast tego można użyć instrukcji lookupswitch. Instrukcja lookupswitch paruje klucze int (wartości etykiet sprawy) z docelowymi przesunięciami w tabeli. Kiedy wykonywana jest instrukcja przełącznika, wartość wyrażenia przełącznika jest porównywana z kluczami w tabeli. Jeśli jeden z kluczy pasuje do wartości wyrażenia, wykonywanie jest kontynuowane z powiązanym przesunięciem docelowym. Jeśli żaden klucz nie pasuje, wykonywanie jest kontynuowane w domyślnym celu. [...]

Vivin Paliath
źródło
1
Zrozumiałem z pytania, że ​​liczby są zawsze ciągłe, ale zakres jest mniej więcej dłuższy - tj. W jednym przykładzie przypadki idą od 0 do 5, podczas gdy w innym przykładzie idą od 0 do 30 - i żaden z przykładów nie używa rzadkich wartości
assylias
@assylias Hmm, ciekawe. Chyba źle zrozumiałem pytanie. Pozwól mi zrobić trochę więcej eksperymentów. Mówisz więc, że nawet przy ciągłym zakresie od 0-30 kompilator używa lookupswitch?
Vivin Paliath,
@VivinPaliath: Tak, w moich testach stałe przypadków są zawsze ciągłe, więc w zasadzie testuję włączniki [0, 1], [0, 1, 2], [0, 1, 2, 3] ... itd.
Andrew Bissell
@VivinPaliath Nie, kod bajtowy zawsze używa przełącznika tabel - jednak kompilator JIT nie wydaje się kompilować przełącznika tabel w celu złożenia w ten sam sposób, w zależności od liczby zawartych w nim elementów.
assylias
6
@VivinPaliath Mógłbym z całą pewnością sformułować pytanie. Jestem trochę z głębi, jeśli chodzi o ocenę odpowiedzi dotyczących tego kodu bajtowego i elementów asemblera na niskim poziomie. Nadal wydaje mi się, że rozróżnienie przełącznika tabel / przełącznika odnośników jest tutaj naprawdę ważne, a twoja jest jedyną odpowiedzią, która używa tych terminów do tej pory (chociaż inni prawdopodobnie przedstawiają tę samą koncepcję z inną terminologią). Dodatkowo lubię też link do specyfikacji JVM.
Andrew Bissell,
19

Ponieważ na pytanie już udzielono odpowiedzi (mniej więcej), oto kilka wskazówek. Posługiwać się

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;
}

Ten kod zużywa znacznie mniej IC (pamięć podręczna instrukcji) i zawsze będzie wstawiany. Tablica będzie w pamięci podręcznej danych L1, jeśli kod jest gorący. Tabela przeglądowa jest prawie zawsze wygrana. (szczególnie w przypadku mikrobenchmarków: D)

Edycja: jeśli chcesz, aby metoda była wprowadzana na gorąco, weź pod uwagę, że ścieżki nie-szybkie throw new ParseException()są tak krótkie jak minimum lub przenieś je do oddzielnej metody statycznej (a zatem skróć je do minimum). Jest to throw new ParseException("Unhandled power of ten " + power, 0);słaby pomysł, ponieważ zużywa on znaczny budżet na kod, który można po prostu zinterpretować - łączenie łańcuchów jest dość szczegółowe w kodzie bajtowym. Więcej informacji i prawdziwy przypadek w / ArrayList

bestsss
źródło