std :: vector (ab) verwendet die automatische Speicherung

46

Betrachten Sie das folgende Snippet:

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

Offensichtlich würde es auf den meisten Plattformen abstürzen, da die Standardstapelgröße normalerweise weniger als 20 MB beträgt.

Betrachten Sie nun den folgenden Code:

#include <array>
#include <vector>

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

Überraschenderweise stürzt es auch ab! Der Traceback (mit einer der neuesten libstdc ++ - Versionen) führt zu einer include/bits/stl_uninitialized.hDatei, in der die folgenden Zeilen angezeigt werden:

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

Der Größenänderungskonstruktor vectormuss die Elemente standardmäßig initialisieren, und so wird er implementiert. Offensichtlich _ValueType()stürzt der Stapel vorübergehend ab.

Die Frage ist, ob es sich um eine konforme Implementierung handelt. Wenn ja, bedeutet dies tatsächlich, dass die Verwendung eines Vektors großer Typen sehr begrenzt ist, nicht wahr?

Igor R.
quelle
Man sollte keine großen Objekte in einem Array-Typ speichern. Dies erfordert möglicherweise einen sehr großen Bereich zusammenhängenden Speichers, der möglicherweise nicht vorhanden ist. Verwenden Sie stattdessen einen Zeigervektor (normalerweise std :: unique_ptr), damit Sie keine so hohen Anforderungen an Ihren Speicher stellen.
NathanOliver
2
Nur Erinnerung. Es werden C ++ - Implementierungen ausgeführt, die keinen virtuellen Speicher verwenden.
NathanOliver
3
Welcher Compiler übrigens? Ich kann nicht mit VS 2019 (16.4.2)
reproduzieren
3
Beim Betrachten des libstdc ++ - Codes wird diese Implementierung nur verwendet, wenn der Elementtyp trivial und kopierzuweisbar ist und wenn der Standard std::allocatorverwendet wird.
Walnuss
1
@Damon Wie oben erwähnt, scheint es nur für triviale Typen mit dem Standard-Allokator verwendet zu werden, daher sollte es keinen beobachtbaren Unterschied geben.
Walnuss

Antworten:

19

Es gibt keine Begrenzung für die Verwendung von automatischem Speicher durch eine Standard-API.

Sie könnten alle 12 Terabyte Stapelspeicherplatz benötigen.

Diese API erfordert jedoch nur Cpp17DefaultInsertable, und Ihre Implementierung erstellt eine zusätzliche Instanz über die Anforderungen des Konstruktors. Diese Implementierung sieht illegal aus, es sei denn, die Erkennung des Objekts ist trivial sicher und kopierbar.

Yakk - Adam Nevraumont
quelle
8
Beim Betrachten des libstdc ++ - Codes wird diese Implementierung nur verwendet, wenn der Elementtyp trivial und kopierzuweisbar ist und wenn der Standard std::allocatorverwendet wird. Ich bin mir nicht sicher, warum dieser Sonderfall überhaupt gemacht wird.
Walnuss
3
@walnut Dies bedeutet, dass der Compiler frei ist, dieses temporäre Objekt so zu erstellen, als ob es nicht tatsächlich erstellt würde. Ich vermute, es gibt eine gute Chance für einen optimierten Build, der nicht erstellt wird.
Yakk - Adam Nevraumont
4
Ja, ich denke es könnte, aber für große Elemente scheint GCC nicht. Das Klirren mit libstdc ++ optimiert das Temporäre, aber es scheint nur, wenn die an den Konstruktor übergebene Vektorgröße eine Konstante zur Kompilierungszeit ist, siehe godbolt.org/z/-2ZDMm .
Walnuss
1
@walnut der Sonderfall ist da, so dass wir std::fillfür triviale Typen versenden , die dann verwendet werden memcpy, um die Bytes an Stellen zu sprengen, was möglicherweise viel schneller ist als das Konstruieren vieler einzelner Objekte in einer Schleife. Ich glaube, dass die libstdc ++ - Implementierung konform ist, aber das Verursachen eines Stapelüberlaufs für große Objekte ist ein QoI-Fehler (Quality of Implementation). Ich habe es als gcc.gnu.org/PR94540 gemeldet und werde es beheben.
Jonathan Wakely
@ JonathanWakely Ja, das macht Sinn. Ich erinnere mich nicht, warum ich nicht daran gedacht habe, als ich meinen Kommentar schrieb. Ich denke, ich hätte gedacht, dass das erste standardmäßig konstruierte Element direkt an Ort und Stelle erstellt wird und man dann davon kopieren kann, so dass niemals zusätzliche Objekte des Elementtyps erstellt werden. Aber natürlich habe ich das nicht wirklich im Detail durchdacht und kenne die Vor- und Nachteile der Implementierung der Standardbibliothek nicht. (Ich habe zu spät festgestellt, dass dies auch Ihr Vorschlag im Fehlerbericht ist.)
Walnuss
9
huge_type t;

