Co jest szybsze: Przydział stosu lub Przydział sterty

To pytanie może zabrzmieć dość elementarnie, ale jest to debata z innym deweloperem, z którym współpracuję.

Starałem się układać w stosy rzeczy tam, gdzie mogłem, zamiast stawiać je. Mówił do mnie i patrzył mi przez ramię i stwierdził, że nie jest to konieczne, ponieważ są one tak samo mądre pod względem wydajności.

Zawsze miałem wrażenie, że powiększanie stosu było stałym czasem, a wydajność alokacji sterty zależała od bieżącej złożoności sterty zarówno dla alokacji (znalezienie dziury o odpowiednim rozmiarze), jak i alokacji (zwijania dziur w celu zmniejszenia fragmentacji, ponieważ wiele standardowych implementacji bibliotek wymaga czasu, aby to zrobić podczas usuwania, jeśli się nie mylę).

Uderza mnie to jako coś, co prawdopodobnie byłoby bardzo zależne od kompilatora. W szczególności do tego projektu używam kompilatora Metrowerks dla architektury PPC . Wgląd w tę kombinację byłby najbardziej pomocny, ale ogólnie w przypadku GCC i MSVC ++, co się dzieje? Czy przydział sterty nie jest tak wydajny jak przydział sterty? Czy nie ma różnicy? Czy różnice są tak małe, że staje się bezcelowa mikrooptymalizacja.

Alokacja stosu jest znacznie szybsza, ponieważ tak naprawdę wszystko przesuwa wskaźnik stosu. Korzystając z pul pamięci, można uzyskać porównywalną wydajność dzięki alokacji sterty, ale wiąże się to z niewielką dodatkową złożonością i własnymi problemami.

Ponadto stos kontra stos to nie tylko kwestia wydajności; mówi również wiele o oczekiwanym okresie użytkowania obiektów.

Układanie jest znacznie szybsze. Dosłownie używa tylko jednej instrukcji na większości architektur, w większości przypadków, np. Na x86:

sub esp, 0x10

(To przesuwa wskaźnik stosu w dół o 0x10 bajtów, a tym samym „przydziela” te bajty do wykorzystania przez zmienną.)

Oczywiście rozmiar stosu jest bardzo, bardzo skończony, ponieważ szybko przekonasz się, czy nadużyjesz przydzielania stosu lub spróbujesz wykonać rekurencję :-)

Ponadto nie ma powodu, aby optymalizować wydajność kodu, który nie wymaga go weryfikowalnie, na przykład poprzez profilowanie. „Przedwczesna optymalizacja” często powoduje więcej problemów, niż jest to warte.

Moja ogólna zasada: jeśli wiem, że będę potrzebować danych w czasie kompilacji , a ich rozmiar nie przekracza kilkuset bajtów, przydzielam je stosowi. W przeciwnym razie przydzielam ją do kupy.

Szczerze mówiąc, napisanie programu do porównania wydajności jest banalne:

#include <ctime>
#include <iostream>

namespace {
    class empty { }; // even empty classes take up 1 byte of space, minimum
}

int main()
{
    std::clock_t start = std::clock();
    for (int i = 0; i < 100000; ++i)
        empty e;
    std::clock_t duration = std::clock() - start;
    std::cout << "stack allocation took " << duration << " clock ticks\n";
    start = std::clock();
    for (int i = 0; i < 100000; ++i) {
        empty* e = new empty;
        delete e;
    };
    duration = std::clock() - start;
    std::cout << "heap allocation took " << duration << " clock ticks\n";
}

Mówi się, że głupia konsekwencja jest hobgoblinem małych umysłów . Najwyraźniej optymalizujące kompilatory są hobgoblinami wielu umysłów programistów. Ta dyskusja znajdowała się u dołu odpowiedzi, ale najwyraźniej ludziom nie przeszkadza czytanie tak daleko, więc przenoszę ją tutaj, aby uniknąć pytań, na które już odpowiedziałem.

Kompilator optymalizujący może zauważyć, że ten kod nic nie robi i może wszystko zoptymalizować. Zadaniem optymalizatora jest robienie takich rzeczy, a walka z optymistą jest głupcem.

Polecam skompilowanie tego kodu z wyłączoną optymalizacją, ponieważ nie ma dobrego sposobu na oszukanie każdego aktualnie używanego optymalizatora lub takiego, który będzie używany w przyszłości.

Każdy, kto włączy optymalizator, a następnie narzeka na jego walkę, powinien zostać publicznie wyszydzony.

Gdybym dbał o precyzję nanosekundową, nie użyłbym tego std::clock(). Gdybym chciał opublikować wyniki pracy doktorskiej, zrobiłbym o tym większy interes i prawdopodobnie porównałbym GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC i inne kompilatory. Obecnie alokacja sterty trwa setki razy dłużej niż alokacja stosu i nie widzę nic użytecznego w dalszym badaniu pytania.

