Spraw, aby Java była szybka: optymalizuj!

Według pioniera informatyka, Donalda Knutha, „przedwczesna optymalizacja jest źródłem wszelkiego zła”. Każdy artykuł na temat optymalizacji musi zaczynać się od wskazania, że ​​zwykle jest więcej powodów, aby nie optymalizować niż optymalizować.

  • Jeśli Twój kod już działa, optymalizacja to pewny sposób na wprowadzenie nowych i prawdopodobnie subtelnych błędów

  • Optymalizacja sprawia, że ​​kod jest trudniejszy do zrozumienia i utrzymania

  • Niektóre z przedstawionych tu technik zwiększają szybkość poprzez zmniejszenie rozszerzalności kodu

  • Optymalizacja kodu dla jednej platformy może faktycznie pogorszyć sytuację na innej platformie

  • Optymalizacja może zająć dużo czasu, przy niewielkim wzroście wydajności i może skutkować zaciemnieniem kodu

  • Jeśli masz obsesję na punkcie optymalizacji kodu, ludzie będą cię nazywać kujonem za twoimi plecami

Przed optymalizacją należy dokładnie rozważyć, czy w ogóle trzeba ją optymalizować. Optymalizacja w Javie może być nieuchwytnym celem, ponieważ środowiska wykonawcze są różne. Użycie lepszego algorytmu prawdopodobnie przyniesie większy wzrost wydajności niż jakakolwiek liczba optymalizacji niskopoziomowych i jest bardziej prawdopodobne, że zapewni poprawę we wszystkich warunkach wykonania. Z reguły optymalizacje wysokiego poziomu należy rozważyć przed wykonaniem optymalizacji niskiego poziomu.

Po co więc optymalizować?

Jeśli to taki zły pomysł, po co w ogóle optymalizować? Cóż, w idealnym świecie byś tego nie zrobił. Ale rzeczywistość jest taka, że ​​czasami największym problemem z programem jest to, że wymaga on po prostu zbyt wielu zasobów, a te zasoby (pamięć, cykle procesora, przepustowość sieci lub kombinacja) mogą być ograniczone. Fragmenty kodu, które występują wielokrotnie w całym programie, mogą być wrażliwe na rozmiar, podczas gdy kod z wieloma iteracjami wykonania może być wrażliwy na szybkość.

Uczyń Javę szybko!

Jako język interpretowany ze zwartym kodem bajtowym, szybkość lub jej brak jest tym, co najczęściej pojawia się jako problem w Javie. Przede wszystkim przyjrzymy się, jak sprawić, by Java działała szybciej, zamiast dopasowywać ją do mniejszej przestrzeni - chociaż wskażemy, gdzie i jak te podejścia wpływają na pamięć lub przepustowość sieci. Nacisk zostanie położony na język podstawowy, a nie na interfejsy API Java.

Nawiasem mówiąc, jedna rzecz, której tutaj nie będziemy omawiać, to użycie metod natywnych napisanych w C lub asemblerze. Chociaż użycie metod natywnych może zapewnić maksymalny wzrost wydajności, odbywa się to kosztem niezależności platformy Java. Możliwe jest napisanie zarówno wersji Java metody, jak i wersji natywnych dla wybranych platform; prowadzi to do zwiększenia wydajności na niektórych platformach bez rezygnacji z możliwości działania na wszystkich platformach. Ale to wszystko, co mam zamiar powiedzieć na temat zastąpienia Javy kodem C. (Więcej informacji na ten temat zawiera Porada dotycząca języka Java „Pisanie metod natywnych”). W tym artykule skupiamy się na tym, jak przyspieszyć Java.

90/10, 80/20, chata, chata, wycieczka!

