Laufzeitverhalten Heap zu Stack

Sprotti

Hi,
weiß jemand von Euch wie groß der Zeitunterschied ist(im Verhältnis), ob ich ein Array mit

int a[20];

oder mit

int size = 20;
int* a = new int[size];

deklariere?

Natürlich hat die zweite Variante den Vorteil die Größe des Arrays zur Laufzeit bestimmen zu können. Aber davon mal ganz abgesehen.
Was passiert im Hintergrund?
Hat jemand 'ne Idee wie man das ausprobieren könnte?

Wie sieht es mit dem Zugriff auf Daten im Stack oder im Heap aus (von der Zeit her)?

Ciao sagt Sprotti

Bashar

Allokation auf dem Stack ist ein einziger Maschinenbefehl (Addition einer festen Größe auf den Stackpointer). Dabei können auch alle Variablen der Funktion zu einer Addition zusammengefasst werden, so dass dieses Array u.U. gar nichts kostet.

Allokation auf dem Heap umfasst eine mglw. umfangreiche Suche nach einem passenden freien Speicherblock, der dann eventuell geteilt und als benutzt markiert werden muss. Deallokation ist ähnlich aufwändig.

Edit: Beim Zugriff sind beide, von Cache-Effekten abgesehen, gleich schnell.

Sprotti

Hm, gibt es denn Möglichkeiten eine Allokierung im Heap zu umgehen wenn man nun doch betrachtet das man erst zur Laufzeit die Größe des Array festlegen möchte?

C++ Forumbot

Dieser Thread wurde von Moderator/in Jansen aus dem Forum Borland C++ Builder (VCL/CLX) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Sprotti schrieb:

Hm, gibt es denn Möglichkeiten eine Allokierung im Heap zu umgehen wenn man nun doch betrachtet das man erst zur Laufzeit die Größe des Array festlegen

wer hindert dich denn daran folgendes zu schreiben:

int size = 20;
int a[size];

SirLant

In C99 (jedenfalls auf dem Papier) sind dynamische Arrays welche auf dem Stack(soweit ich weiß!) liegen möglich, jedoch kenne ich keinen C-Compiler der das unterstützt.

Bashar

gcc kann das. Sogar im C++ Modus, dann natürlich als Erweiterung.

groovemaster

Sprotti schrieb:

Hm, gibt es denn Möglichkeiten eine Allokierung im Heap zu umgehen wenn man nun doch betrachtet das man erst zur Laufzeit die Größe des Array festlegen möchte?

Nein. Bei Stack Arrays musst du unter C++ immer eine maximale Grösse berücksichtigen, alleine schon deshalb, weil dir nicht unendlich viel Stack zur Verfügung steht.

Sprotti

mich hindert der Compiler.
ausprobiert mit 'nem TButton *Button1 und TEdit *Edit1:

void __fastcall TForm1::Button1Click(TObject *Sender)
{
        int size=Edit1->Text.ToInt();
        int array[size];
        for (int i=0;i<size;i++)
        {
                array[i] = i;
        }
}

bringt natürlich den Fehler:
[C++ Fehler] Unit1.cpp(21): E2313 Konstantenausdruck erforderlich in Zeile
"int array[size];"

Sprotti

groovemaster schrieb:

Nein. Bei Stack Arrays musst du unter C++ immer eine maximale Grösse berücksichtigen, alleine schon deshalb, weil dir nicht unendlich viel Stack zur Verfügung steht.

Kann ich denn die Arrays zur Laufzeit irgendwie erweitern wenn ich größere brauche? Also erstmal ein, sagen wir mal, 20 Byte großes int Array anlegen und wenn das voll ist eine Erweiterung dieses Arrays vornehmen oder ein größeres anlegen und den Inhalt des zu kleinen Arrays kopieren?

DEvent

aber klar
zb realloc, unter c++ stl::vector usw

Nicht auf dem Stack. Die Größe eines Arrays auf dem Stack muss zur *Kompilierzeit* bekannt sein. Ich empfehle auch nicht, die entsprechende Erweiterung vom gcc zu nutzen.
Wo ist denn außerdem dein Problem, das Array auf dem Heap anzulegen, das ist doch eine schöne Lösung.

