Was ist schneller:Stack-oder Heap-Zuweisung Zuweisung

https://stackoverflow.com/questions/161053

03-07-2019
|

Frage

Diese Frage klingt ziemlich elementar, aber das ist eine Debatte, die ich mit anderen Entwicklern, mit denen ich arbeite.

Ich war in Sorge um stack reservieren Dinge, wo ich konnte, statt die heap-Zuweisung Ihnen.Er war mit mir zu reden, und während Sie über meine Schulter und bemerkte, dass es nicht nötig war, weil Sie die gleiche Leistung weisen.

Ich hatte immer den Eindruck, dass wächst der Stapel war konstanter Zeit, und heap-Zuweisung ist die Leistung abhängig von der aktuellen Komplexität des heap, der für die Zuweisung (zu finden ein Loch der richtigen Größe) und de-allocating (Einstürzende Löcher, die Fragmentierung zu verringern, als viele standard-Bibliothek-Implementierungen nehmen Sie sich Zeit, um dies zu tun, während löscht, wenn ich mich nicht Irre).

Dies erscheint mir als etwas, das wäre wahrscheinlich sehr compiler abhängig.Für dieses Projekt in allem bin ich mit einer Metrowerks compiler für die PPC Architektur.Einsicht auf diese Kombination wäre sehr hilfreich, aber im Allgemeinen, für GCC und MSVC++, was ist der Fall?Ist die heap-Zuweisung nicht so performant wie stack-Zuweisung?Gibt es da keinen Unterschied?Oder sind die Unterschiede so winzig es wird sinnlos Mikro-Optimierung.

Lösung

Stack-Allokation ist viel schneller, da alle es wirklich tut, ist der Stapelzeiger bewegen. Mit Speicherpools können Sie eine vergleichbare Leistung aus Heapzuordnung, aber das kommt mit einem geringen zusätzlichen Komplexität und seine eigenen Kopfschmerzen.

Auch Stapel vs. Halde ist nicht nur eine Leistung Betracht; es sagt Ihnen auch viel über die erwartete Lebensdauer von Objekten.

Andere Tipps

Stack ist viel schneller. Es buchstäblich nur eine einzige Anweisung auf den meisten Architekturen, in den meisten Fällen, z.B. auf x86:

sub esp, 0x10

(was ich bewegt den Stapelzeiger durch 0x10 Bytes nach unten und damit „ordnet“ dieses Bytes für die Verwendung durch eine Variable.)

Natürlich die Größe des Stapels ist sehr, sehr begrenzt, wie Sie schnell herausfinden, wenn Sie übermäßigen Gebrauch Stack Allocation oder versuchen Rekursion zu tun: -)

Außerdem gibt es wenig Grund, die Leistung von Code zu optimieren, die nicht nachprüfbar es brauchen, wie durch Profilierung unter Beweis gestellt. „Vorzeitige Optimierung“ verursacht oft mehr Probleme als es wert ist.

Meine Faustregel: Wenn ich weiß, ich werde einige Daten zur Compile-Zeit benötigen , und es ist unter ein paar hundert Bytes groß, ich Stack zuweisen es. Ansonsten Heap-zuteilen ich es.

Ehrlich gesagt, es ist 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 törichte Konsistenz ist der Kobold kleiner Geister . Offenbar optimierende Compiler sind die Kobolde von vielen Programmierern Köpfen. Diese Diskussion verwendete am unteren Rande der Antwort zu sein, aber Menschen können offenbar nicht so weit lesen belästigt werden, so dass ich es hier zu bewegen, um zu vermeiden Fragen bekommen, die ich bereits beantwortet habe.

Ein optimierenden Compiler feststellen, dass dieser Code nichts tut, und kann sie alle weg optimieren. Es ist die Aufgabe des Optimierers Sachen wie das zu tun, und das Optimierungsprogramm kämpft, ist ein Auftrag des Narren.

Ich würde empfehlen, diesen Code mit Optimierung kompilieren ausgeschaltet, weil es keine gute Möglichkeit ist es, jeden Optimierer zur Zeit in Gebrauch zu täuschen oder das wird im Gebrauch in der Zukunft.

Wer das Optimierungsprogramm schaltet sich ein und dann beschwert sich über den Kampf gegen sie sollten den öffentlichen Spott unterliegen.

Wenn ich über Nanosekunde Präzision gepflegt würde ich nicht std::clock() verwenden. Wenn ich wollte, dass die Ergebnisse als Dissertation veröffentlichen würde ich einen größeren Deal darüber machen, und ich würde wahrscheinlich vergleichen GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC und anderen Compilern. Wie es ist, nimmt mehrere hundert Mal Heapzuordnung länger als Stapelzuweisung, und ich weiß nicht, etwas Sinnvolles über die Frage der Untersuchung weiter sehen.

Der Optimierer hat eine Mission des Codes, um loszuwerden, teste ich. Ich sehe keinen Grund, den Optimierer zu sagen, zu laufen und dann versuchen, den Optimierer in nicht tatsächlich die Optimierung zu täuschen. Aber wenn ich Wert sah, dass dabei, ich tun würde, eine oder mehrere der folgenden Optionen:

