Stos, statyczne i sterty w C ++


160

Szukałem, ale nie rozumiałem zbyt dobrze tych trzech pojęć. Kiedy muszę używać alokacji dynamicznej (w stercie) i jaka jest jej prawdziwa zaleta? Jakie są problemy ze statowaniem i stosem? Czy mogę napisać całą aplikację bez przydzielania zmiennych w stercie?

Słyszałem, że inne języki zawierają "garbage collector", więc nie musisz się martwić o pamięć. Co robi odśmiecacz?

Co mógłbyś zrobić samodzielnie manipulując pamięcią, czego nie mógłbyś zrobić używając tego garbage collectora?

Kiedyś ktoś mi powiedział, że tą deklaracją:

int * asafe=new int;

Mam „wskaźnik do wskaźnika”. Co to znaczy? Różni się od:

asafe=new int;

?


Jakiś czas temu padło bardzo podobne pytanie: co i gdzie jest stos i sterta? Jest kilka naprawdę dobrych odpowiedzi na to pytanie, które powinny rzucić trochę światła na twoje.
Scott Saad,

Odpowiedzi:


223

Podobne pytanie , ale nie dotyczyło statyki.

Podsumowanie tego, czym są pamięci statyczne, sterty i stosy:

  • Zmienna statyczna jest w zasadzie zmienną globalną, nawet jeśli nie masz do niej dostępu globalnie. Zwykle jest to adres, który znajduje się w samym pliku wykonywalnym. Istnieje tylko jedna kopia całego programu. Bez względu na to, ile razy wchodzisz do wywołania funkcji (lub klasy) (iw ilu wątkach!) Zmienna odwołuje się do tej samej lokalizacji pamięci.

  • Sterta to zbiór pamięci, których można używać dynamicznie. Jeśli chcesz 4kb dla obiektu, dynamiczny alokator przejrzy swoją listę wolnego miejsca w stercie, wybierze fragment 4kb i da wam go. Ogólnie rzecz biorąc, dynamiczny alokator pamięci (malloc, new itp.) Zaczyna się na końcu pamięci i działa wstecz.

  • Wyjaśnienie, w jaki sposób stos rośnie i kurczy się, jest nieco poza zakresem tej odpowiedzi, ale wystarczy powiedzieć, że zawsze dodajesz i usuwasz tylko z końca. Stosy zwykle zaczynają się wysoko i rosną do niższych adresów. Skończy się pamięć, gdy stos spotyka się z dynamicznym alokatorem gdzieś pośrodku (ale odnosi się do pamięci fizycznej i wirtualnej oraz fragmentacji). Wiele wątków będzie wymagać wielu stosów (proces zazwyczaj rezerwuje minimalny rozmiar stosu).

Kiedy chciałbyś użyć każdego z nich:

  • Statyka / wartości globalne są przydatne w przypadku pamięci, o której wiesz, że będziesz jej potrzebować, i wiesz, że nigdy nie chcesz cofać przydziału. (Nawiasem mówiąc, środowiska osadzone mogą być traktowane jako mające tylko pamięć statyczną ... stos i sterta są częścią znanej przestrzeni adresowej współdzielonej przez trzeci typ pamięci: kod programu. Programy często wykonują dynamiczną alokację ze swojego pamięci statycznej, gdy potrzebują takich rzeczy, jak listy połączone. Niezależnie od tego, sama pamięć statyczna (bufor) nie jest sama „alokowana”, ale raczej inne obiekty są przydzielane z pamięci przechowywanej przez bufor do tego celu. Możesz to zrobić również w grach nie osadzonych, a gry konsolowe często unikają wbudowanych mechanizmów pamięci dynamicznej na rzecz ścisłej kontroli procesu alokacji przy użyciu buforów o wstępnie ustawionych rozmiarach dla wszystkich przydziałów).

  • Zmienne stosu są przydatne, gdy wiesz, że dopóki funkcja znajduje się w zasięgu (gdzieś na stosie), będziesz chciał, aby zmienne pozostały. Stosy są dobre dla zmiennych, których potrzebujesz do kodu, w którym się znajdują, ale które nie są potrzebne poza tym kodem. Są również bardzo przydatne, gdy uzyskujesz dostęp do zasobu, takiego jak plik, i chcesz, aby zasób zniknął automatycznie, gdy opuścisz ten kod.

  • Alokacje sterty (pamięć przydzielana dynamicznie) są przydatne, gdy chcesz być bardziej elastyczny niż powyższe. Często funkcja jest wywoływana, aby odpowiedzieć na zdarzenie (użytkownik klika przycisk „utwórz pole”). Właściwa odpowiedź może wymagać przydzielenia nowego obiektu (nowego obiektu Box), który powinien pozostać na długo po zakończeniu funkcji, więc nie może znajdować się na stosie. Ale nie wiesz, ile pól chciałbyś na początku programu, więc nie może to być statyczne.

