Was ist der Stack und der Heap und wo befinden sie sich?

Question

• Was sind der Stack und der Heap?
• Wo befinden sie sich physisch im Speicher eines Computers?
• In welchem Maße werden sie vom Betriebssystem oder der Laufzeitumgebung der Sprache kontrolliert?
• Was ist ihr Geltungsbereich?
• Was bestimmt ihre Größen?
• Was macht einen schneller?

Answer 1

Ich habe etwas zu teilen, obwohl die wichtigsten Punkte bereits abgedeckt sind.

Stack

• Sehr schneller Zugriff.
• In RAM gespeichert.
• Funktionsaufrufe werden hier geladen, zusammen mit den lokalen Variablen und den übergebenen Funktionsparametern.
• Speicher wird automatisch freigegeben, wenn das Programm den Gültigkeitsbereich verlässt.
• In sequenziellem Speicher gespeichert.

Heap

• Vergleichsweise langsamer Zugriff im Vergleich zum Stack.
• In RAM gespeichert.
• Dynamisch erstellte Variablen werden hier gespeichert, die später nach Gebrauch den allokierten Speicher freigeben müssen.
• An dem Ort gespeichert, wo die Speicherzuweisung erfolgt, immer über einen Zeiger zugegriffen.

Interessante Anmerkung:

• Wenn die Funktionsaufrufe im Heap gespeichert worden wären, hätte dies zu 2 unübersichtlichen Punkten geführt:
  1. Aufgrund der sequenziellen Speicherung im Stack erfolgt die Ausführung schneller. Die Speicherung im Heap hätte zu einem erheblichen Zeitverbrauch geführt und das gesamte Programm langsamer ausgeführt.
  2. Wenn die Funktionen im Heap gespeichert worden wären (unübersichtliche Speicherung durch Zeiger), gäbe es keinen Weg mehr, zur Aufruferadresse zurückzukehren (was der Stack aufgrund der sequenziellen Speicherung im Speicher ermöglicht).

Answer 2

Da einige Antworten ins Detail gehen, werde ich meinen Beitrag leisten.

Überraschenderweise hat noch niemand erwähnt, dass mehrere (also nicht nur in Bezug auf die Anzahl der ausgeführten Betriebssystem-Threads) Aufruflisten nicht nur in exotischen Sprachen (PostScript) oder Plattformen (Intel Itanium) zu finden sind, sondern auch in Fasern, Grünen Threads und in einigen Implementierungen von Koroutinen.

Fasern, Grüne Threads und Koroutinen sind in vielerlei Hinsicht ähnlich, was zu viel Verwirrung führt. Der Unterschied zwischen Fasern und Grünen Threads ist, dass erstere kooperatives Multitasking verwenden, während Letztere entweder kooperatives oder präemptives Multitasking (oder sogar beides) aufweisen können. Für den Unterschied zwischen Fasern und Koroutinen, siehe hier.

In jedem Fall haben Fasern, Grüne Threads und Koroutinen den Zweck, mehrere Funktionen gleichzeitig auszuführen, aber nicht parallel (siehe diese SO-Frage für den Unterschied) innerhalb eines einzelnen Betriebssystem-Threads, wobei die Steuerung organisiert von einer zur anderen übergeben wird.

Bei der Verwendung von Fasern, Grünen Threads oder Koroutinen haben Sie normalerweise pro Funktion einen separaten Stapel. (Technisch gesehen nicht nur ein Stapel, sondern der gesamte Ausführungskontext ist pro Funktion. Am wichtigsten sind die CPU-Register.) Für jeden Thread gibt es so viele Stapel wie gleichzeitig ausgeführte Funktionen, und der Thread wechselt gemäß der Logik Ihres Programms zwischen der Ausführung jeder Funktion hin und her. Wenn eine Funktion zu Ende läuft, wird ihr Stapel zerstört. Also sind die Anzahl und Lebensdauer der Stapel dynamisch und werden nicht durch die Anzahl der Betriebssystem-Threads bestimmt!