ein Datenelement hinzufügen empty und Zugriff auf diese Daten Element in der Schleife; aber wenn ich immer nur aus dem Datenelement lesen kann der Optimierer konstantes Falten tun und um die Schleife entfernen; wenn ich immer nur an das Datenelement schreiben, kann der Optimierer überspringt alle, aber die letzte Iteration der Schleife. Zusätzlich wurde die Frage nicht „Stack Zuteilung und Datenzugriff vs. Heapzuordnung und Datenzugriff.“
e volatile erklären, aber volatile wird oft falsch übersetzt (PDF).
Nehmen Sie die Adresse von e innerhalb der Schleife (und vielleicht ist es einer Variablen zuweisen, die extern und definiert in einer anderen Datei deklariert wird). Aber auch in diesem Fall kann der Compiler feststellen, dass - auf dem Stapel zumindest - e wird immer an der gleichen Speicheradresse zugeordnet wird, und dann tut konstante Falte wie in (1) oben. Ich bekomme alle Iterationen der Schleife, aber das Objekt wird nie tatsächlich zugeordnet.

Neben dem offensichtlichen, wird dieser Test in fehlerhaft, dass misst sowohl Zuweisung und Freigabe und die ursprüngliche Frage nach Aufhebung der Zuordnung nicht fragen. Natürlich auf dem Stack zugeordnet Variablen werden am Ende ihres Umfangs automatisch freigegeben, so würden die Zahlen (Stack Deallokation wird in den Zahlen über Stack Zuteilung enthalten, so ist es nur fair zu messen Haufen Deallokation) nicht aufrufen delete (1) schräg und (2) verursacht einen ziemlich schlechten Speicherverlust, wenn wir einen Verweis auf den neuen Zeiger und Anruf delete halten, nachdem wir unsere Zeitmessung haben.

Auf meinem Rechner mit g ++ 3.4.4 unter Windows, erhalte ich „0 Uhr tickt“ für beide Stapel und Heap-Allokation für etwas weniger als 100.000 Zuweisungen, und selbst dann erhalte ich „0 Uhr tickt“ für Stapelzuweisung und " 15 Uhr tickt“für Heapzuordnung. Wenn ich 10.000.000 Zuweisungen messen, nimmt Stapel Zuteilung 31 Uhr tickt und Heap allocatIon nimmt 1562 Uhr tickt.

Ja, ein optimierenden Compiler elide können die leeren Objekte zu schaffen. Wenn ich richtig verstehe, kann es sogar die ganze erste Schleife elide. Wenn ich die Iterationen zu 10.000.000 Stapelzuweisung nahm Uhr tickt 31 gestoßen und Heapzuordnung nahm 1562 Uhr tickt. Ich denke, es ist sicher zu sagen, dass g ohne zu sagen ++ die ausführbare Datei zu optimieren, g ++ haben die Konstrukteure nicht elide.

In den Jahren seit ich dies schrieb, hat sich die Präferenz auf Stack-Überlauf gewesen Leistung schreiben von einer optimierten Builds. Im Allgemeinen denke ich, das ist richtig. Aber ich denke immer noch dumm es ist, den Compiler zu fragen, Code zu optimieren, wenn Sie in der Tat nicht, dass Code wollen optimiert. Es scheint mir sehr ähnlich ist besonders für den Parkservice zu bezahlen, aber weigert sich, die Schlüssel zu übergeben. In diesem speziellen Fall, ich das Optimierungsprogramm läuft nicht wollen.

Mit einer leicht modifizierten Version der Benchmark (den gültigen Punkt ansprechen, dass das ursprüngliche Programm nicht etwas auf dem Stapel jedes Mal durch die Schleife zugewiesen hat) und ohne Optimierungen kompilieren, aber die Verknüpfung Bibliotheken freizugeben (die gültige Adresse

: dass wir durch die Verknüpfung zu Debug-Bibliotheken) verursacht keine Verlangsamung aufnehmen wollen

#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;
}

angezeigt:

on_stack took 2.070003 seconds
on_heap took 57.980081 seconds

auf meinem System, wenn es mit der Befehlszeile cl foo.cc /Od /MT /EHsc zusammengestellt.

Sie können nicht mit meinem Ansatz überein, einen nicht-optimierte Build bekommen. Das ist in Ordnung: Fühlen Sie sich frei, die Benchmark ändern, so viel wie Sie wollen. Wenn ich auf die Optimierung drehen, erhalte ich:

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

Nicht, weil Stapel Zuteilung tatsächlich augenblicklich ist, sondern weil jeder halbwegs anständige Compiler, dass on_stack tun nicht bemerkt kann nichts nützlich und kann entfernt optimiert werden. GCC auf meinem Linux-Laptop merkt auch, dass on_heap nichts tut nützlich und optimiert es entfernt auch:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

