Co jest szybsze: Przydział stosu lub Przydział sterty

503

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.

Adam
źródło
11
Wiem, że to dość starożytne, ale fajnie byłoby zobaczyć fragmenty C / C ++ demonstrujące różne rodzaje alokacji.
Joseph Weissman,
42
Twoja krowa orkera jest strasznie nieświadoma, ale co ważniejsze, jest niebezpieczna, ponieważ czyni autorytatywne twierdzenia na temat rzeczy, o których jest strasznie nieświadomy. Wyciągnij takie osoby ze swojego zespołu tak szybko, jak to możliwe.
Jim Balter
5
Pamiętaj, że sterta jest zwykle znacznie większa niż stos. Jeśli przydzielono ci duże ilości danych, naprawdę musisz umieścić je na stercie lub zmienić rozmiar stosu w systemie operacyjnym.
Paul Draper,
1
Wszystkie optymalizacje są, chyba że masz argumenty porównawcze lub argumenty o złożoności dowodzące inaczej, domyślnie bezcelowe mikrooptymalizacje.
Björn Lindqvist
2
Zastanawiam się, czy twój współpracownik ma głównie doświadczenie w Javie lub C #. W tych językach prawie wszystko jest przydzielane pod maską, co może prowadzić do takich założeń.
Cort Ammon

Odpowiedzi:

493

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.

Torbjörn Gyllebring
źródło
211
I co ważniejsze, stos jest zawsze gorąca, pamięć można dostać o wiele bardziej prawdopodobne, aby być w pamięci podręcznej niż dotąd sterty przydzielonej pamięci
Benoît
47
Na niektórych (głównie osadzonych, o których wiem) architekturach, stos może być przechowywany w szybkiej pamięci on-die (np. SRAM). To może mieć ogromną różnicę!
leander
38
Ponieważ stos to tak naprawdę stos. Nie możesz zwolnić części pamięci używanej przez stos, chyba że jest nad nim. Nie ma zarządzania, pchasz lub pop rzeczy. Z drugiej strony, pamięć sterty jest zarządzana: prosi jądro o fragmenty pamięci, może je dzieli, łączy je, wykorzystuje ponownie i zwalnia. Stos jest naprawdę przeznaczony do szybkich i krótkich alokacji.
Benoît
24
@Pacerier Ponieważ stos jest znacznie mniejszy niż stos. Jeśli chcesz przydzielić duże tablice, lepiej przydziel je na stosie. Jeśli spróbujesz przydzielić dużą tablicę na stosie, dostaniesz przepełnienie stosu. Spróbuj na przykład w C ++ this: int t [100000000]; Spróbuj na przykład t [10000000] = 10; a następnie cout << t [10000000]; Powinien dać ci przepełnienie stosu lub po prostu nie zadziała i niczego ci nie pokaże. Ale jeśli alokujesz tablicę na stercie: int * t = new int [100000000]; i wykonaj te same operacje po, to zadziała, ponieważ Sterta ma rozmiar niezbędny do tak dużej tablicy.
Lilian A. Moraru
7
@Pacerier Najbardziej oczywistym powodem jest to, że obiekty na stosie wychodzą poza zakres po wyjściu z bloku, w którym zostały przydzielone.
Jim Balter
166

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.

