Was schneller ist: Stapelzuweisung oder Heapzuweisung

Diese Frage mag ziemlich elementar klingen, aber dies ist eine Debatte, die ich mit einem anderen Entwickler geführt habe, mit dem ich zusammenarbeite.

Ich habe darauf geachtet, Dinge zu stapeln, wo ich konnte, anstatt sie zu häufen. Er sprach mit mir und beobachtete über meine Schulter und kommentierte, dass es nicht notwendig sei, weil sie in Bezug auf die Leistung gleich sind.

Ich hatte immer den Eindruck, dass das Wachstum des Stapels eine konstante Zeit war, und die Leistung der Heap-Zuweisung hing von der aktuellen Komplexität des Heaps ab, sowohl bei der Zuweisung (Finden eines Lochs mit der richtigen Größe) als auch beim Aufheben der Zuweisung (Zusammenfallen von Löchern, um die Fragmentierung zu verringern, wie z Viele Standardbibliotheksimplementierungen benötigen Zeit, um dies beim Löschen zu tun, wenn ich mich nicht irre.

Dies scheint mir etwas zu sein, das wahrscheinlich sehr vom Compiler abhängig wäre. Insbesondere für dieses Projekt verwende ich ein Metrowerks Compiler für die PPC- Architektur. Ein Einblick in diese Kombination wäre am hilfreichsten, aber was ist im Allgemeinen für GCC und MSVC ++ der Fall? Ist die Heap-Zuweisung nicht so leistungsfähig wie die Stapelzuweisung? Gibt es keinen Unterschied? Oder sind die Unterschiede so klein, dass sie zur sinnlosen Mikrooptimierung werden?

Die Stapelzuweisung ist viel schneller, da nur der Stapelzeiger bewegt wird. Wenn Sie Speicherpools verwenden, können Sie eine vergleichbare Leistung bei der Heap-Zuweisung erzielen. Dies ist jedoch mit einer geringfügig zusätzlichen Komplexität und eigenen Kopfschmerzen verbunden.

Außerdem ist Stack vs. Heap nicht nur eine Leistungsüberlegung. Außerdem erfahren Sie viel über die erwartete Lebensdauer von Objekten.

Der Stapel ist viel schneller. In den meisten Architekturen wird buchstäblich nur eine einzige Anweisung verwendet, in den meisten Fällen z. B. auf x86:

sub esp, 0x10

(Dadurch wird der Stapelzeiger um 0 x 10 Byte nach unten verschoben und diese Bytes werden zur Verwendung durch eine Variable "zugewiesen".)

Natürlich ist die Größe des Stapels sehr, sehr begrenzt, da Sie schnell feststellen werden, ob Sie die Stapelzuweisung überbeanspruchen oder versuchen, eine Rekursion durchzuführen :-)

Es gibt auch wenig Grund, die Leistung von Code zu optimieren, der dies nachweislich nicht benötigt, wie beispielsweise durch Profilerstellung gezeigt wird. "Vorzeitige Optimierung" verursacht oft mehr Probleme als es wert ist.

Meine Faustregel: Wenn ich weiß, dass ich zur Kompilierungszeit einige Daten benötige und diese weniger als ein paar hundert Bytes groß sind, ordne ich sie stapelweise zu. Ansonsten ordne ich es haufenweise zu.

Ehrlich gesagt ist es trivial, ein Programm zu schreiben, um die Leistung zu vergleichen:

#include <ctime>
#include <iostream>

namespace {
    class empty { }; // even empty classes take up 1 byte of space, minimum
}

int main()
{
    std::clock_t start = std::clock();
    for (int i = 0; i < 100000; ++i)
        empty e;
    std::clock_t duration = std::clock() - start;
    std::cout << "stack allocation took " << duration << " clock ticks\n";
    start = std::clock();
    for (int i = 0; i < 100000; ++i) {
        empty* e = new empty;
        delete e;
    };
    duration = std::clock() - start;
    std::cout << "heap allocation took " << duration << " clock ticks\n";
}

Es wird gesagt, dass eine dumme Konsequenz der Hobgoblin der kleinen Köpfe ist . Anscheinend sind optimierende Compiler die Hobgoblins vieler Programmierer. Diese Diskussion stand früher am Ende der Antwort, aber die Leute können sich anscheinend nicht die Mühe machen, so weit zu lesen. Deshalb verschiebe ich sie hierher, um zu vermeiden, dass ich Fragen bekomme, die ich bereits beantwortet habe.

Ein optimierender Compiler stellt möglicherweise fest, dass dieser Code nichts bewirkt, und optimiert möglicherweise alles weg. Es ist die Aufgabe des Optimierers, solche Dinge zu tun, und der Kampf gegen den Optimierer ist ein Kinderspiel.

Ich würde empfehlen, diesen Code bei deaktivierter Optimierung zu kompilieren, da es keine gute Möglichkeit gibt, jeden derzeit verwendeten oder in Zukunft verwendeten Optimierer zu täuschen.

Jeder, der den Optimierer einschaltet und sich dann über dessen Bekämpfung beschwert, sollte öffentlich lächerlich gemacht werden.

Wenn ich mich um Nanosekundengenauigkeit kümmern würde, würde ich sie nicht verwenden std::clock(). Wenn ich die Ergebnisse als Doktorarbeit veröffentlichen wollte, würde ich eine größere Sache darüber machen und wahrscheinlich GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC und andere Compiler vergleichen. So wie es ist, dauert die Heap-Zuweisung hunderte Male länger als die Stapelzuweisung, und ich sehe nichts Nützliches darin, die Frage weiter zu untersuchen.

