[...] (przyznane w środowisku mikrosekund) [...]
Mikrosekundy sumują się, jeśli zapętlamy ponad miliony do miliardów rzeczy. Osobista sesja optymalizacji vtune / mikro z C ++ (bez ulepszeń algorytmicznych):
T-Rex (12.3 million facets):
Initial Time: 32.2372797 seconds
Multithreading: 7.4896073 seconds
4.9201039 seconds
4.6946372 seconds
3.261677 seconds
2.6988536 seconds
SIMD: 1.7831 seconds
4-valence patch optimization: 1.25007 seconds
0.978046 seconds
0.970057 seconds
0.911041 seconds
Wszystko oprócz „wielowątkowości”, „SIMD” (odręcznie pokonany kompilator) oraz optymalizacji łatki 4-walencyjnej były optymalizacjami pamięci na poziomie mikro. Również oryginalny kod, począwszy od początkowych czasów 32 sekund, został już dość zoptymalizowany (teoretycznie optymalna złożoność algorytmu) i jest to ostatnia sesja. Przetwarzanie oryginalnej wersji na długo przed ostatnią sesją zajęło ponad 5 minut.
Optymalizacja wydajności pamięci może często pomóc w dowolnym miejscu, od kilku razy do rzędów wielkości w kontekście jednowątkowym, a więcej w kontekstach wielowątkowych (korzyści z wydajnego rep pamięci często mnożą się z wieloma wątkami w mieszance).
O znaczeniu mikrooptymalizacji
Trochę niepokoi mnie myśl, że mikrooptymalizacje to strata czasu. Zgadzam się, że to dobra ogólna rada, ale nie wszyscy robią to niepoprawnie w oparciu o przeczucia i przesądy, a nie pomiary. Prawidłowo wykonane nie musi wywoływać mikro uderzenia. Jeśli weźmiemy własny Embree (jądro raytracing) Intela i przetestujemy tylko prosty skalarny BVH, który napisali (nie pakiet ray, który jest wykładniczo trudniejszy do pokonania), a następnie spróbujemy pokonać wydajność tej struktury danych, może to być najbardziej upokarzające doświadczenie nawet dla weterana przyzwyczajonego do profilowania i strojenia kodu przez dziesięciolecia. A wszystko to dzięki zastosowanym mikrooptymalizacjom. Ich rozwiązanie może przetwarzać ponad sto milionów promieni na sekundę, gdy widziałem specjalistów przemysłowych pracujących w raytracingu, którzy potrafią „
Nie ma sposobu, aby zastosować prostą implementację BVH z jedynie algorytmicznym skupieniem i uzyskać ponad sto milionów przecięć pierwotnego promienia na sekundę w stosunku do dowolnego kompilatora optymalizującego (nawet własnego ICC Intela). Prosty często nie dostaje nawet miliona promieni na sekundę. Wymaga rozwiązań profesjonalnej jakości, aby często uzyskać nawet kilka milionów promieni na sekundę. Mikrooptymalizacja na poziomie Intela pozwala uzyskać ponad sto milionów promieni na sekundę.
Algorytmy
Myślę, że mikrooptymalizacja nie jest ważna, dopóki wydajność nie jest ważna na poziomie minut do sekund, np. Godzin lub minut. Jeśli weźmiemy przerażający algorytm, taki jak sortowanie bąbelkowe, i wykorzystamy go jako przykład danych wejściowych masy, a następnie porównamy go nawet z podstawową implementacją sortowania korespondencji seryjnej, przetworzenie tego pierwszego może potrwać miesiące, a w rezultacie 12 minut. złożoności kwadratowej vs liniowo-rytmicznej.
Różnica między miesiącami a minutami prawdopodobnie sprawi, że większość ludzi, nawet tych, którzy nie pracują w obszarach krytycznych pod względem wydajności, uważa czas wykonania za niedopuszczalny, jeśli wymaga to od użytkowników oczekiwania miesięcy na uzyskanie wyniku.
Tymczasem, jeśli porównamy niezoptymalizowany mikro-prosty, prosty sposób scalania z sortowaniem scalonym (który wcale nie jest lepszy algorytmicznie od sortowania scalonego i oferuje jedynie ulepszenia na poziomie mikro dla lokalizacji odniesienia), mikrooptymalizowany szybki zestaw może zakończyć się w 15 sekund zamiast 12 minut. Zmuszanie użytkowników do czekania na 12 minut może być całkowicie do przyjęcia (rodzaj przerwy na kawę).
Myślę, że ta różnica jest prawdopodobnie nieistotna dla większości ludzi, powiedzmy, od 12 minut do 15 sekund, i dlatego mikrooptymalizacja jest często uważana za bezużyteczną, ponieważ często przypomina jedynie różnicę między minutami a sekundami, a nie minutami i miesiącami. Innym powodem, dla którego uważam, że jest bezużyteczny, jest to, że często stosuje się go w obszarach, które nie mają znaczenia: jakiś niewielki obszar, który nie jest nawet zapętlony i krytyczny, co daje pewną wątpliwą różnicę 1% (co może być po prostu hałasem). Ale dla osób, które dbają o tego rodzaju różnice czasowe i są skłonne zmierzyć i zrobić to dobrze, myślę, że warto zwrócić uwagę przynajmniej na podstawowe pojęcia hierarchii pamięci (szczególnie na wyższe poziomy związane z błędami strony i brakami pamięci podręcznej) .
Java pozostawia dużo miejsca na dobre mikrooptymalizacje
Uff, przepraszam - z takim narzekaniem na bok:
Czy „magia” JVM utrudnia wpływ programisty na mikrooptymalizacje w Javie?
Trochę, ale nie tak bardzo, jak ludzie mogą pomyśleć, jeśli zrobisz to dobrze. Na przykład, jeśli wykonujesz przetwarzanie obrazu, w natywnym kodzie z ręcznie napisaną kartą SIMD, wielowątkowością i optymalizacją pamięci (wzorce dostępu, a być może nawet reprezentacja w zależności od algorytmu przetwarzania obrazu), łatwo jest zgnieść setki milionów pikseli na sekundę przez 32- bit RGBA (8-bitowe kanały kolorów), a czasem nawet miliardy na sekundę.
Nie można zbliżyć się do Javy, jeśli powiesz, że stworzyłeś Pixelobiekt (to samo zwiększyłoby rozmiar piksela z 4 bajtów do 16 na 64-bit).
Ale możesz być w stanie podejść o wiele bliżej, jeśli unikniesz Pixelobiektu, użyjesz tablicy bajtów i zamodelujesz Imageobiekt. Java jest nadal dość kompetentna, jeśli zaczniesz używać tablic zwykłych starych danych. Próbowałem już tego rodzaju rzeczy w Javie i byłem pod dużym wrażeniem, pod warunkiem , że nie stworzysz wszędzie małych małych obiektów, które są 4 razy większe niż normalnie (np. Użyj intzamiast Integer) i zaczniesz modelować masowe interfejsy jak Imageinterfejs, a nie Pixelinterfejs. Zaryzykuję nawet stwierdzenie, że Java może konkurować z wydajnością C ++, jeśli zapętlasz stare, zwykłe dane, a nie obiekty (ogromne tablice float, np. Nie Float).
Być może nawet ważniejsze niż rozmiary pamięci jest to, że tablica intgwarantuje ciągłą reprezentację. Tablica Integernie. Ciągłość jest często niezbędna dla lokalizacji odniesienia, ponieważ oznacza, że wiele elementów (np. 16 ints) może zmieścić się w jednej linii pamięci podręcznej i potencjalnie być dostępnym razem przed eksmisją dzięki wydajnym wzorcom dostępu do pamięci. Tymczasem pojedynczy Integermoże być spleciony gdzieś w pamięci, a otaczająca pamięć jest nieistotna, tylko po to, aby ten obszar pamięci został załadowany do linii pamięci podręcznej, aby użyć tylko jednej liczby całkowitej przed eksmisją, w przeciwieństwie do 16 liczb całkowitych. Nawet jeśli mieliśmy cudowne szczęście i otoczenieIntegersbyły w porządku obok siebie w pamięci, możemy zmieścić tylko 4 w linii pamięci podręcznej, do której można uzyskać dostęp przed eksmisją, ponieważ Integerjest 4 razy większy, i to jest najlepszy scenariusz.
Jest tam wiele mikrooptymalizacji, ponieważ jesteśmy zunifikowani w ramach tej samej architektury / hierarchii pamięci. Wzorce dostępu do pamięci są ważne bez względu na to, jakiego języka używasz, pojęcia takie jak kafelkowanie / blokowanie pętli mogą być generalnie stosowane znacznie częściej w C lub C ++, ale w równym stopniu korzystają z języka Java.
Niedawno czytałem w C ++ czasami porządkowanie członków danych może zapewnić optymalizacje [...]
Kolejność elementów danych na ogół nie ma znaczenia w Javie, ale to w większości dobra rzecz. W C i C ++ zachowanie kolejności elementów danych jest często ważne z powodów ABI, więc kompilatory nie mają z tym problemu. Pracujący tam programiści muszą być ostrożni, wykonując czynności takie jak rozmieszczanie członków danych w porządku malejącym (od największego do najmniejszego), aby uniknąć marnowania pamięci na wypełnianie. W przypadku Javy najwyraźniej JIT może zmieniać kolejność elementów w locie, aby zapewnić prawidłowe wyrównanie przy jednoczesnym zminimalizowaniu wypełniania, więc pod warunkiem, że tak jest, automatyzuje coś, co przeciętni programiści C i C ++ często robią źle i w ten sposób marnują pamięć ( co nie tylko marnuje pamięć, ale często marnuje prędkość, niepotrzebnie zwiększając krok między strukturami AoS i powodując więcej braków pamięci podręcznej). To' jest bardzo robotyczną rzeczą do zmiany układu pól w celu zminimalizowania paddingu, więc idealnie ludzie nie radzą sobie z tym. Jedynym momentem, w którym rozmieszczenie pól może mieć znaczenie w sposób, który wymaga od człowieka znajomości optymalnego ustawienia, jest to, że obiekt jest większy niż 64 bajty, a my układamy pola w oparciu o wzorzec dostępu (nie optymalne wypełnienie) - w takim przypadku może być przedsięwzięciem bardziej ludzkim (wymaga zrozumienia kluczowych ścieżek, z których niektóre są informacjami, których kompilator nie mógłby przewidzieć, nie wiedząc, co użytkownicy zrobią z oprogramowaniem).
Jeśli nie, ludzie mogą podać przykłady sztuczek, które można zastosować w Javie (oprócz prostych flag kompilatora).
Największą różnicą dla mnie pod względem optymalizującej mentalności między Javą a C ++ jest to, że C ++ może pozwalać na używanie obiektów nieco (nieco mniejszych) niż Java w scenariuszu krytycznym pod względem wydajności. Na przykład C ++ może zawijać liczbę całkowitą do klasy bez żadnego narzutu (testowany w każdym miejscu). Java musi mieć ten styl metadanych w stylu wskaźnika + wypełnienia wyrównania na obiekt, dlatego Booleanjest większy niż boolean(ale w zamian zapewnia jednolite korzyści z odbicia i możliwość zastąpienia dowolnej funkcji nieoznaczonej jak finaldla każdego UDT).
W C ++ jest nieco łatwiej kontrolować ciągłość układów pamięci w niejednorodnych polach (np. Przeplatanie liczb zmiennoprzecinkowych i liczb całkowitych w jednej tablicy poprzez strukturę / klasę), ponieważ lokalizacja przestrzenna jest często gubiona (lub przynajmniej traci się kontrolę) w Javie podczas przydzielania obiektów za pomocą GC.
... ale często rozwiązania o najwyższej wydajności często i tak je dzielą i wykorzystują wzorzec dostępu SoA na ciągłych tablicach zwykłych starych danych. Tak więc w obszarach, które wymagają najwyższej wydajności, strategie optymalizacji układu pamięci między Javą i C ++ są często takie same i często zmuszają cię do demolowania tych niewielkich interfejsów obiektowych na rzecz interfejsów w stylu kolekcji, które mogą wykonywać takie czynności jak hot / dzielenie pola zimnego, powtórzenia SoA itp. Niejednorodne powtórzenia AoSoA wydają się w Javie trochę niemożliwe (chyba że użyłeś surowej tablicy bajtów lub czegoś podobnego), ale są to rzadkie przypadki, w których obasekwencyjne i losowe wzorce dostępu muszą być szybkie, a jednocześnie mieć mieszankę typów pól dla gorących pól. Dla mnie większość różnic w strategii optymalizacji (na ogólnym poziomie) między tymi dwoma jest sporna, jeśli sięgasz po szczytową wydajność.
Różnice różnią się znacznie bardziej, jeśli po prostu sięgasz po „dobrą” wydajność - nie jest w stanie zrobić tyle z małymi obiektami, jak Integervs., intmoże być trochę bardziej PITA, szczególnie ze względu na sposób, w jaki współdziała z lekami generycznymi . Jest to nieco trudniejsze, aby po prostu zbudować jeden rodzajowy struktury danych jako centralny cel optymalizacji w Javie, który pracuje dla int, floatitp unikając tych większych i droższych UDTs, ale często najbardziej obszary wydajności krytycznych wymagać będzie ręcznie toczenia własnych struktur danych i tak dostrojony do bardzo konkretnego celu, więc denerwuje tylko kod, który dąży do dobrej wydajności, ale nie do maksymalnej wydajności.
Obiekt nad głową
Zauważ, że narzut obiektu Java (metadane i utrata lokalizacji przestrzennej oraz tymczasowa utrata lokalizacji czasowej po początkowym cyklu GC) jest często duży dla rzeczy, które są naprawdę małe (jak intvs. Integer), które są przechowywane przez miliony w jakiejś strukturze danych, która w dużej mierze przylegające i dostępne w bardzo ciasnych pętlach. Wydaje się, że w tym temacie jest dużo wrażliwości, więc powinienem wyjaśnić, że nie chcesz się martwić o narzut obiektów w przypadku dużych obiektów, takich jak obrazy, tylko bardzo małe obiekty, takie jak pojedynczy piksel.
Jeśli ktoś ma wątpliwości co do tej części, proponuję zrobić punkt odniesienia między zsumowaniem miliona losowych intsa milionem losowych Integersi zrobić to wielokrotnie ( Integersprzetasowanie pamięci po początkowym cyklu GC).
Ultimate Trick: projekty interfejsów, które pozwalają zoptymalizować
Tak więc najlepsza sztuczka Java, jaką widzę, jeśli masz do czynienia z miejscem, które wytrzymuje duże obciążenie małych obiektów (np. A Pixel, 4-wektorowa, macierz 4x4, a Particlenawet Accountjeśli ma tylko kilka małych pola) to unikanie używania obiektów dla tych drobiazgów i używanie tablic (ewentualnie połączonych razem) zwykłych starych danych. Obiektów następnie stać interfejsy kolekcji jak Image, ParticleSystem, Accounts, zbiór macierzy lub wektorów itp Poszczególne te mogą być dostępne przez indeks, np Jest to również jeden z ostatecznych sztuczek projektowych w C i C ++, ponieważ nawet bez tego podstawowego napowietrznych obiektu i rozłączona pamięć, modelowanie interfejsu na poziomie pojedynczej cząstki zapobiega najbardziej wydajnym rozwiązaniom.