Wie können C und C ++ speichern große Objekte auf dem Stapel?

https://stackoverflow.com/questions/429995

07-07-2019
|

Frage

Ich versuche, herauszufinden, wie C und C ++ speichert große Objekte auf dem Stapel. Normalerweise ist der Stapel die Größe einer ganzen Zahl, so verstehe ich nicht, wie größere Objekte dort gespeichert sind. Haben sie einfach mehrere Stapel „Slots“?

nehmen

Lösung

Der Stapel ist ein Stück Erinnerung. Der Stapelzeiger zeigt auf die Spitze. Die Werte können auf den Stapel geschoben werden und tauchte sie abgerufen werden.

Zum Beispiel, wenn wir eine Funktion, die mit zwei Parametern aufgerufen wird (1 Byte Größe und die anderen 2-Byte-Größe, einfach davon ausgehen, wir haben einen 8-Bit-PC).

Beide sind auf dem Stapel diese bewegt den Stapelzeiger nach oben gedrückt wird:

03: par2 byte2
02: par2 byte1
01: par1

Nun wird die Funktion aufgerufen und die Rückkehr addres wird auf den Stapel gelegt:

05: ret byte2
04: ret byte1
03: par2 byte2
02: par2 byte1
01: par1

OK, innerhalb der Funktion haben wir 2 lokale Variablen; ein von 2 Bytes und ein von 4. diesen für eine Position auf dem Stapel reserviert ist, aber zuerst speichern wir den Stapelzeiger, so dass wir wissen, wo die Variablen durch das Zählen und die Parameter gefunden werden durch Abzählen.

starten

11: var2 byte4
10: var2 byte3
09: var2 byte2
08: var2 byte1
07: var1 byte2
06: var1 byte1
    ---------
05: ret byte2
04: ret byte1
03: par2 byte2
02: par2 byte1
01: par1

Wie Sie sehen, können Sie alles auf den Stapel gelegt, solange Sie Raum links. Und sonst werden Sie die Phänomene bekommen, dass diese Seite seinen Namen gibt.

Andere Tipps

Stack und Heap ist nicht so unterschiedlich, wie Sie denken!

Es stimmt, tun einige Betriebssysteme Stack Einschränkungen. (Einige von denen haben auch böse Haufen Einschränkungen auch!)

Das ist aber nicht 1985 nicht mehr.

In diesen Tagen, ich laufe Linux!

Meine default stack ist auf 10 MB beschränkt. Mein Standard Heapsize ist unbegrenzt. Es ist ziemlich trivial, dass stack Unlimit. (* Hust * [Tcsh] unlimit stack * hust *. Oder setrlimit () ).

Die größten Unterschiede zwischen Stapel und heap sind:

Stapel Zuweisungen nur einen Zeiger-Offset (und möglicherweise neue Speicher-Seiten zuzuweisen, wenn der Stapel groß genug gewachsen ist). Heap hat durch seine Datenstrukturen suchen einen geeigneten Speicherblock zu finden. (Und möglicherweise auch neue Speicherseiten zuweisen zu.)
Stapel geht out of scope wenn der aktuelle Block endet. Heap geht out of scope, wenn Lösch- / frei aufgerufen wird.
Heap fragmentiert erhalten. Stapel wird nie fragmentiert.

Unter Linux beide Stapel und heap durch den virtuellen Speicher manged.

Im Hinblick auf die Zuteilung Zeit, auch heap-Suche durch stark fragmentiert Speicher kann nicht eine Kerze Mapping in neue Speicherseiten halten. Zeitlich sind die Unterschiede vernachlässigbar!

Je nach Betriebssystem, oft ist es nur, wenn Sie tatsächlich diese neuen Speicherseiten verwenden, die sie in abgebildet werden. ( nicht in malloc () Zuordnung!) ( es ist eine lazy evaluation Sache.)

( neue würde den Konstruktor aufrufen, die vermutlich diese Speicherseiten benutzen würde ...)

Sie können die VM-System Thrash durch das Erstellen und zerstören große Objekte auf entweder die Stapel oder heap . Es hängt von Ihrem O / Compiler, ob Speicher / vom System freigegeben wird. Wenn es nicht zurückgewonnen ist, kann Heap der Lage sein, es wieder zu verwenden. (Vorausgesetzt, dass sie nicht durch eine andere malloc umgewidmet worden () in der Zwischenzeit.) Und falls Stapel nicht freigegeben wird, wäre es nur wiederverwendet werden.