Der Optimierer hat die Mission, den Code, den ich teste, loszuwerden. Ich sehe keinen Grund, dem Optimierer zu sagen, dass er ausgeführt werden soll, und dann zu versuchen, den Optimierer dazu zu bringen, nicht wirklich zu optimieren. Aber wenn ich Wert darin sehen würde, würde ich eine oder mehrere der folgenden Aktionen ausführen:

1. Fügen Sie ein Datenelement hinzu emptyund greifen Sie auf dieses Datenelement in der Schleife zu. Wenn ich jedoch immer nur aus dem Datenelement lese, kann der Optimierer ständig falten und die Schleife entfernen. Wenn ich immer nur in das Datenelement schreibe, überspringt der Optimierer möglicherweise alle bis auf die letzte Iteration der Schleife. Außerdem lautete die Frage nicht "Stapelzuweisung und Datenzugriff vs. Heapzuweisung und Datenzugriff".

2. Deklarieren e volatile, wird aber volatileoft falsch kompiliert (PDF).

3. Nehmen Sie die Adresse einnerhalb der Schleife (und weisen Sie sie möglicherweise einer Variablen zu, externdie in einer anderen Datei deklariert und definiert ist). Aber selbst in diesem Fall kann der Compiler feststellen, dass - zumindest auf dem Stapel - eimmer dieselbe Speicheradresse zugewiesen wird, und dann wie in (1) oben konstant gefaltet wird. Ich bekomme alle Iterationen der Schleife, aber das Objekt wird nie wirklich zugewiesen.

Über das Offensichtliche hinaus ist dieser Test insofern fehlerhaft, als er sowohl die Zuweisung als auch die Freigabe misst, und die ursprüngliche Frage hat nicht nach der Freigabe gefragt. Natürlich werden auf dem Stapel zugewiesene Variablen am Ende ihres Gültigkeitsbereichs automatisch freigegeben, sodass ein Nichtaufruf delete(1) die Zahlen verzerren würde (die Freigabe des Stapels ist in den Zahlen zur Stapelzuweisung enthalten, daher ist es nur fair, die Freigabe des Heapspeichers zu messen) und ( 2) verursachen einen ziemlich schlechten Speicherverlust, es sei denn, wir behalten einen Verweis auf den neuen Zeiger und rufen auf, deletenachdem wir unsere Zeitmessung erhalten haben.

Auf meinem Computer, der g ++ 3.4.4 unter Windows verwendet, erhalte ich "0 Clock Ticks" für die Stapel- und Heap-Zuordnung für weniger als 100000 Zuweisungen, und selbst dann erhalte ich "0 Clock Ticks" für die Stack-Zuweisung und "15 Clock Ticks" "für die Heap-Zuordnung. Wenn ich 10.000.000 Zuweisungen messe, benötigt die Stapelzuweisung 31 Takt-Ticks und die Heap-Zuweisung 1562 Takt-Ticks.

Ja, ein optimierender Compiler kann das Erstellen der leeren Objekte vermeiden. Wenn ich es richtig verstehe, kann es sogar die gesamte erste Schleife auslassen. Als ich die Iterationen auf 10.000.000 stapelte, dauerte die Stapelzuweisung 31 Takt-Ticks und die Heap-Zuweisung 1562 Takt-Ticks. Ich denke, man kann mit Sicherheit sagen, dass g ++ die Konstruktoren nicht entfernt hat, ohne g ++ anzuweisen, die ausführbare Datei zu optimieren.

In den Jahren, seit ich dies geschrieben habe, bestand die Präferenz für Stack Overflow darin, die Leistung von optimierten Builds zu veröffentlichen. Im Allgemeinen denke ich, dass dies richtig ist. Ich halte es jedoch immer noch für dumm, den Compiler zu bitten, den Code zu optimieren, wenn Sie diesen Code tatsächlich nicht optimieren möchten. Es scheint mir sehr ähnlich zu sein, als würde man für den Parkservice extra bezahlen, aber ich weigere mich, die Schlüssel zu übergeben. In diesem speziellen Fall möchte ich nicht, dass der Optimierer ausgeführt wird.