Eine interessante Sache, die ich über Stapel vs. Heap Allocation auf der Xbox 360 Xenon-Prozessor gelernt, die auch auf andere Multicore-Systemen anwenden können, ist, dass auf dem Heap Zuweisung eines kritischen Abschnitts verursacht eingegeben werden, um alle anderen Kerne zu stoppen, so dass die alloc steht nicht im Widerspruch. So wird in einer engen Schleife, war Stapel Allocation der Weg für feste Größe Arrays zu gehen, wie es Stände verhindert werden.

Dies kann eine weitere Beschleunigung zu prüfen, ob Sie für Multi-Core / multiproc Codierung sind, dass Ihre Stack Zuweisung nur Ihre scoped Funktion durch den Kern laufen zu sehen sein wird, und das wird keinen anderen Kerne / CPUs beeinflussen.

Sie können einen speziellen Haufen Allocator für bestimmte Größen von Objekten schreiben, die sehr performant ist. Allerdings ist die allgemeine heap Allocator ist nicht besonders performant.

Auch mit Torbjörn Gyllebring über die zu erwartende Lebensdauer von Objekten Ich bin damit einverstanden. Guter Punkt!

Ich glaube nicht, Stack Zuteilung und Heapzuordnung ist in der Regel austauschbar. Ich hoffe auch, dass die Leistung der beiden für den allgemeinen Gebrauch ausreichend ist.

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

Auf 32-Bit-Betriebssysteme, die mehrere Threads haben, Stapel oft eher begrenzt (wenn auch typischerweise zumindest ein paar mb), da der Adressraum werden zerstückelt braucht und früher oder später ein Thread-Stack wird in eine andere laufen . Auf Single-Threaded-Systemen (Linux glibc einzige Gewinde sowieso) die Begrenzung viel weniger ist, weil der Stapel nur wachsen und wachsen kann.

Auf 64-Bit-Betriebssystemen gibt es genug Adressraum Fadenstapel ziemlich groß zu machen.

In der Regel Zuordnung Stack besteht nur aus dem Stapelzeigerregister subtrahieren. Dies ist Tonnen schneller als einen Haufen zu suchen.

Manchmal Stack Zuteilung erfordert eine Seite Zugabe (n) des virtuellen Speichers. eine neue Seite von Null gestellt Speicher Hinzufügen erfordert keine Seite von der Platte zu lesen, so in der Regel ist dies immer noch Tonnen geht schneller zu sein als ein Haufen Benutzer (vor allem, wenn ein Teil des Haufens wurde auch ausgelagert). In einer seltenen Situation, und Sie ein solches Beispiel konstruieren könnte, genügend Platz geschieht nur in einem Teil des Heap zur Verfügung stehen, die bereits im RAM, aber eine neue Seite für den Stapel Zuweisung muss warten, für eine andere Seite zu bekommen geschrieben auf der Festplatte. In diesem seltenen Fall ist der Haufen schneller.

Neben dem Bestellungen-of-Größenordnung Leistungsvorteil gegenüber Heapzuordnung, Stack Zuteilung für lange Laufserveranwendungen vorzuziehen ist. Selbst die besten verwalteten Haufen schließlich so fragmentiert erhalten, dass die Anwendungsleistung verschlechtert.

Ein Stapel hat eine begrenzte Kapazität, während ein Haufen nicht ist. Der typische Stapel für einen Prozess oder Thread ist etwa 8K. Sie können nicht die Größe ändern, sobald es zugeordnet ist.

Ein Stapel Variable folgt die Scoping-Regeln, während ein Haufen eines nicht. Wenn Ihre Befehlszeiger über eine Funktion geht, werden alle neuen Variablen mit der Funktion verbunden sind weg.

Am wichtigsten von allen, können Sie die Gesamtfunktion Call-Kette nicht im Voraus vorhersagen. Also nur etwa 200 Bytes Zuteilung von Ihrer Seite kann einen Stapelüberlauf erhöhen. Dies ist besonders wichtig, wenn Sie eine Bibliothek schreiben, keine Anwendung.

Ich denke, die Lebensdauer von entscheidender Bedeutung ist, und ob das Ding zugeordnet ist hat in komplexer Weise konstruiert werden. Zum Beispiel in transaktionsGetriebene Modellierung, müssen Sie in der Regel in füllen und in einer Transaktionsstruktur mit einem Bündel von Feldern Betriebsfunktionen übergeben. Schauen Sie sich den OSCI SystemC TLM-2.0-Standard für ein Beispiel.

diese Zuweisung auf dem Stapel der Nähe der Aufruf der Operation neigt enormen Aufwand zu verursachen, da die Konstruktion teuer ist. Die gute Art und Weise gibt es auf dem Heap zuzuweisen und wieder verwenden die Transaktionsobjekte entweder durch Bündelung oder eine einfache Politik wie „dieses Modul benötigt nur ein Transaktionsobjekt überhaupt“.

Dies ist ein Vielfaches schneller als bei jedem Operationsaufruf das Objekt zugewiesen wird.

Der Grund dafür ist einfach, dass das Objekt eine aufwendige Konstruktion und eine ziemlich lange Lebensdauer.

Ich würde sagen: beide versuchen und sehen, was am besten in Ihrem Fall funktioniert, weil es wirklich auf dem Verhalten des Codes abhängen.