Obwohl Seiten, die zurück in sein müßten erhalten ausgelagert zu getauscht, und das wird Ihr größter Zeit-Hit.

Von all diesen Dingen, Ich sorge mich um Speicherfragmentierung die meisten

Lebensdauer (wenn es den Bereich verlässt) ist immer der entscheidende Faktor.

Aber wenn Sie Programme für längere Zeit laufen, schafft Fragmentierung einen allmählich zunehmenden Speicherbedarf. Der ständige Austausch tötet mich schließlich!

FASSUNG hinzuzufügen:

Mann, ich habe verdorben!

Etwas einfach nicht war hier addieren ... Ich dachte, entweder * I * war Weg zur Hölle weg von der Unterseite. Oder alle anderen war. Oder, was wahrscheinlicher ist, beide. Oder, nur vielleicht, auch nicht.

Was auch immer die Antwort, ich musste wissen, was los ist!

... Das wird lang sein. Bär mit mir ...

habe ich die meisten der letzten 12 Jahre damit verbringen, unter Linux arbeiten. Und etwa 10 Jahre vor, dass unter verschiedenen Unix-Varianten. Meine Perspektive auf Computern ist etwas voreingenommen. Ich habe verdorben!

Ich habe ein wenig mit dem Windows getan, aber nicht genug, um autoritativ zu sprechen. Auch tragischerweise mit Mac OS / Darwin entweder ... Obwohl Mac OS / Darwin / BSD ist nahe genug, dass einige meiner Kenntnisse überträgt sich.

Mit 32-Bit-Zeiger, Sie laufen Raum aus Adresse bei 4 GB (2 ^ 32).

Praktisch gesprochen, STACK + HEAP kombiniert ist in der Regel irgendwo zwischen 2-4 GB begrenzt, da andere Dinge in dort bekommen abgebildet müssen.

(Es gibt gemeinsam genutzten Speicher, gemeinsam genutzte Bibliotheken, Memory-Mapped-Dateien, die ausführbare Bild Ihren Lauf ist immer schön, usw.)

Unter Linux / Unix / MacOS / Darwin / BSD, können Siekünstlich beschränken, die HEAP oder STACK , was auch immer Sie beliebige Werte zur Laufzeit wollen. Aber schließlich gibt es eine harte Systemgrenze.

Das ist der Unterschied (in tcsh) von "Limit" vs "Limit -h" . Oder (in bash) von "ulimit -Sa" vs "ulimit -Ha" . Oder programmatisch von rlim_cur vs rlim_max in struct rlimit .

Nun kommen wir zum spaßigen Teil. Im Hinblick auf Martin York-Code . (Danke Martin ! Gutes Beispiel. Immer gute Dinge auszuprobieren!).

Martin vermutlich auf einem Mac läuft. (Aktuell genug. Sein Compiler Build neuer ist als meins!)

Sicher, sein Code nicht auf seinem Mac standardmäßig ausgeführt. Aber es wird gut laufen, wenn er zum ersten Mal aufruft "unlimit stack" (tsch) oder "ulimit -Ss unbegrenzt" (bash).

THE Kern der Sache:

Test auf einem alten (veraltet) Linux RH9 2.4.x Kernel-Box, Aufteilung großer Mengen von STACK oder HEAP , entweder durch selbst übersteigt zwischen 2 und 3 aus GB. (Leider RAM der Maschine + SWAP Tops bei einem wenig aus unter 3,5 GB. Es ist ein 32-Bit-Betriebssystem. Und das ist nicht der einzige Prozess ausgeführt wird. Wir machen mit dem, was wir haben ... )

Es gibt also wirklich keine Beschränkungen auf STACK Größe vs HEAP Größe unter Linux, andere als die künstliche ...

ABER:

Auf einem Mac gibt es eine harte stackGrenze von 65532 Kilobyte . Es hat zu tun, wie, was im Speicher angelegt.

Normalerweise halten Sie von einem idealisierten System haben STACK an einem Ende des Speicheradressraum, HEAP auf der anderen, und sie bauen aufeinander. Wenn sie sich treffen, sind Sie aus dem Speicher.

Macs erscheinen ihre Gemeinsam genutzter Systembibliotheken zu halten in zwischen auf einer festen Versatz beiden Seiten begrenzen. Sie können immer noch laufen Martin York-Code mit "unlimit stack", da er nur so etwas wie 8 MiB (<64 MiB) von Daten Zuteilung wird. Aber er wird aus laufen STACK , lange bevor er aus läuft HEAP .