Verwenden einer leicht modifizierten Version des Benchmarks (um den gültigen Punkt zu adressieren, den das ursprüngliche Programm nicht jedes Mal durch die Schleife auf dem Stapel zugewiesen hat) und Kompilieren ohne Optimierungen, sondern Verknüpfen mit Release-Bibliotheken (um den gültigen Punkt zu adressieren, den wir nicht verwenden Ich möchte keine Verlangsamung einschließen, die durch die Verknüpfung mit Debug-Bibliotheken verursacht wird.

#include <cstdio>
#include <chrono>

namespace {
    void on_stack()
    {
        int i;
    }

    void on_heap()
    {
        int* i = new int;
        delete i;
    }
}

int main()
{
    auto begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_stack();
    auto end = std::chrono::system_clock::now();

    std::printf("on_stack took %f seconds\n", std::chrono::duration<double>(end - begin).count());

    begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_heap();
    end = std::chrono::system_clock::now();

    std::printf("on_heap took %f seconds\n", std::chrono::duration<double>(end - begin).count());
    return 0;
}

zeigt an:

on_stack took 2.070003 seconds
on_heap took 57.980081 seconds

auf meinem System beim Kompilieren mit der Kommandozeile cl foo.cc /Od /MT /EHsc.

Sie sind möglicherweise nicht mit meinem Ansatz einverstanden, einen nicht optimierten Build zu erhalten. Das ist in Ordnung: Ändern Sie den Benchmark so oft Sie möchten. Wenn ich die Optimierung einschalte, erhalte ich:

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

Nicht weil die Stapelzuweisung tatsächlich sofort erfolgt, sondern weil jeder halbwegs anständige Compiler feststellen kann, dass on_stackdies nichts Nützliches bewirkt und wegoptimiert werden kann. GCC auf meinem Linux-Laptop bemerkt auch, dass on_heapes nichts Nützliches tut, und optimiert es auch weg:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

Eine interessante Sache, die ich über die Stapel- / Heap-Zuweisung auf dem Xbox 360 Xenon-Prozessor gelernt habe, die möglicherweise auch für andere Multicore-Systeme gilt, ist, dass durch die Zuweisung auf dem Heap ein kritischer Abschnitt eingegeben wird, um alle anderen Kerne anzuhalten, sodass die Zuweisung nicht erfolgt kein Konflikt. In einer engen Schleife war die Stapelzuweisung der richtige Weg für Arrays mit fester Größe, da sie ein Abwürgen verhinderte.

Dies kann eine weitere Beschleunigung sein, die Sie berücksichtigen sollten, wenn Sie für Multicore / Multiproc codieren, da Ihre Stapelzuweisung nur für den Kern sichtbar ist, in dem Ihre Bereichsfunktion ausgeführt wird, und dies keine Auswirkungen auf andere Kerne / CPUs hat.

Sie können einen speziellen Heap-Allokator für bestimmte Objektgrößen schreiben, der sehr leistungsfähig ist. Der allgemeine Heap-Allokator ist jedoch nicht besonders leistungsfähig.

Ich stimme auch Torbjörn Gyllebring hinsichtlich der erwarteten Lebensdauer von Objekten zu. Guter Punkt!

Ich denke nicht, dass Stapelzuweisung und Heapzuweisung im Allgemeinen austauschbar sind. Ich hoffe auch, dass die Leistung beider für den allgemeinen Gebrauch ausreicht.

Ich würde dringend empfehlen, für kleine Gegenstände, je nachdem, welcher für den Umfang der Zuordnung besser geeignet ist. Für große Gegenstände ist der Haufen wahrscheinlich notwendig.

Auf 32-Bit-Betriebssystemen mit mehreren Threads ist der Stapel häufig eher begrenzt (wenn auch normalerweise auf mindestens einige MB), da der Adressraum aufgeteilt werden muss und früher oder später ein Thread-Stapel in einen anderen ausgeführt wird. Auf Single-Thread-Systemen (Linux Glibc Single-Threaded sowieso) ist die Einschränkung viel geringer, da der Stack einfach wachsen und wachsen kann.

Unter 64-Bit-Betriebssystemen ist genügend Adressraum vorhanden, um Thread-Stapel recht groß zu machen.

Normalerweise besteht die Stapelzuweisung nur aus dem Subtrahieren vom Stapelzeigerregister. Dies ist tonnenweise schneller als die Suche nach einem Haufen.

Manchmal erfordert die Stapelzuweisung das Hinzufügen einer oder mehrerer Seiten des virtuellen Speichers. Das Hinzufügen einer neuen Seite mit Nullspeicher erfordert nicht das Lesen einer Seite von der Festplatte. Daher ist dies normalerweise immer noch tonnenweise schneller als das Durchsuchen eines Heaps (insbesondere, wenn ein Teil des Heaps ebenfalls ausgelagert wurde). In einer seltenen Situation, und Sie könnten ein solches Beispiel erstellen, ist gerade in einem Teil des Heapspeichers, der sich bereits im RAM befindet, genügend Speicherplatz verfügbar. Das Zuweisen einer neuen Seite für den Stapel muss jedoch warten, bis eine andere Seite ausgeschrieben ist auf die Festplatte. In dieser seltenen Situation ist der Haufen schneller.

Abgesehen von dem Leistungsvorteil um Größenordnungen gegenüber der Heap-Zuweisung ist die Stapelzuweisung für Serveranwendungen mit langer Laufzeit vorzuziehen. Selbst die am besten verwalteten Heaps werden schließlich so fragmentiert, dass die Anwendungsleistung abnimmt.

Ein Stapel hat eine begrenzte Kapazität, ein Heap jedoch nicht. Der typische Stapel für einen Prozess oder Thread liegt bei 8 KB. Sie können die Größe nach der Zuweisung nicht mehr ändern.

Eine Stapelvariable folgt den Scoping-Regeln, eine Heap-Variable nicht. Wenn Ihr Anweisungszeiger über eine Funktion hinausgeht, verschwinden alle neuen Variablen, die der Funktion zugeordnet sind.

Am wichtigsten ist jedoch, dass Sie die gesamte Funktionsaufrufkette nicht im Voraus vorhersagen können. Eine Zuweisung von nur 200 Bytes kann also einen Stapelüberlauf auslösen. Dies ist besonders wichtig, wenn Sie eine Bibliothek und keine Anwendung schreiben.

Ich denke, die Lebensdauer ist entscheidend und ob die zugewiesene Sache auf komplexe Weise konstruiert werden muss. Beispielsweise müssen Sie bei der transaktionsgesteuerten Modellierung normalerweise eine Transaktionsstruktur mit einer Reihe von Feldern ausfüllen und an Operationsfunktionen übergeben. Ein Beispiel finden Sie im OSCI SystemC TLM-2.0-Standard.

Das Zuweisen dieser auf dem Stapel in der Nähe des Aufrufs zur Operation verursacht tendenziell einen enormen Overhead, da die Konstruktion teuer ist. Die gute Möglichkeit besteht darin, die Transaktionsobjekte auf dem Heap zuzuweisen und entweder durch Pooling oder durch eine einfache Richtlinie wie "Dieses Modul benötigt immer nur ein Transaktionsobjekt" wiederzuverwenden.

Dies ist um ein Vielfaches schneller als das Zuweisen des Objekts bei jedem Operationsaufruf.

Der Grund ist einfach, dass das Objekt eine teure Konstruktion und eine ziemlich lange Lebensdauer hat.

Ich würde sagen: Probieren Sie beide aus und finden Sie heraus, was in Ihrem Fall am besten funktioniert, da dies wirklich vom Verhalten Ihres Codes abhängen kann.

Das wahrscheinlich größte Problem der Heap-Zuweisung im Vergleich zur Stapelzuweisung besteht darin, dass die Heap-Zuweisung im allgemeinen Fall eine unbegrenzte Operation ist und Sie sie daher nicht verwenden können, wenn das Timing ein Problem darstellt.

Bei anderen Anwendungen, bei denen das Timing keine Rolle spielt, spielt es möglicherweise keine Rolle. Wenn Sie jedoch viel Heap zuweisen, wirkt sich dies auf die Ausführungsgeschwindigkeit aus. Versuchen Sie immer, den Stapel für kurzlebigen und häufig zugewiesenen Speicher (z. B. in Schleifen) zu verwenden, und führen Sie so lange wie möglich eine Heap-Zuweisung während des Anwendungsstarts durch.

Es ist nicht die Stapelzuweisung, die schneller ist. Sie gewinnen auch viel bei der Verwendung von Stapelvariablen. Sie haben eine bessere Referenzlokalität. Und schließlich ist die Freigabe auch viel billiger.

Die Stapelzuweisung besteht aus ein paar Anweisungen, während der schnellste mir bekannte RTOS-Heap-Allokator (TLSF) durchschnittlich 150 Anweisungen verwendet. Außerdem erfordern Stapelzuweisungen keine Sperre, da sie lokalen Thread-Speicher verwenden, was ein weiterer großer Leistungsgewinn ist. Die Stapelzuweisungen können also 2-3 Größenordnungen schneller sein, je nachdem, wie stark Ihre Umgebung mit mehreren Threads ausgestattet ist.

Im Allgemeinen ist die Heap-Zuweisung Ihr letzter Ausweg, wenn Sie Wert auf Leistung legen. Eine praktikable Zwischenoption kann ein fester Pool-Allokator sein, der auch nur ein paar Anweisungen enthält und nur einen geringen Overhead pro Zuordnung aufweist, sodass er sich hervorragend für kleine Objekte mit fester Größe eignet. Auf der anderen Seite funktioniert es nur mit Objekten fester Größe, ist nicht von Natur aus threadsicher und hat Probleme mit der Blockfragmentierung.

Spezifische Bedenken für die C ++ - Sprache

Erstens gibt es keine von C ++ vorgeschriebene sogenannte "Stack" - oder "Heap" -Zuweisung . Wenn Sie von automatischen Objekten in Blockbereichen sprechen, werden sie sogar nicht "zugewiesen". (Übrigens ist die automatische Speicherdauer in C definitiv NICHT gleich "zugewiesen"; letzteres ist im C ++ - Sprachgebrauch "dynamisch".) Der dynamisch zugewiesene Speicher befindet sich im freien Speicher , nicht unbedingt auf "dem Heap" Letzteres ist häufig die (Standard-) Implementierung .

Obwohl gemäß den semantischen Regeln der abstrakten Maschine automatische Objekte immer noch Speicher belegen, darf eine konforme C ++ - Implementierung diese Tatsache ignorieren, wenn sie beweisen kann, dass dies keine Rolle spielt (wenn sie das beobachtbare Verhalten des Programms nicht ändert). Diese Berechtigung wird durch die Als-ob-Regel in ISO C ++ erteilt. Dies ist auch die allgemeine Klausel, die die üblichen Optimierungen ermöglicht (und es gibt auch eine fast gleiche Regel in ISO C). Neben der Als-ob-Regel gibt es in ISO C ++ auch Regeln für die Kopierelisionum das Weglassen bestimmter Kreationen von Objekten zu ermöglichen. Die beteiligten Konstruktor- und Destruktoraufrufe werden dabei weggelassen. Infolgedessen werden auch die automatischen Objekte (falls vorhanden) in diesen Konstruktoren und Destruktoren eliminiert, verglichen mit der durch den Quellcode implizierten naiven abstrakten Semantik.

Auf der anderen Seite ist die kostenlose Zuweisung von Filialen definitiv eine "Zuweisung". Nach ISO C ++ - Regeln kann eine solche Zuordnung durch Aufrufen einer Zuordnungsfunktion erreicht werden . Seit ISO C ++ 14 gibt es jedoch eine neue (nicht als ob) Regel, nach der ::operator newin bestimmten Fällen Aufrufe der globalen Zuordnungsfunktion (dh ) zusammengeführt werden können. So können Teile dynamischer Zuordnungsoperationen auch wie bei automatischen Objekten nicht ausgeführt werden.

Zuweisungsfunktionen weisen Speicherressourcen zu. Objekte können basierend auf der Zuordnung mithilfe von Zuweisern weiter zugeordnet werden. Bei automatischen Objekten werden sie direkt dargestellt - obwohl auf den zugrunde liegenden Speicher zugegriffen werden kann und verwendet werden kann, um anderen Objekten Speicher bereitzustellen (durch Platzierung new), ist dies als freier Speicher nicht sehr sinnvoll, da es keine Möglichkeit gibt, den zu verschieben Ressourcen anderswo.

Alle anderen Bedenken liegen außerhalb des Anwendungsbereichs von C ++. Trotzdem können sie immer noch von Bedeutung sein.

Informationen zu Implementierungen von C ++

C ++ stellt keine reifizierten Aktivierungsdatensätze oder erstklassige Fortsetzungen (z. B. von berühmten call/cc) zur Verfügung. Es gibt keine Möglichkeit, die Aktivierungsdatensatzrahmen direkt zu manipulieren - wo die Implementierung die automatischen Objekte platzieren muss. Sobald es keine (nicht portierbaren) Interoperationen mit der zugrunde liegenden Implementierung gibt ("nativer" nicht portabler Code, wie z. B. Inline-Assembly-Code), kann das Weglassen der zugrunde liegenden Zuordnung der Frames recht trivial sein. Wenn beispielsweise die aufgerufene Funktion inline ist, können die Frames effektiv mit anderen zusammengeführt werden, sodass die "Zuordnung" nicht angezeigt werden kann.

Sobald jedoch die Interops eingehalten werden, werden die Dinge immer komplexer. Eine typische Implementierung von C ++ bietet die Möglichkeit der Interop-Funktion auf ISA (Befehlssatzarchitektur) mit einigen Aufrufkonventionen als Binärgrenze, die mit dem nativen Code (Computer auf ISA-Ebene) geteilt wird. Dies wäre explizit kostspielig, insbesondere wenn der Stapelzeiger beibehalten wird , der häufig direkt von einem Register auf ISA-Ebene gehalten wird (mit wahrscheinlich spezifischen Maschinenanweisungen für den Zugriff). Der Stapelzeiger zeigt die Grenze des oberen Rahmens des (derzeit aktiven) Funktionsaufrufs an. Wenn ein Funktionsaufruf eingegeben wird, wird ein neuer Rahmen benötigt und der Stapelzeiger wird (abhängig von der ISA-Konvention) um einen Wert addiert oder subtrahiert, der nicht kleiner als die erforderliche Rahmengröße ist. Der Rahmen wird dann als zugeordnet bezeichnetwenn der Stapelzeiger nach den Operationen. Abhängig von der für den Aufruf verwendeten Aufrufkonvention können auch Funktionsparameter an den Stapelrahmen übergeben werden. Der Frame kann den Speicher von automatischen Objekten (wahrscheinlich einschließlich der Parameter) enthalten, die im C ++ - Quellcode angegeben sind. Im Sinne solcher Implementierungen werden diese Objekte "zugeordnet". Wenn die Steuerung den Funktionsaufruf verlässt, wird der Frame nicht mehr benötigt. Er wird normalerweise freigegeben, indem der Stapelzeiger auf den Zustand vor dem Aufruf zurückgesetzt wird (zuvor gemäß der Aufrufkonvention gespeichert). Dies kann als "Freigabe" angesehen werden. Diese Operationen machen den Aktivierungsdatensatz effektiv zu einer LIFO-Datenstruktur, so dass er häufig als " (Aufruf-) Stapel " bezeichnet wird.

Da die meisten C ++ - Implementierungen (insbesondere diejenigen, die auf nativen Code auf ISA-Ebene abzielen und die Assemblersprache als unmittelbare Ausgabe verwenden) ähnliche Strategien wie diese verwenden, ist ein derart verwirrendes "Zuweisungsschema" beliebt. Solche Zuweisungen (sowie Freigaben) verbringen Maschinenzyklen und können teuer sein, wenn die (nicht optimierten) Aufrufe häufig auftreten, obwohl moderne CPU-Mikroarchitekturen komplexe Optimierungen aufweisen können, die von der Hardware für das gemeinsame Codemuster implementiert werden (wie die Verwendung von a Stack Engine in Implementierung PUSH/ POPAnweisungen).

Im Allgemeinen ist es jedoch richtig, dass die Kosten für die Zuweisung von Stapelrahmen erheblich geringer sind als bei einem Aufruf einer Zuweisungsfunktion, die den freien Speicher betreibt (es sei denn, sie ist vollständig optimiert) , die selbst Hunderte (wenn nicht Millionen von) haben kann :-) Operationen zum Beibehalten des Stapelzeigers und anderer Zustände. Zuweisungsfunktionen basieren normalerweise auf der API, die von der gehosteten Umgebung bereitgestellt wird (z. B. die vom Betriebssystem bereitgestellte Laufzeit). Anders als beim Halten automatischer Objekte für Funktionsaufrufe sind solche Zuordnungen allgemein bestimmt, sodass sie keine Rahmenstruktur wie ein Stapel aufweisen. Traditionell weisen sie Speicherplatz aus dem Poolspeicher zu, der als Heap (oder mehrere Heaps) bezeichnet wird. Anders als beim "Stapel" gibt das Konzept "Heap" hier nicht die verwendete Datenstruktur an;Es wurde aus frühen Sprachimplementierungen vor Jahrzehnten abgeleitet . (Übrigens wird der Aufrufstapel normalerweise von der Umgebung beim Programm- oder Thread-Start mit einer festen oder benutzerdefinierten Größe aus dem Heap zugewiesen.) Die Art der Anwendungsfälle macht Zuweisungen und Freigaben von einem Heap weitaus komplizierter (als Push oder Pop of) Stack-Frames) und kaum direkt durch Hardware zu optimieren.