Wahrscheinlich das größte Problem der Heapzuordnung gegen Stack Allocation, ist, dass Heapzuordnung im allgemeinen Fall ist ein unbeschränkter Betrieb, und daher kann man es nicht verwenden, wo Timing ein Problem.

Für andere Anwendungen, bei denen Zeitpunkt kein Problem ist, kann es nicht so viel, egal, aber wenn Sie viel Heap zuweisen, wird dies die Ausführungsgeschwindigkeit beeinflussen. Versuchen Sie immer, den Stapel für kurzlebig und oft zugewiesenen Speicher zu verwenden (zum Beispiel in Schleifen), und so lange wie möglich -. Tut Heapzuordnung beim Anwendungsstart

Es ist nicht nur Zuteilung stapeln, die schneller ist. Sie gewinnen auch viel auf Stack-Variablen verwenden. Sie haben bessere Referenzlokalität. Und schließlich Deallokation ist auch viel billiger.

Stack Allokation wird fast immer als schnell oder schneller als der heap-Zuweisung, obwohl es sicherlich möglich, für eine heap-Zuweisung verwenden Sie einfach einen stack-basierten Zuordnung Technik.

Es gibt jedoch größere Probleme beim Umgang mit der performance-stack vs.heap-based allocation (oder etwas bessere Bedingungen, lokale vs.externe Vergabe).In der Regel, heap (externen) Zuweisung ist langsam, weil es ist der Umgang mit vielen unterschiedlichen Arten von Zuwendungen und Vergabe von mustern.Reduziert den Umfang der Zuweisung, die Sie verwenden (so dass es lokal auf dem Algorithmus/code) wird dazu neigen, um die Leistung zu erhöhen, ohne größere änderungen.Hinzufügen eine bessere Struktur, um Ihre Zuordnung Muster, für Beispiel, zwingt eine LIFO Bestellung über die Zuteilung und Freigabe Paare können auch verbessern Sie Ihre Zuweisung ist Leistung über die Zuweisung in eine einfachere und besser strukturierte Art und Weise.Oder, Sie verwenden können, oder schreiben Sie eine Zuweisung abgestimmt für Ihre Besondere Zuordnung Muster;die meisten Programme weisen ein paar diskrete Größen Häufig, so dass ein heap, basiert auf einer lookaside-Puffer ein paar Feste (möglichst bekannte) Größen durchführen extrem gut.Verwendet Windows die geringer Fragmentierung heap aus diesem Grund.

Auf der anderen Seite, stack-basierte Zuweisung auf einem 32-bit-memory-Bereich ist auch voller Gefahr, wenn Sie zu viele threads.Die Stapel müssen einen zusammenhängenden Speicherbereich, also je mehr threads Sie haben, desto mehr virtuelle Adresse Speicherplatz Sie benötigen, für Sie zu laufen, ohne einen stack-überlauf.Dies ist nicht ein problem (für jetzt) mit 64-bit -, aber es kann sicherlich wreak havoc in lange Laufenden Programmen mit vielen threads.Der virtuelle Adressraum durch Fragmentierung ist immer ein Schmerz zu behandeln.

Stack-Allokation ist ein paar Anweisungen, während der schnellsten allocator rtos Haufen mir bekannt (TLSF) verwendet im Durchschnitt in der Größenordnung von 150 Anweisungen. Zuweisungen auch stapelt keine Sperre erfordern, weil sie die lokale Speicherung Thread verwenden, die eine weitere große Leistung gewinnen ist. So Stapelzuordnungen können 2-3 Größenordnungen schneller, je nachdem wie stark multithreaded Ihre Umgebung ist.

Generell Heapzuordnung ist Ihr letzter Ausweg, wenn Sie über die Leistung kümmern. Ein gangbarer in-zwischen-Option kann ein fester Pool Allocator sein, die auch nur ein paar Anweisungen und hat sehr wenig pro-Allocation-Overhead so ist es toll für kleine feste Größe Objekte. Auf der anderen Seite funktioniert es nur mit fester Größe Objekten, ist von Natur aus nicht Thread-sicher und hat Fragmentierungsprobleme blockieren.

Es gibt einen allgemeinen Punkt über solche Optimierungen vorgenommen werden.

Die Optimierung Sie ist auf die Höhe der Zeit tatsächlich in diesem Code der Programmzähler ist proportional zu bekommen.

Wenn Sie den Programmzähler probieren, werden Sie herausfinden, wo sie ihre Zeit verbringt, und das ist in der Regel in einem kleinen Teil des Codes, und oft in Bibliotheksroutinen haben Sie keine Kontrolle über.

Nur wenn Sie es zu verbringen viel Zeit in der Heap-Zuordnung Ihrer Objekte zu finden wird es deutlich schneller sein, sie zu stapeln zuweisen.

Wie andere gesagt haben, Stapelzuweisung ist in der Regel viel schneller.

Allerdings, wenn Ihre Objekte sind teuer zu kopieren, auf dem Stapel Zuweisung später zu einer Leistung führen kann Riesenhit, wenn Sie die Objekte verwenden, wenn Sie nicht vorsichtig sind.

