Co wpływa na szybkość programów w C++ i jak ją osiągnąć przy wysokim poziomie kodu? Główny twórca biblioteki CatBoost, Evgeny Petrov, odpowiedział na te pytania, korzystając z przykładów i ilustracji z doświadczeń pracy nad CatBoost dla x86_64.
Relacja wideo
- Cześć wszystkim. Optymalizuję procesor dla biblioteki uczenia maszynowego CatBoost. Główna część naszej biblioteki jest napisana w języku C++. Dziś opowiem Wam w jaki prosty sposób osiągamy prędkość.
Szybkość obliczeń składa się z dwóch części. Pierwsza część to algorytm. Jeśli popełnimy błąd przy wyborze algorytmu, to później nie da się go szybko uruchomić. Druga część dotyczy optymalizacji naszego algorytmu pod kątem posiadanego systemu komputerowego, jego wydajności i przepustowości.
Oddzielnie należy uwzględnić wymianę danych i obliczenia ze względu na dużą różnicę w ich szybkości. Jeśli prędkość pamięci przyjmiemy jako prędkość pieszego, wówczas prędkość obliczeń będzie w przybliżeniu prędkością przelotową samolotu pasażerskiego.
Aby wygładzić tę różnicę, architektura ma kilka poziomów buforowania. Najszybsza i najmniejsza jest pamięć podręczna L1. Następnie jest większa i wolniejsza pamięć podręczna, drugi poziom. Istnieje bardzo duża pamięć podręczna, która może mieć dziesiątki megabajtów, pamięć podręczna trzeciego poziomu, ale jest najwolniejsza.
Ze względu na różne szybkości wymiany danych w obliczeniach, kod obliczeniowy dzieli się na dwie klasy. Jedna klasa jest ograniczona przepustowością, czyli szybkością wymiany danych. Druga klasa jest ograniczona szybkością procesora. Granica między nimi jest ustalana w zależności od liczby operacji wykonywanych na jednym bajcie danych. Zwykle jest to stała dla określonego kodu.
Większość kodu wymagającego dużych obliczeń jest napisana długo, bardzo dobrze zoptymalizowana i istnieje duża liczba bibliotek, więc ma sens, jeśli widzisz w kodzie ciężkie obliczenia, poszukaj biblioteki, która może je wykonać za Ciebie.
Z pozostałych kompilatorów nie wiedzą, jak zrobić wszystko, ponieważ na ich rozwój przeznacza się bardzo ograniczony procent zasobów. Które z nich rozwijają się dziś mniej lub bardziej aktywnie, czyli wspierają standardy i starają się je przestrzegać? To jest frontend EDG, który jest używany w różnych pochodnych, na przykład kompilatorze Intela; LLVM; GNU i frontend Microsoft.
Ponieważ jest ich niewiele, kompilatory obsługują jedynie wzorce kontroli częstotliwości i zależności danych. Jeśli spojrzymy na sterowanie, to są to sekcje liniowe i proste cykle, czyli sekwencja instrukcji i powtórzeń. Uczą się zależności częstotliwościowych na danych z redukcji, kiedy, powiedzmy, sumujemy wiele elementów w jeden, zwijamy i wykonujemy działania element po elemencie na jednej lub większej liczbie tablic.
Co pozostaje deweloperom? Można to z grubsza podzielić na cztery części. Pierwsza to architektura aplikacji, kompilatory po prostu nie są w stanie nam tego wymyślić.
Równoległość jest również trudną rzeczą dla kompilatorów. Praca z pamięcią - bo to naprawdę trudne: trzeba wziąć pod uwagę architekturę, równoległość i to wszystko razem. Ponadto kompilatory nie wiedzą, jak prawidłowo ocenić jakość optymalizacji, jak szybko okazuje się, że kod. My, programiści, również musimy to zrobić, podjąć decyzję – kontynuować optymalizację lub przestać.
W części poświęconej architekturze przyjrzymy się amortyzacji napowietrznych połączeń wirtualnych, na których w wielu przypadkach opiera się architektura.
Pomińmy równoległość w równaniu. Jeśli chodzi o wykorzystanie pamięci: to także w pewnym sensie deprecjacja i poprawna praca z danymi, prawidłowe ich umieszczenie w pamięci. Jeśli chodzi o ocenę efektywności, porozmawiajmy o profilowaniu i o tym, jak szukać wąskich gardeł w kodzie.
Stosowanie interfejsów i abstrakcyjnych typów danych jest jedną z głównych metod projektowania. Rozważmy podobny kod obliczeniowy z uczenia maszynowego. Jest to kod warunkowy, który aktualizuje prognozę metodą gradientową.
Jeśli zajrzymy trochę do środka i spróbujemy zrozumieć, co się dzieje w środku, to mamy interfejs IDerCalcer do obliczania pochodnych funkcji straty oraz funkcję przesuwającą prognozę (naszą prognozę) zgodnie z gradientem funkcji straty.
Po prawej stronie slajdu widać, co to oznacza dla przypadku 10D. A w uczeniu maszynowym wielkość prognozy to nie dwa czy trzy, ale miliony, dziesiątki milionów elementów. Zobaczmy, jak dobry jest ten kod dla wektora składającego się z około XNUMX milionów elementów.
Przyjmijmy odchylenie standardowe jako funkcję celu i zmierzmy, jak to działa, jak bardzo przesunie tę prognozę. Na slajdzie pokazano pochodną tej funkcji celu. Czas działania na maszynie warunkowej, który następnie pozostaje stały, wynosi 40 ms.
Spróbujmy zrozumieć, co tu jest nie tak. Pierwszą rzeczą, która przyciąga uwagę, są wirtualne rozmowy. Jeśli spojrzysz na profiler, zobaczysz, że w zależności od liczby parametrów jest to około pięciu do dziesięciu instrukcji. A jeśli, tak jak w naszym przypadku, obliczenie samej pochodnej to tylko dwie operacje arytmetyczne, to łatwo może się to okazać znacznym narzutem. Dla dużego ciała przy obliczaniu pochodnych jest to ok. W przypadku krótkiego ciała, które oblicza pochodną – powiedzmy nawet nie 500 instrukcji, ale 20, 50 lub nawet mniej – będzie to już znaczny procent czasu. Co robić? Spróbujmy buforować wywołanie funkcji wirtualnej zmieniając interfejs.
Początkowo pochodne obliczaliśmy punkt po punkcie, dla każdego elementu wektora osobno. Przejdźmy od przetwarzania element po elemencie do przetwarzania za pomocą wektorów. Weźmy standardowy szablon C++, który pozwala pracować z widokiem na wektorze. Lub, jeśli Twój kompilator nie obsługuje najnowszego standardu, możesz użyć prostej, domowej roboty klasy, która przechowuje wskaźnik do danych i rozmiaru. Jak zmieni się kod? Pozostaje nam jedno wywołanie, które oblicza instrumenty pochodne, a następnie musimy dodać pętlę, która faktycznie zaktualizuje prognozę.
Oprócz dodania cyklu musimy jeszcze raz spojrzeć na dane, czyli przeczytać po raz drugi sam wektor prognozy i wektor gradientu, który właśnie obliczyliśmy.
Zmierzymy jeszcze raz na tej samej maszynie i zobaczymy co wyszło gorzej, coś poszło nie tak. Rozumiemy, co stało się z kodem.
Nie ma sensu podejrzewać czegoś o cykl, ponieważ jest to dokładnie ten sam wzorzec częstotliwości, który kompilatory dobrze rozpoznają i optymalizują. Liczba operacji na element danych będzie tam mniejsza niż koszt wirtualnego połączenia.
Ale utworzenie dużego wektora i przejście przez niego drugiego - w tym miejscu warto podejrzewać problem. Aby zrozumieć, dlaczego jest to złe i prowadzi do spowolnienia, musisz wyobrazić sobie, co dzieje się w pamięci, gdy uruchomiony jest kod, który widzimy na slajdzie po prawej stronie.
Kiedy obliczany jest wektor instrumentów pochodnych, dochodzi do cyklu, który przesuwa prognozę. Przed tym cyklem tylko bardzo mała część danych pozostanie w szybkiej pamięci podręcznej LXNUMX, która działa z częstotliwością procesora. Na zjeżdżalni jest zielone na światłach. Reszta danych zostanie wypchnięta z pamięci podręcznej do pamięci, a gdy pętla przejdzie do aktualizacji predykcji, dane będą musiały zostać odczytane z pamięci po raz drugi. I u nas to w ogóle działa bardzo powoli, z prędkością pieszego.
Aktualizując prognozę, nie musimy odczytywać wszystkich instrumentów pochodnych na raz. Wystarczy policzyć je w duże pakiety, aby wchłonąć wirtualne rozmowy. Dlatego też warto podzielić kalkulację instrumentów pochodnych i aktualizację prognozy na mniejsze bloki i połączyć te dwa działania. Do czego to doprowadzi, jeśli spojrzymy na to, skąd dane będą odczytywane?
Doprowadzi to do tego, że będziemy cały czas pobierać dane, a dane pozostaną w pamięci podręcznej L1 i nie będą miały czasu przejść do wolnej pamięci. A następnie musimy zrozumieć, kto powie nam ten rozmiar bloku.
Logiczne jest powierzenie samego kalkulatora pochodnych, ponieważ tylko on wie, ile pamięci podręcznej potrzebuje. Następnie musisz przepisać pętlę, w której przeglądaliśmy tablicę. Trzeba to podzielić na dwa. Zewnętrzna pętla przejdzie przez bloki, a wewnątrz dwukrotnie przejdziemy przez elementy bloku.
Tutaj jest, na zewnątrz, przy blokach.
A oto wewnętrzny element bloku.
Bierzemy pod uwagę, że ostatni blok może być niekompletny.
Zobaczmy, co z tego wyniknie. Widzimy, że poprawnie zgadliśmy, poprawnie zrozumieliśmy, co się dzieje, i kosztem niewielkich zmian w kodzie skróciliśmy czas pracy o osiem procent. Ale możemy zrobić jeszcze więcej. Musimy jeszcze raz krytycznie spojrzeć na to, co napisaliśmy. Spójrz na funkcję, która oblicza dla nas pochodne. Zwraca nam wektor pochodnych, do których dostęp w niesprzyjających sytuacjach będzie powolny.
Są dwa powody. Najpierw przydzielenie wektora na stercie. Są duże szanse, że wektor ten będzie wielokrotnie tworzony i niszczony. Drugi minus pod względem szybkości jest taki, że za każdym razem otrzymamy pamięć, prawdopodobnie pod nowym adresem. Pamięć ta będzie „zimna” z punktu widzenia pamięci podręcznej, czyli przed zapisem do niej procesor wykona odczyt pomocniczy w celu inicjacji danych w pamięci podręcznej.
Aby to naprawić, musisz usunąć alokację z pętli. Aby to zrobić, będziemy musieli ponownie zmienić interfejs, przestać zwracać wektory i zacząć zapisywać pochodne do pamięci, którą otrzymamy z kodu wywołującego.
Jest to standardowa technika - usunięcie wszelkich manipulacji zasobami z wąskich gardeł w kodzie obliczeniowym. Dodajmy jeszcze jeden parametr do metody CalcDer, spójrz na wektor, w którym powinny spaść pochodne.
Kod również ulegnie zmianie w oczywisty sposób. Wektor pochodnej będzie miał wartość jeden poza wszystkimi pętlami, a do metody zostanie po prostu dodany nowy parametr.
Patrzymy. Okazuje się, że w porównaniu z poprzednią wersją zdobyliśmy kolejne osiem procent, a w porównaniu z wersją bazową – już 15%.
Oczywiste jest, że optymalizacje nie ograniczają się do amortyzacji kosztów ogólnych, że istnieją inne rodzaje wąskich gardeł.
Aby zilustrować, jak szukać wąskich gardeł, potrzebujemy jeszcze jednego prostego kodu eksperymentalnego. Zająłem się na przykład transpozycją macierzy. Mamy macierz przybliżoną i macierz przybliżonąByCol, w której musimy umieścić transponowane dane. I proste gniazdo dwóch cykli. Nie ma tu żadnych wirtualnych wywołań do tworzenia wektorów. To tylko transfer danych. Pętla jest stosunkowo wygodna dla kompilatora.
Zmierzmy jak ten kod działa na odpowiednio dużej matrycy i na konkretnej maszynie.
Przykładowo przyjąłem liczbę wierszy 1000, liczbę kolumn 100 000. Maszyna to serwer Intel, jeden rdzeń. Pamięć taka właśnie jest, jest dla nas ważna, bo cała praca z pamięcią i szybkością będzie zależała od szybkości pamięci. Zmierzyliśmy i otrzymaliśmy 1,4 s. Czy to dużo czy mało? Co możemy zrobić w tym czasie?
Mamy czas na odczytanie 800 megabajtów, to nie jest matryca transponowana, a oryginalna. A także odczyt i zapis 1,6 GB, to już transponowana matryca. Procesor wykonuje pomocniczy odczyt przed zapisem, aby zainicjować dane w pamięci podręcznej.
Obliczmy, ile przepustowości wykorzystaliśmy z korzyścią. Okazuje się, że przepustowość naszego kodu wyniosła 1,7 GB/s.
To była kalkulacja teoretyczna. Wtedy można wziąć profiler, który będzie w stanie zmierzyć szybkość pracy z pamięcią. Wziąłem VTune'a. Zobaczmy, co pokazuje. Pokazuje podobną liczbę - 1,8 GB. W zasadzie to się zgadza, bo w naszych obliczeniach nie uwzględniliśmy tego, że musimy czytać adresy wierszy i adresy kolumn. Ponadto VTune rejestruje aktywność w tle w systemie operacyjnym. Dlatego nasz model jest zgodny z rzeczywistością.
Aby zrozumieć, czy 1,7 GB to dużo, czy mało, trzeba dowiedzieć się, jaka maksymalna przepustowość jest dla nas dostępna.
Aby to zrobić, musisz przeczytać specyfikację procesora. Istnieje specjalna strona ark.intel.com, na której można dowiedzieć się wszystkiego o dowolnym procesorze. Jeśli przyjrzymy się konkretnie naszemu serwerowi, zobaczymy, że ma on osiem rdzeni i dla najszybszej obsługiwanej przez niego pamięci DDR3, transferuje z prędkością około 60 GB/s w jedną stronę.
Ale tutaj musimy wziąć pod uwagę, że używamy tylko jednego rdzenia i nasza pamięć jest wolniejsza, czyli musimy skalować te 60 GB do naszych warunków proporcjonalnie do liczby rdzeni i częstotliwości pamięci.
Okazuje się, że nasz kod mógłby wykorzystać w jedną stronę 5,3 GB. A ponieważ można czytać i pisać równolegle, to idealnie, gdybyśmy po prostu kopiowali dane z miejsca na miejsce, osiągnęlibyśmy 10,6. Skoro mamy dwa odczyty i jeden zapis to powinno wynosić około 8 GB/s. Pamiętamy, że dostaliśmy 1,7. Oznacza to, że zużyliśmy około 20%.
Dlaczego tak jest? Znów trzeba zająć się architekturą. Faktem jest, że dane między pamięcią a pamięcią podręczną nie są przesyłane w dowolnych pakietach, ale dokładnie w 64 bajtach, nie więcej, nie mniej. To jest pierwsza refleksja.
Drugą kwestią jest to, że transponowane dane zapisujemy nie sekwencyjnie, ale losowo, ponieważ wiersze macierzy są umiejscowione w pamięci w nieprzewidywalny sposób.
Okazuje się, że przed zapisaniem jednej liczby rzeczywistej musimy odjąć 64 bajty danych. Jeżeli oznaczymy wielkość macierzy N, to zamiast optymalnego czasu działania (N/5,3 + N/10,6) otrzymamy (8*N/5,3 + N/10,6). Gdzieś cztery do pięciu razy więcej, co wyjaśnia tę wydajność na poziomie 20%.
Co z tym zrobić? Musisz przestać zapisywać dane w jednej kolumnie i zacząć zapisywać tyle kolumn, ile zmieści się w jednej linii pamięci podręcznej (64 bajty). Aby to zrobić, dzielimy cykl po kolumnach na cykl po liniach pamięci podręcznej i zagnieżdżoną pętlę po elementach linii pamięci podręcznej.
Oto one, iteracje po liniach pamięci podręcznej.
A oto iteracje wewnątrz linii pamięci podręcznej. Tutaj dla uproszczenia zakładamy, że dane są wyrównane do granicy linii pamięci podręcznej. Teraz sprawdźmy za pomocą VTune, co się stanie.
Widzimy, co się stało w pobliżu obliczonych ośmiu gigabajtów na sekundę – 7,6. Ale nie jest jeszcze faktem, że wszystkie te 7,6 są pożyteczną pracą. Być może niektóre z nich są nad głową.
Aby zrozumieć, jakie korzyści uzyskaliśmy, zmierzmy czas działania po optymalizacji. Okazuje się, że na tej samej maszynie 0,5 s. Przepustowość, która wynika z samej transpozycji, wyniosła 4,8 GB/s. Widać, że jest jeszcze margines, którego nie wybraliśmy, ale i tak z 20-procentowej efektywności dostaliśmy 60 proc.
Za pomocą profilera możesz dowiedzieć się, dlaczego nie uzyskaliśmy 80% lub 95%.
Faktem jest, że macierze przechowujemy jako wektor wektorów, czyli korzystamy z dostępu do pamięci z podwójnym pośrednim.
Dzięki VTune możesz zobaczyć, które instrukcje są generowane w celu uzyskania dostępu do elementów tablicy. Instrukcje odejmujące adresy kolumn transponowanej macierzy są podświetlone na żółto po lewej stronie. A są to po pierwsze dodatkowe instrukcje, a po drugie dodatkowe transfery danych. Ale nie będziemy dalej optymalizować, zatrzymamy się i podsumujemy.
Co ci dzisiaj powiedziałem? Przydatną wskazówką do pracy z kodem obliczeniowym jest przetwarzanie blokowe, aby amortyzować koszty ogólne, które są związane na przykład z połączeniami wirtualnymi. Dodatkowo dzięki blokowaniu poprawia się lokalizacja danych i uzyskujemy większą prędkość dostępu.
Usunięcie alokacji z wąskich gardeł oznacza jednocześnie ich amortyzację. A także zwiększenie szybkości dostępu poprzez naprawienie tymczasowych buforów w pamięci.
O profilowaniu. Po pierwsze, profilowanie jest użyteczną techniką znajdowania wąskich gardeł „w ogólnym przypadku”. Po drugie, pozwala nam ocenić wydajność kodu, zdecydować, czy jesteśmy zadowoleni z szybkości, czy też chcemy dalej optymalizować, i pokazuje, w którym kierunku zmierzać.
To wszystko dla mnie. Jeśli korzystasz z CatBoost lub słyszysz o nim po raz pierwszy i chcesz wiedzieć, co to jest, przeczytaj przyjdź do nas na , Napisz do . Dziękuję bardzo za uwagę.
Źródło: www.habr.com