Auswirkungen auf den Speicherzugriff

Bei der üblichen Stapelzuordnung wird der neue Frame immer oben platziert, sodass er eine recht gute Lokalität aufweist. Dies ist freundlich zum Cache. OTOH, Speicher, der zufällig im freien Speicher zugewiesen wird, hat keine solche Eigenschaft. Seit ISO C ++ 17 werden Poolressourcenvorlagen von bereitgestellt <memory>. Der direkte Zweck einer solchen Schnittstelle besteht darin, die Ergebnisse aufeinanderfolgender Zuordnungen im Speicher nahe beieinander liegen zu lassen. Dies erkennt die Tatsache an, dass diese Strategie im Allgemeinen gut für die Leistung bei zeitgemäßen Implementierungen ist, z. B. für das Zwischenspeichern in modernen Architekturen. Hier geht es jedoch eher um die Leistung des Zugriffs als um die Zuweisung .

Parallelität

Die Erwartung eines gleichzeitigen Zugriffs auf den Speicher kann unterschiedliche Auswirkungen zwischen dem Stapel und den Heaps haben. Ein Aufrufstapel gehört normalerweise ausschließlich einem Ausführungsthread in einer C ++ - Implementierung. OTOH, Heaps werden oft geteilt zwischen den Threads in einem Prozess. Für solche Heaps müssen die Zuordnungs- und Freigabefunktionen die gemeinsam genutzte interne Verwaltungsdatenstruktur vor dem Datenrennen schützen. Infolgedessen können Heap-Zuweisungen und Freigaben aufgrund interner Synchronisierungsvorgänge zusätzlichen Aufwand verursachen.