Zum Beispiel, wenn Sie etwas auf dem Stapel zuweisen, und es dann in einen Behälter gegeben, wäre es besser gewesen, auf dem Heap zuweisen und speichert, um den Zeiger in dem Behälter (zB mit einem std :: shared_ptr <>) . Das Gleiche gilt, wenn Sie vorbei oder Objekte, die von Wert und anderen ähnlichen Szenarien zurück.

Der Punkt ist, dass, obwohl Stapelzuweisung ist in der Regel besser als Heapzuordnung in vielen Fällen, manchmal, wenn Sie aus dem Weg gehen zuteilen zu stapeln, wenn sie am besten passen nicht in das Rechenmodell, kann es mehr Probleme verursachen, als es löst.

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 wie dies in asm sein. Wenn Sie in func sind, hat sich die f1 und Zeiger f2 auf Stapel (automatische Speicherung) zugeordnet. Und übrigens, Foo f1(a1) keine Anweisung Auswirkungen auf die Stapelzeiger (esp) hat, hat sie zugewiesen, wenn func das Mitglied f1 will bekommen, es ist Befehl so etwas wie dieses: lea ecx [ebp+f1], call Foo::SomeFunc(). Eine andere Sache, die Stapel zuweisen kann jemand den Speicher denken ist so etwas wie FIFO, die FIFO gerade passiert, wenn Sie in eine Funktion gehen, wenn Sie in der Funktion sind und weisen so etwas wie int i = 0, kein Push passiert ist.

Es wurde bereits erwähnt, dass Stack Zuweisung einfach wird, um den Stapelzeiger bewegt, das heißt, ein einzelner Befehl auf den meisten Architekturen. Vergleichen Sie das mit, was im Allgemeinen geschieht im Fall Zu.

Das Betriebssystem hält Teile des freien Speichers als verkettete Liste mit den Nutzdaten aus den Zeiger auf die Startadresse des freien Abschnitts und der Größe des freien Abschnitts. Zuzuordnen ist, X Bytes des Speichers, die Link-Liste durchlaufen und jede Note wird in der Reihenfolge besucht, zu überprüfen, ob seine Größe mindestens X. Wenn ein Teil mit der Größe P> = X gefunden wird, wird P in zwei Teile geteilt mit Größen X und PX. Die verknüpfte Liste wird aktualisiert und der Zeiger auf den ersten Teil zurückgegeben.

Wie Sie sehen können, Heapzuordnung hängt von vielen Faktoren wie, wie viel Speicher Sie anfordern, wie fragmentiert ist der Speicher und so weiter.

Generell Stack Zuteilung ist schneller als Zuweisung Haufen wie oben durch fast jede Antwort erwähnt. Ein Stapel Schub- oder pop ist O (1), während der Zuteilung oder aus einem Haufen zu befreien könnte eine Wanderung von vorherigen Zuteilungen erfordern. Allerdings sollten Sie nicht in der Regel in engen, leistungsintensive Schleifen werden die Zuteilung, so dass die Wahl wird in der Regel kommen zu anderen Faktoren ab.

Es könnte gut sein, diese Unterscheidung zu treffen: Sie einen „Stapel Allocator“ auf dem Heap verwenden können. Streng genommen, nehme ich Stack Zuteilung die tatsächliche Zuteilungsmethode zu verstehen, anstatt die Position der Zuteilung. Wenn Sie eine Menge Zeug auf dem tatsächlichen Programmstapel Zuweisung, das könnte für eine Vielzahl von Gründen schlecht. Auf der anderen Seite, ein Stapel-Verfahren auf dem Heap zu reservieren, wenn möglich, die beste Wahl ist, dass Sie für die Zuteilung machen.

Da Sie Metrowerks und PPC erwähnt, ich vermute, Sie Wii bedeuten. In diesem Fall Speicher ist mit einer Prämie, und ein Stapel-Zuweisungsverfahren, wo immer möglich, garantiert, dass Sie nicht Speicher auf Fragmente verschwenden. viel mehr Pflege als „normale“ Heapzuordnung Methoden Natürlich erfordert dies zu tun. Es ist klug, die Vor- und Nachteile für jede Situation zu bewerten.

Bemerkung, dass die Überlegungen der Regel nicht um Geschwindigkeit und Leistung, wenn Stapel gegen Heapzuordnung wählen. Die Stapel wirkt wie ein Stapel, das heißt, sie gut geeignet ist, Blöcke zu schieben und sie wieder knallen, last in, first out. Die Ausführung der Verfahren ist auch stapelartig, trat letztes Verfahren ist zunächst beendet werden. In den meisten Programmiersprachen sind alle in einem Verfahren benötigte Variablen werden nur während des Verfahrens der Ausführung sichtbar sein, so dass sie ein Verfahrens beim Betreten und tauchten aus dem Stapel beim Verlassen oder Rückkehr geschoben werden.

Jetzt für ein Beispiel, wo der Stapel kann nicht verwendet werden:

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

