Czy to nie jest narzut pamięci?
Tak nie może?
Jest to dziwne pytanie, ponieważ wyobraź sobie zakres adresowania pamięci na maszynie oraz oprogramowanie, które musi stale śledzić, gdzie są rzeczy w pamięci w sposób, którego nie można powiązać ze stosem.
Wyobraź sobie na przykład odtwarzacz muzyki, w którym plik muzyczny jest ładowany na przycisk przez użytkownika i usuwany z pamięci ulotnej, gdy użytkownik próbuje załadować inny plik muzyczny.
Jak śledzimy miejsce przechowywania danych audio? Potrzebujemy do tego adresu pamięci. Program musi nie tylko śledzić fragment danych audio w pamięci, ale także miejsce w pamięci. Dlatego musimy trzymać się adresu pamięci (tzn. Wskaźnika). Rozmiar pamięci wymaganej dla adresu pamięci będzie pasował do zakresu adresowania urządzenia (np. 64-bitowy wskaźnik dla 64-bitowego zakresu adresowania).
Jest to więc „tak”, wymaga pamięci do przechowywania adresu pamięci, ale nie jest tak, że możemy tego uniknąć w przypadku dynamicznie alokowanej pamięci tego rodzaju.
Jak to jest kompensowane?
Mówiąc o samym rozmiarze samego wskaźnika, możesz w niektórych przypadkach uniknąć kosztu, korzystając ze stosu, np. W takim przypadku kompilatory mogą generować instrukcje, które skutecznie zakodują względny adres pamięci, unikając kosztu wskaźnika. Jednak naraża Cię to na przepełnienie stosu, jeśli robisz to dla dużych alokacji o zmiennej wielkości, a także wydaje się być niepraktyczne (jeśli nie wręcz niemożliwe) dla złożonej serii gałęzi sterowanych przez dane wejściowe użytkownika (jak w przykładzie audio powyżej).
Innym sposobem jest użycie bardziej ciągłych struktur danych. Na przykład zamiast podwójnie połączonej listy można zastosować sekwencję tablicową, która wymaga dwóch wskaźników na węzeł. Możemy również użyć hybrydy tych dwóch jak rozwiniętej listy, która przechowuje tylko wskaźniki pomiędzy każdą ciągłą grupą N elementów.
Czy wskaźniki są używane w aplikacjach o krytycznym czasie niskiej pamięci?
Tak, bardzo często, ponieważ wiele aplikacji krytycznych pod względem wydajności jest napisanych w C lub C ++, które są zdominowane przez użycie wskaźnika (mogą znajdować się za inteligentnym wskaźnikiem lub kontenerem, takim jak std::vectorlub std::string, ale podstawowa mechanika sprowadza się do wskaźnika, który jest używany aby śledzić adres do dynamicznego bloku pamięci).
Wróćmy do tego pytania:
Jak to jest kompensowane? (Część druga)
Wskaźniki są zazwyczaj tandetne, chyba że przechowujesz je jak milion z nich (co wciąż jest kiepskim * 8 megabajtami na komputerze 64-bitowym).
* Uwaga: Ben zauważył, że „nędzne” 8 megapikseli wciąż ma rozmiar pamięci podręcznej L3. Tutaj użyłem „marnej” więcej w sensie całkowitego wykorzystania pamięci DRAM, a typowy względny rozmiar w stosunku do fragmentów pamięci wskaże zdrowe użycie wskaźników.
Gdy wskaźniki stają się drogie, nie same wskaźniki, ale:
Dynamiczna alokacja pamięci. Dynamiczna alokacja pamięci bywa kosztowna, ponieważ musi przejść przez podstawową strukturę danych (np. Kumpel lub alokator płyty). Mimo że są one często zoptymalizowane pod kątem śmierci, są one ogólnego przeznaczenia i zaprojektowane do obsługi bloków o zmiennej wielkości, które wymagają, aby wykonały przynajmniej trochę pracy przypominającej „wyszukiwanie” (choć lekkie, a być może nawet ciągłe) znajdź bezpłatny zestaw ciągłych stron w pamięci.
Dostęp do pamięci. Jest to zwykle większy problem, o który należy się martwić. Za każdym razem, gdy uzyskujemy dostęp do pamięci przydzielanej dynamicznie po raz pierwszy, pojawia się obowiązkowy błąd strony, a także pamięć podręczna pomija przenoszenie pamięci w dół hierarchii pamięci i do rejestru.
Dostęp do pamięci
Dostęp do pamięci jest jednym z najbardziej krytycznych aspektów wydajności poza algorytmami. Wiele dziedzin o kluczowym znaczeniu dla wydajności, takich jak silniki gier AAA, koncentruje dużą część swojej energii na optymalizacjach zorientowanych na dane, które sprowadzają się do bardziej wydajnych wzorów i układów dostępu do pamięci.
Jedną z największych trudności wydajnościowych w językach wyższego poziomu, które chcą przydzielić każdy typ zdefiniowany przez użytkownika osobno za pośrednictwem modułu wyrzucania elementów bezużytecznych, np. Jest to, że mogą one dość fragmentować pamięć. Może to być szczególnie prawdziwe, jeśli nie wszystkie obiekty są przydzielane jednocześnie.
W takich przypadkach, jeśli przechowujesz listę miliona instancji typu obiektu zdefiniowanego przez użytkownika, dostęp do tych instancji sekwencyjnie w pętli może być dość powolny, ponieważ jest analogiczny do listy milionów wskaźników wskazujących na odmienne regiony pamięci. W takich przypadkach architektura chce pobrać pamięć z wyższych, wolniejszych i większych poziomów hierarchii w dużych, wyrównanych porcjach z nadzieją, że dostęp do otaczających danych w tych porcjach będzie możliwy przed eksmisją. Gdy każdy obiekt z takiej listy jest przydzielany osobno, często kończy się to płaceniem za nieudane pamięć podręczną, gdy każda kolejna iteracja może wymagać załadowania z zupełnie innego obszaru pamięci bez dostępu do sąsiednich obiektów przed eksmisją.
Wiele kompilatorów dla takich języków wykonuje obecnie naprawdę świetną robotę w zakresie wyboru instrukcji i przydzielania rejestrów, ale brak bardziej bezpośredniej kontroli nad zarządzaniem pamięcią może być zabójczy (choć często mniej podatny na błędy) i nadal sprawiać, że języki takie jak C i C ++ dość popularne.
Pośrednia optymalizacja dostępu do wskaźnika
W scenariuszach najbardziej krytycznych pod względem wydajności aplikacje często używają pul pamięci, które łączą pamięć z ciągłych porcji, aby poprawić lokalizację odniesienia. W takich przypadkach nawet powiązaną strukturę, taką jak drzewo lub połączoną listę, można uczynić przyjazną dla pamięci podręcznej, pod warunkiem, że układ pamięci jej węzłów ma charakter ciągły. To skutecznie sprawia, że dereferencje wskaźników są tańsze, choć pośrednio, poprzez poprawę lokalizacji odnośników związanych z dereferencją.
Chasing Pointers Around
Załóżmy, że mamy pojedynczo połączoną listę, taką jak:
Foo->Bar->Baz->null
Problem polega na tym, że jeśli alokujemy wszystkie te węzły osobno względem alokatora ogólnego przeznaczenia (i być może nie wszystkie naraz), rzeczywista pamięć może być rozproszona nieco w ten sposób (uproszczony schemat):
Kiedy zaczynamy gonić wskaźniki wokół i uzyskiwać dostęp do Foowęzła, zaczynamy od obowiązkowego pominięcia (i prawdopodobnie błędu strony) przeniesienia fragmentu z jego obszaru pamięci z wolniejszych obszarów pamięci do szybszych obszarów pamięci, tak jak:
To powoduje, że buforujemy (ewentualnie także stronę) obszar pamięci, aby uzyskać dostęp do jego części i eksmitować resztę, gdy gonimy wskaźniki wokół tej listy. Jednak przejmując kontrolę nad alokatorem pamięci, możemy przydzielić taką listę w sposób ciągły:
... a tym samym znacznie poprawić szybkość, z jaką możemy wyłuskać te wskaźniki i przetworzyć ich wskaźniki. Tak więc, choć bardzo pośredni, możemy w ten sposób przyspieszyć dostęp do wskaźnika. Oczywiście, gdybyśmy po prostu przechowywali je w sposób ciągły w tablicy, nie mielibyśmy tego problemu w pierwszej kolejności, ale tutaj przydział pamięci zapewniający nam wyraźną kontrolę nad układem pamięci może uratować dzień, w którym wymagana jest połączona struktura.
* Uwaga: jest to bardzo uproszczony schemat i dyskusja na temat hierarchii pamięci i lokalizacji odniesienia, ale miejmy nadzieję, że jest odpowiedni dla poziomu pytania.