Z reguły 90% czasu wykonywania programu jest poświęcane na wykonanie 10% kodu. (Niektórzy używają reguły 80% / 20%, ale moje doświadczenie w pisaniu i optymalizowaniu gier komercyjnych w kilku językach w ciągu ostatnich 15 lat pokazało, że formuła 90% / 10% jest typowa dla programów żądnych wydajności, ponieważ niewiele zadań być wykonywane z dużą częstotliwością.) Optymalizacja pozostałych 90 procent programu (gdzie spędzono 10 procent czasu wykonywania) nie ma zauważalnego wpływu na wydajność. Gdybyś był w stanie sprawić, by te 90 procent kodu wykonywało się dwa razy szybciej, program byłby tylko o 5 procent szybszy. Zatem pierwszym zadaniem w optymalizacji kodu jest zidentyfikowanie 10 procent (często jest to mniej) programu, który zajmuje większość czasu wykonywania. To jest n't zawsze tam, gdzie się tego spodziewasz.

Ogólne techniki optymalizacji

Istnieje kilka typowych technik optymalizacji, które można zastosować niezależnie od używanego języka. Niektóre z tych technik, takie jak globalne przydzielanie rejestrów, są zaawansowanymi strategiami przydzielania zasobów maszynowych (na przykład rejestrów procesora) i nie mają zastosowania do kodów bajtowych Java. Skoncentrujemy się na technikach, które zasadniczo obejmują restrukturyzację kodu i zastępowanie równoważnych operacji w ramach metody.

Redukcja siły

Zmniejszenie siły występuje, gdy operacja jest zastępowana równoważną operacją, która jest wykonywana szybciej. Najczęstszym przykładem redukcji siły jest użycie operatora przesunięcia do mnożenia i dzielenia liczb całkowitych przez potęgę 2. Na przykład, x >> 2może być używane zamiast x / 4i x << 1zamienia x * 2.

Wspólna eliminacja podwyrażeń

Eliminacja wspólnego wyrażenia podrzędnego eliminuje zbędne obliczenia. Zamiast pisać

double x = d * (lim / max) * sx; double y = d * (lim / max) * sy;

wspólne wyrażenie podrzędne jest obliczane raz i używane do obu obliczeń:

double depth = d * (lim / max); double x = depth * sx; double y = depth * sy;

Kod ruchu

Ruch kodu przenosi kod, który wykonuje operację lub oblicza wyrażenie, którego wynik nie zmienia się lub jest niezmienny . Kod jest przenoszony, tak aby był wykonywany tylko wtedy, gdy wynik może się zmienić, zamiast wykonywania za każdym razem, gdy wynik jest wymagany. Jest to najbardziej powszechne w przypadku pętli, ale może również obejmować kod powtarzany przy każdym wywołaniu metody. Oto przykład niezmiennego ruchu kodu w pętli:

for (int i = 0; i < x.length; i++) x [i] * = Math.PI * Math.cos (y); 

staje się

podwójne pikosy = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i++)x [i] * = pikosy;

Rozwijanie pętli

Rozwijanie pętli zmniejsza narzut kodu sterującego pętlą, wykonując więcej niż jedną operację za każdym razem w pętli, a tym samym wykonując mniej iteracji. Opierając się na poprzednim przykładzie, jeśli wiemy, że długość x[]jest zawsze wielokrotnością dwóch, możemy przepisać pętlę jako:

podwójne pikosy = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i += 2) {x [i] * = pikosy; x [i + 1] * = pikosy; }

W praktyce, rozwijanie pętli, takich jak ta - w których wartość indeksu pętli jest używana w pętli i musi być oddzielnie zwiększana - nie powoduje znacznego wzrostu szybkości w interpretowanej Javie, ponieważ w kodach bajtowych brakuje instrukcji do skutecznego łączenia „ +1”do indeksu tablicy.

Wszystkie wskazówki dotyczące optymalizacji w tym artykule obejmują jedną lub więcej ogólnych technik wymienionych powyżej.

Uruchomienie kompilatora do pracy

Nowoczesne kompilatory C i Fortran tworzą wysoce zoptymalizowany kod. Kompilatory C ++ generalnie tworzą mniej wydajny kod, ale nadal są na dobrej drodze do tworzenia optymalnego kodu. Wszystkie te kompilatory przeszły przez wiele pokoleń pod wpływem silnej konkurencji rynkowej i stały się precyzyjnie dopracowanymi narzędziami do wyciskania każdej ostatniej kropli wydajności ze zwykłego kodu. Prawie na pewno używają wszystkich przedstawionych powyżej ogólnych technik optymalizacji. Ale wciąż pozostaje wiele sztuczek, aby kompilatory generowały wydajny kod.