Zbieranie śmieci

Ostatnio dużo słyszałem o tym, jak świetni są Garbage Collectors, więc może trochę sprzeciwu by się przydał.

Wyrzucanie elementów bezużytecznych to wspaniały mechanizm, gdy wydajność nie jest dużym problemem. Słyszałem, że GC są coraz lepsze i bardziej wyrafinowane, ale faktem jest, że możesz być zmuszony zaakceptować spadek wydajności (w zależności od przypadku użycia). A jeśli jesteś leniwy, to nadal może nie działać poprawnie. W najlepszych momentach Garbage Collectors zdaje sobie sprawę, że twoja pamięć znika, gdy zdaje sobie sprawę, że nie ma już do niej odniesień (patrz odniesień liczenie referencji). Ale jeśli masz obiekt, który odnosi się do samego siebie (być może przez odniesienie do innego obiektu, który odnosi się z powrotem), to samo zliczanie odwołań nie wskaże, że pamięć można usunąć. W takim przypadku GC musi przyjrzeć się całej zupie referencyjnej i dowiedzieć się, czy są jakieś wyspy, do których istnieją tylko odniesienia. Odręcznie, przypuszczam, że jest to operacja O (n ^ 2), ale cokolwiek to jest, może się pogorszyć, jeśli w ogóle zależy ci na wydajności. (Edycja: zwraca uwagę Martin B. że jest O (n) dla rozsądnie efektywnych algorytmów, które wciąż O (n) zbyt wiele, jeśli dotyczą wydajności i może cofnąć przydział w stałym czasie bez zbierania śmieci.).

Osobiście, kiedy słyszę, jak ludzie mówią, że C ++ nie ma funkcji zbierania śmieci, mój umysł oznacza to jako cechę C ++, ale prawdopodobnie jestem w mniejszości. Prawdopodobnie najtrudniejszą rzeczą dla ludzi do nauczenia się programowania w C i C ++ są wskazówki i jak poprawnie obsługiwać ich dynamiczne alokacje pamięci. Niektóre inne języki, takie jak Python, byłyby okropne bez GC, więc myślę, że sprowadza się to do tego, czego chcesz od języka. Jeśli chcesz niezawodnej wydajności, to C ++ bez czyszczenia pamięci jest jedyną rzeczą, o której mogę pomyśleć po tej stronie Fortrana. Jeśli zależy Ci na łatwości użytkowania i treningu kół (aby uchronić Cię przed awarią bez konieczności uczenia się „prawidłowego” zarządzania pamięcią), wybierz coś z GC. Nawet jeśli wiesz, jak dobrze zarządzać pamięcią, pozwoli to zaoszczędzić czas, który możesz poświęcić na optymalizację innego kodu. Naprawdę nie ma już dużego spadku wydajności, ale jeśli naprawdę potrzebujesz niezawodnej wydajności (i możliwości dokładnego poznania, co się dzieje i kiedy, pod osłonami), to trzymam się C ++. Jest powód, dla którego każdy główny silnik gry, o jakim kiedykolwiek słyszałem, jest w C ++ (jeśli nie w C lub w assemblerze). Python i inni nadają się do tworzenia skryptów, ale nie do głównego silnika gry.


