std :: vector (ab) używa automatycznego przechowywania

Rozważ następujący fragment kodu:

#include <array>
int main() {
  using huge_type = std::array<char, 20*1024*1024>;
  huge_type t;
}

Oczywiście ulegnie awarii na większości platform, ponieważ domyślny rozmiar stosu jest zwykle mniejszy niż 20 MB.

Teraz rozważ następujący kod:

#include <array>
#include <vector>

int main() {
  using huge_type = std::array<char, 20*1024*1024>;
  std::vector<huge_type> v(1);
}

Co zaskakujące, również się zawiesza! Tracback (z jedną z najnowszych wersji libstdc ++) prowadzi do include/bits/stl_uninitialized.hpliku, w którym możemy zobaczyć następujące linie:

typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
std::fill(__first, __last, _ValueType());

Konstruktor zmiany rozmiaru vectormusi domyślnie zainicjować elementy i w ten sposób jest implementowany. Oczywiście _ValueType()tymczasowe awarie stosu.

Pytanie brzmi, czy jest to zgodna implementacja. Jeśli tak, to w rzeczywistości oznacza to, że użycie wektora ogromnych typów jest dość ograniczone, prawda?

— Igor R.
źródło

Nie należy przechowywać dużych obiektów w typie tablicowym. Może to potencjalnie wymagać bardzo dużego regionu zarazy pamięci, który może nie być obecny. Zamiast tego przygotuj wektor wskaźników (zwykle std :: unique_ptr), abyś nie wymagał tak dużego zapotrzebowania na pamięć.

— NathanOliver

Po prostu pamięć. Istnieją implementacje C ++, które nie używają pamięci wirtualnej.

— NathanOliver

Który kompilator, btw? Nie mogę się rozmnażać z VS 2019 (16.4.2)

— ChrisMM

Patrząc na kod libstdc ++, ta implementacja jest używana tylko wtedy, gdy typ elementu jest trywialny i można go przypisać do kopiowania oraz jeśli std::allocatorużywana jest wartość domyślna .

— orzech

@Damon Jak wspomniałem powyżej, wydaje się, że jest używany tylko w przypadku trywialnych typów z domyślnym alokatorem, więc nie powinno być żadnej zauważalnej różnicy.

— orzech

Odpowiedzi:

Nie ma ograniczenia, ile automatycznej pamięci używa każdy interfejs std API.

Wszystkie mogą wymagać 12 terabajtów miejsca na stosie.

Jednak ten interfejs API wymaga tylko Cpp17DefaultInsertable, a twoja implementacja tworzy dodatkową instancję w stosunku do wymagań konstruktora. O ile implementacja nie jest ukryta za wykrywaniem obiektu, który można w trywialny sposób kopiować i kopiować, implementacja wygląda nielegalnie.

— Jak - Adam Nevraumont
źródło

— orzech

@walnut Co oznacza, że kompilator może dowolnie tworzyć ten obiekt tymczasowy; Zgaduję, że istnieje spora szansa na zoptymalizowaną kompilację, której nie można utworzyć?

— Jak - Adam Nevraumont

Tak, chyba tak, ale w przypadku dużych elementów wydaje się, że GCC nie. Clang z libstdc ++ optymalizuje tymczasowe, ale wydaje się tylko, jeśli rozmiar wektora przekazywany do konstruktora jest stałą czasową kompilacji, patrz godbolt.org/z/-2ZDMm .

— orzech

@walnut specjalny przypadek jest taki, że wysyłamy do std::filltrywialnych typów, które następnie używają memcpydo wysadzania bajtów w miejsca, co jest potencjalnie znacznie szybsze niż konstruowanie wielu pojedynczych obiektów w pętli. Wierzę, że implementacja libstdc ++ jest zgodna, ale powodowanie przepełnienia stosu dla dużych obiektów jest błędem jakości implementacji (QoI). Zgłosiłem to jako gcc.gnu.org/PR94540 i naprawię to.

— Jonathan Wakely

@JathanathanWakely Tak, to ma sens. Nie pamiętam, dlaczego o tym nie pomyślałem, kiedy napisałem swój komentarz. Wydaje mi się, że pomyślałbym, że pierwszy domyślnie skonstruowany element zostanie zbudowany bezpośrednio w miejscu, a następnie można go skopiować, aby żadne dodatkowe obiekty tego typu nigdy nie zostały zbudowane. Ale oczywiście tak naprawdę nie przemyślałem tego szczegółowo i nie wiem, w jaki sposób wdrożyć standardową bibliotekę. (Za późno zdałem sobie sprawę, że jest to również twoja sugestia w zgłoszeniu błędu).

