Jak dokumentować i uczyć innych „zoptymalizowanych nie do poznania” intensywnych obliczeniowo kodów?

11

Czasami jest 1% kodu, który jest wystarczająco intensywny obliczeniowo, co wymaga najcięższego rodzaju optymalizacji niskiego poziomu. Przykładami są przetwarzanie wideo, przetwarzanie obrazu i ogólnie wszelkiego rodzaju przetwarzanie sygnału.

Celem jest udokumentowanie i nauczenie technik optymalizacji, aby kod nie stał się nieusuwalny i podatny na usuwanie przez nowych programistów. (*)

(*) Niezależnie od możliwości, że określona optymalizacja jest całkowicie bezużyteczna w niektórych nieprzewidywalnych przyszłych procesorach, tak że kod i tak zostanie usunięty.

Biorąc pod uwagę, że oferty oprogramowania (komercyjne lub open-source) zachowują swoją przewagę konkurencyjną dzięki najszybszemu kodowi i wykorzystaniu najnowszej architektury procesorów, twórcy oprogramowania często muszą dostosowywać swój kod, aby działał szybciej, a jednocześnie uzyskiwał te same wyniki zadanie, lista toleruje niewielką liczbę błędów zaokrąglania.

Zazwyczaj programista może przechowywać wiele wersji funkcji jako dokumentację każdej optymalizacji / zmiany algorytmu, która ma miejsce. W jaki sposób udostępnia się te wersje innym osobom w celu zbadania ich technik optymalizacji?

Związane z:

rwong
źródło
1
Możesz po prostu zachować różne wersje kodu, skomentowane, z dużą ilością komentarzy mówiących czytelnikowi, co się dzieje.
Mike Dunlavey,
1
I nie mów im tylko, co robi kod, ale dlaczego jest w ten sposób szybszy. W razie potrzeby dołącz linki do algorytmów, własnych, typu wiki, dokumentów lub zasobów dostępnych w Internecie (w takim przypadku pamiętaj o linku do rotacji, może być rozsądne skopiowanie go do własnego systemu dokumentów z linkiem do oryginału .)
Marjan Venema
1
@MikeDunlavey: Ała, proszę nie komentować go. Wystarczy kilka implementacji tej samej funkcji i wywołać tę, która jest najszybsza. W ten sposób możesz łatwo przejść do innej wersji kodu i przetestować je wszystkie.
sleske
2
@sleske Czasami posiadanie większej ilości kodu binarnego może go spowolnić.
quant_dev
@quant_dev: Tak, to może się zdarzyć. Po prostu uważam, że ważne jest, aby kod był budowany i uruchamiany (najlepiej) regularnie, aby był aktualny. Być może zbuduj go tylko w trybie debugowania.
śleske,

Odpowiedzi:

10

Krótka odpowiedź

Zachowaj lokalne optymalizacje, spraw, aby były oczywiste, dobrze dokumentuj i ułatwiaj porównywanie zoptymalizowanych wersji ze sobą oraz z niezoptymalizowaną wersją, zarówno pod względem kodu źródłowego, jak i wydajności w czasie wykonywania.

Pełna odpowiedź

Jeśli takie optymalizacje naprawdę ważne dla Twojego produktu, musisz wiedzieć nie tylko, dlaczego optymalizacje były wcześniej przydatne, ale także dostarczyć wystarczających informacji, aby pomóc programistom dowiedzieć się, czy będą one przydatne w przyszłości.

Idealnie, musisz zapisać testy wydajności w procesie kompilacji, aby dowiedzieć się, kiedy nowe technologie unieważniają stare optymalizacje.

Zapamiętaj:

Pierwsza zasada optymalizacji programu: nie rób tego.

Druga zasada optymalizacji programu (tylko dla ekspertów!): Nie rób tego jeszcze. ”

- Michael A. Jackson

Aby wiedzieć, czy nadszedł czas, należy przeprowadzić testy porównawcze i testy.

Jak wspomniałeś, największym problemem związanym z wysoce zoptymalizowanym kodem jest to, że trudno go utrzymać, więc w miarę możliwości musisz trzymać zoptymalizowane części oddzielnie od niezoptymalizowanych części. Niezależnie od tego, czy robisz to przez łączenie czasu kompilacji, wywołania funkcji wirtualnych środowiska wykonawczego, czy coś pośredniego, nie powinno to mieć znaczenia. Co powinno mieć znaczenie, że po uruchomieniu testów chcesz mieć możliwość testowania wszystkich wersji, którymi jesteś obecnie zainteresowany.