Dan Lenski
źródło
20
Jedna instrukcja, która jest zwykle współdzielona przez WSZYSTKIE obiekty na stosie.
MSalters
9
Dobrze to zrozumiał, szczególnie jeśli chodzi o weryfikowalną potrzebę tego. Ciągle jestem zdumiony tym, jak obawy ludzi dotyczące wydajności są niewłaściwe.
Mike Dunlavey
6
„Zwolnienie” jest również bardzo proste i odbywa się za pomocą jednej leaveinstrukcji.
dok.
15
Pamiętaj o „ukrytym” koszcie tutaj, szczególnie przy pierwszym rozszerzeniu stosu. Może to spowodować błąd strony, przełączenie kontekstu na jądro, które musi wykonać trochę pracy, aby przydzielić pamięć (lub w najgorszym przypadku załadować ją z systemu wymiany).
nos
2
W niektórych przypadkach możesz nawet przydzielić go z 0 instrukcjami. Jeśli znane są pewne informacje o tym, ile bajtów należy przydzielić, kompilator może przydzielić je z wyprzedzeniem, jednocześnie przydzielając inne zmienne stosu. W takich przypadkach nic nie płacisz!
Cort Ammon,
120

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
Max Lybbert
źródło
2
Powinieneś również dodać pętlę „kalibracyjną” na samym początku swojej głównej funkcji, coś, co da ci wyobrażenie, ile czasu na cykl pętli otrzymujesz, i dostosuj inne pętle, aby upewnić się, że twój przykład działa jakiś czas, zamiast stałej, której używasz.
Joe Pineda
2
Cieszę się również, że zwiększenie liczby uruchomień każdej pętli opcji (plus instruowanie g ++, żeby nie optymalizować?) Dało znaczące wyniki. Więc teraz mamy twarde fakty, aby powiedzieć, że stos jest szybszy. Dziękuję za Twój wysiłek!
Joe Pineda
7
Zadaniem optymalizatora jest pozbycie się takiego kodu. Czy istnieje dobry powód, aby włączyć optymalizator, a następnie uniemożliwić jego optymalizację? Zredagowałem odpowiedź, aby wszystko było jeszcze jaśniejsze: jeśli lubisz walczyć z optymalizatorem, przygotuj się, aby dowiedzieć się, jak inteligentni są autorzy kompilatorów.
Max Lybbert,
3
Jestem bardzo spóźniony, ale warto również wspomnieć, że przydział sterty żąda pamięci przez jądro, więc wydajność zależy również silnie od wydajności jądra. Używanie tego kodu w systemie Linux (Linux 3.10.7-gentoo # 2 SMP Wed Sep 4 18:58:21 MDT 2013 x86_64), modyfikowanie timera HR i stosowanie 100 milionów iteracji w każdej pętli daje tę wydajność: stack allocation took 0.15354 seconds, heap allocation took 0.834044 secondsz -O0ustawieniem, tworzeniem Przydział sterty systemu Linux jest wolniejszy tylko na poziomie około 5,5 na moim komputerze.
Taywee,
4
W systemie Windows bez optymalizacji (kompilacja debugowania) użyje sterty debugowania, która jest znacznie wolniejsza niż sterty debugowania. Nie sądzę, że złym pomysłem jest „oszukanie” optymalizatora. Autorzy kompilatorów są inteligentni, ale nie są to kompilatory AI.
paulm
30

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.

Furious Coder
źródło
4
Dotyczy to większości maszyn wielordzeniowych, nie tylko Xenon. Nawet Cell musi to zrobić, ponieważ na tym rdzeniu PPU mogą być uruchomione dwa wątki sprzętowe.
Crashworks
15
Jest to efekt (szczególnie słabej) implementacji alokatora sterty. Lepsze jednostki przydzielające sterty nie muszą uzyskiwać blokady dla każdej alokacji.
Chris Dodd
19

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!

Chris Jester-Young
źródło
1
Czasami nazywa się to alokacją płyty.
Benoit,
8

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.

MarkR
źródło
6

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.

Programista Windows
źródło
Nie sądzę, aby stos był „przeszukiwany”, chyba że jest stronicowany. Z pewnością pamięć półprzewodnikowa korzysta z multipleksera i może uzyskać bezpośredni dostęp do pamięci, stąd pamięć o dostępie swobodnym.
Joe Phillips
4
Oto przykład. Program wywołujący prosi o przydzielenie 37 bajtów. Funkcja biblioteki szuka bloku o długości co najmniej 40 bajtów. Pierwszy blok na wolnej liście ma 16 bajtów. Drugi blok na wolnej liście ma 12 bajtów. Trzeci blok ma 44 bajty. Biblioteka przestaje przeszukiwać w tym momencie.
programista Windows
6

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.

Sójka
źródło
4

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ę.

jogin
źródło
1
Ilość wirtualnej przestrzeni adresowej przydzielonej dla stosu trybu użytkownika w nowoczesnym systemie operacyjnym prawdopodobnie domyślnie będzie wynosić co najmniej 64 kB (1 MB w systemie Windows). Czy mówisz o rozmiarach stosu jądra?
bk1e
1
Na moim komputerze domyślny rozmiar stosu dla procesu wynosi 8 MB, a nie KB. Ile lat ma twój komputer?
Greg Rogers
3

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.

jakobengblom2
źródło
3

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.

larsivi
źródło
3

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.

MSalters
źródło
3

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.

Andrei Pokrovsky
źródło
3

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ść.

FrankHB
źródło
Podobnie jak STL, coraz mniej chętnie różnicuje te pojęcia. Często używa się też wielu kolesi z cppcon2018 heap.
陳 力
@ 陳 力 „Kupa” może być jednoznaczna z pewnymi konkretnymi implementacjami, o których należy pamiętać, więc czasami może być OK. Jest jednak zbędny „ogólnie”.
FrankHB,
Co to jest interop?
陳 力
@ 陳 力 Miałem na myśli wszelkiego rodzaju „natywne” współdziałanie kodu związane ze źródłem C ++, na przykład dowolny wbudowany kod asemblera. Opiera się to na założeniach (ABI) nieobjętych C ++. Interoperacja COM (oparta na niektórych ABI specyficznych dla systemu Windows) jest mniej więcej podobna, chociaż w większości jest neutralna dla C ++.
FrankHB,
2

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.

Mike Dunlavey
źródło
2

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.

MSN
źródło
Nie zgadzam się z twoim pierwszym zdaniem.
brian beuning
2

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.

wjl
źródło
2
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.

bitnick
źródło
1

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.

Nikhil
źródło
1

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.

Dan Olson
źródło
1

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.

Kent Munthe Caspersen
źródło
0

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

Ketan
źródło
-1

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.

ZijingWu
źródło