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

24

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?

Dunkler Templer
quelle
4
Zwei Auszüge aus Ihrer vorherigen Frage: "Der wichtigste Nachteil ist, dass der Platz begrenzt ist und große Objekte darin zu belassen oder sie für langlebige Objekte zu verwenden, sind sowohl schlechte Ideen" als auch "Stapel sind äußerst effizient Struktur für die Verwaltung von Daten, die den LIFO - Regeln (last in first out) entsprechen ".
Cascabel
2
Ihre Prämisse ist fehlerhaft - auf dem Stack kann nicht alles effizienter ausgeführt werden. Das ist kein Widerspruch zu den Antworten , die Sie erhalten - das , was kann auf dem Stapel getan werden kann , viel schneller dort durchgeführt werden.
Ingo
... vorausgesetzt, Ihre Hardware verfügt über einen Stack oder eine Stack-relative Adressierung.
Ritch Melton
3
Ich bin überzeugt. Ich sage, mach es.
JeffO

Antworten:

25

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)

Pubby
quelle
4
Dies hängt damit zusammen, dass Facebook Inhalte nicht von seiner Festplatte entfernt, wenn Sie darum bitten, sie zu entfernen, sondern lediglich den Zeiger darauf entfernt. Offensichtlich ist der Aufwand für das Defragmentieren oder Auffinden der entsprechenden Lücke auf der Festplatte zu zeitaufwändig, wenn die Daten geschrieben werden. Fügen Sie einfach alles an der Hochwassermarke der Festplatte hinzu.
Paul Tomblin
Nun, Facebooks Festplatten können als Haufen angesehen werden. Und ich bin mir ziemlich sicher, dass sie eine Art Müllsammlung für diese Datenträger haben.
Deadalnix
2
@deadalnix Tatsächlich ist dies ein Beispiel für die Verwendung eines großen Stapels anstelle des Heaps, der normalerweise für größere Speichermengen verwendet wird. Facebook ist jedoch ein Sonderfall. Daten werden so viel schneller hinzugefügt als entfernt, dass die Aufhebung der Zuordnung keinen signifikanten Unterschied zur Wachstumsrate darstellt. Sie können absichtlich Speicherverluste in den Entwurf einbeziehen, um diese O (1) -Zuordnung zu erhalten.
Tom Clarkson
7
@PaulTomblin Der Hauptgrund, warum FB den Inhalt nicht entfernt, ist, dass sie ihn für ihren Profit
abbauen können
5
Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it- Was im Wesentlichen passiert, wenn Sie eine Datei auf einem beliebigen Betriebssystem löschen.
Robert Harvey
5

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.

JBRWilkinson
quelle
4

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.

Alex
quelle
3
LIFO, nicht FIFO.
Pubby
manchmal auch FILO genannt;)
oenone
3

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.

Charles E. Grant
quelle
0

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.

anon
quelle
0

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.

James Anderson
quelle