— orzech

huge_type t;
Oczywiście miałoby to awarię na większości platform ...

Kwestionuję założenie „większości”. Ponieważ pamięć dużego obiektu nigdy nie jest używana, kompilator może go całkowicie zignorować i nigdy nie przydzielać pamięci, w którym to przypadku nie nastąpiłby awaria.

Pytanie brzmi, czy jest to zgodna implementacja.

Standard C ++ nie ogranicza użycia stosu, a nawet potwierdza istnienie stosu. Tak, to jest zgodne ze standardem. Można jednak uznać to za kwestię jakości wdrożenia.

w rzeczywistości oznacza to, że użycie wektora wielkich typów jest dość ograniczone, prawda?

Tak wydaje się być w przypadku libstdc ++. Katastrofa nie została odtworzona w libc ++ (przy użyciu clang), więc wydaje się, że nie jest to ograniczenie w języku, ale tylko w tej konkretnej implementacji.

— eerorika
źródło

„niekoniecznie zawiesi się pomimo przepełnienia stosu, ponieważ program nigdy nie uzyskuje dostępu do przydzielonej pamięci” - jeśli stos zostanie później w jakikolwiek sposób wykorzystany (np. do wywołania funkcji), nastąpi awaria nawet na nadmiernie zaangażowanych platformach .

— Ruslan

Każda platforma, na której nie ulega awarii (zakładając, że obiekt nie został pomyślnie przydzielony), jest podatna na zderzenie stosu.

— user253751

@ user253751 Optymistyczne byłoby założenie, że większość platform / programów nie jest zagrożona.

— eerorika

Myślę, że overcommit dotyczy tylko stosu, a nie stosu. Stos ma ustaloną górną granicę swojego rozmiaru.

— Jonathan Wakely

@JonathanWakely Masz rację. Wydaje się, że przyczyną tego nie jest awaria, ponieważ kompilator nigdy nie przydziela obiektu, który nie jest używany.

— eerorika

Nie jestem prawnikiem językowym ani ekspertem od standardu C ++, ale cppreference.com mówi:

explicit vector( size_type count, const Allocator& alloc = Allocator() );

Konstruuje kontener z licznikami wstawionymi domyślnie instancjami T. Nie wykonuje się kopii.

Być może źle rozumiem „domyślnie wstawiony”, ale oczekiwałbym:

std::vector<huge_type> v(1);

być równoważnym z

std::vector<huge_type> v;
v.emplace_back();

Ta ostatnia wersja nie powinna tworzyć kopii stosu, ale konstruować ogromny typ bezpośrednio w pamięci dynamicznej wektora.

Nie mogę autorytatywnie powiedzieć, że to, co widzisz, jest niezgodne, ale z pewnością nie jest to, czego oczekiwałbym od wysokiej jakości wdrożenia.

— Adrian McCarthy
źródło

Jak wspomniałem w komentarzu do pytania, libstdc ++ używa tej implementacji tylko dla trywialnych typów z przypisaniem kopii std::allocator, więc nie powinno być zauważalnej różnicy między wstawieniem bezpośrednio do pamięci wektorów a utworzeniem kopii pośredniej.

— orzech

@walnut: Racja, ale olbrzymi przydział stosu i wpływ init i kopiowania na wydajność to wciąż rzeczy, których nie spodziewałbym się po wysokiej jakości implementacji.

— Adrian McCarthy

Tak, zgadzam się. Myślę, że był to niedopatrzenie we wdrażaniu. Chodziło mi tylko o to, że nie ma to znaczenia pod względem standardowej zgodności.

— orzech

IIRC potrzebujesz również możliwości kopiowania lub przenoszenia, emplace_backale nie tylko do tworzenia wektora. Co oznacza, że możesz mieć, vector<mutex> v(1)ale nie możesz. vector<mutex> v; v.emplace_back();W przypadku czegoś takiego huge_typenadal możesz mieć przydział i przenieść operację więcej w drugiej wersji. Żadne nie powinno tworzyć obiektów tymczasowych.

— dyp

@IgorR. vector::vector(size_type, Allocator const&)wymaga (Cpp17) DefaultInsertable

— dyp