Raumeffizienz

Aufgrund der Art der Anwendungsfälle und internen Datenstrukturen können Heaps unter einer internen Speicherfragmentierung leiden , während dies beim Stack nicht der Fall ist. Dies hat keine direkten Auswirkungen auf die Leistung der Speicherzuweisung, aber in einem System mit virtuellem Speicher kann eine geringe Speichereffizienz die Gesamtleistung des Speicherzugriffs beeinträchtigen. Dies ist besonders schrecklich, wenn die Festplatte als Austausch des physischen Speichers verwendet wird. Dies kann zu einer recht langen Latenz führen - manchmal zu Milliarden von Zyklen.

Einschränkungen der Stapelzuweisungen

Obwohl Stapelzuweisungen in der Realität häufig überlegen sind als Heapzuweisungen, bedeutet dies sicherlich nicht, dass Stapelzuweisungen immer Heapzuweisungen ersetzen können.

Erstens gibt es mit ISO C ++ keine Möglichkeit, Speicherplatz auf dem Stapel mit einer zur Laufzeit angegebenen Größe portabel zuzuweisen. Es gibt Erweiterungen, die von Implementierungen wie allocaund G ++ 's VLA (Array variabler Länge) bereitgestellt werden , aber es gibt Gründe, sie zu vermeiden. (IIRC, Linux-Quelle entfernt kürzlich die Verwendung von VLA.) (Beachten Sie auch, dass ISO C99 VLA vorgeschrieben hat, ISO C11 jedoch die Unterstützung optional macht.)