Optymalizator ma za zadanie pozbyć się kodu, który testuję. Nie widzę żadnego powodu, aby nakazać optymalizatorowi uruchomienie, a następnie spróbować oszukać optymalizator, aby faktycznie nie optymalizował. Ale gdybym zobaczył w tym wartość, zrobiłbym co najmniej jedną z następujących czynności:

1. Dodaj element danych emptyi uzyskaj dostęp do tego elementu danych w pętli; ale jeśli kiedykolwiek czytam tylko element danych, optymalizator może stale składać i usuwać pętlę; jeśli kiedykolwiek piszę tylko do elementu danych, optymalizator może pominąć wszystko oprócz ostatniej iteracji pętli. Ponadto pytanie nie brzmiało: „alokacja stosu i dostęp do danych vs. alokacja sterty i dostęp do danych”.

2. Deklaracja e volatile, ale volatileczęsto jest niepoprawnie kompilowana (PDF).

3. Weź adres ewewnątrz pętli (i może przypisz go do zmiennej zadeklarowanej externi zdefiniowanej w innym pliku). Ale nawet w tym przypadku kompilator może zauważyć, że - przynajmniej na stosie - ezawsze będzie przydzielany pod tym samym adresem pamięci, a następnie będzie się składał tak jak w (1) powyżej. Otrzymuję wszystkie iteracje pętli, ale obiekt nigdy nie jest tak naprawdę przydzielany.

Poza oczywistym, test ten jest wadliwy, ponieważ mierzy zarówno przydział, jak i dezalokację, a pierwotne pytanie nie dotyczyło dezalokacji. Oczywiście zmienne przydzielone na stosie są automatycznie zwalniane na końcu zakresu, więc brak wywołania delete(1) wypaczy numery (dezalokacja stosu jest uwzględniona w liczbach dotyczących przydzielania stosu, więc sprawiedliwe jest jedynie zmierzenie zwolnienia stosu) i ( 2) spowodować dość zły wyciek pamięci, chyba że zachowamy odniesienie do nowego wskaźnika i zadzwonimy deletepo tym, jak zmierzymy czas.

Na moim komputerze, używając g ++ 3.4.4 w systemie Windows, dostaję „0 taktów zegara” dla alokacji stosu i sterty dla mniej niż 100000 przydziałów, a nawet wtedy dostaję „0 tyknięć zegara” dla alokacji stosu i „15 tyknięć zegara ”w celu przydzielenia sterty. Kiedy mierzę 10 000 000 alokacji, alokacja stosu zajmuje 31 tyknięć zegara, a alokacja sterty zajmuje 1562 tyknięć zegara.

Tak, kompilator optymalizujący może pomijać tworzenie pustych obiektów. Jeśli dobrze rozumiem, może nawet obejść całą pierwszą pętlę. Kiedy podniosłem liczbę iteracji do 10 000 000 alokacja stosu zajęła 31 tyknięć zegara, a alokacja sterty zajęła 1562 tyknięć zegara. Myślę, że można bezpiecznie powiedzieć, że bez polecenia g ++ optymalizacji pliku wykonywalnego, g ++ nie pomija konstruktorów.

Przez lata, odkąd to napisałem, preferencją w stosie przepełnienia stosu było publikowanie wydajności ze zoptymalizowanych kompilacji. Ogólnie myślę, że to prawda. Jednak nadal uważam, że głupio jest prosić kompilator o optymalizację kodu, gdy w rzeczywistości nie chcesz go optymalizować. Wydaje mi się, że bardzo przypomina płacenie za parkowanie samochodu, ale odmawia wydania kluczy. W tym konkretnym przypadku nie chcę, aby optymalizator działał.

Korzystanie z nieco zmodyfikowanej wersji testu porównawczego (w celu zajęcia się poprawnym punktem, że oryginalny program nie przydzielał czegoś na stosie za każdym razem przez pętlę) i kompilacja bez optymalizacji, ale połączenie z bibliotekami wydań (w celu zajęcia się poprawnym punktem, który nie przekazujemy nie chcę uwzględniać żadnego spowolnienia spowodowanego przez linkowanie do bibliotek debugowania):

#include <cstdio>
#include <chrono>

namespace {
    void on_stack()
    {
        int i;
    }

    void on_heap()
    {
        int* i = new int;
        delete i;
    }
}

int main()
{
    auto begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_stack();
    auto end = std::chrono::system_clock::now();

    std::printf("on_stack took %f seconds\n", std::chrono::duration<double>(end - begin).count());

    begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_heap();
    end = std::chrono::system_clock::now();

    std::printf("on_heap took %f seconds\n", std::chrono::duration<double>(end - begin).count());
    return 0;
}

wyświetla:

on_stack took 2.070003 seconds
on_heap took 57.980081 seconds

w moim systemie po kompilacji z linii poleceń cl foo.cc /Od /MT /EHsc .

Możesz nie zgodzić się z moim podejściem do uzyskania niezoptymalizowanej wersji. W porządku: nie krępuj się modyfikować benchmarku tak bardzo, jak chcesz. Po włączeniu optymalizacji otrzymuję:

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

