Czy może być bardziej wydajne dla systemów, aby pozbyć się stosów i po prostu użyć Sterty do zarządzania pamięcią?

14

Wydaje mi się, że wszystko, co można zrobić za pomocą stosu, można zrobić za pomocą stosu, ale nie wszystko, co można zrobić za pomocą stosu, można wykonać za pomocą stosu. Czy to jest poprawne? Zatem dla uproszczenia, a nawet jeśli stracimy trochę wydajności przy niektórych obciążeniach, czy nie lepiej byłoby po prostu użyć jednego standardu (tj. Sterty)?

Pomyśl o kompromisie między modułowością a wydajnością. Wiem, że nie jest to najlepszy sposób na opisanie tego scenariusza, ale ogólnie wydaje się, że prostota zrozumienia i projektowania może być lepszą opcją, nawet jeśli istnieje potencjał do lepszej wydajności.

memory

— Mroczny Templariusz
źródło

1

W C i C ++ musisz jawnie zwolnić pamięć przydzieloną na stercie. To nie jest prostsze.

— user16764

Użyłem implementacji C #, gdy profilowanie ujawniło, że obiekty stosu zostały przydzielone w obszarze przypominającym stertę ze strasznym odśmiecaniem. Moje rozwiązanie? Przenieś wszystko, co możliwe (np. Zmienne pętli, zmienne tymczasowe itp.) Do trwałej pamięci sterty. Sprawił, że program zjadł 10 razy więcej pamięci RAM i działał z prędkością 10 razy większą.

— imallett

@IanMallett: Nie rozumiem twojego wyjaśnienia problemu i rozwiązania. Czy masz gdzieś link z dodatkowymi informacjami? Zazwyczaj przydziały oparte na stosie są szybsze.

— Frank Hileman

@FrankHileman podstawowy problem polegał na tym: implementacja używanego przeze mnie języka C # miała bardzo niską prędkość zbierania śmieci. „Rozwiązaniem” było spowodowanie, aby wszystkie zmienne były trwałe, aby w czasie wykonywania nie miały miejsca żadne operacje pamięci. Jakiś czas temu napisałem opinię na temat rozwoju C # / XNA, która również omawia niektóre konteksty.

— imallett

@IanMallett: dziękuję. Jako były programista C / C ++, który obecnie używa głównie języka C #, moje doświadczenie jest zupełnie inne. Uważam, że biblioteki są największym problemem. Wygląda na to, że platforma XBox360 została na wpół wypalona dla programistów .net. Zwykle, gdy mam problemy z GC, przełączam się na pule. To pomaga.

— Frank Hileman

30

Sterty są złe w szybkim przydzielaniu i zwalnianiu pamięci. Jeśli chcesz pobrać wiele niewielkich ilości pamięci przez ograniczony czas, kupa nie jest najlepszym wyborem. Stos z bardzo prostym algorytmem alokacji / dezalokacji, naturalnie przoduje w tym (nawet bardziej, jeśli jest wbudowany w sprzęt), dlatego ludzie używają go do przekazywania argumentów do funkcji i przechowywania zmiennych lokalnych - najbardziej ważnym 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.

Całkowite pozbycie się stosu w celu uproszczenia języka programowania jest niewłaściwym sposobem IMO - lepszym rozwiązaniem byłoby wyodrębnienie różnic, pozwól kompilatorowi dowiedzieć się, jakiego rodzaju pamięci użyć, podczas gdy programista składa razem wyższe- konstrukcje poziomów, które są bliższe myśleniu ludzi - i tak naprawdę robią to języki wysokiego poziomu, takie jak C #, Java, Python itp. Oferują one prawie identyczną składnię dla obiektów przydzielanych na stercie i operacji podstawowych przydzielanych na stosie („typy referencyjne” vs. „typy wartości” w języku .NET), albo w pełni przejrzyste, albo z kilkoma różnicami funkcjonalnymi, które należy zrozumieć, aby używać języka poprawnie (ale tak naprawdę nie musisz wiedzieć, jak stos i stos działają wewnętrznie).

— tdammers
źródło

2

WOW TO BYŁO DOBRE :) Naprawdę zwięzłe i pouczające dla początkującego!

— Dark Templar,

1

Na wielu procesorach stos jest obsługiwany sprzętowo, co jest problemem poza językiem, ale odgrywa dużą rolę w czasie wykonywania.

