Dlaczego potrzebujemy stosu, jeśli wszystko można zrobić znacznie wydajniej na stosie?

W rzeczywistości jest to nieco związane z pytaniem, które zadałem wczoraj, dlaczego stos i stos są niezbędne w aplikacjach, których używamy dzisiaj (i dlaczego nie możemy po prostu wybrać stosu zamiast obu, aby mieć proste & szczególny standard).

Jednak wiele odpowiedzi wskazywało, że stos jest niezastąpiony ze względu na fakt, że jest on setki (lub tysiące) razy szybszy niż próba alokacji / odwołania do stosu. Wiem, że istnieje problem z dynamiczną alokacją pamięci, jeśli zlikwidujemy Stertę, ale czy nie istnieje sposób na obejście tego, a może sposób na ulepszenie stosu, aby mógł on obsłużyć dynamiczną alokację pamięci?

Problem ze stosami polega na tym, że nie można „zwolnić” pamięci, chyba że jest na wierzchu stosu. Załóżmy na przykład, że przydzieliłeś 3 rzeczy o różnych rozmiarach:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

Stos miałby ana dole, bna środku i cna górze. Staje się to problematyczne, jeśli chcemy uwolnić b:

free(b); // b is not on top! We have to wait until c is freed!

Obejściem tego problemu jest przeniesienie wszystkich danych po bi przesunięcie, jeśli tak, aby nastąpiło później a. To działa, ale w tym przypadku będzie wymagało 5000000 kopii - coś, co będzie znacznie wolniejsze niż kupa.

Właśnie dlatego mamy stos. Chociaż alokacja może być wolniejsza niż stos ( O(log n)vs O(1)), stosy pozwalają na szybkie zwolnienie pamięci w dowolnym miejscu - O(log n)w porównaniu do stosuO(n)

Stos jest zależny od wątku, a stos jest cały proces

Jeśli 100 wątków ma wszystkie przetwarzane elementy pracy, które umieszczam w kolejce, to gdzie dokładnie mam alokować elementy pracy, aby każdy ze 100 wątków mógł je zobaczyć?

Istnieją również inne rodzaje pamięci

Np. Pliki mapowane w pamięci, pamięć współdzielona, ​​mapowane we / wy (tryb jądra). Argument wydajności jest w takich sytuacjach dyskusyjny.

Stos jest strukturą LIFO (ostatni na wejściu, pierwszy na wyjściu), na której górze znajduje się wskaźnik odniesienia (zwykle obsługiwany przez sprzęt). Powiedziawszy to, wszystko, co próbujesz przydzielić na stosie zamiast na stosie, musiałoby być zmienną lokalną w każdej funkcji na górze tego stosu. Zatem głównym powodem stosu jest to, że twoja procedura główna () musiałaby wstępnie przydzielić wszystkie struktury danych, z których korzysta Twój program (które mają być dostępne przez cały czas trwania programu), zanim wszystkie struktury danych zostaną przydzielone wywołania funkcji zostaną ostatecznie usunięte, gdy te wywołania funkcji powrócą, a ich ramki lub rekordy aktywacji zostaną usunięte ze stosu.

Stosy świetnie sprawdzają się w przypadku alokacji pamięci, które są zgodne z regułami Last in First out (LIFO), co oznacza, że ​​zwalniasz pamięć w dokładnie odwrotnej kolejności, w jakiej ją alokujesz. LIFO jest bardzo powszechnym, być może najczęstszym wzorem przydziału pamięci. Ale to nie jedyny wzór, ani nawet wspólny wzór. Aby napisać skuteczny program, który może rozwiązać wiele różnych problemów, musimy uwzględnić mniej popularne wzorce, nawet jeśli oznacza to bardziej złożoną infrastrukturę.

Jeśli uda mi się uzyskać wszystkie meta dla akapitu: jesteś początkującym, jako początkujący cenisz prostotę i zasady czarno-białe. Jednak jako początkujący masz tylko wizjer z szerokiej gamy problemów i ograniczeń, które muszą zostać uwzględnione przez programy komputerowe. Wchodzisz w technologię, która jest aktywnie rozwijana przez 75 lat. Nie ma nic złego w pytaniu, dlaczego rzeczy są takie, jakie są, ale ogólnie odpowiedź brzmi: „Tak, wypróbowaliśmy prostą, bezpośrednią metodę 50 lat temu i okazało się, że nie działa zbyt dobrze dla całych klas problemów, więc musieliśmy zrobić coś bardziej skomplikowanego ”. W miarę postępu technologii prostota musi ustępować miejsca wydajności i elastyczności.

Na inny przykład, zamknięcia. Jeśli ustawisz pop, możesz stracić rekord aktywacyjny zamknięcia. Jeśli więc chcesz, aby ta anonimowa funkcja i jej dane trwały, musisz ją zapisać gdzie indziej niż na stosie wykonawczym.

Wśród wielu innych powodów przydzielania miejsca na sterty.

Jeśli chcesz przekazać adres obiektu z powrotem do programu wywołującego, nie powinieneś przekazywać adresu zmiennej stosu, ponieważ pamięć stosu zostanie ponownie użyta i prawdopodobnie nadpisana przez następną wywoływaną funkcję. Musisz uzyskać wymaganą pamięć za pomocą malloc (), aby upewnić się, że nie zostanie ona zastąpiona wywołaniami kolejnych funkcji.

Możesz przekazać adresy elementów stosu z funkcji do wywoływanych funkcji, ponieważ możesz zagwarantować, że będą one istnieć, dopóki Twój program nie „zwróci ()”. Ale gdy tylko funkcja zwróci, cała pamięć stosu jest gotowa do pobrania.