Nie dlatego, że alokacja stosu jest w rzeczywistości natychmiastowa, ale dlatego, że każdy na wpół przyzwoity kompilator może zauważyć, że on_stacknie robi nic użytecznego i można go zoptymalizować. GCC na moim laptopie z Linuksem również zauważa, że on_heapnic nie robi, i optymalizuje go również:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

Interesującą rzeczą, której nauczyłem się o alokacji stosu i sterty na procesorze ksenonowym Xbox 360, która może również dotyczyć innych systemów wielordzeniowych, jest to, że alokacja na sterty powoduje wprowadzenie sekcji krytycznej, aby zatrzymać wszystkie inne rdzenie, aby alokacja nie konflikt. Tak więc, w wąskiej pętli, alokacja stosu była sposobem na uzyskanie tablic o stałej wielkości, ponieważ zapobiegała przeciągnięciom.

Może to być kolejne przyspieszenie do rozważenia, jeśli kodujesz dla wielordzeniowego / wieloprocesorowego, ponieważ alokacja stosu będzie widoczna tylko przez rdzeń, w którym działa funkcja zakresowa, i nie wpłynie to na żadne inne rdzenie / procesory.

Możesz napisać specjalny rozdzielacz sterty dla określonych rozmiarów obiektów, który jest bardzo wydajny. Jednak ogólne alokator sterty nie jest szczególnie wydajny.

Zgadzam się również z Torbjörn Gyllebring w sprawie oczekiwanego czasu życia obiektów. Słuszna uwaga!

Nie sądzę, aby alokacja stosu i alokacja stosu były ogólnie wymienne. Mam również nadzieję, że wydajność obu z nich jest wystarczająca do ogólnego użytku.

Zdecydowanie polecam w przypadku małych przedmiotów, w zależności od tego, który z nich jest bardziej odpowiedni dla zakresu przydziału. W przypadku dużych przedmiotów stos jest prawdopodobnie konieczny.

W 32-bitowych systemach operacyjnych, które mają wiele wątków, stos jest często raczej ograniczony (choć zwykle do co najmniej kilku MB), ponieważ przestrzeń adresowa musi zostać wykrojona i prędzej czy później jeden stos wątków przejdzie na inny. W systemach jednowątkowych (w każdym razie Linux glibc jednowątkowy) ograniczenie jest znacznie mniejsze, ponieważ stos może po prostu rosnąć i rosnąć.

W 64-bitowych systemach operacyjnych jest wystarczająca przestrzeń adresowa, aby stosy wątków były dość duże.

Zwykle alokacja stosu polega na odejmowaniu od rejestru wskaźnika stosu. To o wiele szybciej niż wyszukiwanie sterty.

Czasami alokacja stosu wymaga dodania strony pamięci wirtualnej. Dodanie nowej strony zerowanej pamięci nie wymaga odczytu strony z dysku, więc zwykle będzie to o wiele ton szybciej niż wyszukiwanie stosu (szczególnie jeśli część stosu została również stronicowana). W rzadkiej sytuacji, którą można skonstruować na takim przykładzie, akurat dostępna jest wystarczająca ilość miejsca w części sterty, która jest już w pamięci RAM, ale przydzielenie nowej strony dla stosu musi czekać na zapisanie innej strony na dysk. W tej rzadkiej sytuacji stos jest szybszy.

Oprócz przewagi wydajności rzędu wielkości nad alokacją sterty, alokacja stosu jest lepsza w przypadku długo działających aplikacji serwerowych. Nawet najlepiej zarządzane sterty ostatecznie stają się tak rozdrobnione, że wydajność aplikacji spada.

Stos ma ograniczoną pojemność, a stos nie. Typowy stos dla procesu lub wątku wynosi około 8 KB. Nie można zmienić rozmiaru po przydzieleniu.

Zmienna stosu jest zgodna z regułami określania zakresu, podczas gdy zmienna stosu nie. Jeśli wskaźnik instrukcji wykracza poza funkcję, wszystkie nowe zmienne powiązane z funkcją znikają.

Co najważniejsze, nie można z góry przewidzieć całego łańcucha wywołań funkcji. Tak więc przydział 200 bajtów z twojej strony może spowodować przepełnienie stosu. Jest to szczególnie ważne, jeśli piszesz bibliotekę, a nie aplikację.

Uważam, że żywotność ma kluczowe znaczenie i to, czy przydzielana rzecz musi być zbudowana w złożony sposób. Na przykład w modelowaniu opartym na transakcjach zwykle trzeba wypełnić i przekazać strukturę transakcji z kilkoma polami do funkcji operacyjnych. Spójrz na przykład na OSCI SystemC TLM-2.0.

Przydzielanie ich na stosie blisko wezwania do operacji powoduje zwykle ogromne koszty ogólne, ponieważ konstrukcja jest droga. Dobrym sposobem jest przydzielenie na stercie i ponowne użycie obiektów transakcji albo przez pule, albo prostą zasadę, taką jak: „ten moduł potrzebuje tylko jednego obiektu transakcji kiedykolwiek”.