Wenn Sie einige Speicher in Prozedur S zuweisen und legen sie auf dem Stapel und dann die Ausfahrt S, werden die zugeordneten Daten von dem Stapel genommene werden. Aber die Variable x in P wies auch auf diese Daten, so x jetzt zeigt auf einen Ort unterhalb der Stapelzeiger (nehmen Stapel wächst nach unten) mit einem unbekannten Inhalt. Der Inhalt könnte noch da sein, wenn der Stapelzeiger nur ohne Löschen der Daten darunter bewegt, aber wenn Sie auf dem Stapel neuer Daten starten Zuweisung könnte der Zeiger x Punkt tatsächlich zu, dass neue Daten statt.

Bedenken Spezifisch für die C ++ Sprache

Zu allererst gibt es keine „Stapel“ oder „Haufen“ Zuteilung beauftragt von C ++ so genannten . Wenn Sie über die automatische Objekte im Block Umfang sprechen, sind sie auch nicht „zugeordnet“. (BTW, automatische Speicherdauer in C ist definitiv nicht das gleiche zu „zugeordnet“, letzteres ist „dynamisch“ in der C ++ Sprachgebrauch.) Und der dynamisch zugewiesenen Speicher ist auf dem Free-Store , die nicht unbedingt auf "die Halde", obwohl letztere ist oft der (Standard) Implementierung .

Obwohl gemäß den abstrakten semantischen Regeln, automatische Objekte noch Speicher belegen, ist ein konformer C ++ Implementierung erlaubt, diese Tatsache zu ignorieren, wenn sie nachweisen kann, das spielt keine Rolle (wenn es nicht das beobachtbare Verhalten des Programms ändern). Diese Erlaubnis wird erteilt von der As-if-Regel in ISO C ++, die auch die allgemeinen Klausel ermöglicht die üblichen Optimierungen (und es gibt auch eine fast gleiche Regel in ISO C). Neben der As-if Regel ISO C ++ hat auch Kopie elision Regeln Weglassen bestimmter Kreationen von Objekten zu ermöglichen. Der Konstruktor und Destruktor Anrufe beteiligt sind dabei weggelassen. Als Ergebnis werden die automatischen Objekte (falls vorhanden) in diesen Konstruktoren und Destruktoren ebenfalls eliminiert, im Vergleich zu naiver abstrakter Semantik implizierte den Quellcode.

Auf der anderen Seite, Heap Allocation ist definitiv „Zuteilung“ von Design. Unter ISO C ++ Regeln eine solche Zuordnung kann durch einen Aufruf einer Zuordnungsfunktion erreicht werden. Da jedoch 14 ++ ISO C, gibt es eine neue (nicht-as-if) Regel globale Zuteilungsfunktion Zusammenführung zu ermöglichen (das heißt ::operator new) fordert in bestimmten Fällen. So Teile der dynamischen Zuordnung Operationen können auch nicht-op wie bei automatischen Objekten sein.

Zuordnungsfunktionen Zuweisung von Ressourcen an Speicher. Objekte können weiter basierend auf Zuteilung mit Verteilern zugeordnet werden. Für die automatische Objekte, werden sie direkt präsentiert - obwohl die zugrunde liegenden Speicher zugegriffen werden kann und verwendet werden, um Speicher zu anderen Objekten zu schaffen (durch Platzierung new), aber dies nicht viel Sinn als freie Speicher, weil es keine Möglichkeit gibt, sich zu bewegen die Ressourcen an anderer Stelle.

Alle anderen Bedenken sind aus dem Anwendungsbereich von C ++. Dennoch können sie immer noch von Bedeutung sein.

Über Implementationen von C ++

C ++ belichten nicht verdinglicht Aktivierung Aufzeichnungen oder einige Arten von erstklassigen Fortsetzungen (zum Beispiel durch den berühmten call/cc), gibt es keine Möglichkeit, direkt auf die Aktivierung Rekord Rahmen zu manipulieren - wenn die Umsetzung muß die automatischen Objekte platzieren. Einmal gibt es kein (nicht tragbar) interoperations mit der zugrunde liegenden Implementierung ist ( „native“ nicht-portablen Code, wie Inline-Assembler-Code), eine Auslassung der zugrunde liegenden Verteilung der Frames kann ziemlich trivial sein. Zum Beispiel, wenn die aufgerufene Funktion inlined wird, kann der Rahmen effektiv in anderen verschmolzen werden, so gibt es keine Möglichkeit, zu zeigen, was ist die „Zuordnung“.

