Warum brauchen wir einen Heap, wenn alles auf dem Stack viel effizienter erledigt werden kann?

Dies hängt tatsächlich etwas mit der Frage zusammen, die ich gestern gestellt habe, warum in den heute verwendeten Anwendungen sowohl ein Stack als auch ein Heap erforderlich sind (und warum wir nicht einfach einen Heap anstelle von beidem verwenden können, um ein einfaches & einzigartiger Standard).

In vielen Antworten wurde jedoch darauf hingewiesen, dass ein Stapel unersetzbar ist, da er Hunderte (oder Tausende) Mal schneller ist als der Versuch, den Heap zuzuweisen / zu referenzieren. Ich weiß, dass es ein Problem mit der dynamischen Speicherzuweisung gibt, wenn der Heap abgeschafft wird, aber gibt es keinen Weg, dies zu umgehen oder den Stack zu verbessern, damit er die dynamische Speicherzuweisung verarbeiten kann?

Das Problem bei Stapeln ist, dass Sie nur dann Speicher "freigeben" können, wenn er sich oben auf dem Stapel befindet. Angenommen, Sie haben drei Dinge unterschiedlicher Größe zugewiesen:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

Der Stapel würde aunten, bin der Mitte und coben liegen. Dies wird problematisch, wenn wir befreien wollen b:

free(b); // b is not on top! We have to wait until c is freed!

Die Problemumgehung besteht darin, alle Daten nach bund nach zu verschieben, wenn dies der Fall ist a. Dies funktioniert, erfordert jedoch in diesem Fall 5000000 Kopien - etwas, das viel langsamer ist als ein Haufen.

Deshalb haben wir einen Haufen. Zwar ist die Zuweisung möglicherweise langsamer als bei einem Stapel ( O(log n)vs O(1)), doch bei Heaps kann Speicher an einem beliebigen Ort schneller freigegeben werden - O(log n)im Vergleich zu einem StapelO(n)

Stack ist pro Thread, Heap ist prozessweit

Wenn 100 Threads alle verarbeitenden Arbeitselemente enthalten, die ich in eine Warteschlange gestellt habe, wo ordne ich die Arbeitselemente genau so zu, dass jeder der 100 Threads sie sehen kann?

Es gibt auch andere Arten von Speicher

ZB speicherabgebildete Dateien, gemeinsam genutzter Speicher, zugeordnete E / A (Kernel-Modus). Das Effizienzargument ist in diesen Situationen eher umstritten.

Ein Stack ist eine LIFO-Struktur (Last-In-First-Out), an deren oberster Stelle sich ein Referenzzeiger befindet (normalerweise von der Hardware unterstützt). Abgesehen davon müsste alles, was Sie versuchen, auf dem Stapel anstelle des Heaps zuzuweisen, in jeder Funktion oben auf diesem Stapel eine lokale Variable sein. Der Hauptgrund für einen Stack ist also, dass Ihre main () - Routine alle Datenstrukturen, die Ihr Programm verwendet (die für die gesamte Dauer Ihres Programms verfügbar sein sollen), vorab zuweisen muss, bevor alle Datenstrukturen zugewiesen werden Innerhalb von Funktionsaufrufen werden möglicherweise entfernt, wenn diese Funktionsaufrufe zurückkehren und ihre Frames oder Aktivierungsdatensätze vom Stapel entfernt werden.

Stapel eignen sich hervorragend für Speicherzuweisungen, die den LIFO-Regeln (Last in First Out) entsprechen, dh, Sie geben den Speicher in der genau umgekehrten Reihenfolge frei, in der Sie ihn zuweisen. LIFO ist ein sehr verbreitetes, vielleicht das häufigste Speicherzuweisungsmuster. Aber es ist nicht das einzige oder sogar das einzige gemeinsame Muster. Um ein effizientes Programm zu schreiben, das eine Vielzahl von Problemen lösen kann, müssen wir die weniger verbreiteten Muster berücksichtigen, auch wenn dies eine komplexere Infrastruktur bedeutet.

Wenn ich alle Metawerte für einen Absatz erhalten kann: Sie sind Anfänger, und als Anfänger legen Sie Wert auf Einfachheit und Schwarz-Weiß-Regeln. Als Anfänger haben Sie jedoch nur einen Überblick über die Bandbreite der Probleme und Einschränkungen, denen Computerprogramme gerecht werden müssen. Sie betreten eine Technologie, die seit 75 Jahren aktiv weiterentwickelt wird. Es ist nichts Falsches daran zu fragen, warum die Dinge so sind, wie sie sind, aber die Antwort lautet im Allgemeinen: "Ja, wir haben es vor 50 Jahren mit der einfachen, unkomplizierten Methode versucht, und es hat sich herausgestellt, dass es für ganze Klassen nicht sehr gut funktioniert von Problemen, so mussten wir etwas komplizierter machen ". Mit fortschreitender Technologie muss die Einfachheit im Allgemeinen der Effizienz und Flexibilität weichen.

Ein anderes Beispiel sind Verschlüsse. Wenn Sie Pop stapeln, können Sie den Aktivierungsdatensatz Ihres Verschlusses verlieren. Wenn Sie also möchten, dass diese anonyme Funktion und ihre Daten erhalten bleiben, müssen Sie sie an einem anderen Ort als dem Laufzeitstapel speichern.

Neben vielen anderen Gründen für die Zuweisung von Heap-Speicher.

Wenn Sie die Adresse eines Objekts an ein aufrufendes Programm zurückgeben möchten, sollten Sie die Adresse einer Stapelvariablen nicht weitergeben, da der Stapelspeicher von der nächsten aufgerufenen Funktion wiederverwendet und möglicherweise überschrieben wird. Sie müssen den erforderlichen Speicher mit malloc () abrufen, um sicherzustellen, dass er nicht durch Aufrufe nachfolgender Funktionen überschrieben wird.

Sie können Adressen von Stapelelementen aus Ihrer Funktion an aufgerufene Funktionen übergeben, da Sie garantieren können, dass sie existieren, bis Ihr Programm "return ()" zurückgibt. Sobald jedoch Ihre Funktion zurückgegeben wird, ist der gesamte Stapelspeicher verfügbar.