Kann ich denn die Arrays zur Laufzeit irgendwie erweitern wenn ich größere brauche? Also erstmal ein, sagen wir mal, 20 Byte großes int Array anlegen und wenn das voll ist eine Erweiterung dieses Arrays vornehmen oder ein größeres anlegen und den Inhalt des zu kleinen Arrays kopieren?

Ja, wenn du deine Arrays auf dem Heap hast, geht das wunderbar. Da kann dir dann sogar std::vector die Arbeit des vergrößerns abnehmen.

EDIT: bezieht sich nicht auf den direkt vorherigen Post.

DEvent

kann man das nicht mit asm machen?
dynamische arrays aufn stack?

Das Problem ist, dass die Größe eines Stackframes dann nicht mehr konstant ist. Wenn sich der C++ Compiler darauf verlässt, bringt das vielleicht Ärger.

SirLant

Natürlich würde es mit ASM gehen, aber wie Optimizer schon sagte kann das Probleme mit dem Compiler geben, wobei man da sicher auch irgendwo was einstellen kann.

rapso

mit asm geht das, wenn der compiler probleme damit hat, dann ist es compiler schuld, denn wenn man inline assembler ausführen kann, muss der compiler an der stelle davon ausgehen, dass jedes register vom 'user' verändert wird. für das verhalten dann ist natürlich der user zuständig, denn er muss bei c++ wissen was er macht.
das problem was jedoch auftauchen könnte, wäre dass das array nicht die höchste variable auf dem stack ist und man deswegen speicher überschreibt.

ich empfehle an dieser stelle, sich ne kleine klasse zu schreiben die speicher wie einen stack verwaltet, dann legt man sich dort arrays beliebiger größe zur laufzeit an, dann ist das laufzeitverhalten wie beim normalen stack, man hat die größenlimitierung wie beim normalen stack, kein problem damit den speicher mit anderen variablen zu überschreiben und kein assemblergefricke.

rapso->greets();

Sprotti

Optimizer schrieb:

Wo ist denn außerdem dein Problem, das Array auf dem Heap anzulegen, das ist doch eine schöne Lösung.

Es geht mir halt um die Laufzeit. Meine Daten die ich in das Array schmeißen muß kommen so fix rein, daß jede µs zählt die ich sparen kann. Nun kann ich aber die Anzahl der Daten die ins Array gespeichert werden müssen nicht zur Compilierzeit abschätzen.

Wie Bashar so sagte, auf dem Heap solltest du mit der selben Geschwindigkeit zugreifen können müssen. Das Anlegen wird vermutlich etwas länger dauern, aber das ist einmalig. Ich kann mir nicht vorstellen, dass die paar Nanosekunden groß was rausreißen.
Und du hast so wie es aussieht auch noch kein konkretes Problem, nachdem du es ja noch überhaupt nicht implementiert hast. Premature optimization is the root of all evil. Das hier ist ein wunderschönes Beispiel. Anstatt komfortabel std::vector zu benutzen, wird hier auf Verdacht mal schnell was mit Assembler gehackt um dynamische Arrays auf dem Stack zu haben.
Davon rate ich ab.

Artchi

Lächerlich und traurig als angebliche C++-Coder was von realloc oder gar ASM zu reden. Es gibt doch (wie von leider nur wenigen gesagt) das std::vector. Alles andere ist SCHWACHSINN!

Shade Of Mine

std::vector verwenden und wenn der Profiler dir dann zeigt, dass vector zu langsam allokiert einfach nen eigenen Allokator schreiben -> erstmal einen fastAllocator, der großzügiger mit dem Speicher umgeht um reallokationen zu vermeiden/verringern. Wenn das auch nicht klappt non-standard Wege suchen, zB per alloca() auf dem Stack reservieren oder andere Allokatorstrategieren ausprobieren.

Das schöne: du hast erstmal ne Lösung mit std::vector die funktioniert und vielleicht sogar schnell genug ist. Wenn es zu langsam ist, kannst du (ohne den Code zu ändern) einfach andere Allocatoren testen.

So macht optimierung mehr sinn.
Premature optimiziation ist zwar the root of all evil, aber dennoch sollte man Optimierungen in der Designphase beachten (und versuchen sich diese nicht durch Designentscheidungen zu verbauen - natürlich heisst das jetzt nicht, dass man gleich alle Optimierungen "reindesignen" soll - aber im Hinterkopf behalten ist ganz gut) -> wie du siehst ist std::vector somit eine gute Entscheidung.