Nie jest to tak naprawdę istotne dla pierwotnego pytania (a właściwie zbyt wiele), ale masz lokalizacje stosu i stosujesz od tyłu. Zwykle stos rośnie, a sterta rośnie (chociaż sterta w rzeczywistości nie rośnie, więc jest to ogromne uproszczenie) ...
P Daddy,

Nie sądzę, aby to pytanie było podobne lub nawet powielało inne pytanie. ten jest konkretnie o C ++ i miał na myśli prawie na pewno trzy czasy przechowywania istniejące w C ++. Możesz mieć obiekt dynamiczny przydzielony do pamięci statycznej, na przykład, przeciążenie op nowy.
Johannes Schaub - litb

7
Twoje uwłaczające traktowanie wywozu śmieci było trochę mniej niż pomocne.
P Daddy,

9
Często zbieranie śmieci jest obecnie lepsze niż ręczne zwalnianie pamięci, ponieważ dzieje się tak, gdy jest niewiele do zrobienia, w przeciwieństwie do zwalniania pamięci, które może się zdarzyć, gdy wydajność może być wykorzystana w inny sposób.
Georg Schölly

3
Tylko mały komentarz - czyszczenie pamięci nie ma złożoności O (n ^ 2) (co rzeczywiście miałoby katastrofalne skutki dla wydajności). Czas potrzebny na jeden cykl czyszczenia pamięci jest proporcjonalny do rozmiaru sterty - patrz hpl.hp.com/personal/Hans_Boehm/gc/complexity.html .
Martin B

54

Poniższe informacje są oczywiście niezupełnie dokładne. Czytając to traktuj to z przymrużeniem oka :)

Cóż, trzy rzeczy, o których mówisz, to automatyczny, statyczny i dynamiczny czas przechowywania , który ma coś wspólnego z tym, jak długo obiekty żyją i kiedy zaczynają życie.


Automatyczny czas przechowywania

Używasz automatycznego czasu przechowywania dla krótkotrwałych i małych danych, które są potrzebne tylko lokalnie w pewnym bloku:

if(some condition) {
    int a[3]; // array a has automatic storage duration
    fill_it(a);
    print_it(a);
}

Okres istnienia kończy się, gdy tylko wyjdziemy z bloku i zaczyna się, gdy tylko obiekt zostanie zdefiniowany. Są to najprostsze rodzaje czasu przechowywania i są znacznie szybsze niż w szczególności dynamiczny czas przechowywania.


Statyczny czas przechowywania

Używasz statycznego czasu przechowywania dla wolnych zmiennych, do których może mieć dostęp dowolny kod przez cały czas, jeśli ich zakres pozwala na takie użycie (zakres przestrzeni nazw), oraz dla zmiennych lokalnych, które wymagają przedłużenia czasu życia poprzez wyjście z ich zakresu (zakres lokalny), oraz dla zmiennych składowych, które muszą być współużytkowane przez wszystkie obiekty swojej klasy (zakres klas). Ich trwałość zależy od zakresu w którym się znajdują. Mogą one mieć zakres przestrzeni nazw i zakresu lokalnego i zakresu klasy . Prawdą jest, że obaj z nich zaczynają żyć, a kończy się wraz z zakończeniem programu . Oto dwa przykłady:

// static storage duration. in global namespace scope
string globalA; 
int main() {
    foo();
    foo();
}

void foo() {
    // static storage duration. in local scope
    static string localA;
    localA += "ab"
    cout << localA;
}

Program drukuje ababab, ponieważ localAnie jest niszczony po wyjściu z jego bloku. Można powiedzieć, że obiekty o zasięgu lokalnym rozpoczynają okres istnienia, gdy kontrola osiągnie swoją definicję . Na localAto się dzieje, gdy ciało funkcja jest wpisany. W przypadku obiektów w zakresie przestrzeni nazw okres istnienia rozpoczyna się podczas uruchamiania programu . To samo dotyczy statycznych obiektów o zasięgu klasowym:

class A {
    static string classScopeA;
};

string A::classScopeA;

A a, b; &a.classScopeA == &b.classScopeA == &A::classScopeA;

