Gibt es Alternativen zu Stack + Heap + statischem Speichermodell?

9

Alle Programme, die ich gesehen habe, organisieren ihren Datenspeicher in einen oder mehrere Aufrufstapel (normalerweise feste Größe, aber manchmal nicht), den Heap und den statischen Speicher. In letzter Zeit wurde auch ein threadlokaler statischer Speicher hinzugefügt.

Gab es Versuche, das Layout des Datenspeichers radikal anders zu organisieren, z. B. ohne den Aufrufstapel? Oder das Gedächtnis anders organisieren, um dasselbe zu erreichen?

ikh
quelle
Kommt darauf an, was du mit "Stapel" meinst. Sie können die Call-Stack-Frames in den Heap einfügen (mit Zeigern verknüpfen). Dann haben Sie keinen dedizierten linearen Speicherbereich für den Stapel, aber konzeptionell haben Sie immer noch einen Aufrufstapel.
und hängt davon ab, was Sie mit "vor kurzem" meinen. Ich denke, der lokale Thread-Speicher ist so alt wie die Threads. Bisher war der Zugriff jedoch über Systemaufrufe möglich, während Sie jetzt in neueren Sprachen direkt darauf zugreifen können.
DXM
Der Aufrufstapel ist erforderlich, da prozedurale Funktionen wissen müssen, wer sie aufgerufen hat, damit sie Ergebnisse zurückgeben und die Ausführung fortsetzen können. Der derzeitige Mechanismus ist in Bezug auf die CPU-Zyklen recht günstig, und zumindest mit x64 werden fast alle Funktionsargumente durch Register geleitet
James
2
Vielleicht finden Sie Eric Lipperts Beitrag " Why Have a Stack". von Interesse. Sein Hauptpunkt ist, dass ein Stapel eine effiziente und einfache Möglichkeit bietet, Speicherorte zu verfolgen. Er diskutiert eine Alternative in mehreren viel älteren Beiträgen, Continuation Passing Style .
Brian

Antworten:

8

Vielleicht möchten Sie einen Schritt zurücktreten und sehen, woher und warum diese vorhandenen Modelle stammen. Wenn ein Prozess erstellt wird, erhält er einfach einen flachen Speicherbereich, der einfach von 0 bis N indiziert wird. Da dieser Speicherbereich (hier geht es um RAM) von einer dedizierten Hardware und einigen ausgefallenen Halbleitern unterstützt wird, ist er ziemlich schnell. aber es ist nicht das einzige seiner Art. Andere Geräte wie Festplatten sind im Wesentlichen dasselbe, flacher Speicherplatz, der durch einen Index adressierbar ist, aber viele Größenordnungen langsamer.

Der Grund, warum "ein Heap" existiert, ist, dass es für jede Anwendung unpraktisch wäre, zu versuchen, die Verwendung von RAM selbst zu verwalten. Vor langer Zeit, genau so geschah es, planten Programmierer im Voraus genau, wofür jeder RAM-Speicherort verwendet werden würde. Da die Software immer komplexer wurde, sagte jemand, wäre es nicht schön, wenn ich einfach zu einer Black Box gehen und sagen könnte: "Ich brauche 10 Bytes, also gib mir" und mich nicht um all die komplizierten Details kümmern müsste, wo und wie diese 10 Bytes sind kommen von oder wie sie zurückgefordert werden. Das ist, was ein Haufen ist, wird nicht wirklich grundlegender als das.

Jedes Mal, wenn ein Thread erstellt wird, gibt es einige Datenstrukturen (und einen Stapel), die mit derselben "Gimme-Operation" erfasst werden, die ich gerade beschrieben habe. Ein Stack, der nahezu universell einsetzbar ist, da er perfekt zu Funktionsaufruf-Stack-Frames und deren LIFO-Charakter passt. Theoretisch könnten jeder Funktionsaufruf und jede lokale Variable auf dem Heap zugewiesen werden, aber das wäre einfach zu teuer, verglichen mit nur wenigen Montageanweisungen, die zum Aktualisieren des Stapelzeigerregisters (ESP auf x86) erforderlich sind.