Sobald jedoch Interops respektiert werden, Dinge werden immer komplexer. Eine typische Implementierung von C ++ wird die Fähigkeit der Interop auf ISA (Befehlssatzarchitektur) mit einigen Aufrufkonventionen als binäre Grenze mit dem nativen (ISA-Level-Maschine) Code geteilt aus. Dies wäre ausdrücklich teuer, vor allem, wenn die Aufrechterhaltung Stapelzeiger , die oft direkt von einem ISA-Level-Register gehalten (mit wahrscheinlich spezifischen Maschinenbefehlen zugegriffen werden soll). Der Stapelzeiger zeigt die Grenze des oberen Rahmens des (derzeit aktiv) Funktionsaufruf. Wenn ein Funktionsaufruf eingegeben wird, wird ein neuer Rahmen benötigt, und der Stapelzeiger addiert oder subtrahiert (je nach Konvention von ISA) durch einen Wert nicht kleiner als die erforderliche Rahmengröße. Der Rahmen wird dann als zugeordnet , wenn der Stapelzeiger nach den Operationen. Parameter der Funktionen können auf den Stapelrahmen übergeben werden alsgut, abhängig von der Aufrufkonvention für den Anruf verwendet. Der Rahmen kann den Speicher von automatischen Objekten halten (wahrscheinlich einschließlich der Parameter), indem der Quellcode ++ C angegeben. Im Sinne solcher Implementierungen werden diese Aufgaben „zugewiesen“. Wenn die Steuerung des Funktionsaufruf beendet wird, wird der Rahmen nicht mehr benötigt wird, ist es in der Regel durch die Wiederherstellung der Stapelzeiger wieder in den Zustand vor dem Aufruf (zuvor gespeicherten gemäß der Aufrufkonvention) freigegeben wird. Dies kann als „Freigabe“ eingesehen werden. Diese Operationen machen die Aktivierung Aufzeichnung effektiv eine LIFO-Datenstruktur, so ist es oft „ die (Call) genannt Stack “. Der Stapelzeiger zeigt effektiv die Spitzenposition des Stapels.

Da die meisten C ++ Implementierungen (besonders die, die ISA-Ebene nativen Code Targeting und mit der Assemblersprache als seine sofortigen Ausgabe) verwenden ähnliche Strategien wie diese, so verwirrend „Zuweisung“ Schema ist sehr beliebt. Solche Zuordnungen (wie auch das Aufheben dieser Zuordnungen) tun Maschinenzyklen verbringen, und es kann teuer werden, wenn die (nicht optimierte) Anrufe häufig auftreten, obwohl moderne CPU-Mikroarchitekturen komplexe Optimierungen von Hardware für das gemeinsame Codemuster implementiert haben können (wie ein mit Stapel Motor in der Umsetzung PUSH / POP Anleitung).

Aber wie auch immer, in der Regel es ist wahr, dass die Kosten für die Stapelrahmen Zuordnung ist deutlich weniger als ein Anruf an eine Zuordnungsfunktion des freien Speicher arbeitet (es sei denn, es ist völlig optimiert entfernt) , die selbst können Hunderte (wenn nicht Millionen von :-) Operationen haben die Stapelzeiger und andere Staaten zu halten. Zuordnungsfunktionen werden in der Regel auf Basis von API von der gehosteten Umgebung bereitgestellt (z.B. Laufzeit von dem O zur Verfügung gestellt). Im Unterschied zum Zwecke der automatischen Objekte für Funktionen Halten von Anrufen, sind solche Zuteilungen allgemeinen vorgesetzt, so dass sie nicht-Rahmenstruktur wie ein Stapel haben. Traditionell sie zuzuteilen Raum aus dem Pool Speicher genannt Haufen (oder mehrere Haufen). Anders als bei dem „Stack“, wird der Begriff „Halde“ hier nicht die Datenstruktur anzuzeigen, wird verwendet; Vor es von der frühen Sprachimplementierungen Jahrzehnte abgeleitet ist. (BTW, wird der Call-Stack in der Regel mit fester oder vom Benutzer angegebene Größe aus dem Heap von der Umgebung, in Programm oder Thread Start zuzugeordnet.) Die Art der Anwendungsfälle macht Zuweisungen und Freigaben von einem Haufen weitaus komplizierter (als Push oder Pop von Stack Frames), und kaum möglich, durch Hardware direkt optimiert werden.

Effekte auf Memory Access

Die übliche Stapelzuweisung immer wieder die neuen Rahmen auf der Oberseite, so hat es eine recht gute Lokalität. Das ist freundlich zu Cache. OTOH, Speicher zufällig in dem freien Speicher zugewiesen haben keine solche Eigenschaft. Da ISO C ++ 17, gibt es Pool-Ressource-Vorlagen von <memory> zur Verfügung gestellt. Die direkte Zweck einer solchen Schnittstelle ist, die Ergebnisse der aufeinanderfolgenden Zuführungen zu ermöglichen, nahe beieinander im Speicher ist. Dies trägt der Tatsache Rechnung, dass diese Strategie für die Leistung mit modernen Implementierungen im Allgemeinen gut ist, z.B. freundlich sein in modernen Architekturen zwischenzuspeichern. Dies ist über die Leistung von Zugriff statt Zuordnung , though.

Concurrency

Erwartung der gleichzeitigen Zugriff von Speicher kann verschiedene Effekte zwischen dem Stapel und Haufen hat. Ein Call-Stack in der Regel wird ausschließlich von einem Ausführungs-Thread in einer C ++ Implementierung gehört. OTOH, Halden sind oft shared unter den Threads in einem Prozess. Für einen solchen Haufen haben die Zuweisung und Freigabe-Funktionen die gemeinsame interne Verwaltungs dat zu schützeneine Struktur, von den Daten Rennen. Als Ergebnis können Heapzuweisungen und das Aufheben dieser Zuordnungen haben zusätzlichen Aufwand aufgrund interner Synchronisierungsvorgänge.

