Warum ist die Speicherzuweisung auf dem Heap VIEL langsamer als auf dem Stack?

Das wurde mir schon oft gesagt. Aber ich weiß nicht, WARUM … Welche zusätzlichen Kosten entstehen beim Zuweisen von Speicher aus dem Heap? Liegt es an der Hardware? Liegt es an den CPU-Zyklen? So viele Vermutungen, aber keine genauen Antworten … Könnte mir jemand etwas näher erläutern?

Wie “entspannen” sagte, ist die Heap-Datenstruktur komplizierter als Stack. Und meiner Meinung nach wird einem Thread etwas Speicherplatz als Stack zugewiesen, wenn er zu laufen beginnt, während der Heap von allen Threads innerhalb eines Prozesses gemeinsam genutzt wird. Dieses Paradigma erfordert einen zusätzlichen Mechanismus, um die Nutzung des gemeinsam genutzten Heaps durch jeden Thread zu verwalten, wie z. B. Garbage Collection. Liege ich damit richtig?

HINZUFÜGEN 1 – 10:42 AM 13.5.2022

Die Verwaltung eines Stacks betrifft nur die Befehle und Register (SP, BP), was in gewissem Sinne natürlich/reine Hardware ist.

Während es sich bei einem Heap um komplexe Softwaredatenstrukturen und -algorithmen handelt, die Funktionsaufrufe (wiederum Stack-involviert), Speicherzugriff usw. umfassen.

Hardware ist schnell, aber nicht so flexibel wie Software.

Software ist flexibel, aber nicht so schnell wie Hardware.

Haufen ist also nicht billig.

Denn der Heap ist eine weitaus kompliziertere Datenstruktur als der Stack.

Bei vielen Architekturen ist das Zuweisen von Speicher auf dem Stack nur eine Frage des Änderns des Stack-Zeigers, dh es ist eine Anweisung. Das Zuweisen von Speicher auf dem Heap beinhaltet das Suchen nach einem ausreichend großen Block, dessen Aufteilung und die Verwaltung der “Buchhaltung”, die Dinge wie ermöglicht free() in einer anderen Reihenfolge.

Auf dem Stapel zugewiesener Speicher wird garantiert freigegeben, wenn der Gültigkeitsbereich (normalerweise die Funktion) beendet wird, und es ist nicht möglich, nur einen Teil davon freizugeben.

In Ihrer Bearbeitung, in der Sie die Antwort von Unwind wiederholen, erwähnen Sie die “Heap-Datenstruktur”. Seien Sie sehr vorsichtig, da die als a Haufen hat keine Beziehung zur dynamischen Speicherzuweisung. Um ganz klar zu sein, werde ich die mehrsprachige Anwaltsterminologie von verwenden kostenlos speichern.

Wie bereits erwähnt wurde, erfordert die Stack-Zuweisung das Inkrementieren eines Zeigers, der in den meisten Architekturen typischerweise ein dediziertes Register hat, und das Aufheben der Zuweisung erfordert den gleichen Arbeitsaufwand. Stack-Zuweisungen sind auch auf eine bestimmte Funktion beschränkt. Dies macht sie zu viel besseren Kandidaten für Compiler-Optimierungen wie das Vorberechnen des gesamten auf dem Stack benötigten Speicherplatzes und das Ausführen eines einzelnen Inkrements für einen gesamten Stack-Frame. Ebenso hat der Stack eine besser garantierte Datenlokalität. Die Spitze des Stapels befindet sich fast immer garantiert innerhalb einer Cache-Zeile, und wie ich bereits erwähnt habe, wird der Stapelzeiger normalerweise in einem Register gespeichert. Die Optimierung von Compilern auf einigen Architekturen kann sogar Zuweisungen auf dem Stack vollständig eliminieren, indem Argumente aus vorherigen Stack-Frames wiederverwendet werden, die als Argumente an aufgerufene Funktionen in tieferen Stack-Frames übergeben werden. Ebenso können Stack-zugewiesene Variablen oft in Register hochgestuft werden, um Zuweisungen ebenfalls zu vermeiden.

Im Gegensatz dazu ist der kostenlose Shop viel komplexer. Ich werde nicht einmal anfangen, Garbage-Collection-Systeme zu behandeln, da dies ein ganz anderes Thema ist, und diese Frage wurde in Bezug auf die C-Sprache gestellt. Typischerweise beinhalten Zuweisungen und Freigaben von einem freien Speicher mehrere unterschiedliche Datenstrukturen wie eine freie Liste oder einen Blockpool. Diese Datenstrukturen und die Buchführung erfordern ebenfalls Speicherplatz, und somit wird dieser Speicherplatz verschwendet. Außerdem werden die Buchhaltungsunterlagen oft mit den Zuweisungen vermischt und beeinträchtigen somit die Datenlokalität anderer Zuweisungen. Zuweisungen aus dem freien Speicher können beinhalten, dass das zugrunde liegende Betriebssystem nach mehr Prozessspeicher gefragt wird, typischerweise von irgendeiner Art von Slab-Zuordner.

Für einen einfachen Vergleich und unter Verwendung von jemalloc-2.2.5 und Zahlen von sloccount als Referenz enthält die jemalloc-Implementierung über 8.800 Zeilen Quellcode in der Sprache C und weitere über 700 Zeilen Testcode. Dies sollte Ihnen eine gute Vorstellung vom Komplexitätsunterschied zwischen freier Speicherzuweisung und Stapelzuweisung geben: Tausende von Zeilen C-Code im Vergleich zu einer einzelnen Anweisung.