Jest to wielokrotnie szybsze niż przydzielanie obiektu przy każdym wywołaniu operacji.

Powodem jest po prostu to, że obiekt ma kosztowną konstrukcję i dość długi okres użytkowania.

Powiedziałbym: spróbuj obu i zobacz, co działa najlepiej w twoim przypadku, ponieważ może to naprawdę zależeć od zachowania twojego kodu.

Prawdopodobnie największym problemem alokacji sterty w porównaniu z alokacją stosu jest to, że alokacja sterty w ogólnym przypadku jest operacją nieograniczoną, a zatem nie można jej użyć, gdy problemem jest czas.

W przypadku innych aplikacji, w których czas nie jest problemem, może to nie mieć większego znaczenia, ale jeśli dużo przydzielisz, wpłynie to na szybkość wykonywania. Zawsze staraj się używać stosu do krótkotrwałej i często alokowanej pamięci (na przykład w pętlach), a tak długo, jak to możliwe - przydziel alokację podczas uruchamiania aplikacji.

To nie jest alokacja stosu jsut, która jest szybsza. Wygrywasz także dużo, używając zmiennych stosu. Mają lepszą lokalizację odniesienia. Wreszcie dezalokacja jest również znacznie tańsza.

Alokacja stosu to kilka instrukcji, podczas gdy najszybszy znany mi alokator sterty rtos (TLSF) używa średnio rzędu 150 instrukcji. Również alokacje stosu nie wymagają blokady, ponieważ używają lokalnej pamięci wątków, co jest kolejną ogromną wygraną wydajności. Przydziały stosu mogą być więc 2-3 rzędy wielkości szybsze, w zależności od intensywności wielowątkowości twojego środowiska.

Ogólnie przydział sterty jest ostatecznością, jeśli zależy Ci na wydajności. Przydatną opcją pośrednią może być stały alokator puli, który jest również tylko kilkoma instrukcjami i ma bardzo mały narzut na alokację, więc jest świetny dla małych obiektów o stałym rozmiarze. Z drugiej strony działa tylko z obiektami o stałym rozmiarze, nie jest z natury bezpieczny dla wątków i ma problemy z fragmentacją bloków.

Problemy specyficzne dla języka C ++

Przede wszystkim nie istnieje tak zwany przydział „stosu” lub „stosu”, który jest wymagany przez C ++ . Jeśli mówisz o automatycznych obiektach w zakresach bloków, nie są one nawet „przydzielane”. (BTW, automatyczny czas przechowywania w C zdecydowanie NIE jest taki sam jak „przydzielony”; ten ostatni jest „dynamiczny” w języku C ++.) Dynamicznie przydzielana pamięć znajduje się w wolnym magazynie , niekoniecznie w „stercie”, chociaż ta ostatnia jest często (domyślną) implementacją .

Chociaż zgodnie z regułami semantycznymi abstrakcyjnych maszyn , obiekty automatyczne nadal zajmują pamięć, zgodna implementacja C ++ może zignorować ten fakt, gdy może udowodnić, że to nie ma znaczenia (gdy nie zmienia obserwowalnego zachowania programu). To zezwolenie jest udzielane przez regułę „jak gdyby” w ISO C ++, która jest również ogólną klauzulą ​​umożliwiającą zwykłe optymalizacje (aw ISO C istnieje prawie taka sama reguła). Oprócz zasady „tak, jak”, ISO C ++ ma również reguły wymuszania kopiiaby umożliwić pominięcie określonych dzieł obiektów. W ten sposób omawiane wywołania konstruktora i destruktora są pomijane. W rezultacie obiekty automatyczne (jeśli istnieją) w tych konstruktorach i destruktorach są również eliminowane w porównaniu z naiwną abstrakcyjną semantyką sugerowaną przez kod źródłowy.

Z drugiej strony, bezpłatna alokacja sklepu jest zdecydowanie „alokacją” z założenia. Zgodnie z regułami ISO C ++ taki przydział może zostać osiągnięty przez wywołanie funkcji przydziału . Jednak od ISO C ++ 14 wprowadzono nową zasadę („nie jak gdyby”), która zezwala na łączenie ::operator newwywołań funkcji globalnej alokacji (tj. ) W określonych przypadkach. Tak więc części operacji alokacji dynamicznej mogą być również niedostępne, jak w przypadku obiektów automatycznych.

Funkcje alokacji przydzielają zasoby pamięci. Obiekty mogą być dalej alokowane na podstawie alokacji przy użyciu alokatorów. W przypadku obiektów automatycznych są one prezentowane bezpośrednio - chociaż dostęp do pamięci podstawowej można uzyskać i wykorzystać do zapewnienia pamięci innym obiektom (poprzez umieszczenie new), ale nie ma to większego sensu jako bezpłatny sklep, ponieważ nie ma możliwości przeniesienia zasoby gdzie indziej.

Wszystkie inne obawy są poza zakresem C ++. Niemniej jednak mogą być nadal znaczące.

O implementacjach C ++

C ++ nie ujawnia zreifikowanych rekordów aktywacyjnych ani niektórych pierwszorzędnych kontynuacji (np. Przez słynnych call/cc), nie ma możliwości bezpośredniego manipulowania ramkami rekordów aktywacyjnych - w których implementacja musi umieścić automatyczne obiekty. Gdy nie ma (nieprzenośnych) interoperacyjności z podstawową implementacją („natywny” nieprzenośny kod, taki jak wbudowany kod zestawu), pominięcie podstawowej alokacji ramek może być dość trywialne. Na przykład, gdy wywoływana funkcja jest wstawiana, ramki mogą być skutecznie łączone w inne, więc nie ma sposobu, aby pokazać, co to jest „przydział”.

Jednak po respekcie interakcje stają się skomplikowane. Typowa implementacja C ++ ujawni zdolność interopu na ISA (architektura zestawu instrukcji) z pewnymi konwencjami wywoływania jako granicy binarnej współdzielonej z natywnym (maszynowym na poziomie ISA) kodem. Byłoby to wyraźnie kosztowne, zwłaszcza w przypadku utrzymywania wskaźnika stosu , który często jest bezpośrednio przechowywany przez rejestr na poziomie ISA (z zapewnieniem dostępu do konkretnych instrukcji maszyny). Wskaźnik stosu wskazuje granicę górnej ramki wywołania funkcji (aktualnie aktywnego). Po wprowadzeniu wywołania funkcji potrzebna jest nowa ramka, a wskaźnik stosu jest dodawany lub odejmowany (w zależności od konwencji ISA) o wartość nie mniejszą niż wymagany rozmiar ramki. Ramka jest następnie powiedziana alokowanagdy wskaźnik stosu po operacjach. Parametry funkcji mogą być również przekazywane na ramkę stosu, w zależności od przyjętej konwencji wywołania. Ramka może przechowywać pamięć automatycznych obiektów (prawdopodobnie łącznie z parametrami) określonych przez kod źródłowy C ++. W sensie takich implementacji obiekty te są „przydzielane”. Kiedy sterowanie wychodzi z wywołania funkcji, ramka nie jest już potrzebna, zwykle jest zwalniana przez przywrócenie wskaźnika stosu z powrotem do stanu przed wywołaniem (zapisanego wcześniej zgodnie z konwencją wywoływania). Można to uznać za „zwolnienie”. Operacje te sprawiają, że rekord aktywacji skutecznie stanowi strukturę danych LIFO, dlatego często nazywany jest „ stosem (wywołania) ”.

Ponieważ większość implementacji C ++ (szczególnie tych ukierunkowanych na natywny kod na poziomie ISA i wykorzystujących język asemblera jako jego natychmiastowe wyjście) używa podobnych strategii takich jak ta, taki mylący schemat „alokacji” jest popularny. Takie alokacje (jak również dezalokacje) zużywają cykle maszynowe i może być kosztowne, gdy często pojawiają się (niezoptymalizowane) wywołania, nawet jeśli współczesne mikroarchitekty procesora mogą mieć skomplikowane optymalizacje implementowane przez sprzęt dla wspólnego wzorca kodu (np. Przy użyciu stos silnika w implementacji PUSH/ POPinstrukcjach).

Ale tak czy inaczej, ogólnie prawdą jest, że koszt przydziału ramki stosu jest znacznie mniejszy niż wywołanie funkcji alokacji obsługującej darmowy magazyn (chyba że jest całkowicie zoptymalizowany) , który sam może mieć setki (jeśli nie miliony :-) operacji w celu utrzymania wskaźnika stosu i innych stanów. Funkcje alokacji są zazwyczaj oparte na interfejsie API udostępnianym przez środowisko hostowane (np. Środowisko wykonawcze dostarczane przez system operacyjny). W odróżnieniu od celu przechowywania automatycznych obiektów dla wywołań funkcji, takie alokacje mają charakter ogólny, więc nie będą miały struktury ramek jak stos. Tradycyjnie przydzielają miejsce z pamięci puli zwanej stertą (lub kilkoma stertami). W odróżnieniu od „stosu” pojęcie „sterty” nie wskazuje tutaj na używaną strukturę danych; która pochodzi z wczesnych implementacji języka sprzed dziesięcioleci. (BTW, stos wywołań jest zwykle przydzielany przez środowisko ze stałą lub określoną przez użytkownika wielkością ze stosu podczas uruchamiania programu lub wątku.) Charakter przypadków użycia sprawia, że ​​przydzielanie i zwalnianie ze stosu jest znacznie bardziej skomplikowane (niż wypychanie lub pop stosy ramek) i trudno jest je bezpośrednio zoptymalizować sprzętowo.

Wpływ na dostęp do pamięci

