Nauka optymalizacji z asemblerem [zamknięte]

Jestem studentem drugiego roku technologii gier komputerowych. Niedawno ukończyłem swój pierwszy prototyp mojego „rodzaju” własnego pathfindera (który nie używa A * zamiast geometrycznego podejścia / rozpoznawania wzorców, pathfinder potrzebuje jedynie wiedzy o terenie, który jest jego zdaniem do podejmowania decyzji, ponieważ ja chciałem sztucznej inteligencji, która mogłaby faktycznie eksplorować, jeśli teren jest już znany, wtedy będzie mógł przejść najkrótszą drogą, ponieważ pathfinder ma pamięć węzłów).

W każdym razie moje pytanie jest bardziej ogólne: jak rozpocząć optymalizację algorytmów / pętli / for_each / etc. za pomocą zestawu, choć ogólne wskazówki są mile widziane. Szczególnie szukam dobrych książek, ponieważ naprawdę trudno jest znaleźć dobre książki na ten temat. Istnieje kilka małych artykułów, takich jak ten , ale wciąż nie ma wystarczającej wiedzy, aby zoptymalizować algorytm / grę ...

Mam nadzieję, że jest tam nowoczesna dobra książka, której po prostu nie mogłam znaleźć ...

Będę tu przeciwnikiem i powiem, że nigdy nie jest za wcześnie, aby uczyć się o optymalizacjach, szczególnie o optymalizacji złożenia i, co ważniejsze, debugowaniu w asemblerze. Wierzę, że uzyskasz maksymalne korzyści z tego, jeśli jesteś studentem (ponieważ wtedy masz bardzo mało do stracenia [tj. Pod względem czasu / pieniędzy]) i wszystkiego, co możesz zyskać.

Jeśli pracujesz w branży i nie musisz majstrować przy montażu, to nie rób tego. W przeciwnym razie, jeśli jesteś studentem lub ogólnie masz czas, znajdę czas na naukę deasemblacji programów i zobaczę, czy mogę wymyślić lepsze rozwiązanie niż kompilator. Jeśli nie mogę, kogo to obchodzi! Właśnie nauczyłem się pisać, a także kompilator i jest to OGROMNY plus, gdy masz do czynienia z błędem w kodzie wydania (bez symboli debugowania) i wpatrujesz się w dezasemblację, ponieważ to jedyna rzecz, na którą możesz patrzeć.

Odpowiedź

Jest to jeden z najlepszych zasobów, jaki znalazłem, aby dowiedzieć się o optymalizacji.

http://www.agner.org/optimize/

Rant

Jeśli czytasz niektóre artykuły głównych programistów (na przykład, rozumowanie stojące za tworzeniem EASTL i dokładniejsza kontrola kodu doprowadzi cię do takich komentarzy, jak to zrobiono, ponieważ GCC jest okropny w wstawianiu tej instrukcji if, która powie ci, co większość ludzie mówią, że ufasz, że kompilator nie zawsze ma rację, W SZCZEGÓLNOŚCI w tworzeniu gier), a następnie postawiłeś stopę w branży, przekonasz się, że optymalizacje są codziennością, a wiedza o tym, co oznacza wynik montażu, jest dużym plusem. Ponadto ludzie nie zdają sobie sprawy (szczególnie przy przepływie stosów), że profilowanie gier jest bardzo trudne i nie zawsze dokładne.

Jest jednak zastrzeżenie. Możesz poświęcić czas na optymalizację czegoś, a później uświadomić sobie, że to był czas stracony. Ale czego się nauczyłeś? Nauczyłeś się nie powtarzać tego samego błędu w podobnych okolicznościach.

To, co teraz przyjmuje SO, to moim zdaniem postawa religijna w stosunku do oświadczenia, które nie jest optymalizowane, dopóki nie profilujesz i nie martw się, kompilator wie lepiej niż ty . Utrudnia naukę. Znam ekspertów w branży, którym wypłacane są bardzo dobre pieniądze (i mam na myśli BARDZO dobre pieniądze), aby bawić się w asemblerze, aby zoptymalizować grę i debugować ją, ponieważ kompilator jest zły lub po prostu nie może ci pomóc, ponieważ, no cóż, to nie może (awarie związane z GPU, awarie, w których danych nie można odczytać w debuggerze itp.)!