Jak widać, classScopeAnie jest powiązany z określonymi obiektami swojej klasy, ale z samą klasą. Adres wszystkich trzech powyższych nazw jest taki sam i wszystkie oznaczają ten sam obiekt. Istnieją specjalne zasady dotyczące tego, kiedy i jak inicjowane są obiekty statyczne, ale nie przejmujmy się tym teraz. Oznacza to termin fiasko kolejności inicjalizacji statycznej .


Dynamiczny czas przechowywania

Ostatni okres przechowywania jest dynamiczny. Używasz go, jeśli chcesz, aby obiekty żyły na innej wyspie i chcesz umieścić wskaźniki wokół tych obiektów. Używasz ich również, jeśli twoje obiekty są duże i jeśli chcesz tworzyć tablice o rozmiarze znanym tylko w czasie wykonywania . Z powodu tej elastyczności obiekty o dynamicznym czasie trwania są skomplikowane i powolne w zarządzaniu. Obiekty mające ten dynamiczny czas trwania rozpoczynają okres istnienia, gdy nastąpi odpowiednie wywołanie nowego operatora:

int main() {
    // the object that s points to has dynamic storage 
    // duration
    string *s = new string;
    // pass a pointer pointing to the object around. 
    // the object itself isn't touched
    foo(s);
    delete s;
}

void foo(string *s) {
    cout << s->size();
}

Jego żywotność kończy się tylko wtedy, gdy wywołasz ich usunięcie . Jeśli o tym zapomnisz, te obiekty nigdy nie kończą swojego życia. A obiekty klas, które definiują konstruktor zadeklarowany przez użytkownika, nie będą miały wywoływanych destruktorów. Obiekty o dynamicznym czasie trwania wymagają ręcznej obsługi ich okresu istnienia i skojarzonego zasobu pamięci. Biblioteki istnieją po to, aby ułatwić z nich korzystanie. Jawne wyrzucanie elementów bezużytecznych dla określonych obiektów można ustalić za pomocą inteligentnego wskaźnika:

int main() {
    shared_ptr<string> s(new string);
    foo(s);
}

void foo(shared_ptr<string> s) {
    cout << s->size();
}

Nie musisz przejmować się wywołaniem funkcji delete: udostępniony ptr robi to za Ciebie, jeśli ostatni wskaźnik, który odwołuje się do obiektu, znajdzie się poza zakresem. Sam udostępniony plik ptr ma automatyczny czas trwania. Więc jego żywotność jest automatycznie zarządzana, co pozwala mu sprawdzić, czy powinien usunąć wskazany dynamiczny obiekt w swoim destruktorze. Aby uzyskać informacje o shared_ptr, zobacz dokumenty boost: http://www.boost.org/doc/libs/1_37_0/libs/smart_ptr/shared_ptr.htm


39

Zostało to powiedziane obszernie, podobnie jak „krótka odpowiedź”:

  • zmienna statyczna (klasa)
    żywotność = czas działania programu (1)
    widoczność = określona przez modyfikatory dostępu (prywatna / chroniona / publiczna)

  • zmienna statyczna (zasięg globalny)
    żywotność = czas działania programu (1)
    widoczność = jednostka kompilacji, w której jest tworzona instancja (2)


  • żywotność zmiennej stosu = zdefiniowana przez Ciebie (nowa do usunięcia)
    widoczność = zdefiniowana przez Ciebie (cokolwiek przypiszesz wskaźnik)


  • widoczność zmiennej stosu = od deklaracji do wyjścia
    z zakresu lifetime = od deklaracji do zakończenia deklarowania zakresu


(1) dokładniej: od inicjalizacji do deinicjalizacji jednostki kompilacji (tj. Pliku C / C ++). Kolejność inicjalizacji jednostek kompilacji nie jest określona przez normę.

(2) Uwaga: jeśli utworzysz instancję zmiennej statycznej w nagłówku, każda jednostka kompilacji otrzyma własną kopię.


5

Jestem pewien, że wkrótce jeden z pedantów udzieli lepszej odpowiedzi, ale główną różnicą jest prędkość i rozmiar.