Byłbym skłonny zbudować system w taki sposób, że podstawowa niezoptymalizowana wersja kodu produkcyjnego mogłaby zawsze zostać wykorzystana do zrozumienia zamiaru kodu, a następnie zbudować różne zoptymalizowane moduły wraz z tym zawierającym zoptymalizowaną wersję lub wersje, wyraźnie dokumentując gdziekolwiek wersja zoptymalizowana różni się od linii podstawowej. Po uruchomieniu testów (jednostkowych i integracyjnych) uruchamia się go w niezoptymalizowanej wersji i na wszystkich aktualnie zoptymalizowanych modułach.

Przykład

Załóżmy na przykład, że masz funkcję szybkiej transformacji Fouriera . Być może masz podstawową, algorytmiczną implementację fft.ci testy w fft_tests.c.

Potem pojawia się Pentium i decydujesz się na implementację wersji z punktem stałym fft_mmx.cprzy użyciu instrukcji MMX . Później pentium 3 przyjdzie i zdecydować, aby dodać wersję, która używa Streaming SIMD Extensions w fft_sse.c.

Teraz chcesz dodać CUDA , więc dodajesz fft_cuda.c, ale przekonaj się, że dzięki testowemu zestawowi danych, którego używasz od lat, wersja CUDA jest wolniejsza niż wersja SSE! Przeprowadzasz analizę i dodajesz zestaw danych, który jest 100 razy większy, i otrzymujesz przyspieszenie, którego oczekujesz, ale teraz wiesz, że czas przygotowania do użycia wersji CUDA jest znaczący i że w przypadku małych zestawów danych powinieneś użyć algorytm bez tego kosztu konfiguracji.

W każdym z tych przypadków implementujesz ten sam algorytm, wszystkie powinny zachowywać się w ten sam sposób, ale będą działać z różnymi wydajnościami i prędkościami na różnych architekturach (jeśli w ogóle będą działać). Jednak z punktu widzenia kodu możesz porównać dowolną parę plików źródłowych, aby dowiedzieć się, dlaczego ten sam interfejs jest implementowany na różne sposoby i zwykle najłatwiej będzie odnieść się do oryginalnej niezoptymalizowanej wersji.

To samo dotyczy implementacji OOP, w której klasa bazowa, która implementuje niezoptymalizowany algorytm, oraz klasy pochodne implementują różne optymalizacje.

Ważne jest, aby zachować te same rzeczy, które są takie same , aby różnice były oczywiste .

Mark Booth
źródło
7

W szczególności, skoro wzięto przykład przetwarzania wideo i obrazu, można zachować kod jako część tej samej wersji, ale aktywny lub nieaktywny w zależności od kontekstu.

Chociaż nie wspomniałeś, zakładam Ctutaj.

Najprostszym sposobem w Ckodzie jest optymalizacja (i ma to również zastosowanie przy próbie uczynienia rzeczy przenośnymi), którą należy zachować

 
#ifdef OPTIMIZATION_XYZ_ENABLE 
   // your optimzied code here... 
#else  
   // your basic code here...

Po włączeniu #define OPTIMIZATION_XYZ_ENABLEpodczas kompilacji w Makefile wszystko działa odpowiednio.

Zwykle wycięcie kilku wierszy kodu w środku funkcji może stać się nieporządne, gdy zoptymalizowanych jest zbyt wiele funkcji. Dlatego w tym przypadku definiuje się różne wskaźniki funkcji w celu wykonania określonej funkcji.

główny kod zawsze wykonuje się za pomocą wskaźnika funkcji takiego jak


   codec->computed_idct(blocks); 