Space Efficiency

Aufgrund der Art der Anwendungsfälle und interner Datenstrukturen können Haufen von internem Speicherfragmentierung , während der Stapel nicht. Dies hat keine direkten Auswirkungen auf die Leistung der Speicherzuweisung, sondern in einem System mit virtuellen Speicher , geringe Raumeffizienz Gesamtleistung des Speicherzugriffs entarten können. Dies ist besonders schrecklich, wenn HDD als Swap physischen Speicher verwendet wird. Es kann sehr lange Latenzzeit führen. - manchmal Milliarden Zyklen

Einschränkungen von Stapelzuordnungen

Obwohl Stapelzuordnungen oft überlegen sind in der Leistung als Heapzuweisungen in Wirklichkeit, es kann sicherlich bedeutet nicht, Stapelzuordnungen immer Heapzuweisungen ersetzen.

Erstens gibt es keine Möglichkeit, Raum auf dem Stapel mit einer Größe zur Laufzeit in einen tragbaren Weise mit ISO C ++ angegeben zuzuordnen. Es gibt Erweiterungen zur Verfügung gestellt von Implementierungen wie alloca und G ++ 's VLA (mit variabler Länge Array), aber es gibt Gründe, sie zu vermeiden verwenden. (IIRC, Linux Quelle Verwendung von VLA entfernt vor kurzem.) (Beachten Sie auch ISO C99 VLA hat, aber ISO C11 schaltet die Unterstützung optional.)

Zweitens gibt es keine zuverlässige und tragbare Art und Weise Stapelraum Erschöpfung zu erkennen. Dies wird oft Stack-Überlauf (hmm, Etymologie dieser Seite) genannt, aber wahrscheinlich mehr accruately, „Stack überlaufen“. In der Realität führt dies oft ungültigen Zugriff des Speichers und der Zustand des Programms ist dann corruptied (... oder vielleicht noch schlimmer, ein Sicherheitsloch). In der Tat hat ISO C ++ kein Konzept Stack und macht es nicht definiertes Verhalten, wenn die Ressource erschöpft ist. Seien Sie vorsichtig, wie viel Raum sollte für die automatische Objekte gelassen werden.

Wenn der Stapelspeicher leer ist, gibt es zu viele Objekte zugeordnet, in dem Stapel, die durch zu viele aktiven Anrufe von Funktionen oder unsachgemäßer Verwendung von automatischen Objekten verursacht werden können. Solche Fälle können Existenz von Bugs vorschlagen, zum Beispiel ein rekursive Funktionsaufruf ohne korrekte Ausgangsbedingungen.

Dennoch tief rekursive Anrufe werden manchmal gewünscht. In Implementierungen von Sprachen erfordern Unterstützung von ungebundenen aktiven Anrufen (Call Tiefe nur durch Gesamtspeicher begrenzt), ist es unmöglich nativen Call-Stack zu verwenden, um direkt als Zielsprache Aktivierungsdatensatz wie typisches C ++ Implementierungen. Zum Beispiel SML / NJ explizit ordnet Frames auf dem Heap und verwendet Kaktus Stapel . Die komplizierte Aufteilung dieses Aktivierungsdatensatz Rahmen ist in der Regel nicht schnell wie das Call-Stack-Frames. Wenn jedoch weitere Sprachen Umsetzung mit richtigen Endrekursion , direkte Stapel Zuordnung in Objektsprache (dh , wird das „Objekt“ in der Sprache nicht als Referenz gespeichert, sondern primitive Werte, die eine eins-zu-eins-zu unshared C ++ Objekten abgebildet werden können) mit mehr Leistungseinbuße im allgemeinen noch komplizierter ist. Wenn C ++ unter Verwendung eines solchen Sprachen zu implementieren, ist es schwierig, die Auswirkungen auf die Leistung zu schätzen.

Sie niemals vorzeitige Annahme als anderer Anwendungscode und Nutzung kann Ihre Funktion auswirken. Also bei Funktion sucht, ist die Isolierung von keinem Nutzen ist.

Wenn Sie mit der Anwendung dann ernst sind es VTune oder ähnliches Profilierungswerkzeug verwenden und an Hotspots suchen.

Ketan

Ich mag eigentlich Code von GCC generieren sagen (ich erinnere VS auch) nicht Overhead-Stack Zuweisung zu tun .

Sprich für folgende Funktion:

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

Im Folgenden ist der Code zu generieren:

  __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:

So whatevery wie viel lokale Variable Sie haben (auch im Inneren, wenn oder Switch), nur wird der 3880 auf einen anderen Wert ändern. Sofern Sie nicht lokalen Variable haben, diese Anweisung muß nur auszuführen. So lokalen Variable keine Zuteilung von Overhead hat.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow