Czy współczesny procesor (taki jak i7) będzie śledził wskaźniki i pobierze ich dane podczas iteracji na ich liście?

Question

Chcę nauczyć się pisać lepszy kod, który wykorzystuje pamięć podręczną procesora. Praca z ciągłą pamięcią wydaje się być idealną sytuacją. Mając na uwadze powyższe, jestem ciekawy, czy istnieją podobne ulepszenia, które mogą być wykonane z nie-pamięci ciągłej, ale z tablicą wskaźników do naśladowania, jak:

struct Position { 
    int32_t x,y,z; 
} 
... 
std::vector<Position*> posPointers; 
... 
updatePosition() { 
    for (uint32_t i = 0; i < posPointers.size(); i++) { 
     Position& nextPos = *posPointers[i]; 
     nextPos.x++; 
     nextPos.y++; 
     nextPos.z++; 
    } 
} 

To tylko niektóre szorstki kod makiety , i aby się tego nauczyć poprawnie, powiedzmy, że wszystkie Struktury Pozycji zostały utworzone losowo na całym stercie.

Czy nowoczesne, inteligentne procesory, takie jak Intel i7, będą wyglądały na przyszłość i zobaczą, że bardzo szybko będą potrzebować danych o wartościach X_ptr? Czy pomocna byłaby poniższa linia kodu?

... // for loop 
Position& nextPos1 = *posPointers[i]; 
Position& nextPos2 = *posPointers[i+1]; 
Position& nextPos3 = *posPointers[i+2]; 
Position& nextPos4 = *posPointers[i+3]; 
... // Work on data here 

Czytałem niektóre slajdy prezentacji, które zdawały się wskazywać, kod taki jak ten spowoduje procesor do wstępnego pobierania niektórych danych. Czy to prawda? Jestem świadomy, że istnieją niestandardowe, specyficzne dla platformy sposoby wywoływania pobierania z wyprzedzeniem, takie jak __builtin_prefetch, ale rzucanie tego w dowolne miejsce wydaje się brzydką przedwczesną optymalizacją. Szukam sposobu, w jaki podświadomie napiszę kod efektywny w pamięci podręcznej.

Answer 1

Wiem, że nie zapytałeś (i prawdopodobnie nie potrzebujesz kazania o właściwym traktowaniu pamięci podręcznych, ale pomyślałem, że i tak wesprze moje dwa centy.) Należy zauważyć, że wszystko to dotyczy tylko gorącego kodu. Pamiętaj, że przedwczesna optymalizacja jest źródłem wszelkiego zła:

Jak podkreślono w komentarzach, najlepszym sposobem jest posiadanie pojemników z rzeczywistymi danymi, mówiąc ogólnie, płaskie struktury danych są znacznie lepsze niż "wskaźnik spaghetti", nawet jeśli musisz skopiować pewne dane i/lub zapłacić cenę za zmianę rozmiaru/przeniesienie/defragmentację struktur danych. tablica danych) opłacają się tylko wtedy, gdy uzyskujesz do nich dostęp liniowo i sekwencyjnie przez większość czasu.

Jednak ta strategia może nie zawsze być użyteczna. Zamiast rzeczywistych danych liniowych można użyć innych strategii, takich jak wykorzystanie alokatorów puli i iteracja nad pulami, zamiast na wektorach zawierających wskaźniki. Ma to oczywiście swoje wady i może być nieco bardziej skomplikowane.

Jestem pewien, że już o tym wiesz, ale warto jeszcze raz wspomnieć, że jedną z najskuteczniejszych technik uzyskiwania jak najwięcej z pamięci podręcznej jest posiadanie mniejszych danych! W powyższym kodzie, jeśli możesz uciec z int16_t zamiast int32_t, zdecydowanie powinieneś to zrobić.Powinieneś spakować swoje liczne numery i znaczniki i wyliczyć w polach bitowych, użyć indeksów zamiast wskaźników (szczególnie w systemach 64-bitowych), używać wartości skrótów o stałym rozmiarze w strukturach danych zamiast łańcuchów, itp.

Teraz, na temat głównego pytania, czy procesor może śledzić losowe wskaźniki i przenosić dane do pamięci podręcznej, zanim będą potrzebne. W bardzo ograniczonym zakresie tak się dzieje. Jak zapewne wiecie, nowoczesne procesory wykorzystują wiele sztuczek, aby zwiększyć ich prędkość (tj. Podnoszą wskaźnik wycofywania instrukcji). Sztuczki takie jak bufor sklepu, wykonywanie poza kolejnością, rurociągi superskalarne, wiele jednostek funkcjonalnych każdego rodzaju, oddział przewidywania itp. W większości przypadków te sztuczki pomagają CPU w wykonaniu wykonywania instrukcji, nawet jeśli aktualne instrukcje zostały zatrzymane lub trwają zbyt długo. W przypadku obciążeń pamięci (co jest najwolniejszą czynnością, iff dane nie znajdują się w pamięci podręcznej) oznacza to, że procesor powinien jak najszybciej dostać się do instrukcji, obliczyć adres i zażądać danych z kontrolera pamięci. Jednak kontroler pamięci może mieć tylko bardzo ograniczoną liczbę zaległych żądań (zwykle dwa dni, ale nie jestem pewien.) Oznacza to, że nawet jeśli CPU zrobił bardzo wyrafinowane rzeczy, aby spojrzeć w przyszłość do innych lokalizacji pamięci (np. elementy twojego wektora posPointers) i wywnioskuj, że są to adresy nowych danych, których twój kod będzie potrzebował, nie mógł się bardzo daleko wyprzedzić, ponieważ kontroler pamięci może mieć tylko tyle zgłoszeń oczekujących.

W każdym razie, AFAIK, nie sądzę, żeby procesory faktycznie to jeszcze robiły. Zauważ, że jest to trudny przypadek, ponieważ adresy twoich losowo rozmieszczonych lokalizacji pamięci są same w pamięci (w przeciwieństwie do bycia w rejestrze lub obliczalne z zawartości rejestru). Jeśli procesory to zrobiły, to nie i tak ma to znaczny wpływ z powodu ograniczeń interfejsu pamięci.

Wydana przeze mnie technika pobierania wstępnego wydaje mi się ważna i widziałem, że była używana, ale daje zauważalny efekt tylko wtedy, gdy procesor ma coś do zrobienia, czekając na przyszłe dane. Inkrementowanie trzech liczb całkowitych zajmuje o wiele mniej czasu niż ładowanie 12 bajtów z pamięci (w rzeczywistości ładowanie jednej linii pamięci podręcznej), a zatem nie będzie to miało większego znaczenia dla czasu wykonywania. Ale gdybyś miał coś wartościowego i cięższego do nałożenia na przedrostki pamięci (na przykład obliczenia złożonej funkcji, która nie wymaga danych z pamięci!), Możesz uzyskać bardzo dobre przyspieszenia. Widzisz, czas przejścia przez powyższą pętlę jest zasadniczo sumą czasu wszystkich chybień w pamięci podręcznej; a otrzymujesz przyrosty współrzędnych i księgowanie w pętli za darmo. Wygrałbyś więcej, gdyby darmowe rzeczy były bardziej wartościowe!

Answer 2

Nowoczesne procesory mają sprzętowe mechanizmy preselekcji: Intel Hardware prefetcher. Dostarczają schematy dostępu do pamięci i wstępnie pobierają lokalizacje pamięci, do których można uzyskać dostęp w niedalekiej przyszłości.

Jednak w przypadku całkowicie losowego wskaźnika pogoń za takimi technikami nie może pomóc. Procesor nie wie, że program w trakcie wykonywania wykonuje śledzenie wskaźnika, dlatego nie można go wstępnie pobrać. W takich przypadkach mechanizmy sprzętowe mają szkodliwy wpływ na wydajność, ponieważ pobierają wstępnie wartości, które prawdopodobnie nie będą używane.

Najlepsze, co możesz zrobić, to uporządkować struktury danych w pamięci w taki sposób, że dostęp do sąsiednich części pamięci jest bardziej prawdopodobny.