Beachten Sie, dass ich gesagt habe "normalerweise pro Funktion einen separaten Stapel haben". Es gibt sowohl stapelhaltige als auch stapellose Implementierungen von Koroutinen. Die bekanntesten stapelhaltigen C++-Implementierungen sind Boost.Coroutine und Microsoft PPL's async/await. (Allerdings verwenden C++'s fortsetzbare Funktionen (auch bekannt als "async und await"), die für C++17 vorgeschlagen wurden, wahrscheinlich stapellose Koroutinen.)

Ein Vorschlag zur Implementierung von Fasern in der C++-Standardbibliothek steht aus. Außerdem gibt es einige Drittanbieter Bibliotheken. Grüne Threads sind äußerst beliebt in Sprachen wie Python und Ruby.

Answer 3

Wow! So many answers and I don't think one of them got it right...

1) Wo befinden sie sich (physisch im Speicher eines echten Computers) und was sind sie?

Der Stack ist ein Speicher, der als die höchste Speicheradresse reserviert ist, die Ihrem Programm zugewiesen wird, und dann von dort aus im Wert abnimmt. Er ist für Funktionenparameter und für alle temporären Variablen reserviert, die in Funktionen verwendet werden.

Es gibt zwei Heaps: öffentlich und privat.

Der private Heap beginnt auf einer 16-Byte-Grenze (für 64-Bit-Programme) oder einer 8-Byte-Grenze (für 32-Bit-Programme) nach dem letzten Byte des Codes Ihres Programms und steigt von dort aus im Wert an. Er wird auch als Standard-Heap bezeichnet.

Wenn der private Heap zu groß wird, überschneidet er sich mit dem Stack-Bereich, genauso wie der Stack sich mit dem Heap überschneidet, wenn er zu groß wird. Da der Stack bei einer höheren Adresse beginnt und sich von dort aus zu einer niedrigeren Adresse bewegt, können Sie mit entsprechenden Hacks den Stack so groß machen, dass er den privaten Heapbereich überschreitet und den Codebereich überlappt. Der Trick besteht dann darin, genügend des Codebereichs zu überlappen, damit Sie sich in den Code einklinken können. Es ist etwas knifflig zu machen und Sie riskieren einen Programmabsturz, aber es ist einfach und sehr effektiv.

Der öffentliche Heap befindet sich in seinem eigenen Speicherbereich außerhalb des Speicherplatzes Ihres Programmimages. Es ist dieser Speicher, der auf die Festplatte abgesaugt wird, wenn der Speicher knapp wird.

2) Inwieweit werden sie durch das Betriebssystem oder die Laufzeitumgebung der Sprache kontrolliert?

Der Stack wird vom Programmierer kontrolliert, der private Heap wird vom Betriebssystem verwaltet, und der öffentliche Heap wird von niemandem kontrolliert, weil es sich um einen Betriebssystemdienst handelt - Sie stellen Anfragen und entweder werden sie genehmigt oder abgelehnt.

2b) Was ist ihr Geltungsbereich?

Sie sind alle global für das Programm, aber ihr Inhalt kann privat, öffentlich oder global sein.

2c) Was bestimmt die Größe von jedem von ihnen?

Die Größe des Stacks und des privaten Heaps wird durch die Compiler-Laufzeitoptionen bestimmt. Der öffentliche Heap wird zur Laufzeit mit einem Größenparameter initialisiert.

2d) Was macht einen schneller?

Sie sind nicht darauf ausgelegt, schnell zu sein, sondern nützlich. Wie der Programmierer sie nutzt, bestimmt, ob sie "schnell" oder "langsam" sind.

REF:

https://norasandler.com/2019/02/18/Write-a-Compiler-10.html

https://learn.microsoft.com/de-de/windows/desktop/api/heapapi/nf-heapapi-getprocessheap

https://learn.microsoft.com/de-de/windows/desktop/api/heapapi/nf-heapapi-heapcreate

Answer 4

Wo und was sind sie (physisch im Speicher eines echten Computers)?

ANTWORT: Beide sind im RAM.

NEBENBEI:

