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.
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.
źródło
switchstwierdzeniach, ponieważ jest to zdecydowanie najbardziej optymalne rozwiązanie. : D (Nie pokazuj mi tego, proszę).lookupswitchna atableswitch. Demontaż kodu za pomocąjavappokazałby na pewno.Odpowiedzi:
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ądalookupswitch(podobne do strukturyif/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):
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: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:źródło
Przełączanie wielkości liter jest szybsze, jeśli wartości wielkości liter są umieszczone w wąskim zakresie np.
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.
źródło
Odpowiedź leży w kodzie bajtowym:
SwitchTest10.java
Odpowiedni kod bajtowy; pokazano tylko odpowiednie części:
SwitchTest22.java:
Odpowiedni kod bajtowy; ponownie pokazane tylko odpowiednie części:
W pierwszym przypadku, przy wąskich zakresach, skompilowany kod bajtowy używa a
tableswitch. W drugim przypadku skompilowany kod bajtowy używalookupswitch.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 toO(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 tabelalookupswitchjest sortowana, a algorytm wyszukiwania binarnego może zostać użyty do znalezienia właściwego klucza. Wydajność wyszukiwania binarnego jestO(log n)taka sama, jak cały procesO(log n), ponieważ skok nadal trwaO(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 nadefaultopcję. Na przykład, zakładając, że ostatni wpisSwitchTest10.javabył21zamiast10, otrzymujesz: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 madefault, 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 onlookupswitchzamiast atableswitch.Zachowanie
switchinstrukcji jest określone w specyfikacji wirtualnej maszyny Java (§3.10) :źródło
lookupswitch?Ponieważ na pytanie już udzielono odpowiedzi (mniej więcej), oto kilka wskazówek. Posługiwać się
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 tothrow 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źródło