Co jeśli ktoś, kto uwielbia to robić, nie zdaje sobie jeszcze z tego sprawy, zadaje pytanie tutaj i jest wyłączony / wyłączony przez kompilator wielu odpowiedzi, który zna lepiej niż ty! i nigdy nie staje się jednym z tych wysoko opłacanych programistów?

Ostatnia myśl. Jeśli zaczniesz robić to wcześnie, przekonasz się, że wkrótce zaczniesz pisać kod, który jest najgorszy, nie ma żadnej poprawy wydajności, ponieważ kompilator zoptymalizował go w ten sam sposób lub w najlepszym razie, ma pewne ulepszenia wydajności, ponieważ teraz kompilator może go zoptymalizować . W obu przypadkach stało się to nawykiem, a pisanie kodu w ten sposób jest wolniejsze niż wcześniej. Oto kilka przykładów (jest ich o wiele więcej):

1. Wstępna inkrementacja, chyba że naprawdę chcesz dodatkowej inkrementacji
2. Zapisywanie pętli dla kontenerów przy użyciu stałej zmiennej lokalnego rozmiaru zamiast wywoływania size () na kontenerze w pętli.

EDYCJA: Aktualizacja po 8 latach w branży. Naucz się montażu. Dowiedz się, jak działają optymalizatory i generowany przez nie zespół (CompilerExplorer jest do tego doskonałym narzędziem). Natknąłem się na niezliczone awarie w kompilacjach testowych (kompilacje zoptymalizowane do testowania wewnętrznego), w których nie można polegać na debuggerze nawet przy symbolach debugowania. Kompilator zoptymalizował zbyt wiele rzeczy, a zespół jest twoim jedynym źródłem cennych informacji, aby znaleźć błąd z zrzutu awaryjnego. Każda kompilacja zajmuje 30-40 minut, jeśli masz szczęście i najpierw w kolejce kompilacji - więc nie możesz polegać na tradycyjnych technikach izolowania błędu. Tryb wieloosobowy pogarsza sytuację. Znajomość montażu i sposób czytania zoptymalizowanego zestawu sprawi, że będziesz lepszy i ostatecznie bardziej wartościowy dla zespołu.

Pierwszą wskazówką, jaką dostaniesz, jest: nie.

Współczesne kompilatory są naprawdę bardzo dobre w optymalizacji kodu i będą o wiele bardziej prawdopodobne, że zrobią to lepiej niż jakikolwiek samodzielnie napisany język asemblera.

Wyjątkiem byłby każdy konkretny przypadek, w którym ustalono na pewno, że kompilator źle wykonuje optymalizację, więc to druga wskazówka. Nie ma tu ogólnych wskazówek, musisz znać swój własny kod, wiedzieć, co on robi, być w stanie wskoczyć do jego demontażu i być w stanie absolutnie upewnić się, że kompilator robi złą robotę.

Nawet w tym przypadku nadal możesz nie chcieć. Musisz mieć pewność, że nie będzie dla ciebie żadnych bieżących kosztów utrzymania. Możesz wrócić do tego kodu za 6 miesięcy i zmodyfikować jego część, lub możesz znaleźć bardzo subtelny błąd, który będzie trudniejszy do naprawienia w asemblerze. Nawet jeśli myślisz, że udało Ci się rozwiązać wszystkie błędy, kiedy twój program przejdzie do błędów publicznych, o których nawet nie pomyślałeś, że to się stanie, stanie się dla Ciebie rzeczywistością. To naprawdę przyciąga wzrok (i upokarzające doświadczenie).

I nawet jeśli z przyjemnością to zaakceptujesz, może się okazać, że nie ma absolutnie żadnej wymiernej poprawy wydajności, ponieważ twoje główne wąskie gardło może być zupełnie inne w twoim programie. To znów sprowadza mnie do numeru 1. Nie rób