— Patrick Hughes,

@Patrick Hughes: Tak, ale Kupa również znajduje się w sprzęcie, prawda?

— Dark Templar,

@Dark Prawdopodobnie Patrick chce powiedzieć, że architektury takie jak x86 mają specjalne rejestry do zarządzania stosem oraz specjalne instrukcje dotyczące umieszczania lub usuwania czegoś na / ze stosu. To sprawia, że jest dość szybki.

— FUZxxl,

3

@Donal Fellows: All true. Chodzi o to, że zarówno stosy, jak i stosy mają swoje mocne i słabe strony, a użycie ich odpowiednio zapewni najbardziej wydajny kod.

— tdammers

8

Mówiąc najprościej, stos nie jest odrobiną wydajności. Jest setki lub tysiące razy szybszy niż kupa. Ponadto większość nowoczesnych maszyn ma obsługę sprzętową stosu (jak x86) i tej funkcji sprzętowej, np. Stosu wywołań, nie można usunąć.

— DeadMG
źródło

Co masz na myśli, mówiąc, że nowoczesne maszyny mają wsparcie sprzętowe dla stosu? Sam stos jest już w sprzęcie, prawda?

— Dark Templar,

1

x86 ma specjalne rejestry i instrukcje postępowania ze stosem. x86 nie obsługuje stert - takie rzeczy są tworzone przez system operacyjny.

— Pubby

8

Nie

Obszar stosu w C ++ jest niezwykle szybki w porównaniu. Podejrzewam, że żaden doświadczony programista C ++ nie byłby otwarty na wyłączenie tej funkcjonalności.

Dzięki C ++ masz wybór i masz kontrolę. Projektanci nie byli szczególnie skłonni do wprowadzania funkcji, które zwiększyły czas wykonania lub przestrzeń.

Korzystam z tego wyboru

Jeśli chcesz zbudować bibliotekę lub program, który wymaga dynamicznego przydzielania każdego obiektu, możesz to zrobić za pomocą C ++. Wykonałby się stosunkowo wolno, ale można by wtedy mieć taką „modułowość”. Dla reszty z nas modułowość jest zawsze opcjonalna, wprowadzaj ją w razie potrzeby, ponieważ oba są wymagane do dobrych / szybkich wdrożeń.

Alternatywy

Istnieją inne języki, które wymagają utworzenia pamięci dla każdego obiektu na stercie; jest dość powolny, tak że kompromituje projekty (programy ze świata rzeczywistego) w sposób gorszy niż konieczność uczenia się obu (IMO).

Oba są ważne, a C ++ zapewnia efektywne wykorzystanie mocy w obu scenariuszach. Powiedziawszy to, język C ++ może nie być idealny do twojego projektu, jeśli te czynniki w twoim OP są dla ciebie ważne (na przykład, przeczytaj o językach wyższego poziomu).

— justin
źródło

Stos jest w rzeczywistości tej samej prędkości co stos, ale nie ma specjalistycznej obsługi sprzętowej do alokacji. Z drugiej strony istnieją sposoby na znaczne przyspieszenie stosów (z zastrzeżeniem szeregu warunków, które czynią z nich techniki wyłącznie dla ekspertów).

— Donal Fellows

@DonalFellows: Obsługa sprzętu dla stosów jest nieistotna. Ważne jest, aby wiedzieć, że za każdym razem, gdy coś zostanie wydane, można zwolnić wszystko, co zostało po nim wydane. Niektóre języki programowania nie mają stosów, które mogą niezależnie uwalniać obiekty, ale zamiast tego mają tylko metodę „wszystko wolne przydzielane po”.

— supercat

6

Zatem dla uproszczenia, a nawet jeśli stracimy trochę wydajności przy niektórych obciążeniach, czy nie lepiej byłoby po prostu użyć jednego standardu (tj. Sterty)?

W rzeczywistości wydajność może być znaczna!

Jak zauważyli inni, stosy są niezwykle wydajną strukturą do zarządzania danymi, która jest zgodna z zasadami LIFO (ostatni na pierwszy raz). Alokacja / zwalnianie pamięci na stosie jest zwykle tylko zmianą rejestru w CPU. Zmiana rejestru jest prawie zawsze jedną z najszybszych operacji, jakie procesor może wykonać.