RAM ist wie ein Schreibtisch und HDDs/SSDs (permanenter Speicher) sind wie Bücherregale. Um etwas zu lesen, musst du ein Buch auf deinem Schreibtisch offen haben, und du kannst nur so viele Bücher offen haben, wie auf deinen Schreibtisch passen. Um ein Buch zu bekommen, ziehst du es aus dem Regal und legst es auf deinen Schreibtisch. Um ein Buch zurückzulegen, schließt du das Buch auf deinem Schreibtisch und stellst es ins Regal zurück.

Stack und Heap sind Namen, die wir zwei Arten, wie Compiler verschiedene Arten von Daten an derselben Stelle speichern (d.h. im RAM), geben.

Was ist ihr Umfang?
Was bestimmt die Größe jeder von ihnen?
Was macht einen schneller?

ANTWORT:

1. Der Stack ist für statische (feste Größe) Daten

   a. Zur Compile-Zeit liest der Compiler die Variablentypen, die in deinem Code verwendet werden.

   i. Er reserviert eine feste Menge an Speicher für diese Variablen.
   ii. Die Größe dieses Speichers kann nicht wachsen.

   b. Der Speicher ist zusammenhängend (ein einzelner Block), daher ist der Zugriff manchmal schneller als auf dem Heap

   c. Ein Objekt, das auf dem Stack platziert wird und im Speicher während der Laufzeit über die Größe des Stacks hinaus wächst, führt zu einem Stacküberlauffehler

2. Der Heap ist für dynamische (sich ändernde Größe) Daten

   a. Die Menge an Speicher ist nur durch den vorhandenen leeren Platz im RAM begrenzt
   i. Der verwendete Betrag kann bei Bedarf zur Laufzeit wachsen oder schrumpfen

   b. Weil Elemente auf dem Heap zugeordnet werden, indem leerer Speicherplatz überall im RAM gefunden wird, ist nicht immer ein zusammenhängender Abschnitt, was manchmal den Zugriff langsamer macht als auf dem Stack

   c. Programmierer platzieren manuell Elemente auf dem Heap mit dem Schlüsselwort new und MÜSSEN diesen Speicher manuell freigeben, wenn sie damit fertig sind.
   i. Code, der wiederholt neuen Speicher reserviert, ohne ihn freizugeben, wenn er nicht mehr benötigt wird, führt zu einem Speicherleck.

NEBENBEI:

Der Stack und der Heap wurden nicht primär eingeführt, um die Geschwindigkeit zu verbessern; sie wurden eingeführt, um Speicherüberläufe zu behandeln. Die erste Überlegung bei der Verwendung des Stacks gegenüber dem Heap sollte sein, ob ein Speicherüberlauf auftreten wird. Wenn ein Objekt beabsichtigt ist, in unbekanntem Umfang zu wachsen (wie eine verkettete Liste oder ein Objekt, dessen Elemente eine willkürliche Menge an Daten speichern können), platziere es auf dem Heap. Verwende soweit wie möglich die C++ Standardbibliothek (STL) Container vector, map und list, da sie speicher- und geschwindigkeitseffizient sind und hinzugefügt wurden, um dein Leben zu erleichtern (du musst dich nicht um Speicherzuweisung/-freigabe kümmern).

Nachdem du deinen Code zum Laufen gebracht hast, wenn du feststellst, dass er inakzeptabel langsam läuft, gehe zurück und optimiere deinen Code und prüfe, ob er effizienter programmiert werden kann. Es könnte sich herausstellen, dass das Problem direkt überhaupt nichts mit dem Stack oder Heap zu tun hat (z.B. Verwendung eines iterativen Algorithmus anstelle eines rekursiven, Betrachtung von Ein-/Ausgabe vs. CPU-gebundenen Aufgaben, vielleicht Hinzufügen von Mehrfaden- oder Mehrprozessfähigkeit).

Ich sage manchmal langsamer/schneller oben, weil die Geschwindigkeit des Programms möglicherweise nichts damit zu tun hat, ob Elemente auf dem Stack oder dem Heap zugeordnet sind.