Zweitens gibt es keine zuverlässige und tragbare Möglichkeit, die Erschöpfung des Stapelplatzes zu erkennen. Dies wird oft als Stapelüberlauf bezeichnet _{(hmm, die Etymologie dieser Site)} , aber wahrscheinlich genauer als Stapelüberlauf . In der Realität führt dies häufig zu einem ungültigen Speicherzugriff, und der Status des Programms wird dann beschädigt (... oder schlimmer noch, eine Sicherheitslücke). In der Tat hat ISO C ++ kein Konzept von "The Stack" und macht es zu einem undefinierten Verhalten, wenn die Ressource erschöpft ist . Seien Sie vorsichtig, wie viel Platz für automatische Objekte übrig bleiben soll.

Wenn der Stapelspeicherplatz knapp wird, sind zu viele Objekte im Stapel zugeordnet, was durch zu viele aktive Funktionsaufrufe oder die missbräuchliche Verwendung automatischer Objekte verursacht werden kann. Solche Fälle können auf das Vorhandensein von Fehlern hinweisen, z. B. einen rekursiven Funktionsaufruf ohne korrekte Beendigungsbedingungen.

Trotzdem sind manchmal tiefe rekursive Aufrufe erwünscht. Bei Implementierungen von Sprachen, die die Unterstützung ungebundener aktiver Aufrufe erfordern (wobei die Anruftiefe nur durch den Gesamtspeicher begrenzt ist), ist es unmöglich , den (zeitgemäßen) nativen Aufrufstapel wie typische C ++ - Implementierungen direkt als Aktivierungsdatensatz für die Zielsprache zu verwenden. Um das Problem zu umgehen, werden alternative Methoden zur Erstellung von Aktivierungsdatensätzen benötigt. Beispielsweise weist SML / NJ Frames explizit auf dem Heap zu und verwendet Kaktusstapel . Die komplizierte Zuordnung solcher Aktivierungsdatensatzrahmen ist normalerweise nicht so schnell wie die Aufrufstapelrahmen. Wenn solche Sprachen jedoch mit der Garantie einer ordnungsgemäßen Schwanzrekursion weiter implementiert werdenDie direkte Stapelzuweisung in der Objektsprache (dh das "Objekt" in der Sprache wird nicht als Referenz gespeichert, sondern native primitive Werte, die eins zu eins auf nicht gemeinsam genutzte C ++ - Objekte abgebildet werden können) ist noch komplizierter Leistungsstrafe im Allgemeinen. Bei der Implementierung solcher Sprachen in C ++ ist es schwierig, die Auswirkungen auf die Leistung abzuschätzen.