Ich bin auf Linux. Das werde ich nicht. Leider Kind. Hier ist ein Nickel. Gehen Sie holen Sie sich eine bessere OS.

Es gibt Workarounds für den Mac. Aber sie hässlich und chaotisch und beinhalten die Kernel oder Linker Parameter zwicken.

Auf lange Sicht, es sei denn, Apple-tut etwas wirklich dumm, 64-Bit-Adressräume machen wird diese ganze Stapel-Beschränkung, was veraltet irgendwann wirklich bald Jetzt.

Bewegen Sie sich auf Fragmentation:

Immer, drücken Sie etwas auf die STACK es am Ende angehängt ist. Und es entfernt (Rollback), wenn der aktuelle Block beendet.

Als Ergebnis gibt es keine Löcher in der STACK . Es ist alles ein großer fester Block des verwendeten Speichers. Mit vielleicht nur ein wenig freien Speicherplatz auf der sehr alle zur Wiederverwendung bereit beenden.

Im Gegensatz dazu als HEAP zugeordnet ist und free'd, wickeln Sie mit unbenutztem Speicher Löchern auf. Diese können nach und nach zu einem erhöhten Speicherbedarf im Laufe der Zeit führen. Nicht das, was wir in der Regel durch einen Kern Leck bedeuten, aber die Ergebnisse sind ähnlich.

Memory Fragmentation ist nicht ein Grund zu vermeiden HEAP Lagerung. Es ist einfach etwas bewusst zu sein, wenn Sie Codierung.

, die bis bringt SWAP Dreschen :

Wenn Sie bereits ein la habenrge Menge Heap zugewiesen / in Gebrauch ist.
Wenn Sie viele fragmentierte Löcher verstreut.
Und wenn Sie eine große Anzahl von kleinen Zuweisungen haben.

Dann können Sie mit einer großen Anzahl von Variablen aufzuwickeln, die alle innerhalb eines kleinen lokalisierten Bereichs des Codes verwendet werden, die über sehr viele virtuellen Speicherseiten verstreut sind. (Wie in dem Sie verwenden 4 Bytes auf dieser Seite 2k und 8 Bytes auf dieser 2k Seite, und so weiter für eine ganze Reihe von Seiten ...)

All das bedeutet, dass Ihr Programm eine große Anzahl von Seiten haben muss getauscht in laufen. Oder es geht um Seiten in und aus ständig zu tauschen. (Wir das Dreschen nennen.)

Auf der anderen Seite hatten diese kleinen Zuweisungen auf der gemacht worden STACK , würden sie alle in einem zusammenhängenden Abschnitt von Speicher befinden. Weniger VM Speicherseiten würde geladen werden müssen. (4 + 8 + ... <2k für den Sieg.)

Nebenbei bemerkt: Mein Grund für die Aufmerksamkeit auf diesen von einem bestimmten Elektroingenieur stammt ich wusste, wer darauf bestand, dass alle Arrays auf dem Heap zugewiesen werden. Wir machten Matrix Mathematik für Grafiken. A * LOT * von 3 oder 4-Element-Arrays. Verwalten von neuen / löschen allein war ein Alptraum. Auch in den Klassen abstrahiert es verursacht Schmerz!

Nächstes Thema. Threading:

Ja, Fäden zu sehr kleine Stapel standardmäßig beschränkt.

Sie können mit pthread_attr_setstacksize das ändern (). Obwohl je nach Einfädeln Implementierung, wenn mehrere Threads die gleiche 32-Bit-Adressraum teilen, große individuelle pro-Thread-Stacks ein Problem sein! Es ist einfach nicht so viel Raum! Auch hier helfen wird, den Übergang zu 64-Bit-Adressräumen (OS).

pthread_t       threadData;
pthread_attr_t  threadAttributes;

pthread_attr_init( & threadAttributes );
ASSERT_IS( 0, pthread_attr_setdetachstate( & threadAttributes,
                                             PTHREAD_CREATE_DETACHED ) );

ASSERT_IS( 0, pthread_attr_setstacksize  ( & threadAttributes,
                                             128 * 1024 * 1024 ) );

ASSERT_IS( 0, pthread_create ( & threadData,
                               & threadAttributes,
                               & runthread,
                               NULL ) );

In Bezug auf Martin York Stack-Frames:

Vielleicht sind Sie und ich denke an verschiedene Dinge?