Thread Local Storage (TLS) basiert ebenfalls auf dem Heap. Wenn ein Thread erstellt wird, wird im Rahmen einer Reise zum Heap zum Zuweisen von Speicher für Verwaltungsstrukturen auch ein separater Speicherplatz für TLS vom Heap zugewiesen.

Am Ende haben Sie also nur einen generischen Speicherzuweiser (dh den Heap), und alles andere ist darüber hinaus eine spezielle Form. Mit anderen Worten, wenn Sie bereit sind, einen Aspekt von "Ich möchte so viel (oder so wenig) zuweisen, wie ich möchte, so lange ich möchte und frei zu lassen, wann immer ich möchte" aufzugeben, könnten Sie dem Handel entkommen Aus generischem Heap-Allokator für ein anderes Modell, das Geschwindigkeit bietet, jedoch auf Kosten einer anderen Einschränkung.

Stapel nehmen. Es ist unglaublich schnell im Vergleich zum Heap, aber die beiden Kompromisse sind: 1) Sie steuern nicht, wann Speicher freigegeben wird; Sobald die Funktion beendet ist, ist alles, was Sie zugewiesen haben, weg und 2) da Stapel im Allgemeinen nur eine begrenzte Größe haben, sollten Sie vorsichtig sein, große Datenmengen direkt auf dem Stapel zuzuweisen.

Eine andere Art von "Speichermodell" ist der Virtual Memory Manager (VMM), der von nahezu jedem wichtigen Betriebssystem über Systemaufrufe angeboten wird. VMM ist Heap in dem Sinne sehr ähnlich, dass Sie nach beliebig viel Speicher fragen und ihn so lange aufbewahren können, wie Sie möchten. Die Einschränkung besteht jedoch darin, dass Sie Speicher nur in Seitengrößen-Vielfachen (z. B. 4 KB) zuweisen können, sodass die direkte Verwendung von VMM in einer typischen Anwendung, die häufig 8 bis 24 Byte gleichzeitig zuweist, viel Overhead verursachen würde. Tatsächlich basiert nahezu jede Heap-Implementierung auf VMM, um eine sehr allgemeine, nicht spezialisierte Zuweisung kleiner Blöcke zu ermöglichen. Heap geht immer dann an VMM, wenn mehr Speicher benötigt wird, und verteilt dann viele kleine Teile dieses Speichers an die Anwendung.

Wenn Sie eine App haben, für die große Blöcke zugewiesen werden müssen, können Sie direkt zu VMM wechseln. Einige Heaps enthalten jedoch eine if-Anweisung in malloc (). Wenn die Blockgröße einen bestimmten Schwellenwert überschreitet, werden sie einfach zu VMM weitergeleitet für dich.

Eine andere Form von Allokatoren, anstatt Heap direkt zu verwenden, wären Pools. Ein Pool ist ein spezialisierter Allokator, bei dem alle Blöcke dieselbe Größe haben. Pools (genau wie Stack und TLS) werden auf Heap oder VMM erstellt. Pools sind an Orten nützlich, an denen Sie viele (Millionen) kurzlebige, kleine Objekte derselben Größe zuweisen. Stellen Sie sich einen Netzwerkdienst vor, der eingehende Anforderungen verarbeitet. Jede Clientanforderung kann dazu führen, dass dieselbe N-Byte-Struktur zugewiesen wird, um diese Anforderung zu verarbeiten. Der Nachteil bei der Verwendung von Pools besteht darin, dass jeder Pool nur eine Blockgröße verarbeitet (Sie können jedoch mehrere Pools erstellen). Der Vorteil von Pools besteht darin, dass keine komplizierte Logik erforderlich ist, da alle Objekte dieselbe Größe haben. Wenn Sie stattdessen einen neuen Block benötigen, erhalten Sie nur den Block, der kürzlich freigegeben wurde.

Und zum Schluss denken Sie an die Festplatte, die ich oben erwähnt habe. Sie könnten ein Speichermodell haben, das sich wie ein Dateisystem verhält und dieselbe Vorstellung von Verzeichniseinträgen und i-Knoten dupliziert, um eine hierarchische Zuordnung von Datenblöcken zu ermöglichen, wobei jeder Datenblock mit einem Pfad adressiert ist. Genau das macht tmpfs .

