20% spadek wydajności za ładny projekt oprogramowania

17

Piszę małą bibliotekę do rzadkich obliczeń macierzowych, aby nauczyć się jak najlepiej korzystać z programowania obiektowego. Bardzo ciężko pracowałem nad stworzeniem ładnego modelu obiektowego, w którym części (rzadkie macierze i wykresy opisujące ich strukturę połączeń) są bardzo luźno połączone. Moim zdaniem kod jest znacznie bardziej rozszerzalny i łatwiejszy w utrzymaniu.

Jest to jednak nieco wolniejsze niż w przypadku zastosowania tępego podejścia. Aby przetestować kompromisy związane z posiadaniem tego modelu obiektowego, napisałem nowy rzadki typ matrycy, który przerwał enkapsulację podstawowego wykresu, aby zobaczyć, o ile szybciej by to działało.

Z początku wyglądało to dość ponuro; kod, z którego byłem kiedyś dumny, działał o 60% wolniej niż wersja bez eleganckiego oprogramowania. Ale byłem w stanie dokonać kilku optymalizacji na niskim poziomie - wprowadzając funkcję i zmieniając trochę pętlę - bez zmiany API. Dzięki tym zmianom jest teraz tylko 20% wolniejszy niż u konkurencji.

Co prowadzi mnie do pytania: ile strat wydajności powinienem zaakceptować, jeśli oznacza to, że mam ładny model obiektowy?

linear-algebra sparse-matrix oop

— Daniel Shapero
źródło

Którą operację macierzy rzadkich mierzysz?

— Bill Barth

Mnożenie wektor-macierz. Rozmiar macierzy wahał się od

n = 1024, . . ., 16384

$n = 1024,...,16384$ . Zrobiłem im wykres Laplaciana dla losowych wykresów Erdosa-Renyi ze średnim stopniem

d = \log_{2} n

$d = \log_2n$ . Ponadto liczba 20% pogarsza się na niektórych maszynach, więc teraz jestem bardziej skłonny do wyrzucenia tego wszystkiego. Głębokie westchnienie

— Daniel Shapero

3

Jakiego języka programowania używasz? Zazwyczaj coś takiego jak C ++ pozwoli ci uciec od eleganckich (ish) wzorów przy niskim (lub nieistniejącym) koszcie. W innych językach bez metaprogramowania (Java, Fortran itp.) Uzasadniony wydaje się koszt 20%.

— LKlevin

Czy możesz pokazać nam swój kod? Jakiego języka używałeś? Jakie flagi kompilatora i kompilacji? Czy znalazłeś dokładnie, skąd pochodzi przebój? Jak upewniłeś się, że znalazłeś właściwy powód? Z jakiego profilera korzystałeś i jak go używałeś? Czy jesteś pewien, że ładny model obiektowy nie został wdrożony nieefektywnie? 20% jest wystarczająco małe, że musisz zebrać dużo danych i przeprowadzić szczegółową analizę, zanim powiesz, że jest to zdecydowanie spowodowane projektem, a nie, powiedzmy, gorszą implementacją lub innymi problemami z kodowaniem.

— Kirill

Krótka uwaga: wszyscy wydają się publicznie chwalić dobry design nad czystą wydajnością (oczywiście z bardzo ważnych powodów). Ale dlaczego tak dużo kodu świata rzeczywistego jest naprawdę nie do utrzymania? Czy wszystkie dziwki kodu czują się winne, a zatem publicznie milczą?

— AlexE,

9

Bardzo niewielu twórców oprogramowania naukowego rozumie dobre zasady projektowania, więc przepraszam, jeśli ta odpowiedź jest nieco długa. Z punktu widzenia inżynierii oprogramowania celem naukowego twórcy oprogramowania jest zaprojektowanie rozwiązania, które spełnia zestaw ograniczeń, które często są ze sobą sprzeczne .

Oto kilka typowych przykładów tych ograniczeń, które można zastosować do projektu biblioteki rzadkich macierzy:

Ukończone w jeden miesiąc
Działa poprawnie na twoim laptopie i kilku stacjach roboczych
Działa wydajnie

Naukowcy stopniowo zwracają większą uwagę na inne wspólne wymagania inżynierii oprogramowania:

Dokumentacja (instrukcja obsługi, samouczek, komentowanie kodu)
Konserwowalność (kontrola wersji, testowanie, konstrukcja modułowa)
Wielokrotnego użytku (budowa modułowa, „elastyczność”)

Możesz potrzebować mniej więcej jednego z tych wymagań. Jeśli próbujesz wygrać nagrodę Gordona Bella za wydajność, nawet ułamki procent są istotne, a niewielu sędziów ocenia jakość twojego kodu (o ile tylko możesz przekonać ich, że ma rację). Jeśli próbujesz uzasadnić uruchomienie tego kodu na współdzielonym zasobie, takim jak klaster lub superkomputer, często musisz bronić twierdzeń dotyczących wydajności kodu, ale rzadko są one bardzo rygorystyczne. Jeśli próbujesz opublikować artykuł w czasopiśmie opisujący wzrost wydajności swojego podejścia, musisz być prawowitym szybszy niż konkurenci, a 20% wydajności to kompromis, który z przyjemnością zapewniłbym lepszą konserwację i możliwość ponownego użycia.