Stos

Znacznie szybsze przydzielanie. Odbywa się to w O (1), ponieważ jest przydzielane podczas konfigurowania ramki stosu, więc jest zasadniczo wolne. Wadą jest to, że jeśli zabraknie miejsca w stosie, zostaniesz pozbawiony kości. Możesz dostosować rozmiar stosu, ale IIRC masz ~ 2 MB do gry. Ponadto, gdy tylko wyjdziesz z tej funkcji, wszystko na stosie zostanie wyczyszczone. Dlatego odwołanie się do tego później może być problematyczne. (Wskaźniki stosu przydzielonych obiektów prowadzą do błędów).

Sterta

Znacznie wolniejsze przydzielanie. Ale masz GB do zabawy i wskaż.

Śmieciarz

Moduł odśmiecania pamięci to kod działający w tle i zwalniający pamięć. Kiedy alokujesz pamięć na stercie, bardzo łatwo zapomnieć o jej zwolnieniu, co jest znane jako wyciek pamięci. Z biegiem czasu ilość pamięci używanej przez aplikację rośnie i powiększa się, aż do awarii. Okresowe zwalnianie pamięci przez moduł odśmiecania pamięci, której już nie potrzebujesz, pomaga wyeliminować tę klasę błędów. Oczywiście ma to swoją cenę, ponieważ śmieciarz spowalnia wszystko.


3

Jakie są problemy ze statowaniem i stosem?

Problem z alokacją „statyczną” polega na tym, że alokacja jest dokonywana w czasie kompilacji: nie można jej użyć do przydzielenia zmiennej liczby danych, których liczba nie jest znana do czasu wykonania.

Problem z alokacją na „stosie” polega na tym, że alokacja jest niszczona, gdy tylko podprogram, który ją wykonuje, powróci.

Mógłbym napisać całą aplikację bez przydzielania zmiennych w stercie?

Być może, ale nie nietrywialna, normalna, duża aplikacja (ale tak zwane programy „osadzone” można napisać bez stosu, używając podzbioru C ++).

Co robi odśmiecacz?

Ciągle obserwuje dane („zaznaczaj i usuwaj”), aby wykryć, kiedy aplikacja już się do nich nie odwołuje. Jest to wygodne dla aplikacji, ponieważ aplikacja nie musi zwalniać danych ... ale moduł odśmiecania pamięci może być kosztowny obliczeniowo.

Odśmiecacze nie są typową funkcją programowania w C ++.

Co mógłbyś zrobić samodzielnie manipulując pamięcią, czego nie mógłbyś zrobić używając tego garbage collectora?

Poznaj C ++ mechanizmy deterministycznego zwalniania pamięci:

  • „statyczny”: nigdy nie zwalniany
  • „stos”: gdy tylko zmienna „wyjdzie poza zakres”
  • `` sterta '': kiedy wskaźnik jest usuwany (jawnie usuwany przez aplikację lub niejawnie usuwany w ramach jakiegoś lub innego podprogramu)

1

Alokacja pamięci stosu (zmienne funkcyjne, zmienne lokalne) może być problematyczna, gdy twój stos jest zbyt „głęboki” i przepełnia się pamięć dostępną do alokacji stosu. Sterta jest przeznaczona dla obiektów, do których należy uzyskać dostęp z wielu wątków lub przez cały cykl życia programu. Możesz napisać cały program bez używania sterty.

Możesz dość łatwo wyciekać pamięć bez garbage collectora, ale możesz także dyktować, kiedy obiekty i pamięć zostaną zwolnione. Napotkałem problemy z Javą, gdy uruchamia ona GC i mam proces w czasie rzeczywistym, ponieważ GC jest wyłącznym wątkiem (nic innego nie może działać). Więc jeśli wydajność jest krytyczna i możesz zagwarantować, że nie ma przecieków, nieużywanie GC jest bardzo pomocne. W przeciwnym razie po prostu nienawidzisz życia, gdy aplikacja zużywa pamięć i musisz wyśledzić źródło wycieku.


1

A co jeśli twój program nie wie z góry, ile pamięci ma przydzielić (stąd nie możesz użyć zmiennych stosu). Powiedzmy, że listy połączone, mogą rosnąć, nie wiedząc z góry, jaki jest ich rozmiar. Dlatego alokowanie na stercie ma sens w przypadku listy połączonej, gdy nie wiesz, ile elementów zostanie do niej wstawionych.


0

Zaletą GC w niektórych sytuacjach jest irytacja w innych; poleganie na GC zachęca do nie myślenia o tym zbyt wiele. Teoretycznie czeka na okres bezczynności lub do momentu, gdy będzie to absolutnie konieczne, kiedy to wykradnie przepustowość i spowoduje opóźnienie odpowiedzi w Twojej aplikacji.

Ale nie musisz „o tym nie myśleć”. Podobnie jak w przypadku wszystkiego innego w aplikacjach wielowątkowych, kiedy możesz ustąpić, możesz ustąpić. Na przykład w .Net można zażądać GC; robiąc to, zamiast rzadziej działającego dłużej GC, możesz mieć częstsze krótsze działające GC i rozłożyć opóźnienie związane z tym narzutem.

Ale to pokonuje główną atrakcyjność GC, która wydaje się być „zachęcana, aby nie musieć dużo o tym myśleć, ponieważ jest ona automatyczna”.

Jeśli po raz pierwszy zostałeś narażony na programowanie, zanim GC stał się powszechny i ​​czułeś się komfortowo z malloc / free i new / delete, może nawet być tak, że uznasz GC za trochę irytujące i / lub nieufne (jak ktoś może być nieufny) optymalizacja ”, która ma burzliwą historię). Wiele aplikacji toleruje losowe opóźnienia. Ale w przypadku aplikacji, które tego nie robią, gdzie losowe opóźnienia są mniej akceptowalne, typową reakcją jest unikanie środowisk GC i poruszanie się w kierunku czysto niezarządzanego kodu (lub nie daj Boże, dawno umierającej sztuki, języka asemblera).

Miałem tu pewnego letniego studenta, stażystę, bystre dziecko, którego odstawiono od piersi na GC; był tak przywiązany do wyższości GC, że nawet programując w niezarządzanym C / C ++ odmówił przestrzegania modelu malloc / free new / delete, ponieważ cytuj: „nie powinieneś tego robić w nowoczesnym języku programowania”. I wiesz? W przypadku małych, krótko działających aplikacji rzeczywiście można to uciec, ale nie w przypadku długo działających wydajnych aplikacji.


0

Stos to pamięć przydzielana przez kompilator, kiedy kompilujemy program, domyślnie kompilator przydziela trochę pamięci z systemu operacyjnego (możemy zmienić ustawienia z ustawień kompilatora w twoim IDE), a system operacyjny jest tym, który daje ci pamięć, to zależy na wielu dostępnej pamięci w systemie i wielu innych rzeczach, a przychodząca do stosu pamięć jest alokowana kiedy deklarujemy zmienną, którą kopiują (odwołuj się do formalnych) te zmienne są umieszczane na stosie, domyślnie przestrzegają pewnych konwencji nazewnictwa, zgodnie z jego CDECL w studiach Visual np. notacja wrostkowa: c = a + b; Pchanie stosu odbywa się od prawej do lewej PUSHING, b do stosu, operator, a do stosu i wynik tych i, ec do stosu. W notacji wstępnej: = + cab Tutaj wszystkie zmienne są umieszczane na stosie 1 (od prawej do lewej), a następnie wykonywana jest operacja. Ta pamięć przydzielona przez kompilator jest naprawiona. Więc załóżmy, że 1MB pamięci jest przydzielone naszej aplikacji, powiedzmy, że zmienne używają 700kb pamięci (wszystkie lokalne zmienne są umieszczane na stosie, chyba że są przydzielane dynamicznie), więc pozostała pamięć 324kb jest przydzielana do sterty. A ten stos ma krótszy czas życia, gdy zakres funkcji się kończy, te stosy są czyszczone.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.