Zwykły przydział stosu zawsze umieszcza nową ramkę na górze, więc ma całkiem dobrą lokalizację. Jest to przyjazne dla pamięci podręcznej. OTOH, pamięć przydzielana losowo w bezpłatnym sklepie nie ma takiej właściwości. Od ISO C ++ 17 istnieją szablony zasobów puli dostarczane przez <memory>. Bezpośrednim celem takiego interfejsu jest umożliwienie, aby wyniki kolejnych alokacji były blisko siebie w pamięci. Potwierdza to fakt, że strategia ta jest ogólnie dobra pod względem wydajności we współczesnych implementacjach, np. Jest przyjazna dla buforowania w nowoczesnych architekturach. Chodzi jednak o wydajność dostępu, a nie o alokację .

Konkurencja

Oczekiwanie na równoczesny dostęp do pamięci może mieć różny wpływ na stos i stosy. Stos wywołań jest zwykle własnością jednego wątku wykonania w implementacji C ++. OTOH, stosy są często dzielone między wątkami w procesie. W przypadku takich hałd funkcje alokacji i dezalokacji muszą chronić wspólną wewnętrzną strukturę danych administracyjnych przed wyścigiem danych. W rezultacie przydziały i zwolnienia sterty mogą mieć dodatkowy narzut z powodu wewnętrznych operacji synchronizacji.

Wydajność przestrzeni

Ze względu na naturę przypadków użycia i wewnętrznych struktur danych, stosy mogą cierpieć z powodu fragmentacji pamięci wewnętrznej , podczas gdy stos nie. Nie ma to bezpośredniego wpływu na wydajność alokacji pamięci, ale w systemie z pamięcią wirtualną niska efektywność miejsca może pogorszyć ogólną wydajność dostępu do pamięci. Jest to szczególnie okropne, gdy dysk twardy jest używany jako miejsce wymiany pamięci fizycznej. Może to powodować dość długie opóźnienia - czasami miliardy cykli.

Ograniczenia przydziału stosu

Chociaż przydziały stosu są często lepsze w porównaniu z przydziałami stosu, w rzeczywistości nie oznacza to, że przydziały stosu zawsze mogą zastąpić przydziały stosu.

Po pierwsze, nie ma możliwości przydzielenia miejsca na stosie o rozmiarze określonym w środowisku wykonawczym w przenośny sposób z ISO C ++. Istnieją rozszerzenia zapewniane przez implementacje takie jak allocaVLA (tablica o zmiennej długości), ale istnieją powody, aby ich unikać. (IIRC, źródło Linuxa ostatnio usuwa korzystanie z VLA.) (Należy również pamiętać, że ISO C99 ma obowiązkowe VLA, ale ISO C11 włącza obsługę opcjonalną.)

Po drugie, nie ma niezawodnego i przenośnego sposobu na wykrycie wyczerpania przestrzeni stosu. Jest to często nazywane przepełnieniem stosu _{(hmm, etymologia tej witryny)} , ale prawdopodobnie bardziej dokładnie, przepełnienie stosu . W rzeczywistości często powoduje to nieprawidłowy dostęp do pamięci, a stan programu jest wówczas uszkodzony (... lub, co gorsza, dziura w zabezpieczeniach). W rzeczywistości ISO C ++ nie ma pojęcia „stos” i sprawia, że ​​zachowanie jest niezdefiniowane, gdy zasób jest wyczerpany . Zachowaj ostrożność, ile miejsca powinno pozostać dla automatycznych obiektów.

Jeśli skończy się miejsce na stosie, na stosie jest przydzielonych zbyt wiele obiektów, co może być spowodowane zbyt dużą liczbą aktywnych wywołań funkcji lub niewłaściwym użyciem automatycznych obiektów. Takie przypadki mogą sugerować istnienie błędów, np. Wywołanie funkcji rekurencyjnej bez poprawnych warunków wyjścia.

Niemniej jednak czasami pożądane są głębokie połączenia rekurencyjne. W implementacjach języków wymagających obsługi niezwiązanych aktywnych połączeń (gdzie głębokość połączeń jest ograniczona tylko przez całkowitą pamięć), niemożliwe jest użycie (współczesnego) stosu wywołań bezpośrednio jako rekordu aktywacji języka docelowego, jak typowe implementacje C ++. Aby obejść ten problem, potrzebne są alternatywne sposoby budowy rekordów aktywacyjnych. Na przykład SML / NJ jawnie przydziela ramki na stercie i używa stosów kaktusów . Skomplikowany przydział takich ramek rekordów aktywacyjnych zwykle nie jest tak szybki jak ramek stosu wywołań. Jeśli jednak takie języki zostaną wdrożone dalej z gwarancją właściwej rekurencji ogona, bezpośredni przydział stosu w języku obiektowym (to znaczy „obiekt” w tym języku nie jest przechowywany jako referencje, ale rodzime prymitywne wartości, które mogą być odwzorowane jeden na jeden na nieudostępnionych obiektach C ++) jest jeszcze bardziej skomplikowane z większą liczbą kara za wyniki ogólnie. Podczas używania C ++ do implementacji takich języków trudno jest oszacować wpływ na wydajność.

Należy ogólnie zwrócić uwagę na takie optymalizacje.

Optymalizacja, którą otrzymujesz, jest proporcjonalna do ilości czasu, w którym licznik programu faktycznie znajduje się w tym kodzie.

