Czy użycie zmiennych wskaźnikowych nie jest narzutem pamięci?

W językach takich jak C i C ++, używając wskaźników do zmiennych, potrzebujemy jeszcze jednej lokalizacji pamięci do przechowywania tego adresu. Czy to nie jest narzut pamięci? Jak to jest kompensowane? Czy wskaźniki są używane w aplikacjach o krytycznym czasie niskiej pamięci?

W rzeczywistości narzut naprawdę nie leży w dodatkowych 4 lub 8 bajtach potrzebnych do przechowywania wskaźnika. W większości przypadków wskaźniki są używane do dynamicznego przydzielania pamięci , co oznacza, że ​​wywołujemy funkcję, aby przydzielić blok pamięci, a ta funkcja zwraca nam wskaźnik, który wskazuje na ten blok pamięci. Ten nowy blok sam w sobie stanowi znaczne obciążenie.

Teraz nie musisz angażować się w alokację pamięci, aby użyć wskaźnika: możesz mieć tablicę intzadeklarowaną statycznie lub na stosie, i możesz użyć wskaźnika zamiast indeksu, aby odwiedzić ints, i jest to wszystko bardzo ładne, proste i wydajne. Przydział pamięci nie jest konieczny, a wskaźnik zwykle zajmuje dokładnie tyle miejsca w pamięci, co indeks całkowity.

Ponadto, jak przypomina nam Joshua Taylor w komentarzu, wskaźniki służą do przekazywania czegoś przez odniesienie. Np. struct foo f; init_foo(&f);Przydzieliłby f na stosie, a następnie wywołałby init_foo()do tego wskaźnik ze wskaźnikiem struct. To bardzo powszechne. (Uważaj tylko, aby nie przekazać tych wskaźników „w górę”.) W C ++ możesz zobaczyć, jak robi się to za pomocą „referencji” ( foo&) zamiast wskaźnika, ale referencje są niczym innym jak wskaźnikami, których nie możesz zmienić, a one zajmują taka sama ilość pamięci.

Ale głównym powodem, dla którego używane są wskaźniki, jest dynamiczny przydział pamięci, a odbywa się to w celu rozwiązania problemów, których inaczej nie można by rozwiązać. Oto uproszczony przykład: Wyobraź sobie, że chcesz przeczytać całą zawartość pliku. Gdzie zamierzasz je przechowywać? Jeśli spróbujesz użyć bufora o stałym rozmiarze, będziesz mógł odczytać tylko pliki, które nie są dłuższe niż ten bufor. Ale przy użyciu alokacji pamięci można przydzielić tyle pamięci, ile jest konieczne do odczytania pliku, a następnie przejść do odczytu.

Ponadto C ++ jest językiem obiektowym i istnieją pewne aspekty OOP, takie jak abstrakcja, które można osiągnąć tylko za pomocą wskaźników. Nawet języki takie jak Java i C # często korzystają ze wskaźników, po prostu nie pozwalają bezpośrednio manipulować wskaźnikami, aby uniemożliwić robienie z nimi niebezpiecznych rzeczy, ale mimo to języki te zaczynają mieć sens, gdy już masz zdałem sobie sprawę, że za kulisami wszystko odbywa się za pomocą wskaźników.

Wskaźniki są więc używane nie tylko w aplikacjach o krytycznym czasie i małej ilości pamięci, ale wszędzie .

Czy to nie jest narzut pamięci?

Oczywiście, dodatkowy adres (zwykle 4/8 bajtów w zależności od procesora).

Jak to jest kompensowane?

Nie jest. Jeśli potrzebujesz pośrednictwa niezbędnego do wskazówek, możesz za to zapłacić.

Czy wskaźniki są używane w aplikacjach o krytycznym czasie niskiej pamięci?

Nie zrobiłem tam dużo pracy, ale zakładam, że tak. Dostęp do wskaźnika jest podstawowym aspektem programowania asemblera. Zajmuje trywialne ilości pamięci, a operacje wskaźnika są szybkie - nawet w kontekście tego rodzaju aplikacji.

Nie mam tego samego sporu co Telastyn.

Globale systemowe we wbudowanym procesorze mogą być adresowane za pomocą określonych, zakodowanych adresów.

Globały w programie zostaną potraktowane jako odsunięcie od specjalnego wskaźnika wskazującego miejsce w pamięci, w którym przechowywane są globały i statyka.

Zmienne lokalne pojawiają się po wprowadzeniu funkcji i są adresowane jako przesunięcie względem innego specjalnego wskaźnika, często nazywanego „wskaźnikiem ramki”. Obejmuje to argumenty funkcji. Jeśli jesteś ostrożny w kwestii wypychania i wyskakiwania za pomocą wskaźnika stosu, możesz pozbyć się wskaźnika ramki i uzyskać dostęp do lokalnych zmiennych bezpośrednio ze wskaźnika stosu.

Płacisz więc za pośrednictwo wskaźników, niezależnie od tego, czy kroczysz przez tablicę, czy po prostu chwytasz jakąś niezwykłą zmienną lokalną lub globalną. Jest po prostu oparty na innym wskaźniku, w zależności od rodzaju zmiennej. Dobrze skompilowany kod zachowa ten wskaźnik w rejestrze procesora, zamiast przeładowywać go za każdym razem, gdy zostanie użyty.

Tak oczywiście. Ale to równowaga.

Aplikacje o małej pamięci byłyby zwykle konstruowane z uwzględnieniem kompromisu między narzutem kilku zmiennych wskaźnikowych w porównaniu do narzutu, jaki byłby ogromny program (który musi być przechowywany w pamięci, pamiętaj!), Gdyby wskaźniki nie mogły zostać użyte .

Ta uwaga dotyczy wszystkich programów, ponieważ nikt nie chce zbudować okropnego, niemożliwego do utrzymania bałaganu ze zduplikowanym kodem po lewej i prawej stronie, który jest dwadzieścia razy większy niż powinien.

W językach takich jak C i C ++, używając wskaźników do zmiennych, potrzebujemy jeszcze jednej lokalizacji pamięci do przechowywania tego adresu. Czy to nie jest narzut pamięci?

Zakładasz, że wskaźnik musi być przechowywany. Nie zawsze tak jest. Każda zmienna jest przechowywana pod pewnym adresem pamięci. Powiedz, że masz longzadeklarowany jako long n = 5L;. Przydziela miejsce do przechowywania dla nokreślonego adresu. Możemy użyć tego adresu do robienia fantazyjnych rzeczy, takich jak *((char *) &n) = (char) 0xFF;manipulowanie częściami n. Adres nnie jest nigdzie przechowywany jako dodatkowy koszt.

Jak to jest kompensowane?

Nawet jeśli wskaźniki są jawnie przechowywane (np. W strukturach danych, takich jak listy), wynikowa struktura danych jest często bardziej elegancka (prostsza, łatwiejsza do zrozumienia, łatwiejsza w obsłudze itp.) Niż równoważna struktura danych bez wskaźników.

Czy wskaźniki są używane w aplikacjach o krytycznym czasie niskiej pamięci?

Tak. Urządzenia wykorzystujące mikrokontrolery często zawierają bardzo mało pamięci, ale oprogramowanie układowe może wykorzystywać wskaźniki do obsługi wektorów przerwań lub zarządzania buforami itp.

Posiadanie wskaźnika na pewno zużywa trochę narzutu, ale widać też jego pozytywną stronę. Wskaźnik jest jak indeks. W C można używać złożonych struktur danych, takich jak łańcuch i struktury, wyłącznie ze względu na wskaźniki.

W rzeczywistości załóżmy, że chcesz przekazać zmienną przez odniesienie, wtedy łatwo jest utrzymywać wskaźnik zamiast replikować całą strukturę i synchronizować zmiany między nimi (nawet do ich skopiowania potrzebujesz wskaźnika). Jak poradziłbyś sobie z nieciągłymi alokacjami pamięci i alokacjami bez wskaźnika?

Nawet normalne zmienne mają wpis w tabeli symboli, który przechowuje adres, na który wskazuje twoja zmienna. Więc nie sądzę, że powoduje to duże obciążenie pamięci (tylko 4 lub 8 bajtów). Nawet języki takie jak Java używają wskaźników wewnętrznie (odniesienie), po prostu nie pozwalają ci nimi manipulować, ponieważ spowoduje to, że JVM będzie mniej bezpieczny.

Powinieneś używać wskaźników tylko wtedy, gdy nie masz innego wyboru, jak brakujące typy danych, struktury (w c), ponieważ użycie wskaźników może prowadzić do błędów, jeśli nie jest odpowiednio obsługiwane i jest stosunkowo trudniej debugować.

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:

1. 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.

2. 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.}

Czy to nie jest narzut pamięci?

Rzeczywiście jest to narzut pamięci, ale bardzo mały (do tego stopnia, że ​​nie ma znaczenia).

Jak to jest kompensowane?

To nie jest rekompensowane. Musisz zdać sobie sprawę, że dostęp do danych przez wskaźnik (dereferencja wskaźnika) jest niezwykle szybki (o ile dobrze pamiętam, używa tylko jednej instrukcji asemblera na dereferencję). Jest wystarczająco szybki, aby w wielu przypadkach był najszybszą dostępną alternatywą.

Czy wskaźniki są używane w aplikacjach o krytycznym czasie niskiej pamięci?

Tak.

Potrzebujesz tylko dodatkowego użycia pamięci (zwykle 4-8 bajtów na wskaźnik), podczas gdy potrzebujesz tego wskaźnika. Istnieje wiele technik, które czynią to bardziej przystępnym cenowo.

Najbardziej podstawową techniką, która sprawia, że ​​wskaźniki są silne, jest to, że nie musisz utrzymywać każdego wskaźnika. Czasami możesz użyć algorytmu do skonstruowania wskaźnika ze wskaźnika na coś innego. Najbardziej trywialnym przykładem tego jest arytmetyka tablicowa. Jeśli przydzielisz tablicę 50 liczb całkowitych, nie musisz przechowywać 50 wskaźników, po jednym do każdej liczby całkowitej. Zazwyczaj śledzisz jeden wskaźnik (pierwszy) i używasz arytmetyki wskaźnika do generowania pozostałych w locie. Czasami możesz tymczasowo zatrzymać jeden z tych wskaźników do określonego elementu tablicy, ale tylko wtedy, gdy jest to potrzebne. Gdy skończysz, możesz go odrzucić, o ile zachowałeś wystarczającą ilość informacji, aby później je zregenerować, jeśli zajdzie taka potrzeba. Może to zabrzmieć trywialnie, ale jest to dokładnie ten rodzaj narzędzia do ochrony, który „

W wyjątkowo ciasnych sytuacjach pamięciowych można to wykorzystać, aby zminimalizować koszty. Jeśli pracujesz w bardzo ciasnej przestrzeni pamięci, zwykle masz dobre wyczucie, ile obiektów musisz manipulować. Zamiast przydzielić kilka liczb całkowitych pojedynczo i zachować dla nich pełne wskaźniki, możesz skorzystać z wiedzy programisty, że nigdy nie będziesz mieć więcej niż 256 liczb całkowitych w tym konkretnym algorytmie. W takim przypadku możesz zachować wskaźnik do pierwszej liczby całkowitej i śledzić indeks przy użyciu znaku char (1 bajt) zamiast pełnego wskaźnika (4/8 bajtów). Możesz także użyć sztuczek algorytmicznych, aby wygenerować niektóre z tych wskaźników w locie.

Ten rodzaj sumienności pamięci był bardzo popularny w przeszłości. Na przykład gry NES polegałyby w dużej mierze na ich zdolności do wczytywania danych i algorytmicznego generowania wskaźników, zamiast konieczności przechowywania ich wszystkich hurtowo.

Ekstremalne sytuacje w pamięci mogą również prowadzić do przydzielania wszystkich przestrzeni, na których operujesz w czasie kompilacji. Następnie wskaźnik, który musisz zapisać do tej pamięci, jest zapisywany w programie, a nie w danych. W wielu sytuacjach z ograniczoną pamięcią masz oddzielną pamięć programu i danych (często ROM vs RAM), więc możesz być w stanie dostosować sposób, w jaki używasz algorytmu, aby wepchnąć wskaźniki do pamięci tego programu.

Zasadniczo nie można pozbyć się wszystkich kosztów ogólnych. Możesz to jednak kontrolować. Stosując techniki algorytmiczne, możesz zminimalizować liczbę przechowywanych wskaźników. Jeśli akurat używasz wskaźników do pamięci dynamicznej, nigdy nie obniżysz kosztu utrzymania 1 wskaźnika w tym dynamicznym miejscu pamięci, ponieważ jest to minimalna ilość informacji potrzebna do uzyskania dostępu do czegokolwiek w tym bloku pamięci. Jednak w scenariuszach z bardzo wąskim ograniczeniem pamięci jest to przypadek szczególny (dynamiczne i bardzo wąskie ograniczenia pamięci zwykle nie pojawiają się w tych samych sytuacjach).

W wielu sytuacjach wskaźniki faktycznie oszczędzają pamięć. Częstą alternatywą dla używania wskaźników jest wykonanie kopii struktury danych. Pełna kopia struktury danych będzie większa niż wskaźnik.

Jednym z przykładów aplikacji krytycznych czasowo jest stos sieciowy. Dobry stos sieci zostanie zaprojektowany jako „kopia zerowa” - a do tego wymaga sprytnego użycia wskaźników.