Sterta jest zwykle dość złożoną strukturą danych, a przydzielanie / zwalnianie pamięci zajmie wiele instrukcji, aby wykonać całą powiązaną księgowość. Co gorsza, w typowych implementacjach każde wywołanie do pracy ze stertą może spowodować wywołanie systemu operacyjnego. Wywołania systemu operacyjnego są bardzo czasochłonne! Program zwykle musi przełączać się z trybu użytkownika do trybu jądra, a gdy to się stanie, system operacyjny może zdecydować, że inne programy mają pilniejsze potrzeby i że Twój program będzie musiał poczekać.

— Charles E. Grant
źródło

5

Simula wykorzystała kupę do wszystkiego. Umieszczenie wszystkiego na stosie zawsze wywołuje jeszcze jeden poziom pośredni dla zmiennych lokalnych, a to wywiera dodatkową presję na Garbage Collector (musisz wziąć pod uwagę, że Garbage Collectors naprawdę wtedy zasysali). Po części dlatego Bjarne wynalazł C ++.

— fredoverflow
źródło

Więc w zasadzie C ++ używa tylko sterty?

— Dark Templar,

2

@Dark: Co? Nie. Brak stosu w Simuli był inspiracją do zrobienia tego lepiej.

— fredoverflow

Ach, rozumiem co masz teraz na myśli! Dzięki +1 :)

— Mroczny Templariusz

3

Stosy są niezwykle wydajne w przypadku danych LIFO, takich jak na przykład metadane związane z wywołaniami funkcji. Stos wykorzystuje również nieodłączne cechy konstrukcyjne procesora. Ponieważ wydajność na tym poziomie ma fundamentalne znaczenie dla niemal wszystkiego innego w procesie, przyjęcie tego „małego” trafienia na tym poziomie będzie się bardzo rozpowszechniać. Ponadto pamięć sterty może być przenoszona przez system operacyjny, co byłoby śmiertelnie niebezpieczne dla stosów. Chociaż stos może być zaimplementowany w stercie, wymaga narzutu, który wpłynie dosłownie na każdy kawałek procesu na najbardziej szczegółowym poziomie.

— Kylben
źródło

2

„efektywny” pod względem pisania kodu, ale na pewno nie pod względem wydajności oprogramowania. Przydziały stosu są zasadniczo wolne (potrzeba tylko kilku instrukcji maszyny, aby przenieść wskaźnik stosu i zarezerwować miejsce na stosie dla zmiennych lokalnych).

Ponieważ alokacja stosu nie zajmuje prawie czasu, alokacja nawet na bardzo wydajnym stosie będzie 100k (jeśli nie 1M +) razy wolniejsza.

Teraz wyobraź sobie, ile lokalnych zmiennych i innych struktur danych używa typowa aplikacja. Każde małe „i”, którego używasz jako licznika pętli, jest przydzielane milion razy wolniej.

Pewnie, jeśli sprzęt jest wystarczająco szybki, możesz napisać aplikację, która używa tylko sterty. Ale teraz wyobrażam sobie, jaką aplikację możesz napisać, jeśli skorzystasz ze sterty i użyjesz tego samego sprzętu.

— DXM
źródło

Kiedy mówisz „wyobraź sobie, ile zmiennych lokalnych i innych struktur danych używa typowa aplikacja”, do jakich innych struktur danych masz na myśli?

— Dark Templar,

1

Czy wartości „100k” i „1M +” są w jakiś sposób naukowe? Czy to tylko sposób na powiedzenie „dużo”?

— Bruno Reis

@Bruno - IMHO, których użyłem liczb 100K i 1M, jest w rzeczywistości zachowawczym szacunkiem, aby udowodnić, że ma rację. Jeśli znasz VS i C ++, napisz program, który przydziela 100 bajtów na stosie, i napisz taki, który przydziela 100 bajtów na stosie. Następnie przejdź do widoku demontażu i po prostu policz liczbę instrukcji montażu przy każdej alokacji. Operacje sterty to zwykle kilka wywołań funkcji do biblioteki DLL systemu Windows, są segmenty i listy połączone, a następnie istnieje algorytm koalescencji i inne. Dzięki stosowi może sprowadzać się do jednej instrukcji montażu „add esp, 100” ...

— DXM