Da außerdem freie Speicherzuordnungen nicht auf einen einzigen lexikalischen Bereich beschränkt sind, muss die Lebensdauer jeder Zuordnung verfolgt werden. Ebenso können diese Zuweisungen über Threads hinweg weitergegeben werden, und daher treten Thread-Synchronisationsprobleme in den Problemraum ein. Ein weiteres großes Problem für die kostenlose Speicherzuweisung ist die Fragmentierung. Fragmentierung verursacht viele Probleme:

• Fragmentierung schadet der Datenlokalität.
• Fragmentierung verschwendet Speicher.
• Fragmentierung erschwert die Suche nach freiem Speicherplatz für große Zuweisungen.

Auf modernen Systemen sind Stacks im Vergleich zum kostenlosen Speicher oft relativ klein, sodass der kostenlose Speicher letztendlich mehr Speicherplatz verwaltet und somit ein schwierigeres Problem angeht. Aufgrund der Beschränkungen der Stack-Größen wird der kostenlose Speicher typischerweise auch für größere Zuordnungen verwendet, diese Diskrepanz zwischen der Handhabung sowohl sehr großer als auch sehr kleiner Zuordnungen erschwert die Arbeit des kostenlosen Speichers ebenfalls. Typischerweise sind Stapelzuordnungen klein in der Größenordnung von einigen Kilobyte oder weniger, und die Gesamtgröße des Stapels beträgt nur wenige Megabyte. Der kostenlose Shop ist in der Regel die gegeben gesamten restlichen Prozessraum in einem Programm. Auf modernen Computern können dies mehrere hundert Gigabyte sein, und es ist nicht ungewöhnlich, dass kostenlose Speicherzuordnungen in der Größe von wenigen Bytes wie einer kurzen Zeichenfolge bis zu Megabytes oder sogar Gigabytes beliebiger Daten variieren. Dies bedeutet, dass Zuordner für freie Speicher sich mit der Verwaltung des virtuellen Speichers des zugrunde liegenden Betriebssystems befassen müssen. Die Stapelzuweisung ist im Wesentlichen in die Computerhardware integriert.

Wenn Sie wirklich etwas über die kostenlose Speicherzuweisung erfahren möchten, empfehle ich Ihnen dringend, einige der vielen Artikel und Artikel zu lesen, die über verschiedene Malloc-Implementierungen veröffentlicht wurden, oder sogar den Code zu lesen. Hier sind ein paar Links für den Einstieg:

• dlmalloc – Malloc von Doug Lea, eine historische Malloc-Referenzimplementierung, die zu einem bestimmten Zeitpunkt in GNU C++ verwendet wurde
• Phkmalloc – FreeBSD-Implementierung von malloc, geschrieben von Poul-Henning Kamp, dem Autor des Varnish-Webcaches
• tcmalloc – Thread-Caching Malloc, implementiert von einigen Google-Entwicklern
• jemalloc – Jason Evans malloc-Implementierung für FreeBSD (Nachfolger von phkmalloc)

Hier sind einige zusätzliche Links mit Beschreibungen der tcmalloc-Implementierung:

• http://jamesgolick.com/2013/5/15/memory-allocators-101.html
• http://jamesgolick.com/2013/5/19/how-tcmalloc-works.html

Der Hauptunterschied zwischen einem Stapel und einem Haufen besteht darin, dass Gegenstände auf einem Stapel nicht aus der Reihenfolge entfernt werden können. Wenn Sie die Elemente A, B, C zu einem Stapel hinzufügen, können Sie B nicht entfernen, ohne zuerst C zu entfernen. Das bedeutet, dass das Hinzufügen eines neuen Elements zu einem Stapel immer ein Hinzufügen zum Stapel bedeutet Ende des Stapels, was eine sehr einfache Operation ist. Sie bewegen einfach den Zeiger, der auf das Ende des Stapels zeigt.

Auf einem Haufen hingegen du kann Artikel aus der Reihenfolge entfernen. Und solange Sie die anderen Elemente nicht nachträglich im Speicher verschieben (wie es einige Müllhaufen tun), hat Ihr Haufen dann ein “Loch” in der Mitte. Dh wenn Sie A, B, C zu einem Heap hinzufügen und B entfernen, sieht Ihr Heap im Speicher so aus: A _ C wobei _ ein Block unbenutzten (freien) Speichers ist. Wenn Sie jetzt ein neues Element D hinzufügen, muss der Zuordner einen zusammenhängenden freien Speicherplatz finden, der groß genug ist, um D aufzunehmen. Je nachdem, wie viele zusammenhängende freie Plätze in Ihrem Speicher vorhanden sind, kann dies eine teure Operation sein. Und es ist fast immer teurer, als nur den “letztes Element”-Zeiger eines Stapels zu verschieben.

Erstellung von Daten im Stapelbereich: Bewegen Sie einfach den Stapelzeiger. Erstellung von Daten im Kopfbereich: Suchen Sie nach einem Bereich im Speicherpool, der die angegebene Anforderung erfüllt (Sie können First Fit, Best Fit oder Worst Fit verwenden). Nachdem Sie den Bereich gefunden haben, speichern Sie die Informationen (Buchführung)

Löschen auf Stapel : Löschen auf Stapel ist einfach. Bewegen Sie einfach den Stapelzeiger nach unten. Löschen auf Haufenbereich : Finden Sie heraus, wo das Element auf dem Haufen gespeichert ist (unter Verwendung der Buchhaltung) und führen Sie zwei benachbarte freie Blöcke zusammen, falls erforderlich;