Wracając do pytania: „dobry projekt”, który ma wystarczająco dużo czasu na opracowanie, nigdy nie powinien poświęcać wydajności. Jeśli celem jest, aby kod działał tak szybko, jak to możliwe, kod powinien być zaprojektowany w oparciu o te ograniczenia. Możesz skorzystać z takich technik, jak generowanie kodu, asembler lub skorzystaj z dobrze dostrojonych bibliotek, które pomogą Ci rozwiązać problem.

Ale co, jeśli nie masz wystarczająco dużo czasu na rozwój? Co jest wystarczająco dobre? Cóż, to zależy i nikt nie będzie w stanie udzielić ci dobrej odpowiedzi na to pytanie bez większego kontekstu.

FWIW: Jeśli naprawdę interesuje Cię pisanie wysokowydajnych rzadkich jąder matrycowych, powinieneś porównać się ze zoptymalizowaną instalacją PETSc i współpracować z ich zespołem, jeśli ich pokonujesz, chętnie wprowadzą dostrojone jądra do biblioteki.

— Aron Ahmadia
źródło

Ciekawi mnie generatory kodów - myślę, że mogą być dla mnie przydatne, ale obawiam się, że będą trudne do utrzymania. Wiem, że programiści Java często ich używają, ale często są dostosowani do generowania kodu dla określonych aplikacji. Czy znasz jakieś kody naukowe, które ich używają?

— Daniel Shapero

ATLAS, FFTW, Spiral, OSKI, Ignition, stencil_codegen, aby wymienić kilka. Nie jest to publicznie reklamowane, ale nie zdziwiłbym się, gdyby kilka ważnych jąder w MKL i ESSL zostało wygenerowanych w ten sposób. Ciekawym pytaniem byłoby napisanie łatwego do utrzymania kodu generowania jądra. Mam w tym doświadczenie, ale nie uważałbym się za autorytet.

— Aron Ahmadia

12

To pytanie, na co spędzasz czas. Dla większości z nas spędzamy 3/4 czasu na programowaniu i 1/4 czasu na oczekiwaniu na wyniki. (Twoje liczby mogą się różnić, ale myślę, że liczba nie jest całkowicie pozbawiona zalet.) Jeśli więc masz projekt, który pozwala ci zaprogramować dwa razy szybciej (3/4 jednostki czasu zamiast 1,5 jednostki czasu), to może wytrzymać 300% wydajności (od 1/4 do 1 jednostki czasu), a ty nadal masz przewagę, jeśli chodzi o czas spędzony na rozwiązaniu problemu.

Z drugiej strony, jeśli wykonujesz ciężkie obliczenia, twoje obliczenia mogą wyglądać inaczej i możesz poświęcić więcej czasu na optymalizację kodu.

Dla mnie 20% wydaje się dość dobrym kompromisem, jeśli w końcu będziesz bardziej produktywny.

— Wolfgang Bangerth
źródło

Dobra odpowiedź, dodam też znaczenie, gdy liczy się wydajność. Dany kod naukowy nie dokonuje wyłącznie mnożenia macierzy; jeśli 20% twojego środowiska wykonawczego zwielokrotnia macierz, to 20% trafienie w wydajność oznacza ogólnie tylko 4% różnicę, i chętnie wezmę to w zamian za łatwiejszą w użyciu bibliotekę.

— Aurelius

1

A lepiej napisana biblioteka oznacza mniej błędów, dzięki czemu masz mniej czasu na oczekiwanie na nieprawidłowe wyniki.

— Davidmh

4

IMHO kara do 50% (z jakiegokolwiek powodu) nie jest taka zła.

W rzeczywistości widziałem różnicę wydajności 0-30% w zależności od rodzaju kompilatora. Dotyczy to rzadkiej procedury PETMc MatMult dotyczącej matryc wynikającej z dyskretyzacji FE niskiego rzędu.

— stali
źródło

1

Projekt oprogramowania nie poprawi się automatycznie w miarę upływu czasu. Spektakl będzie. Otrzymasz 20% z powrotem przy następnym procesorze. Poza tym dobry projekt oprogramowania ułatwi rozbudowę lub ulepszenie biblioteki w przyszłości.

— MirekE
źródło

Nie sądzę, że to odpowiada na pytanie.

— nicoguaro

0

Ogólną zasadą jest, aby najpierw wybrać dobry projekt, a następnie zoptymalizować wydajność tylko w razie potrzeby . Przypadki użycia, w których naprawdę potrzebny jest wzrost wydajności o 20%, są raczej rzadkie, jeśli w ogóle się pojawią.

— Jolvi
źródło