Szybki dostęp do pamięci w C++?

Question

Co powinienem wziąć pod uwagę przy tworzeniu gry pod kątem szybkiego dostępu do pamięci w C++?

Pamięć, którą ładuję jest statyczna, więc powinienem umieścić w ciągłym bloku pamięci w prawo?

Ponadto, w jaki sposób uporządkować zmienne wewnątrz struktur, aby poprawić wydajność?

Answer 1

Wydajność pamięci jest niezwykle ogólnikowa.

Myślę, że to, czego szukasz, dotyczy obsługi pamięci podręcznej procesora, ponieważ między dostępem w pamięci podręcznej a dostępem do pamięci głównej jest około 10.

Aby uzyskać pełne informacje na temat mechanizmów kryjących się za pamięcią podręczną, możesz przeczytać tę doskonałą serię artykułów pod numerem Ulrich Drepper on lwn.net.

W skrócie:

Cel LOCALITY

Nie należy skakać w pamięci, więc spróbuj (jeśli to możliwe) do grupowania elementów, które będą używane razem.

Cel na Przewidywalność

Jeśli dostępów pamięci są przewidywalne, CPU będzie prawdopodobnie wstępne pobieranie pamięć na następny kawałek pracy, tak, że jest on dostępny natychmiast, lub wkrótce po zakończeniu bieżącego klocek.

Typowym przykładem jest z for pętli na tablicach:

for (int i = 0; i != MAX; ++i) 
    for (int j = 0; j != MAX; ++j) 
    array[i][j] += 1; 

Zmiany array[i][j] += 1; z array[j][i] += 1; a wydajność waha się ... na poziomie niskim optymalizacyjnych;)

Kompilator powinien nadrobić te oczywiste przypadki, ale niektóre są bardziej podstępne. Na przykład użycie kontenerów opartych na węźle (listy połączone, drzewa wyszukiwania binarnego) zamiast kontenerów opartych na tablicach (wektor, niektóre tabele mieszania) może spowolnić działanie aplikacji.

nie trać miejsca ... Strzeżcie się fałszywych dzielenia

Spróbuj spakować struktury. Ma to związek z wyrównaniem, a użytkownik może marnować przestrzeń z powodu problemów z dopasowaniem w strukturach, które sztucznie zawyżają rozmiar struktury i zajmują miejsce w pamięci podręcznej.

Typową regułą jest zamawianie elementów w strukturze poprzez zmniejszanie rozmiaru (użyj sizeof). To jest głupie, ale działa dobrze. Jeśli masz większą wiedzę na temat rozmiaru i wyrównania, po prostu unikaj dziur :) Uwaga: przydatne tylko w przypadku struktury z wieloma przypadkami ...

Należy jednak uważać na fałszywe udostępnianie. W programach z wieloma wątkami równoczesny dostęp do dwóch zmiennych, które są wystarczająco blisko, aby współdzielić tę samą linię pamięci podręcznej, jest kosztowny, ponieważ wiąże się z wieloma unieważnieniami pamięci podręcznej i walką z CPU o własność linii pamięci podręcznej.

profilu

Niestety, jest to HARD do rozszyfrowania.

Jeśli programujesz na Unixie, Callgrind (część zestawu Valgrind) można uruchomić z symulacją pamięci podręcznej i zidentyfikować fragmenty kodu powodujące chybienia pamięci podręcznej.

Sądzę, że są inne narzędzia, których po prostu nigdy nie używałem.

Answer 2

Nie obchodzi cię to. Takie rzeczy to prawdopodobnie mikro-optymalizacje o najmniejszej naturze. Najpierw działaj, jeśli jest zbyt wolny, a następnie sprawdź, które części są wolne, i zoptymalizuj je (podpowiedź: prawdopodobnie będzie to sposób wywoływania bibliotek itp., A nie dostępu do pamięci).

Answer 3

Znajdowanie rozwiązania przed wystąpieniem problemu nie przynosi oczekiwanych rezultatów.

Lepiej jest, aby skoncentrować się na projekcie pozostawiając takie szczegóły na później, kto wie, może skończysz nigdy nie mając żadnych problemów z wydajnością ze względu na dobry ogólny projekt.

Answer 4

użycie pamięci nie musi być ciągłe. jeśli możesz zmniejszyć o połowę wielkość pamięci, to może trochę pomóc.

Jeśli chodzi o organizację struktury, powinieneś przechowywać bajty razem, potem szorty razem, i tak dalej. W przeciwnym razie kompilator będzie marnował pamięć, wyrównując mniejsze bajty i szorty do podwójnych lokalizacji słów.

jeszcze jedna wskazówka. jeśli używasz klasy, możesz umieścić ją na stosie, zamiast przydzielać ją nowym.

mam na myśli

CmyClass x; 

instead of 

Cmyclass px = new CmyClass; 
... 
delete px; 

** edit Po wywołaniu new() lub malloc zadzwonić do C++ sterty, czasami kupie zwraca nowy blok pamięci w ciągu kilku cykli, czasem to robi” t. Kiedy deklarujesz klasę na stosie, nadal jesz tę samą ilość pamięci (może nawet bardziej skomplikowaną), ale klasa jest po prostu "pchnięta" na stosie i nie są wymagane żadne wywołania funkcji. zawsze. Kiedy funkcja się kończy, stos jest czyszczony, a stos kurczy się.

