Pierwszą rzeczą, którą musisz zrozumieć, jest sprzęt, na którym pracujesz. Jak radzi sobie z rozgałęzianiem? Co z buforowaniem? Czy ma zestaw instrukcji SIMD? Z ilu procesorów może korzystać? Czy musi dzielić czas procesora z czymkolwiek innym?
Możesz rozwiązać ten sam problem na bardzo różne sposoby - nawet twój wybór algorytmu powinien zależeć od sprzętu. W niektórych przypadkach O (N) może działać wolniej niż O (NlogN) (w zależności od implementacji).
Jako ogólny przegląd optymalizacji, pierwszą rzeczą, którą chciałbym zrobić, jest przyjrzenie się dokładnie, jakie problemy i jakie dane próbujesz rozwiązać. Następnie zoptymalizuj to. Jeśli chcesz uzyskać ekstremalną wydajność, zapomnij o ogólnych rozwiązaniach - możesz w specjalnej obudowie umieścić wszystko, co nie pasuje do najczęściej używanej skrzynki.
Następnie profil. Profil, profil, profil. Spójrz na wykorzystanie pamięci, spójrz na kary za rozgałęzienie, spójrz na ogólne wywołanie funkcji, spójrz na wykorzystanie potoku. Sprawdź, co spowalnia Twój kod. Prawdopodobnie jest to dostęp do danych (napisałem artykuł zatytułowany „The Latency Elephant” o narzutach związanych z dostępem do danych - google. Nie mogę opublikować tutaj 2 linków, ponieważ nie mam wystarczającej „reputacji”), więc dokładnie to zbadaj i następnie zoptymalizuj układ danych ( fajne, duże, płaskie, jednorodne tablice są niesamowite ) i dostęp do danych (w miarę możliwości pobierz).
Po zminimalizowaniu obciążenia podsystemu pamięci, spróbuj ustalić, czy instrukcje są teraz wąskim gardłem (mam nadzieję, że są), a następnie spójrz na implementacje SIMD Twojego algorytmu - implementacje Structure-of-Arrays (SoA) mogą być bardzo danymi i wydajna pamięć podręczna instrukcji. Jeśli SIMD nie pasuje do twojego problemu, konieczne może być wewnętrzne kodowanie i asembler.
Jeśli nadal potrzebujesz większej prędkości, idź równolegle. Jeśli korzystasz z systemu PS3, to SPU są twoimi przyjaciółmi. Używaj ich, kochaj ich. Jeśli już napisałeś rozwiązanie SIMD, otrzymasz ogromną korzyść, przechodząc do SPU.
A potem profiluj więcej. Test w scenariuszach gry - czy ten kod wciąż stanowi wąskie gardło? Czy możesz zmienić sposób używania tego kodu na wyższym poziomie, aby zminimalizować jego użycie (tak naprawdę powinien to być Twój pierwszy krok)? Czy możesz odłożyć obliczenia na wiele ramek?
Na dowolnej platformie dowiedz się jak najwięcej na temat dostępnego sprzętu i profilerów. Nie zakładaj, że wiesz, co to jest wąskie gardło - znajdź to za pomocą swojego profilera. I upewnij się, że masz heurystykę, aby ustalić, czy rzeczywiście przyspieszyłeś grę.
A następnie profiluj to ponownie.