Ale wskaźniki funkcji są zdefiniowane w zależności od rodzaju przykładu (np. Tutaj funkcja idct jest zoptymalizowana dla różnych architektur CPU.



if(OPTIMIZE_X86) {
  codec->computed_idct = compute_idct_x86; 
}
else if(OPTIMZE_ARM) {
  codec->computed_idct = compute_idct_ARM;
}
else {
  codec->computed_idct = compute_idct_C; 
}

powinieneś zobaczyć kod libjpeg i kod libmpeg2 i być może ffmpeg dla takich technik.

Dipan Mehta
źródło
6

Jako badacz kończę pisać kod „wąskiego gardła”. Jednak po wdrożeniu do produkcji ciężar jego integracji z produktem i zapewnienia późniejszego wsparcia spoczywa na programistach. Jak możesz sobie wyobrazić, niezwykle ważne jest jasne przekazanie informacji o tym, co i jak program ma działać.

Przekonałem się, że trzy kroki do pomyślnego ukończenia tego kroku są trzy

  1. Zastosowany algorytm musi być absolutnie jasny.
  2. Cel każdej linii wdrożenia musi być jasny.
  3. Odchylenia od oczekiwanych wyników należy zidentyfikować jak najszybciej.

W pierwszym kroku zawsze piszę krótki oficjalny dokument, który dokumentuje algorytm. Celem jest napisanie go tak, aby inna osoba mogła go wdrożyć od zera przy użyciu wyłącznie białej księgi. Jeśli jest to dobrze znany, opublikowany algorytm, wystarczy podać odniesienia i powtórzyć kluczowe równania. Jeśli jest to oryginalna praca, będziesz musiał być bardziej wyraźny. Dzięki temu dowiesz się, co powinien zrobić kod .

Rzeczywista implementacja przekazana do programowania musi być udokumentowana w taki sposób, aby wszystkie subtelności były jawne. Jeśli uzyskasz blokady w określonej kolejności, aby uniknąć zakleszczenia, dodaj komentarz. Jeśli iterujesz po kolumnach zamiast nad wierszami macierzy z powodu problemów ze spójnością pamięci podręcznej, dodaj komentarz. Jeśli zrobisz coś choć odrobinę sprytnego, skomentuj to. Jeśli możesz zagwarantować oficjalny dokument, a kod nigdy nie zostanie rozdzielony (za pomocą VCS lub podobnego systemu), możesz powrócić do oficjalnego dokumentu. Wynik może być łatwo ponad 50% komentarzem. Jest w porządku. Dzięki temu dowiesz się, dlaczego kod robi to, co robi.

Wreszcie, musisz być w stanie zagwarantować poprawność w obliczu zmian. Na szczęście jesteśmy przydatnym narzędziem w automatycznych testach i platformach ciągłej integracji . Dzięki temu dowiesz się, co faktycznie robi kod .

Moim najserdeczniejszym zaleceniem byłoby nie skąpić na żadnym z kroków. Będziesz ich później potrzebować;)

drxzcl
źródło
Dziękujemy za wyczerpującą odpowiedź. Zgadzam się ze wszystkimi twoimi punktami. Pod względem zautomatyzowanego testowania uważam, że odpowiednie pokrycie zakresu liczbowego arytmetyki stałoprzecinkowej i kodu SIMD jest trudne, coś, co spaliłem dwukrotnie. Warunki wstępne podane tylko w komentarzach (bez kodu do wzmocnienia) nie zawsze były spełnione.
rwong
Powodem, dla którego jeszcze nie zaakceptowałem twojej odpowiedzi, jest to, że potrzebuję więcej wskazówek na temat tego, co oznacza „krótki oficjalny dokument” i jaki wysiłek należy włożyć w jego opracowanie. W niektórych branżach jest to część głównej linii biznesowej, ale w innych branżach należy wziąć pod uwagę koszty i zastosować legalnie dostępne skróty.
rwong
Przede wszystkim odczuwam twój ból związany z automatycznymi testami, arytmetyką zmiennoprzecinkową i kodem równoległym. Obawiam się, że nie ma rozwiązania, które byłoby ważne we wszystkich przypadkach. Zwykle pracuję z dość liberalnymi tolerancjami, ale w twojej branży może to nie być możliwe.
drxzcl
2
W praktyce biała księga często przypomina pierwszy szkic artykułu naukowego, bez fragmentów „puchu” (bez sensownego wprowadzenia, bez streszczenia, minimalnych wniosków / dyskusji i tylko odniesienia niezbędne do zrozumienia). Widzę pisanie pracy jako raportu i integralnej części rozwoju algorytmu i / lub wyboru algorytmu. Wybrałeś implementację tego algorytmu (powiedzmy spektralną FFT). Co to właściwie jest? Dlaczego wybrałeś ten spośród innych? Jakie są jego cechy paralelizacji? Wysiłek powinien być proporcjonalny do prac związanych z selekcją / rozwojem.
drxzcl
5

Uważam, że najlepiej to rozwiązać poprzez kompleksowe komentowanie kodu, do tego stopnia, że ​​każdy znaczący blok kodu ma wcześniej komentarz wyjaśniający.

Komentarze powinny zawierać cytowania specyfikacji lub materiały odniesienia do sprzętu.

W stosownych przypadkach używaj terminologii i nazw algorytmów dla całej branży - np. „Architektura X generuje pułapki procesora dla nie wyrównanych odczytów, więc urządzenie Duffa wypełnia się do następnej granicy wyrównania”.

Używałbym nazewnictwa zmiennych w twojej twarzy, aby uniknąć nieporozumień o tym, co się dzieje. Nie węgierski, ale rzeczy takie jak „krok”, aby opisać odległość w bajtach między dwoma pionowymi pikselami.

Uzupełniałbym to również krótkim, czytelnym dla człowieka dokumentem, który ma schematy wysokiego poziomu i układ bloków.

JBRWilkinson
źródło
1
Pomocne byłoby zastosowanie jednej spójnej terminologii dla jednej rzeczy (np. Użycie „kroku” w odniesieniu do podobnych znaczeń, np. „Krok”, „wyrównanie”) w tym samym projekcie. Jest to nieco trudne, gdy integruje się bazę kodu kilku projektów w jednym projekcie.
rwong 24.11.11