Zwykle solidna optymalizacja nie zależy od użycia asemblera lub robienia mikrooptymalizacji z kodem w językach wyższego poziomu. Jeśli czytasz wiele artykułów naukowych (tak jak ja - lub próbuję!), Zobaczysz, że często ulepszenia algorytmów są na szerszym poziomie koncepcyjnym, „jakościowym”, a nie na bardziej „ilościowym” poziom mikrooptymalizacji. Chciałbym podkreślić, że wzrosty rzędu wielkości są bardziej prawdopodobne, patrząc na algorytmy z tego punktu widzenia lub na wektoryzację / równoległość istniejących rozwiązań.

Powiedziawszy to, niedawno się na tym natknąłem , co może być dobrą drogą do nauki ASM x86 specjalnie dla twórców gier.

UZUPEŁNIENIE

Dwa źródła z mojej głowy:

• Podręcznik projektowania algorytmów - Steve Skiena
• Struktury danych dla programistów gier - Ron Penton i Andre LaMothe

Ponadto czytanie artykułów naukowych jest doskonałym sposobem na śledzenie mądrych procesów myślowych, ponieważ optymalizują algorytmy w celu uzyskania lepszej wydajności. Najczęściej zyski są widoczne przez:

• Ograniczenie użycia najbardziej kosztownych operacji (przede wszystkim div, SQRT, trygery operacyjne i warunkowe);
• Poprawa wydajności pamięci podręcznej dzięki wykorzystaniu bardziej wydajnych struktur danych, wyrównania pamięci i zredukowanych warunków warunkowych;
• Obniżenie jakości produkcji w akceptowalnych obszarach w celu poprawy wydajności;
• Wektoryzacja (SIMD);
• Równoległość (wątki, obejmuje przeniesienie zadań do GPU);
• I oczywiście (coraz rzadziej) ręcznie kodowany montaż. Najpierw sprawdzam zestawy C / C ++, aby zobaczyć, gdzie kompilator dokonuje nieoptymalnych wyborów. Więcej na ten temat znajdziesz w starszych artykułach z lat 80. i 90., IME.

Czytanie badań utrzymuje Cię na czele branży, zamiast czekać na zdobycie tej wiedzy w branży.

Myślę, że może być za wcześnie.

W każdym razie ważne jest, aby zrozumieć, że sam kompilator nie generuje wolniejszego kodu niż ekwiwalent asemblera, nie uzyskuje się żadnej wydajności po prostu przez napisanie tego samego kodu asemblera, co kompilator.

Na początek przynajmniej skoncentruj się na optymalizacji bez montażu. Igor Ostrovsky ma kilka dobrych artykułów, które pokazują niektóre z podstaw: http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/

Zwróć uwagę, że niepoprawne przewidywania gałęzi i pamięci podręczne są tym, na czym przede wszystkim powinieneś zoptymalizować, nawet jeśli musisz zapłacić wykonując dodatkowe operacje arytmetyczne, zwykle warto unikać nieprzewidzianych gałęzi lub odczytywać losowo ze zbyt dużej pamięci.

I, co najważniejsze, najpierw zoptymalizuj algorytm. Powolna implementacja szybkiego algorytmu prawie zawsze będzie szybsza niż szybka implementacja wolnego algorytmu.

Ta książka jest wyjątkowo dobra jak na podręcznik. Ale nie jest specjalnie ukierunkowany na optymalizację. Język asemblera dla procesorów x86, 6. edycja

Chodzi bardziej o nauczenie podstaw montażu, używając MASM. Następnie, pod koniec książki, dowie się, jak wbudować asembler w c ++ i zintegrować go z większymi programami.

Podaję to tutaj, ponieważ warto nauczyć się podstaw asemblera, zanim nauczysz się, jak optymalizować programy za jego pomocą.

Podoba mi się ta książka, ponieważ Irvine uczy, jak korzystać z narzędzi potrzebnych do pisania programów masmowych. W szczególności zajmuje się używaniem IDE (Visual Studio C ++) i debuggera. Każdy rozdział zawiera kilka filmów poświęconych rozwiązywaniu problemów. Niektóre z tych informacji są dostępne bezpłatnie na wymienionej stronie internetowej.