Abgesehen von dem, was ich erwähnt habe, gibt es sicher noch andere spezialisiertere Modelle, aber am Ende basiert alles auf einem flachen Adressraum (bis einige Genuis einen seltsamen, nicht flachen Raum finden ) geht alles auf diesen generischen "Gimme" -Zuweiser zurück, der entweder VMM oder der Heap ist.

DXM
quelle
1

Die einzigen Fälle, an die ich denken kann, sind spezielle Hardware, bei denen möglicherweise alles an festen Speicherorten ausgeführt wird. Im aktuellen Speichermodell ist so ziemlich alles erforderlich, wenn Sie voll flexible Programme wünschen.

Ohne den Stapel können Sie keine lokalen Variablen, Aufrufstapel usw. haben. Alles andere, was Sie zur Implementierung schreiben, wird dem Stapel sehr ähnlich sehen.

Statischer Speicher und der Heap, den Sie möglicherweise für bestimmte Anwendungen löschen könnten, aber auch hier benötigen Sie sie in irgendeiner Form zurück, um etwas Fortgeschritteneres zu tun.

Alles, was Sie erfinden, um eines dieser drei zu ersetzen, wird am Ende einem dieser drei sehr ähnlich sehen ...

Was könnten Sie hinzufügen, um es aus einem anderen Blickwinkel zu betrachten, das neu ist? Sie könnten möglicherweise argumentieren, dass Dinge wie Grafik- / Physikprozessoren / CPU-Caches / usw. ein neuer Speicherort sind, aber in Wirklichkeit sind sie nur eine separate Instanz oder eine Möglichkeit, den Zugriff auf die vorhandenen Modelle zu beschleunigen.

... also bis jemand einen riesigen konzeptionellen Sprung macht, denke ich, dass wir in diesem Bereich für lange Zeit wahrscheinlich keine größeren Veränderungen sehen werden ...

Tim B.
quelle
4
Die meisten Leute neigen dazu anzunehmen, dass der aktuelle Weg der beste / einzige Weg ist, und wenn eine leere Tafel gegeben würde, würde nur kopiert, was bereits existiert. Die anderen Menschen sind diejenigen, die den technologischen Fortschritt tatsächlich vorantreiben. Um nicht zu sagen, dass ich persönlich ernsthafte konkurrierende Modelle kenne (es sei denn, Sie zählen Quantencomputer), aber zu behaupten, dass alles, was man sich einfallen lassen könnte , genauso aussehen würde wie das, was bereits existiert, ist im Wesentlichen eine Form des Zirkelschlusses.
Aaronaught
@Aaronaught: Die Kehrseite Ihres Arguments ist, dass andere Menschen viel Zeit, Geld und Energie damit verbringen, über den Tellerrand hinaus zu denken, und für jeweils 1000 (vielleicht viel mehr) von ihnen könnte man irgendwann den technologischen Fortschritt vorantreiben, während der Rest nirgendwo hinkommt . Während die erste Gruppe, die man für praktischer halten könnte, diese vorhandenen Modelle
unverändert
@aaronaught Ich denke, ich habe das mit "also bis jemand einen riesigen konzeptuellen Sprung auf irgendeine Art einfällt" abgedeckt;) Wenn Sie ein besseres alternatives Modell haben, können Sie es gerne vorschlagen ... wenn nicht, fühlt es sich ein bisschen scheinheilig an, sich darüber zu beschweren "einige Leute", wenn Sie einer von ihnen sind :)
Tim B
1
@ DXM: Also? Habe ich gesagt, dass wir alle unsere Zeit in die Erforschung neuer Speichermodelle investieren sollten? Ich habe nur auf den (signifikanten) Fehler in der Behauptung hingewiesen, dass eine Person nur Dinge erfinden kann, die bereits erfunden wurden.
Aaronaught
Eine Behauptung, die ich nie gemacht habe ...
Tim B