javac, JIT i kompilatory kodu natywnego

Poziom optymalizacji javacwykonywany podczas kompilowania kodu w tym momencie jest minimalny. Domyślnie wykonuje następujące czynności:

  • Stałe składanie - kompilator rozwiązuje wszelkie wyrażenia stałe, takie które i = (10 *10)kompiluje do i = 100.

  • Składanie gałęzi (w większości przypadków) - gotounika się zbędnych kodów bajtowych.

  • Ograniczona eliminacja martwego kodu - dla instrukcji takich jak if(false) i = 1.

Poziom optymalizacji zapewniany przez javac powinien ulec poprawie, prawdopodobnie dramatycznie, w miarę dojrzewania języka i rozpoczęcia rywalizacji przez dostawców kompilatorów w oparciu o generowanie kodu. Java właśnie teraz otrzymuje kompilatory drugiej generacji.

Istnieją również kompilatory just-in-time (JIT), które w czasie wykonywania konwertują kody bajtowe Java na kod natywny. Kilka z nich jest już dostępnych i chociaż mogą znacznie zwiększyć szybkość wykonywania programu, poziom optymalizacji, jaki mogą wykonać, jest ograniczony, ponieważ optymalizacja następuje w czasie wykonywania. Kompilator JIT jest bardziej zainteresowany szybkim generowaniem kodu niż generowaniem najszybszego kodu.

Kompilatory kodu natywnego, które kompilują Javę bezpośrednio do kodu natywnego, powinny oferować największą wydajność, ale kosztem niezależności platformy. Na szczęście wiele z przedstawionych tutaj sztuczek zostanie osiągniętych przez przyszłe kompilatory, ale na razie potrzeba trochę pracy, aby jak najlepiej wykorzystać kompilator.

javacoferuje jedną opcję wydajności, którą możesz włączyć: wywołanie -Oopcji powodującej, że kompilator wbudowuje pewne wywołania metod:

javac -O MyClass

Wstawienie wywołania metody powoduje wstawienie kodu metody bezpośrednio do kodu wywołującego metodę. Eliminuje to narzut wywołania metody. W przypadku małej metody ten narzut może stanowić znaczny procent czasu jej wykonania. Należy zauważyć, że tylko metody zadeklarowane jako albo private, staticlub finalmogą być brane pod uwagę do wstawiania, ponieważ tylko te metody są statycznie rozpoznawane przez kompilator. Ponadto synchronizedmetody nie będą wbudowane. Kompilator wbuduje tylko małe metody składające się zazwyczaj z jednego lub dwóch wierszy kodu.

Niestety, wersje 1.0 kompilatora javac mają błąd, który generuje kod, który nie może przekazać weryfikatora kodu bajtowego, gdy -Oużywana jest opcja. Zostało to naprawione w JDK 1.1. (Weryfikator kodu bajtowego sprawdza kod, zanim zostanie on dopuszczony do uruchomienia, aby upewnić się, że nie narusza on żadnych reguł języka Java). Wstawia metody, które odwołują się do elementów klasy niedostępnych dla klasy wywołującej. Na przykład, jeśli poniższe klasy są kompilowane razem przy użyciu -Oopcji

klasa A {private static int x = 10; public static void getX () {return x; }} klasa B {int y = A.getX (); }

wywołanie A.getX () w klasie B zostanie wstawione w klasie B, tak jakby B zostało zapisane jako:

klasa B {int y = Ax; }

Jednak spowoduje to generowanie kodów bajtowych w celu uzyskania dostępu do prywatnej zmiennej Ax, która zostanie wygenerowana w kodzie B. Ten kod będzie działać poprawnie, ale ponieważ narusza ograniczenia dostępu Javy, zostanie oznaczony przez weryfikatora przy IllegalAccessErrorpierwszym wykonaniu kodu.