Bei solchen Optimierungen ist ein allgemeiner Punkt zu beachten.

Die Optimierung, die Sie erhalten, ist proportional zu der Zeit, die sich der Programmzähler tatsächlich in diesem Code befindet.

Wenn Sie den Programmzähler testen, werden Sie herausfinden, wo er seine Zeit verbringt, und das ist normalerweise in einem winzigen Teil des Codes und häufig in Bibliotheksroutinen, über die Sie keine Kontrolle haben.

Nur wenn Sie feststellen, dass es viel Zeit in der Heap-Zuordnung Ihrer Objekte verbringt, ist die Stapelzuweisung spürbar schneller.

Die Stapelzuweisung ist fast immer so schnell oder schneller als die Heapzuweisung, obwohl es für einen Heapzuweiser sicherlich möglich ist, einfach eine stapelbasierte Zuweisungstechnik zu verwenden.

Es gibt jedoch größere Probleme, wenn es um die Gesamtleistung der Stapel- / Heap-basierten Zuordnung geht (oder, etwas besser ausgedrückt, der lokalen vs. externen Zuweisung). Normalerweise ist die (externe) Heap-Zuweisung langsam, da es sich um viele verschiedene Arten von Zuweisungen und Zuordnungsmustern handelt. Wenn Sie den Umfang des verwendeten Allokators reduzieren (lokal für den Algorithmus / Code), wird die Leistung tendenziell ohne größere Änderungen gesteigert. Wenn Sie Ihren Zuordnungsmustern eine bessere Struktur hinzufügen, z. B. eine LIFO-Reihenfolge für Zuordnungs- und Freigabepaare erzwingen, können Sie auch die Leistung Ihres Zuweisers verbessern, indem Sie den Zuweiser einfacher und strukturierter verwenden. Sie können auch einen Allokator verwenden oder schreiben, der auf Ihr bestimmtes Allokationsmuster abgestimmt ist. Die meisten Programme weisen häufig einige diskrete Größen zu. Ein Heap, der auf einem Lookaside-Puffer mit einigen festen (vorzugsweise bekannten) Größen basiert, ist daher äußerst leistungsfähig. Windows verwendet aus diesem Grund seinen Low-Fragmentation-Heap.

Andererseits ist die stapelbasierte Zuweisung in einem 32-Bit-Speicherbereich auch mit Gefahren verbunden, wenn Sie zu viele Threads haben. Stapel benötigen einen zusammenhängenden Speicherbereich. Je mehr Threads Sie haben, desto mehr virtuellen Adressraum benötigen Sie, damit sie ohne Stapelüberlauf ausgeführt werden können. Dies ist (vorerst) kein Problem mit 64-Bit, aber es kann in lang laufenden Programmen mit vielen Threads sicherlich Chaos anrichten. Der virtuelle Adressraum aufgrund von Fragmentierung ist immer ein Problem.

Wie andere gesagt haben, ist die Stapelzuweisung im Allgemeinen viel schneller.

Wenn das Kopieren Ihrer Objekte jedoch teuer ist, kann das Zuweisen auf dem Stapel später zu einem enormen Leistungseinbruch führen, wenn Sie die Objekte verwenden, wenn Sie nicht vorsichtig sind.

Wenn Sie beispielsweise etwas auf dem Stapel zuweisen und es dann in einen Container legen, wäre es besser gewesen, es auf dem Heap zuzuweisen und den Zeiger im Container zu speichern (z. B. mit einem std :: shared_ptr <>). Das Gleiche gilt, wenn Sie Objekte nach Wert und andere ähnliche Szenarien übergeben oder zurückgeben.

Der Punkt ist, dass, obwohl die Stapelzuweisung in vielen Fällen normalerweise besser ist als die Heapzuweisung, manchmal mehr Probleme verursachen als lösen können, wenn Sie sich die Mühe machen, die Stapelzuweisung vorzunehmen, wenn sie nicht am besten zum Berechnungsmodell passt.

class Foo {
public:
    Foo(int a) {

    }
}
int func() {
    int a1, a2;
    std::cin >> a1;
    std::cin >> a2;

    Foo f1(a1);
    __asm push a1;
    __asm lea ecx, [this];
    __asm call Foo::Foo(int);

    Foo* f2 = new Foo(a2);
    __asm push sizeof(Foo);
    __asm call operator new;//there's a lot instruction here(depends on system)
    __asm push a2;
    __asm call Foo::Foo(int);

    delete f2;
}

Es wäre so in asm. Wenn Sie sich in befinden func, wurde der f1Zeiger f2und auf dem Stapel zugewiesen (automatisierter Speicher). Übrigens f1(a1)hat Foo keine Anweisungseffekte auf den Stapelzeiger ( esp). Es wurde zugewiesen. Wenn funcSie das Mitglied erhalten möchten f1, ist die Anweisung ungefähr so ​​: lea ecx [ebp+f1], call Foo::SomeFunc(). Eine andere Sache, die die Stapelzuweisung dazu führen kann, dass jemand denkt, der Speicher sei so etwas wie das FIFO, FIFOwas gerade passiert ist, wenn Sie in eine Funktion gehen. Wenn Sie in der Funktion sind und so etwas zuweisen int i = 0, ist kein Push passiert.

Es wurde zuvor erwähnt, dass die Stapelzuweisung einfach den Stapelzeiger bewegt, dh eine einzelne Anweisung auf den meisten Architekturen. Vergleichen Sie dies mit dem, was im Allgemeinen bei der Heap-Zuweisung geschieht.