Wenn ich an einem Stapelrahmen , denke ich an einem Call-Stack. Jede Funktion oder Methode hat ihre eigenen Stapelrahmen , bestehend aus der Absenderadresse, Argumente und lokale Daten.

Ich habe nie irgendwelche Beschränkungen für die Größe einer Stapelrahmen gesehen. Es gibt Einschränkungen auf die STACK als Ganzes, aber das ist alles Stapelrahmen kombiniert werden.

Es gibt ein schönes Diagramm und Diskussion von Stapelrahmen über auf Wiki .

Ein letzter Punkt:

Unter Linux / Unix / MacOS / Darwin / BSD ist es möglich, das Maximum zu ändern STACK Größenbeschränkungen programmatisch als auch Grenze (tsch) oder ulimit (bash):

struct rlimit  limits;
limits.rlim_cur = RLIM_INFINITY;
limits.rlim_max = RLIM_INFINITY;
ASSERT_IS( 0, setrlimit( RLIMIT_STACK, & limits ) );

Nur nicht versuchen, es zu INFINITY setzen auf einem Mac ... Und es ändern, bevor Sie versuchen, es zu benutzen. ;-)

Weiterführende Literatur:

Push und pop Anweisungen sind in der Regel nicht zum Speichern von lokalen Stack-Frame-Variablen verwendet. Zu Beginn der Funktion wird der Stapelrahmen durch Dekrementieren des Stapelzeigers mit der Anzahl von Bytes (ausgerichtet auf die Wortgröße) erforderlich durch die Funktion der lokalen Variablen eingestellt. Dies ordnet die erforderliche Menge an Speicherplatz „auf dem Stapel“ für diese Werte. Alle lokalen Variablen werden dann über einen Zeiger auf diesen Stapelrahmen (ebp auf x86) abgerufen.

Der Stapel ist ein großer Speicherblock, des lokalen Variablen speichert, Informationen für von Funktionsaufrufen Rückkehr usw. Die tatsächliche Größe des Stapels deutlich auf dem O variiert. Wenn zum Beispiel einen neuen Thread auf Windows erstellen, die Standard Größe ist 1 MB .

Wenn Sie versuchen, ein Stapel-Objekt zu erstellen, die mehr Speicher benötigt als auf dem Stapel zur Zeit verfügbar ist, erhalten Sie einen Stapelüberlauf und schlechte Dinge passieren. Eine große Klasse von Exploit-Code absichtlich versucht, diese oder ähnliche Bedingungen zu schaffen.

Der Stapel wird nicht in ganzzahlige großen Stücke aufgeteilt. Es ist nur ein flacher Byte-Array. Es wird von einer „integer“ vom Typ size_t (nicht int) indiziert. Wenn Sie ein großen Stapel Objekt erstellen, das in dem derzeit verfügbaren Raum paßt, verwendet es nur, dass der Raum durch Stoßen nach oben (oder unten), um den Stapelzeiger.

Wie andere haben darauf hingewiesen, es ist am besten, den Heap für große Objekte zu verwenden, nicht den Stapel. Dies vermeidet Stapelüberlauf Probleme.

EDIT: Wenn Sie eine 64-Bit-Anwendung und Betriebssystem und Laufzeit verwenden Bibliotheken sind nett zu dir (mrree der Post sehen), dann sollte es in Ordnung sein große temporäre Objekte auf der zuzuteilen Stapel. Wenn Ihre Anwendung ist 32-Bit und / oder O / Laufzeitbibliothek ist nicht schön, werden Sie wahrscheinlich benötigen, um diese Objekte auf dem Heap zugewiesen werden.

Wenn Sie eine Funktion eingeben, wächst der Stapel die lokalen Variablen in dieser Funktion passen. Bei einer largeObject Klasse, die 400 Bytes verwendet sagen:

void MyFunc(int p1, largeObject p2, largeObject *p3)
{
   int s1;
   largeObject s2;
   largeObject *s3;
}

Wenn Sie diese Funktion aufrufen, Ihren Stack etwas wie folgt aussehen (Details werden Konvention und Architektur auf Aufruf variieren):

   [... rest of stack ...]
   [4 bytes for p1] 
   [400 bytes for p2]
   [4 bytes for p3]
   [return address]
   [old frame pointer]
   [4 bytes for s1]
   [400 bytes for s2]
   [4 bytes for s3]