Ten błąd nie sprawia, że -Oopcja jest bezużyteczna, ale musisz uważać, jak jej używasz. Jeśli jest wywoływany dla pojedynczej klasy, może bez ryzyka wbudować pewne wywołania metod w klasie. Kilka klas można wstawić razem, o ile nie ma żadnych potencjalnych ograniczeń dostępu. Część kodu (na przykład aplikacje) nie podlega weryfikacji kodu bajtowego. Możesz zignorować błąd, jeśli wiesz, że Twój kod będzie wykonywany tylko bez poddawania go weryfikacji. Aby uzyskać dodatkowe informacje, zobacz moje często zadawane pytania dotyczące javac-O.

Profilerzy

Na szczęście JDK jest wyposażony we wbudowany profiler, który pomaga określić, gdzie spędza się czas w programie. Będzie śledzić czas spędzony na każdej procedurze i zapisywać informacje do pliku java.prof. Aby uruchomić profiler, użyj -profopcji podczas wywoływania interpretera Java:

java -prof myClass

Lub do użytku z apletem:

java -prof sun.applet.AppletViewer myApplet.html

Istnieje kilka zastrzeżeń dotyczących korzystania z profilera. Dane wyjściowe programu profilującego nie są szczególnie łatwe do odszyfrowania. Ponadto w JDK 1.0.2 skraca nazwy metod do 30 znaków, więc rozróżnienie niektórych metod może być niemożliwe. Niestety w przypadku Maca nie ma sposobu na wywołanie profilera, więc użytkownicy komputerów Mac nie mają szczęścia. Ponadto strona dokumentów Java firmy Sun (zobacz Zasoby) nie zawiera już dokumentacji dla tej -profopcji). Jeśli jednak Twoja platforma obsługuje tę -profopcję, do interpretacji wyników można użyć programu HyperProf Vladimira Bulatova lub ProfileViewer Grega White'a (patrz Zasoby).

Możliwe jest również "profilowanie" kodu poprzez wstawienie do kodu wyraźnego timingu:

long start = System.currentTimeMillis(); // do operation to be timed here long time = System.currentTimeMillis() - start;

System.currentTimeMillis()zwraca czas z dokładnością do 1/1000 sekundy. Jednak niektóre systemy, takie jak komputer z systemem Windows, mają zegar systemowy z rozdzielczością mniejszą (znacznie mniejszą) niż 1/1000 sekundy. Nawet 1/1000 sekundy nie jest wystarczająco długa, aby dokładnie określić czas wielu operacji. W takich przypadkach lub w systemach z licznikami czasu o niskiej rozdzielczości może być konieczne określenie czasu potrzebnego na powtórzenie operacji n razy, a następnie podzielenie całkowitego czasu przez n, aby uzyskać rzeczywisty czas. Nawet jeśli profilowanie jest dostępne, technika ta może być przydatna do określania czasu wykonania określonego zadania lub operacji.

Oto kilka uwag końcowych na temat profilowania:

  • Zawsze sprawdzaj czas kodu przed i po wprowadzeniu zmian, aby sprawdzić, czy przynajmniej na platformie testowej Twoje zmiany poprawiły program

  • Spróbuj przeprowadzić każdy test synchronizacji w identycznych warunkach

  • Jeśli to możliwe, opracuj test, który nie opiera się na żadnych danych wejściowych użytkownika, ponieważ różnice w odpowiedzi użytkownika mogą powodować wahania wyników

Aplet Benchmark

Aplet Benchmark mierzy czas potrzebny na wykonanie operacji tysiące (lub nawet miliony) razy, odejmuje czas spędzony na wykonywaniu operacji innych niż test (takich jak obciążenie pętli), a następnie wykorzystuje te informacje do obliczenia czasu trwania każdej operacji wzięła. Uruchamia każdy test na około jedną sekundę. Próbując wyeliminować przypadkowe opóźnienia z innych operacji, które komputer może wykonać podczas testu, uruchamia każdy test trzykrotnie i wykorzystuje najlepszy wynik. Próbuje również wyeliminować zbieranie śmieci jako czynnik w testach. Z tego powodu im więcej pamięci jest dostępne dla testu porównawczego, tym dokładniejsze są wyniki testu.