Jeśli próbkujesz licznik programu, dowiesz się, gdzie spędza swój czas, i to zwykle jest w niewielkiej części kodu, a często w procedurach bibliotecznych, nad którymi nie masz kontroli.

Tylko jeśli okaże się, że spędza dużo czasu na przydzielaniu sterty twoich obiektów, zauważalnie szybsze będzie przydzielanie ich na stos.

Alokacja stosu prawie zawsze będzie tak szybka lub szybsza niż alokacja sterty, chociaż z pewnością możliwe jest, aby alokator sterty po prostu użył techniki alokacji opartej na stosie.

Istnieją jednak większe problemy związane z ogólną wydajnością alokacji stosu w porównaniu do alokacji stosu (lub, nieco lepiej, alokacji lokalnej i zewnętrznej). Zwykle alokacja sterty (zewnętrzna) jest powolna, ponieważ dotyczy wielu różnych rodzajów alokacji i wzorców alokacji. Zmniejszenie zakresu używanego alokatora (uczynienie go lokalnym dla algorytmu / kodu) będzie miało tendencję do zwiększania wydajności bez większych zmian. Dodanie lepszej struktury do wzorców alokacji, na przykład wymuszenie zamówienia LIFO na parach alokacji i dezalokacji, może również poprawić wydajność alokatora poprzez użycie alokatora w prostszy i bardziej uporządkowany sposób. Możesz także użyć lub napisać alokator dostosowany do konkretnego wzorca alokacji; większość programów często przydziela kilka dyskretnych rozmiarów, więc sterty oparte na buforze lookaside o kilku ustalonych (najlepiej znanych) rozmiarach będą działać wyjątkowo dobrze. Z tego właśnie powodu system Windows używa stosu niskiej fragmentacji.

Z drugiej strony alokacja oparta na stosie w 32-bitowym zakresie pamięci jest również obarczona niebezpieczeństwem, jeśli masz zbyt wiele wątków. Stosy potrzebują ciągłego zakresu pamięci, więc im więcej wątków masz, tym więcej wirtualnej przestrzeni adresowej będziesz potrzebować, aby działały bez przepełnienia stosu. Nie będzie to (jak na razie) problem w przypadku wersji 64-bitowej, ale z pewnością może siać spustoszenie w długo działających programach z dużą ilością wątków. Skończy się wirtualna przestrzeń adresowa z powodu fragmentacji jest zawsze trudnym problemem.

Jak powiedzieli inni, alokacja stosu jest na ogół znacznie szybsza.

Jeśli jednak kopiowanie obiektów jest kosztowne, przydział na stosie może doprowadzić do ogromnego spadku wydajności później, gdy będziesz używać obiektów, jeśli nie będziesz ostrożny.

Na przykład, jeśli przydzielisz coś na stosie, a następnie umieścisz w pojemniku, lepiej byłoby przydzielić na stosie i przechowywać wskaźnik w pojemniku (np. Ze std :: shared_ptr <>). To samo jest prawdą, jeśli przekazujesz lub zwracasz obiekty według wartości oraz w innych podobnych scenariuszach.

Chodzi o to, że chociaż alokacja stosu jest zwykle lepsza niż alokacja sterty w wielu przypadkach, czasami jeśli robisz wszystko, co w twojej mocy, aby alokować stos, gdy nie najlepiej pasuje on do modelu obliczeniowego, może powodować więcej problemów niż rozwiązuje.

class Foo {
public:
    Foo(int a) {

    }
}
int func() {
    int a1, a2;
    std::cin >> a1;
    std::cin >> a2;

    Foo f1(a1);
    __asm push a1;
    __asm lea ecx, [this];
    __asm call Foo::Foo(int);

    Foo* f2 = new Foo(a2);
    __asm push sizeof(Foo);
    __asm call operator new;//there's a lot instruction here(depends on system)
    __asm push a2;
    __asm call Foo::Foo(int);

    delete f2;
}

Tak byłoby w asm. Kiedy jesteś w środku func, f1wskaźnik i f2został przydzielony na stosie (automatyczne przechowywanie). A tak przy okazji, Foo f1(a1)ma skutków Instrukcja o wskaźnik stosu ( esp), zostało przyznane, jeśli funcpragnienia uzyskać element f1, to instrukcja jest coś takiego: lea ecx [ebp+f1], call Foo::SomeFunc(). Kolejną rzeczą, jaką alokuje stos, może sprawić, że ktoś pomyśli, że pamięć jest czymś podobnym FIFO, po FIFOprostu zdarzyło się, gdy wchodzisz w jakąś funkcję, jeśli jesteś w tej funkcji i alokujesz coś takiego int i = 0, nie następuje push.

Wspomniano wcześniej, że alokacja stosu polega po prostu na przesunięciu wskaźnika stosu, to znaczy jednej instrukcji na większości architektur. Porównaj to z tym, co ogólnie dzieje się w przypadku przydziału sterty.