Offensichtlich würde es auf den meisten Plattformen abstürzen ...

Ich bestreite die Annahme von "am meisten". Da der Speicher des riesigen Objekts niemals verwendet wird, kann der Compiler ihn vollständig ignorieren und niemals den Speicher zuweisen. In diesem Fall würde es nicht zum Absturz kommen.

Die Frage ist, ob es sich um eine konforme Implementierung handelt.

Der C ++ - Standard schränkt die Stapelverwendung nicht ein oder erkennt sogar die Existenz eines Stapels an. Also ja, es entspricht dem Standard. Man könnte dies jedoch als ein Problem der Qualität der Implementierung betrachten.

es bedeutet tatsächlich, dass die Verwendung eines Vektors großer Typen ziemlich begrenzt ist, nicht wahr?

Dies scheint bei libstdc ++ der Fall zu sein. Der Absturz wurde nicht mit libc ++ (unter Verwendung von clang) reproduziert, daher scheint dies keine Einschränkung in der Sprache zu sein, sondern nur in dieser bestimmten Implementierung.

Eerorika
quelle
6
"wird trotz Überlaufen des Stapels nicht unbedingt abstürzen, da das Programm niemals auf den zugewiesenen Speicher zugreift" - wenn der Stapel danach in irgendeiner Weise verwendet wird (z. B. um eine Funktion aufzurufen), stürzt dies sogar auf den überlasteten Plattformen ab .
Ruslan
Jede Plattform, auf der dies nicht abstürzt (vorausgesetzt, das Objekt wird nicht erfolgreich zugewiesen), ist anfällig für Stack Clash.
user253751
@ user253751 Es wäre optimistisch anzunehmen, dass die meisten Plattformen / Programme nicht anfällig sind.
Eerorika
Ich denke, Overcommit gilt nur für den Heap, nicht für den Stack. Der Stapel hat eine feste Obergrenze für seine Größe.
Jonathan Wakely
@ JonathanWakely Du hast recht. Es scheint, dass der Grund, warum es nicht abstürzt, darin besteht, dass der Compiler das nicht verwendete Objekt niemals zuweist.
Eerorika
5

Ich bin weder ein Sprachanwalt noch ein C ++ - Standardexperte, aber cppreference.com sagt:

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

Konstruiert den Container mit der Anzahl der standardmäßig eingefügten Instanzen von T. Es werden keine Kopien erstellt.

Vielleicht verstehe ich "Standardeinfügung" falsch, aber ich würde erwarten:

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

gleichwertig sein mit

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

Die letztere Version sollte keine Stapelkopie erstellen, sondern einen riesigen Typ direkt im dynamischen Speicher des Vektors erstellen.

Ich kann nicht verbindlich sagen, dass das, was Sie sehen, nicht konform ist, aber es ist sicherlich nicht das, was ich von einer Qualitätsimplementierung erwarten würde.

Adrian McCarthy
quelle
4
Wie ich in einem Kommentar zu der Frage erwähnt habe, verwendet libstdc ++ diese Implementierung nur für triviale Typen mit Kopierzuweisung. Daher std::allocatorsollte es keinen erkennbaren Unterschied zwischen dem direkten Einfügen in den Vektorspeicher und dem Erstellen einer Zwischenkopie geben.
Walnuss
@walnut: Richtig, aber die enorme Stapelzuweisung und die Auswirkungen von Init und Copy auf die Leistung sind immer noch Dinge, die ich von einer qualitativ hochwertigen Implementierung nicht erwarten würde.
Adrian McCarthy
2
Ja, ich stimme zu. Ich denke, das war ein Versehen bei der Implementierung. Mein Punkt war nur, dass es in Bezug auf die Standardkonformität keine Rolle spielt.
Walnuss
IIRC Sie benötigen auch Kopierbarkeit oder Beweglichkeit, emplace_backaber nicht nur zum Erstellen eines Vektors. Was bedeutet, dass Sie haben können, vector<mutex> v(1)aber nicht vector<mutex> v; v.emplace_back();Für so etwas wie haben huge_typeSie möglicherweise noch eine Zuordnung und Verschiebungsoperation mehr mit der zweiten Version. Weder sollten temporäre Objekte erstellen.
Dyp
1
@IgorR. vector::vector(size_type, Allocator const&)erfordert (Cpp17) DefaultInsertable
dyp