Das Betriebssystem verwaltet Teile des freien Speichers als verknüpfte Liste mit den Nutzdaten, die aus dem Zeiger auf die Startadresse des freien Teils und der Größe des freien Teils bestehen. Um X Bytes Speicher zuzuweisen, wird die Verknüpfungsliste durchlaufen und jede Note wird nacheinander besucht, um zu prüfen, ob ihre Größe mindestens X beträgt. Wenn ein Teil mit der Größe P> = X gefunden wird, wird P in zwei Teile mit aufgeteilt Größen X und PX. Die verknüpfte Liste wird aktualisiert und der Zeiger auf den ersten Teil wird zurückgegeben.

Wie Sie sehen können, hängt die Heap-Zuweisung von Faktoren ab, wie z. B. wie viel Speicher Sie anfordern, wie fragmentiert der Speicher ist und so weiter.

Im Allgemeinen ist die Stapelzuweisung schneller als die Heapzuweisung, wie in fast jeder Antwort oben erwähnt. Ein Stack-Push oder Pop ist O (1), wohingegen das Zuweisen oder Freigeben von einem Heap einen Spaziergang vorheriger Zuweisungen erfordern kann. Normalerweise sollten Sie jedoch nicht in engen, leistungsintensiven Schleifen zuordnen, sodass die Auswahl normalerweise von anderen Faktoren abhängt.

Es könnte gut sein, diese Unterscheidung zu treffen: Sie können einen "Stapelzuweiser" auf dem Heap verwenden. Genau genommen verstehe ich unter Stapelzuweisung eher die tatsächliche Zuweisungsmethode als den Ort der Zuweisung. Wenn Sie dem eigentlichen Programmstapel viel Material zuweisen, kann dies aus verschiedenen Gründen schlecht sein. Auf der anderen Seite ist die Verwendung einer Stapelmethode zum Zuweisen auf dem Heap, wenn möglich, die beste Wahl, die Sie für eine Zuweisungsmethode treffen können.

Da Sie Metrowerks und PPC erwähnt haben, meinen Sie wohl Wii. In diesem Fall ist der Speicher knapp und die Verwendung einer Stapelzuweisungsmethode, wo immer dies möglich ist, garantiert, dass Sie keinen Speicher für Fragmente verschwenden. Dies erfordert natürlich viel mehr Sorgfalt als "normale" Heap-Zuweisungsmethoden. Es ist ratsam, die Kompromisse für jede Situation zu bewerten.

Beachten Sie, dass es bei den Überlegungen normalerweise nicht um Geschwindigkeit und Leistung geht, wenn Sie die Stapel- oder Heap-Zuordnung auswählen. Der Stapel verhält sich wie ein Stapel, was bedeutet, dass er gut zum Schieben und erneuten Herausspringen von Blöcken geeignet ist. Die Ausführung von Prozeduren ist ebenfalls stapelartig. Die zuletzt eingegebene Prozedur muss zuerst beendet werden. In den meisten Programmiersprachen sind alle in einer Prozedur benötigten Variablen nur während der Ausführung der Prozedur sichtbar. Sie werden daher beim Eingeben einer Prozedur verschoben und beim Beenden oder Zurückgeben vom Stapel entfernt.

Nun ein Beispiel, in dem der Stapel nicht verwendet werden kann:

Proc P
{
  pointer x;
  Proc S
  {
    pointer y;
    y = allocate_some_data();
    x = y;
  }
}

Wenn Sie in Prozedur S Speicher zuweisen und ihn auf den Stapel legen und dann S beenden, werden die zugewiesenen Daten vom Stapel entfernt. Die Variable x in P zeigte jedoch auch auf diese Daten, sodass x jetzt auf eine Stelle unter dem Stapelzeiger (vorausgesetzt, der Stapel wächst nach unten) mit unbekanntem Inhalt zeigt. Der Inhalt ist möglicherweise noch vorhanden, wenn der Stapelzeiger nur nach oben verschoben wird, ohne die darunter liegenden Daten zu löschen. Wenn Sie jedoch neue Daten auf dem Stapel zuweisen, zeigt der Zeiger x möglicherweise stattdessen auf diese neuen Daten.

Machen Sie niemals vorzeitige Annahmen, da anderer Anwendungscode und andere Verwendung Ihre Funktion beeinträchtigen können. Das Betrachten der Funktion als Isolation nützt also nichts.

Wenn Sie es mit der Anwendung ernst meinen, stimmen Sie sie ab oder verwenden Sie ein ähnliches Profiling-Tool und sehen Sie sich Hotspots an.

Ketan

Ich möchte sagen, dass der von GCC generierte Code (ich erinnere mich auch an VS) keinen Overhead für die Stapelzuweisung hat .

Sprich für folgende Funktion:

  int f(int i)
  {
      if (i > 0)
      {   
          int array[1000];
      }   
  }

Es folgt der Code, der generiert wird:

  __Z1fi:
  Leh_func_begin1:
      pushq   %rbp
  Ltmp0:
      movq    %rsp, %rbp
  Ltmp1:
      subq    $**3880**, %rsp <--- here we have the array allocated, even the if doesn't excited.
  Ltmp2:
      movl    %edi, -4(%rbp)
      movl    -8(%rbp), %eax
      addq    $3880, %rsp
      popq    %rbp
      ret 
  Leh_func_end1:

Unabhängig davon, wie viele lokale Variablen Sie haben (auch innerhalb von if oder switch), ändert sich nur der 3880 in einen anderen Wert. Sofern Sie keine lokale Variable hatten, muss diese Anweisung nur ausgeführt werden. Das Zuweisen lokaler Variablen hat also keinen Overhead.