In welchem Maße werden sie vom Betriebssystem oder der Laufzeitumgebung der Sprache kontrolliert?

ANTWORT:

• Die Stackgröße wird zur Compile-Zeit vom Compiler bestimmt.

• Die Heapgröße variiert zur Laufzeit. (Der Heap arbeitet während der Laufzeit mit dem Betriebssystem zusammen, um Speicher zuzuweisen.)

NEBENBEI:

Nachfolgend noch etwas zur Kontrolle und zu den Unterschieden zwischen Compile-Zeit und Laufzeit-Operationen.

Jeder Computer hat eine einzigartige Befehlssatzarchitektur (ISA), das sind seine Hardware-Befehle (z.B. "BEWEGEN", "SPRINGEN", "ADDIEREN", etc.).

• Ein Betriebssystem ist nichts weiter als ein Ressourcenmanager (der kontrolliert, wie/wann/und wo Speicher, Prozessoren, Geräte und Informationen verwendet werden).

• Die ISA des Betriebssystems wird als das nackte System bezeichnet und die übrigen Befehle als die erweiterte Maschine. Der Kernel ist die erste Schicht der erweiterten Maschine. Er kontrolliert Dinge wie

  • festzulegen, welche Aufgaben einen Prozessor verwenden dürfen (der Scheduler),
  • wie viel Speicher oder wie viele Hardware-Register einer Aufgabe zugeordnet werden (der Dispatcher), und
  • in welcher Reihenfolge Aufgaben ausgeführt werden sollen (der Verkehrssteuerer).

• Wenn wir von "Compiler" sprechen, meinen wir im Allgemeinen den Compiler, Assembler und den Linker zusammen

  • Der Compiler wandelt den Quellcode in Assemblersprache um und übergibt ihn an den Assembler,
  • Der Assembler wandelt die Assemblersprache in Maschinencode (ISA-Befehle) um und übergibt sie an den Linker
  • Der Linker nimmt alle Maschinencodes (möglicherweise generiert aus mehreren Quelldateien) und kombiniert sie zu einem Programm.

• Der Maschinencode wird an den Kernel übergeben, wenn er ausgeführt wird, der dann entscheidet, wann er ausgeführt wird und die Kontrolle übernimmt, aber der Maschinencode selbst enthält ISA-Befehle zum Anfordern von Dateien, zur Anforderung von Speicher usw. Also der Code gibt ISA-Befehle aus, aber alles muss vom Kernel durchgehen.

Answer 5

Viele Antworten sind als Konzepte richtig, aber wir müssen beachten, dass die Hardware (d.h. der Mikroprozessor) einen Stapel benötigt, um den Aufruf von Unterprogrammen (Aufruf in Assemblersprache..) zu ermöglichen. (OOP-Leute werden es Methoden nennen)

Auf dem Stapel speichern Sie Rückgabeadressen und rufen push / ret pop wird direkt in der Hardware verwaltet.

Sie können den Stapel verwenden, um Parameter zu übergeben.. selbst wenn es langsamer ist als die Verwendung von Registern (würde ein Mikroprozessor-Guru sagen oder ein gutes BIOS-Buch aus den 1980er Jahren...)

• Ohne Stapel kann kein Mikroprozessor arbeiten. (Wir können uns kein Programm vorstellen, nicht einmal in Assemblersprache, ohne Unterprogramme/Funktionen)
• Ohne den Heap kann es arbeiten. (Ein Programm in Assemblersprache kann ohne arbeiten, da der Heap ein OS-Konzept ist, wie malloc, das ein OS/Lib-Aufruf ist.

Die Nutzung des Stapels ist schneller, da:

• Es ist Hardware, und auch push/pop sind sehr effizient.
• malloc erfordert das Betreten des Kernel-Modus, die Verwendung von Lock/Semaphore (oder anderen Synchronisierungsprimitiven), die Ausführung von Code und die Verwaltung einiger Strukturen, die erforderlich sind, um die Zuweisung zu verfolgen.