2

„100k (jeśli nie 1M +) razy wolniej”? To trochę przesadzone. Niech będą dwa rzędy wielkości wolniejsze, może trzy, ale to wszystko. Przynajmniej mój Linux jest w stanie wykonać 100 mln przydziałów sterty (+ niektóre otaczające instrukcje) na rdzeniu i5 w mniej niż 6 sekund, co nie może być więcej niż kilkaset instrukcji na przydział - w rzeczywistości jest to prawie na pewno mniej. Jeśli jest o sześć rzędów wielkości wolniejszy niż stos, jest coś poważnie nie tak z implementacją sterty systemu operacyjnego. Pewnie, że w Windowsie jest wiele błędów, ale to ...

— lewo około

1

moderatorzy prawdopodobnie zabiją cały ten wątek komentarza. Więc oto umowa, przyznaję, że rzeczywiste liczby zostały wyciągnięte z mojej ...., ale zgódźmy się, że czynnik jest naprawdę, bardzo duży i nie rób więcej komentarzy :)

— DXM,

2

Być może interesuje Cię „Śmieci jest szybkie, ale stos jest szybszy”.

http://dspace.mit.edu/bitstream/handle/1721.1/6622/AIM-1462.ps.Z

Jeśli przeczytam go poprawnie, ci faceci zmodyfikowali kompilator C, aby przydzielić „stos ramek” na stosie, a następnie za pomocą odśmiecania pamięci oddzielić ramki zamiast usuwać stos.

„Ramki stosu” przydzielone stosowi zdecydowanie przewyższają „ramki stosu” przydzielone do stosu.

— Bruce Ediger
źródło

1

Jak stos wywołań będzie działał na stercie? Zasadniczo musiałbyś przydzielić stos na stosie w każdym programie, więc dlaczego nie masz sprzętu OS + dla ciebie?

Jeśli chcesz, aby rzeczy były naprawdę proste i wydajne, po prostu daj użytkownikowi swoją pamięć i pozwól sobie z tym poradzić. Oczywiście nikt nie chce wdrażać wszystkiego samodzielnie i dlatego mamy stos i stos.

— Pubby
źródło

Ściśle mówiąc, „stos wywołań” nie jest wymaganą funkcją środowiska wykonawczego języka programowania. np. Prosta implementacja leniwie ocenianego języka funkcjonalnego poprzez redukcję wykresów (którą zakodowałem) nie ma stosu wywołań. Ale stos wywołań jest bardzo powszechnie użyteczną i powszechnie stosowaną techniką, zwłaszcza że nowoczesne procesory zakładają, że go używasz i są zoptymalizowane pod kątem jego wykorzystania.

— Ben

@Ben - chociaż prawdą (i dobrą rzeczą) jest abstrakcyjne rzeczy, takie jak przydział pamięci z języka, nie zmienia to obecnie dominującej architektury komputerowej. W związku z tym Twój kod redukcji wykresu nadal będzie korzystał ze stosu podczas pracy - lubisz go, czy nie.

— Ingo

@Ingo Nie w żadnym sensownym znaczeniu. Jasne, system operacyjny zainicjuje sekcję pamięci tradycyjnie zwaną „stosem” i wskaże do niej rejestr. Ale funkcje w języku źródłowym nie są przedstawiane jako ramki stosu w kolejności wywołań. Wykonywanie funkcji jest w całości reprezentowane przez manipulowanie strukturami danych na stercie. Nawet bez użycia optymalizacji ostatniego połączenia nie można „przepełnić stosu”. Właśnie to mam na myśli, gdy mówię, że w stosie wywołań nie ma nic fundamentalnego.

— Ben

Nie mówię o funkcjach języka źródłowego, ale o funkcjach interpretera (lub cokolwiek innego), które faktycznie dokonują redukcji wykresu. Będą potrzebować stosu. Jest to oczywiste, ponieważ współczesny sprzęt nie redukuje wykresów. W związku z tym twój algorytm redukcji wykresu jest ostatecznie odwzorowany na odę maszyny i założę się, że są wśród nich wywołania podprogramów. CO BYŁO DO OKAZANIA.

— Ingo

1

Wymagane są zarówno stos, jak i stos. Są używane w różnych sytuacjach, na przykład:

Przydział sterty ma takie ograniczenie, że sizeof (a [0]) == sizeof (a [1])
Przydział stosu ma ograniczenie polegające na tym, że sizeof (a) jest stałą czasową kompilacji
Przydział sterty może wykonywać pętle, wykresy itp. Złożone struktury danych
Przydział stosu może wykonywać drzewa o rozmiarach kompilacyjnych
Sterta wymaga śledzenia własności
Alokacja i zwalnianie stosu odbywa się automatycznie
Pamięć sterty może być łatwo przekazywana z jednego zakresu do drugiego za pomocą wskaźników
Pamięć stosu jest lokalna dla każdej funkcji, a obiekty muszą zostać przeniesione do górnego zakresu, aby przedłużyć ich żywotność (lub przechowywane w obiektach zamiast w funkcjach składowych)
Sterty są szkodliwe dla wydajności
Układanie jest dość szybkie
Obiekty sterty są zwracane z funkcji za pośrednictwem wskaźników przejmujących własność. Lub shared_ptrs.
Obiekty stosu są zwracane z funkcji przez odwołania, które nie przejmują własności.
Kupa wymaga dopasowania każdego nowego z poprawnym rodzajem usuwania lub usuwania []
Obiekty stosu używają list inicjalizacji RAII i konstruktora
Obiekty sterty mogą być inicjalizowane w dowolnym punkcie funkcji i nie mogą używać parametrów konstruktora
Obiekty stosu używają parametrów konstruktora do inicjalizacji
Sterta używa tablic, a rozmiar tablicy może się zmieniać w czasie wykonywania
Stos jest przeznaczony dla pojedynczych obiektów, a rozmiar jest ustalany na czas kompilacji

Zasadniczo mechanizmów nie można w ogóle porównać, ponieważ tak wiele szczegółów jest różnych. Jedyną wspólną cechą jest to, że oboje w jakiś sposób radzą sobie z pamięcią.

— tp1
źródło

1

Nowoczesne komputery mają kilka warstw pamięci podręcznej oraz duży, ale wolny system pamięci głównej. Można uzyskać dziesiątki dostępów do najszybszej pamięci podręcznej w czasie wymaganym do odczytania lub zapisu jednego bajtu z głównego systemu pamięci. Zatem dostęp do jednej lokalizacji tysiąc razy jest znacznie szybszy niż dostęp do 1000 (lub nawet 100) niezależnych lokalizacji raz. Ponieważ większość aplikacji wielokrotnie przydziela i zwalnia małe ilości pamięci w górnej części stosu, lokalizacje na górze stosu są wykorzystywane i ponownie wykorzystywane ogromną ilość, tak że ogromna większość (99% + w typowej aplikacji) dostęp do stosu może być obsługiwany przy użyciu pamięci podręcznej.

Natomiast jeśli aplikacja będzie wielokrotnie tworzyć i porzucać obiekty sterty w celu przechowywania informacji o kontynuacji, każda wersja każdego obiektu stosu, który kiedykolwiek został utworzony, musiałaby zostać zapisana w pamięci głównej. Nawet jeśli ogromna większość takich obiektów byłaby całkowicie bezużyteczna, zanim procesor zechciałby ponownie przetworzyć strony pamięci podręcznej, w których zaczęły, procesor nie byłby w stanie tego wiedzieć. W rezultacie procesor musiałby tracić dużo czasu na powolne zapisywanie w pamięci bezużytecznych informacji. Nie do końca przepis na szybkość.

Inną rzeczą do rozważenia jest to, że w wielu przypadkach warto wiedzieć, że odwołanie do obiektu przekazane do procedury nie będzie używane po jej zakończeniu. Jeśli parametry i zmienne lokalne są przekazywane przez stos, a kontrola kodu procedury ujawnia, że nie zachowuje ona kopii przekazywanego odwołania, wówczas kod wywołujący procedurę może być pewien, że jeśli nie będzie zewnętrznego odwołania do obiekt istniał przed wywołaniem, żaden nie będzie istniał później. Natomiast jeśli parametry byłyby przekazywane przez obiekty sterty, pojęcia takie jak „po zwróceniu procedury” stają się nieco bardziej mgliste, ponieważ gdyby kod zachował kopię kontynuacji, procedura mogłaby „wrócić” więcej niż raz po pojedyncze połączenie.

— supercat
źródło