System operacyjny utrzymuje części wolnej pamięci jako połączoną listę z danymi ładunku składającymi się ze wskaźnika do adresu początkowego wolnej części i wielkości wolnej części. Aby przydzielić X bajtów pamięci, lista łączy jest przeglądana, a każda nuta jest odwiedzana po kolei, sprawdzając, czy jej rozmiar wynosi co najmniej X. Gdy zostanie znaleziona część o rozmiarze P> = X, P jest podzielone na dwie części z rozmiary X i PX. Połączona lista jest aktualizowana, a wskaźnik do pierwszej części jest zwracany.

Jak widać, przydzielanie sterty zależy od czynników, takich jak żądana ilość pamięci, stopień fragmentacji pamięci i tak dalej.

Ogólnie przydział stosu jest szybszy niż przydział stosu, jak wspomniano w prawie każdej odpowiedzi powyżej. Push lub pop stosu to O (1), podczas gdy przydzielanie lub zwalnianie ze sterty może wymagać przejścia poprzednich alokacji. Jednak zwykle nie powinieneś alokować w ciasnych, intensywnych pętlach, więc wybór zwykle sprowadza się do innych czynników.

Rozróżnienie może być dobre: ​​możesz użyć „alokatora stosu” na stercie. Mówiąc ściśle, przydział alokacji stosu oznacza rzeczywistą metodę alokacji, a nie lokalizację alokacji. Jeśli przeznaczasz wiele rzeczy na stos programów, może to być złe z różnych powodów. Z drugiej strony użycie metody stosu do alokacji na stercie, gdy jest to możliwe, jest najlepszym wyborem dla metody alokacji.

Ponieważ wspomniałeś o Metrowerks i PPC, zgaduję, że masz na myśli Wii. W tym przypadku pamięć jest na wagę złota, a użycie metody alokacji stosu, gdzie to możliwe, gwarantuje, że nie marnujesz pamięci na fragmenty. Oczywiście wykonanie tego wymaga dużo więcej uwagi niż „normalnych” metod alokacji sterty. Mądrze jest ocenić kompromisy dla każdej sytuacji.

Należy zauważyć, że rozważania zwykle nie dotyczą szybkości i wydajności przy wyborze alokacji stosu a sterty. Stos działa jak stos, co oznacza, że ​​dobrze nadaje się do wypychania bloków i wbijania ich ponownie, ostatni raz, pierwszy raz. Wykonywanie procedur jest również podobne do stosu, ostatnia wprowadzona procedura jest pierwsza, aby wyjść. W większości języków programowania wszystkie zmienne potrzebne w procedurze będą widoczne tylko podczas wykonywania procedury, dlatego są one wypychane po wejściu do procedury i wyskakują ze stosu po wyjściu lub powrocie.

Teraz na przykład, gdy nie można użyć stosu:

Proc P
{
  pointer x;
  Proc S
  {
    pointer y;
    y = allocate_some_data();
    x = y;
  }
}

Jeśli przydzielisz trochę pamięci w procedurze S i umieścisz ją na stosie, a następnie opuścisz S, przydzielone dane zostaną usunięte ze stosu. Ale zmienna x w P również wskazywała na te dane, więc x wskazuje teraz pewne miejsce pod wskaźnikiem stosu (zakładając, że stos rośnie w dół) z nieznaną zawartością. Zawartość może nadal tam być, jeśli wskaźnik stosu zostanie po prostu przesunięty w górę bez czyszczenia danych pod nim, ale jeśli zaczniesz alokować nowe dane na stosie, wskaźnik x może faktycznie wskazywać na te nowe dane.

Nigdy nie rób przedwczesnych założeń, ponieważ inny kod aplikacji i użycie może wpłynąć na twoją funkcję. Więc patrząc na funkcję, izolacja nie ma sensu.

Jeśli poważnie podchodzisz do aplikacji, użyj VTune lub skorzystaj z dowolnego podobnego narzędzia do profilowania i spójrz na punkty aktywne.

Ketan

Chciałbym powiedzieć, że kod generowany przez GCC (pamiętam również VS) nie ma narzutu na przydzielanie stosu .

Powiedz o następującej funkcji:

  int f(int i)
  {
      if (i > 0)
      {   
          int array[1000];
      }   
  }

Poniżej przedstawiono generowany kod:

  __Z1fi:
  Leh_func_begin1:
      pushq   %rbp
  Ltmp0:
      movq    %rsp, %rbp
  Ltmp1:
      subq    $**3880**, %rsp <--- here we have the array allocated, even the if doesn't excited.
  Ltmp2:
      movl    %edi, -4(%rbp)
      movl    -8(%rbp), %eax
      addq    $3880, %rsp
      popq    %rbp
      ret 
  Leh_func_end1:

Niezależnie od tego, ile masz zmiennych lokalnych (nawet wewnątrz, jeśli lub przełączasz), tylko 3880 zmieni się na inną wartość. Jeśli nie masz zmiennej lokalnej, ta instrukcja musi zostać wykonana. Więc przydziel lokalną zmienną nie ma narzutu.