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

24

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?

Mroczny Templariusz
źródło
4
Dwa fragmenty z poprzedniego pytania: „najważniejszym minusem jest to, że ma ograniczoną przestrzeń, a więc trzymanie w niej dużych obiektów lub próba użycia go do obiektów długowiecznych, są złymi pomysłami” i „stosy są niezwykle wydajne struktura zarządzania danymi zgodnymi z regułami LIFO (ostatnie weszło pierwsze wyszło) ”.
Cascabel,
2
Twoja przesłanka jest wadliwa - nie wszystko można zrobić znacznie wydajniej na stosie. Nie jest to sprzeczne z otrzymanymi odpowiedziami - że to, co można zrobić na stosie, można tam zrobić znacznie szybciej.
Ingo
... zakładając, że twój sprzęt ma stos lub adresowanie zależne od stosu.
Ritch Melton
3
Jestem przekonany. Mówię, zrób to.
JeffO,

Odpowiedzi:

25

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)

Pubby
źródło
4
Wiąże się to z tym, że Facebook nie usuwa zawartości z dysku, gdy poprosisz ją o usunięcie, po prostu usuwa do niej wskaźnik. Najwyraźniej narzut związany z próbą defragmentacji lub znalezienia równoważnej luki na dysku jest zbyt czasochłonny przy szybkościach zapisywania danych, więc po prostu dodają wszystko do znaku wysokiej wody na dysku.
Paul Tomblin,
Cóż, dyski Facebooka można traktować jak kupę. I jestem prawie pewien, że mają jakieś śmieci do tych dysków.
deadalnix,
2
@deadalnix W rzeczywistości jest to przykład użycia ogromnego stosu zamiast stosu, który jest zwykle używany dla większej ilości pamięci. Facebook jest jednak szczególnym przypadkiem. Dane są dodawane o wiele szybciej niż są usuwane, więc dealokacja nie ma znaczącego wpływu na szybkość wzrostu - możesz celowo uwzględnić przecieki pamięci w projekcie, aby uzyskać alokację O (1).
Tom Clarkson,
7
@PaulTomblin Głównym powodem, dla którego FB nie usuwa zawartości, jest to, że mogą ją wydobywać dla własnego zysku ...
quant_dev
5
Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it- Co w zasadzie dzieje się, gdy wykonujesz zwykłe usuwanie pliku w dowolnym systemie operacyjnym.
Robert Harvey
5

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.

JBRWilkinson
źródło
4

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.

Alex
źródło
3
LIFO, nie FIFO.
Pubby
czasami nazywany także FILO;)
oenone 10.10.11
3

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.

Charles E. Grant
źródło
0

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.

zaraz
źródło
0

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.

James Anderson
źródło