Answer 5

Adres odczytany z pamięci podręcznej jest znacznie szybszy niż podczas odczytu z pamięci głównej. Dlatego staraj się, aby adresy, które czytasz, były wyświetlane blisko siebie tak blisko siebie, jak to tylko możliwe.

Na przykład podczas budowania połączonej listy prawdopodobnie lepiej będzie wyciąć jeden duży blok dla wszystkich węzłów (który może być umieszczony mniej więcej w kolejności) niż przy użyciu jednego malloc na węzeł (który może dobrze podzielić dane struktura)

Answer 6

Zgadzam się z wcześniejszymi oświadczeniami. Powinieneś napisać swoją grę, a następnie dowiedzieć się, gdzie spędza się czas i spróbować poprawić.

Jednak w duchu zapewniając niektóre potencjalnie pomocne [i potencjalnie rozpraszać od rzeczywistych problemów :-)] rada istnieją pewne wspólne pułapek Państwo mogą znaleźć:

• wskaźników funkcji i metody wirtualne zapewniają dużo elastyczności projektu, ale jeśli są używane bardzo często, okaże się, że są wolniejsze niż rzeczy, które można nakreślić. Dzieje się tak głównie dlatego, że procesorowi trudniej jest przewidzieć rozgałęzienia podczas wywoływania za pomocą wskaźnika funkcji. Dobrym złagodzeniem tego w C++ jest użycie szablonów, które mogą zapewnić podobną elastyczność projektowania w czasie kompilacji.
  
  Jedną z potencjalnych wad tego podejścia jest to, że wprowadzanie zwiększa twój rozmiar kodu. Dobrą wiadomością jest to, że twój kompilator podejmuje decyzję, czy zainwestować, i prawdopodobnie podejmie lepsze decyzje o tym, niż ty. W wielu przypadkach twój optymalizator wie o twojej specyficznej architekturze procesora i może zgadywać o tym.

• Unikaj pośrednictwa w często używanych strukturach danych.

Na przykład w ten sposób:

struct Foo 
{ 
    // [snip] other members here... 

    Bar *barObject; // pointer to another allocation owned by Foo structure 
}; 

może czasami tworzyć mniej wydajnych układów pamięci niż to:

struct Foo 
{ 
    // [snip] other members here... 

    Bar barObject; // object is a part of Foo, with no indirection 
}; 

To może wydawać się głupie, aw większości przypadków nie zauważy żadnej różnicy . Ale ogólna idea jest taka, że ​​"niepotrzebne pośrednictwo" jest dobrą rzeczą, której należy unikać. Nie rób zbyt wiele, aby to zrobić, ale należy o tym pamiętać.

Jednym z potencjalnych Wadą tego podejścia jest to, że może dokonać Foo obiekty nie nadają się już porządnie w pamięci podręcznej ...

• Wzdłuż linii poprzednich dwóch kul ... W C++, STL Kontenery i algorytmy mogą prowadzić do całkiem sprawnego kodu obiektowego. W przypadku <algorithm>, twój funktor przekazany do różnych algorytmów może łatwo zostać wstawiony, pomagając ci uniknąć niepotrzebnych wywołań wskaźnikowych, a jednocześnie pozwala na generyczne procedury. W przypadku kontenerów, STL może odpowiednio zadeklarować obiekty typu parametru T wewnątrz węzłów list itp., Pomagając uniknąć niepotrzebnego pośrednictwa w strukturach danych.

• Tak, dostęp do pamięci może coś zmienić ... Przykładem może być zapętlenie pikseli na dużym obrazie. Jeśli przetwarzasz kolumnę obrazu w czasie, może być gorsza niż przetwarzanie linii w czasie. W najpopularniejszych formatach obrazu, piksel na (x, y) jest zwykle obok tego w (x + 1, y), podczas gdy piksel na (x, y) jest zwykle (szerokość) pikseli od (x, y + 1).

• Podobnie jak druga kulka, jeden raz pracując nad projektem z manipulacją obrazem (chociaż na starym sprzęcie według dzisiejszych standardów) zauważyłem, że nawet arytmetyka polegająca na określeniu lokalizacji piksela spowodowała spowolnienie . Na przykład, jeśli masz do czynienia z współrzędnymi (x, y), intuicyjnym rozwiązaniem jest odwołanie się do piksela pod adresem buf[y * bytes_per_line + x]. Jeśli twój procesor jest powolny w mnożeniu, a twój obraz jest duży, może się to sumować. W takich okolicznościach lepiej jest zapętlić linię w czasie, niż utrzymywać obliczanie położenia (x, y) dla różnych współrzędnych.

Oczywiście ogólny projekt gry powinien wpłynąć na wcześniejsze decyzje, a pomiary powinny pomóc w udoskonaleniu wydajności. Nie powinieneś wchodzić ci w drogę, aby zaimplementować te punkty, jeśli uniemożliwia ci to wykonanie "prawdziwej pracy" lub sprawia, że ​​projekt jest trudniejszy do zrozumienia. Ale te punkty mają na celu dostarczenie przykładów miejsc, w których możesz napotkać pewne problemy, oraz wprowadzenie kontekstu na temat tego, co może powodować problemy z wydajnością w praktyce, oprócz innych środków, takich jak algorytmiczna złożoność.