Siehe x86-Aufrufkonventionen für einige Informationen darüber, wie der Stapel arbeitet. MSDN hat auch ein paar schöne Diagramme für ein paar verschiedene calling Konvektionen, mit Beispielcode und resultierende Stapel Diagramme .

Wie andere gesagt haben, es ist nicht klar, was du mit „großen Objekten“ bedeuten ... Aber da man dann fragen

Nehmen Sie sie einfach auf mehrere Stapel "Slots"?

Ich werde davon ausgehen, dass man einfach etwas größer als eine ganze Zahl bedeuten. Als jemand anders erwähnt, obwohl, wird der Stapel nicht integer-sized „Slots“ hat - es ist nur ein Abschnitt des Speichers, und jedes Byte in ihm seine eigene Adresse hat. Der Compiler verfolgt jede Variable durch die Adresse des zuerst Byte dieser Variable - das ist der Wert, den Sie erhalten, wenn Sie die Adresse-of verwenden Operator (&var), und der Wert eines Zeigers nur diese Adresse für eine andere Variable. Der Compiler weiß auch, welche Art jede Variable ist (Sie es gesagt, wenn Sie die Variable deklariert), und er weiß, wie groß sollte jeder Art sein - wenn Sie das Programm kompilieren, tut es, was Mathematik ist notwendig, wie viel Platz, um herauszufinden, diejenigen, Variablen müssen, wenn eine Funktion aufgerufen wird, und enthalten das Ergebnis, daß in dem Funktionseingabe-Punktcode (der Stapelrahmen daß PDaddy erwähnt).

In C und C ++ Sie nicht große Objekte auf dem Stapel gespeichert werden sollten, da der Stapel begrenzt ist (wie Sie erraten). Der Stapel für jeden Thread ist in der Regel nur ein paar Megabyte oder weniger (es kann angegeben werden, wenn ein Gewinde zu schaffen). Wenn Sie „neu“ nennen, ein Objekt zu erstellen, wird es nicht auf den Stapel gelegt -. Es wird stattdessen auf dem Heap setzen

Stackgröße ist begrenzt. Normalerweise ist die Stapelgröße wird gesetzt, wenn der Prozess erstellt wird. Jeder Thread in diesem Prozess wird automatisch die Standardstapelgröße, wenn nicht anders in dem Createthread () Aufruf angegeben. Also ja: Es können mehrere Stapel ‚Slots‘, aber jeder Thread hat nur einen. Und sie können nicht zwischen Threads gemeinsam genutzt werden.

Wenn Sie Objekte setzen, die auf den Stapel größer als die verbleibenden Stack-Größe sind, werden Sie einen Stapelüberlauf erhalten und Ihre Anwendung zum Absturz bringen.

Also, wenn Sie sehr große Objekte haben, weisen sie auf dem Heap, nicht auf dem Stapel. Der Haufen wird nur durch die Größe des virtuellen Speichers begrenzt (das ist eine Größenordnung größer ist als der Stapel ist).

Sie können die Objekte, die massiv genug sind (oder zahlreich genug), dass es nicht sinnvoll, werden sie auf den Stapel zu legen. In diesem Fall können Sie das Objekt auf dem Heap setzen und einen Zeiger auf sie auf den Stapel gelegt. Dies ist ein Unterschied zwischen Pass von Wert und Pass Bezug genommen wird.

Wie definieren Sie ein großes Objekt? reden wir mehr oder weniger als die Größe des Stapels Raum zugeordnet?

zum Beispiel, wenn Sie so etwas wie diese:

void main() {
    int reallyreallybigobjectonthestack[1000000000];
}

auf Ihrem System abhängig werden Sie wahrscheinlich eine segfault bekommen, weil es einfach nicht genug Platz ist, um das Objekt zu speichern. Ansonsten ist es wie jedes andere Objekt gespeichert. Wenn Ihr Gespräch in tatsächlichen physischen Speicher dann müssen Sie sich nicht kümmern, da virtuellen Speicher auf der Betriebssystemebene kümmern, dass der Umgang mit.

Auch die Größe des Stapels ist wahrscheinlich nicht die Größe eines Integer es ganz auf Ihrem Betriebssystem und das Layout der Anwendungen Virtual Address Space .

Mit dem „Stack Größe eines Integer“, meinen Sie „der Stapelzeiger ist die Größe einer ganzen Zahl“. Er zeigt auf die Oberseite des Stapels, was ein großer Bereich des Speichers ist. Nun, größer ist als eine ganze Zahl ist.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow