Wie ist das mit der Rekursion und dem Stack?

[Matze]

Hi!

Ich habe nochmal eine Frage zur Rekursion ;)


Wenn ich größere Rechenschritte nicht iterativ, sondern rekursiv löse, dann kommt es manchmal zum Stacküberlauf.

Wie groß ist dwer Speicher, der dem Stack zugewiesen ist?

Mein Lehrer hat gesagt, man muss sich das wie übereinander gestapelte Teller vorstellen.
Nur kann ich das nicht so richtig :oops:


Kann mir jemand erklären, was genau ein Stack ist und wieso es da zum Überlauf kommen kann?

[Jens Schumann]

Hallo,
der Stack ist ein Speicherbereich in dem lokale Variablen und (jetzt kommt es) die Rücksprungadressen zu Prozeduren oder Funktionen, die ihrerseits ein Unterprogramm (Prozeduren oder Funktionen) aufrufen gespeichert.

Dasraus folgt: Da der Arbeitsspeicher in einem Computer leider endlich ist und wenn das Programm immer mehr Rücksprungadressen auf den Stack legen muss wird der Speicher irgendwann nicht mehr ausreichen.

Behauptung: Wenn es bei einer Rekursion zu einen Stackoverflow kommt ist die Abbruchbedingnung der Rekursion fehlerhaft.

[Matze]

Danke, aber die Behauptung muss falsch sein ;)

Mein lehrer hat gemeint, aus dem Grund ist die Rekursion nur für "kleinere", wie soll ich sagen, "Schleifen" :mrgreen: geeignet.

[Matze]

Aber, wenn das so wäre, dann wäre Quicksort ja echt doof! :mrgreen:
Das ist ja auch rekursiv.

[jbg]

QuickSort kann man auch iterativ schreiben. Nur macht das kaum jemand, da es viel zu umständlich ist.

Und wenn ich mich nicht täusche, braucht Quicksort ca. n*log(n) rekursive Schritte (log = 2er-Logarithmus)

[Matze]

Aha, danke!

[Phoenix]

Zitat:

Zitat von Jens Schumann

Behauptung: Wenn es bei einer Rekursion zu einen Stackoverflow kommt ist die Abbruchbedingnung der Rekursion fehlerhaft.

Ich behaupte einfach mal, die Behauptung ist falsch ;-)

Zum einen wird bei einem Funktionsaufruf nicht nur die Rücksprungadresse auf den Stack gelegt, sondern auch die lokalen variablen wie bereits erklärt - sowie ein Teil der Übergabeparameter. Um genauer zu sein die ersten drei. Alle weiteren landen auf dem Heap.

Man kann nun hergehen und den Aufruf so optimieren, daß nur das allernötigste auf dem Stack liegt. - Das geht natürlich zu Lasten der Geschwindigkeit, aber der Stack kann somit mehr Aufrufe - also einen höheren Stapel an Tellern - fassen.

An der Stelle wie man die Funktion optimiert bin ich aber (leider) noch überfragt. Ich könnte wetten, daß Hagen bzw. Assarbad hier gute Hinweise liefern können.

Zum anderen gibt es eine Funktion (wurde hier im Forum auch ein paar mal gepostet, ich weiss den Namen nur nicht mehr), die mehr oder weniger garantiert zu einem Stack overflow führt. Zumindest bei mir und bei einigen anderen :)

(Edit:) Der Name ist gefunden ;-)
Es handelt sich um die Berechnung von Fibonacci - Zahlen. Die Anzahl der Aufrufe steigt die exponentiell mit der Anzahl der zu berechnenden Summanden an - was nicht an einer falschen Abbruchbedingung sondern einfach an der hohen Anzahl der zu berechnenden Werte liegt. In irgendeinen Thread steht was von maximal 96 als Startzahl, alles was darüber hinaus geht scheint für normale 32bit - Rechner etwas zu schwierig zu sein ;-) (/edit)

[neolithos]

Zitat:

Zitat von Phoenix

...wie ein Teil der Übergabeparameter. Um genauer zu sein die ersten drei. Alle weiteren landen auf dem Heap.

Kleine Bereichtigung:

Die Übergabe der Parameter hängt erstmal von den Worten stdcall, register, pascal, cdecl ab.

Was Delphi meinst nimmt ist register, und das bedeutet das die ersten 3 Parameter via Register eax, edx, ecx übergeben werden und der Rest auf dem Stack liegt. Desweiteren wird bei den anderen nur der Stack verwendet (Heap wäre sinnlos da die gefahr besteht das er zu stark fragmentiert).

[neolithos]

Zur Optimierung:

1. Vermeide große statische Parameter.

Schlechtes Bsp.

Delphi-Quellcode:

BinSearch(afData : array [0..1023] of Integer; aiLo, aiHi : Integer)

Hier würde mit jeder Rekursion 1032 Byte verbraucht.

Besseres Bsp.

Delphi-Quellcode:

PIntegerArray = ^TIntegerArray;
TIntegerArray = array [0..1023] of Integer;

BinSearch(apData : PIntegerArray; aiLo, aiHi : Integer)

d.h. heißt auch nur sinnvolle Sachen Übergeben, z.B. habe ich mal zu DOS-Zeiten (wo der Stack noch kleiner war) alle in der Rekursion fixen Variablen in ein Record gepackt und eine Referenz darauf übergeben.

Bsp.

Delphi-Quellcode:

function BinSeach(var pParams : TBinSearchParams; apData : PIntegerArray; aiLo, aiHi : Integer) : integer;

2. Genau so ähnlich läuft es bei den statische lokale Variablen

Immer lieber Dynamische Variablen verwenden wenn es um große Sache geht.

Delphi-Quellcode:

var s : ShortString // verbrauch 256 Byte
    s : String; // verbrauch 4 Byte

3. Überlege dir das Nutzen <-> Aufwand verhältnis

Wie oft schachtelt sich die Rekursion, brauch ich dann überhaupt den Aufwand treiben.

4. Windows hat ausreichend Stack

So DOS-Zeiten hate man max. 64 kB Stack-Speicher. Heute geht die Geschichte rein Theoretisch in die Giga Byte (max. 2 GB).

Im Dialogfeld Optionen -> Linker -> Speichergrößen kann man den Stack beeinflussen.


Sei Vorsichtig mit den Lehrern: Ich habe mal einen von der Sorte rundgemacht wegen falschen Aussagen. Ergebnis: Strafplatz und für immer Mundhalten! :wink:
Und nur der kleinste Fehler wurde bestraft.
Ich hate mal ein Minus mit Plus vertauscht, schon gab es nur noch eine Zwei! Beschwehren hilft da auch nix!
Trotzdem noch auf Eins am Ende geschafft!

[choose]

Zitat:

Zitat von Phoenix

Zum einen wird bei einem Funktionsaufruf nicht nur die Rücksprungadresse auf den Stack gelegt, sondern auch die lokalen variablen wie bereits erklärt - sowie ein Teil der Übergabeparameter. Um genauer zu sein die ersten drei. Alle weiteren landen auf dem Heap.

Hallo Phoenix,
die Parameterübergabe in Delphi entspricht (per Default) nicht ganz Deinen Darstellungen: Zum einen wird beim Aufruf einer Funktion/Methode unbedingt eine Rücksprungadresse abgelegt (4Bytes), sofern man nicht mit dem Inline-ASM einen Fake-Call via jmp verwendet und die "eigene" Rücksprungadresse wiederverwendet, was insbesondere bei einer endrekursion Sinn machen könnte.
Dann wird bei (Klasse-)Methoden eine nicht in der DL sichtbare Referenz auf die Klasse/das Exemplar übergeben (4Bytes), um das Schlüsselwort Self auch bei nicht-statischen Methoden mit Referenzen auf Exemplarvariablen bzw Delegationen auf nicht-statische Methoden verwenden zu können.
Sofern möglich, werden die ersten drei Parameter über die Register EAX, EDX und ECX, also ohne Verwendung des Stacks übergeben. Zu beachten ist an dieser Stelle, dass der zuvor erwähnte "unsichtbare Parameter" ebenfalls zu diesen drei zu zählen ist, also bei Methoden im besten Fall nur die ersten beiden Parameter auf diese Weise übergeben werden können.
Im Fall von komplexeren Parametern (Daten, die nicht unmittelbar in ein Register passen) als Integer, Chars, Referenzen etc. werden stattdessen Referenzen auf die Daten übergeben. In wenigen Fällen (zB ad-hoc erstellte Array-Parameter) muss hierzu zunächst eine "unsichtbare lokale Variable" erzeugt werden, um diese Referenz erzeugen zu können. Sollte ein solcher Parameter mit dem Attribute const, var oder out versehen sein, bleibt es dabei. Andernfalls kann es sein, dass der Compiler innerhalb des Codes der aufgerufenen Routine zusätzlich eine lokale Kopie des Parametes auf dem Stack anlegt, um das "call by value"-Prinzip bei Schreibzugriffen nicht zu verletzen. Dies kann insbesondere bei komplexen Records oder großen statischen Arrays die Größe des verwendeten Stacks gravierend beeinflussen.
Objekte, Dynamische Arrays und Strings bilden in diesem Konzept eine Ausnehme, ihre Daten werden generell auf dem Heap abgelegt, bei der Übergabe wird allerdings das Prinzip der "Übergabe der Referenz" verfolgt. Während "lokale" Kopien des dynamischen Arrays wiederum auf dem Heap angelegt werden, um eine spätere Größenänderung zuzulassen, wird bei den Strings das Komzept des copy on write verfolgt.
Fließkommazahlen scheinen (außer bei den Compiler-Magic Funktion) ihre Daten immer über den Stack zu erwarten (hat hier jmd genauere Infos?)

Zusätzlich zu diesen Parametern liegen die lokalen Variablen (im Falle von Strings, dynamischen Arrays und anderen Objekten zumindest Referenzen auf sie) auf dem Stack, sofern der Compiler nicht in der Lage ist, sie über Register abzubilden.

Sollte es sich bei der Routine um eine Funktion handeln, deren Ergebnis gem obiger Darstellung nicht über EAX bzw bei Floats über ST(0) übergeben werden können, reserviert die aufrufende Routine zunächst einen Speicherbereich auf dem Stack (bzw verwendet den Platz einer lokalen Variablen), un übergibt eine Referenz als Parameter auf den mit dem Ergebnis zu füllenden Bereich.


Die von mir dargestellte Aufrufkonvention entspricht mit der Delphi-Default-Variante (register) jedoch nur einer der Möglichkeiten. So werden zB die Werte bei cdecl wesentlich stacklastiger übergeben, genaueres in der OH.

Zitat:

Zitat von Phoenix

Man kann nun hergehen und den Aufruf [..] optimieren[..]. Das geht natürlich zu Lasten der Geschwindigkeit[..]

Optimierungen dieser Art sind im Gegenteil häufig auch von Vorteil hinsichtlich der Geschwindigkeit geprägt.

Zitat:

Zitat von Phoenix

[..]aber der Stack kann somit mehr Aufrufe - also einen höheren Stapel an Tellern - fassen.

Anschaulicher wäre wohl: "eine größere Anzahl von dünneren Tellern fassen." Schließlich bleibt die höhe des Stapels (größe des Stacks) konstant (idR ;)).

Zitat:

Zitat von Phoenix

Ich könnte wetten, daß Hagen bzw. Assarbad hier gute Hinweise liefern können.

Das wette ich auch ;) Vor kurzem hat Luckie auch einmal im Zusammenhang mit der Erstellung eines Guides zur Erstellung "besseren Codes" nachgefragt, wie das mit diesen "komischen Parametern" war, vielleicht hilft dieser Thread weiter...

[choose]

Zitat:

Zitat von neolithos

Delphi-Quellcode:

BinSearch(apData : PIntegerArray; aiLo, aiHi : Integer)

Die Arbeit mit Pointern ist eine häufige Fehlerursache, wenn man nicht genau weiß, was man macht. Sollen die Daten in der aufrufenden Routine verändert werden, empfiehlt sich stattdessen das Attribut var, sollen die Daten nie verändert werden stattdessen const. Technisch gesehen, entspricht dies vollständig Deiner Lösung, neolithos, allerdings bewegst Du Dich in der "sicheren Pascal-Umgebung", typenstrenge, (ohne Tricks) kein nil möglich, bei const (ohne Tricks) auch wirklich keine Veränderungen möglich, ...

Zitat:

Zitat von neolithos

Wie oft schachtelt sich die Rekursion, brauch ich dann überhaupt den Aufwand treiben.

Bzw verwende wann immer möglich, auch um sprechenderen Code zu schreiben, die Schlüsseworte const, var und out.

Zitat:

Zitat von neolithos

Trotzdem noch auf Eins am Ende geschafft!

Glück gehabt, es gibt mit Sicherheit auch nachtragendere Menschen ;)

[neolithos]

@choose

Danke für die Wertvollen Ergänzungen! (Mit den floats hab ich selbst noch nicht gewußt)
Mit den var, const und out ist ein guter Hinweis. Stimm ich generell zu, dass das sicherere ist und auf des selbe wie ich Def. habe hinaus läuft. Dummerweise bin ich noch DOS-Pascal belasstet und da hat sich so manches eingeschlichen was man nur schwehr rausgriegt.

[NeoXpert]

ich weiß kommt en bisserl spät.. aber wir durften im LK die Türme von Babylon, das Springerporblem (übern schabrett mit nem springer, jedes feld nur einmal berühren) und den quicksort iterativ schreiben.... gar nicht lustig und da ichs net verstanden habe, bzw. mir kopiert habe kann ichs euch leider net geben :( aber sagen wir es sind ein paar mehr zeilen ^^

[Matze]

OK, ich danke euch allen! :)
Jetzt müsst ich's kappiert haben ;)

[negaH]

Zitat:

Sofern möglich, werden die ersten drei Parameter über die Register EAX, EDX und ECX, also ohne Verwendung des Stacks übergeben. Zu beachten ist an dieser Stelle, dass der zuvor erwähnte "unsichtbare Parameter" ebenfalls zu diesen drei zu zählen ist, also bei Methoden im besten Fall nur die ersten beiden Parameter auf diese Weise übergeben werden können.

Das ist insofern richtig, für den realen Stackverbrauch ist dies aber leider NICHT relevant. Denn selbst wenn die Parameter über Register und NICHT dem Stack übergeben werden, so sind die meisten rekursiven Funktionen denoch komplexer Natur. Somit werden diese Register-Parameter nach dem Eintritt in die rekursive Funktion wiederum auf dem Stack gesichert, oder aber in den Registern ESI,EDI,EBX gesichert NACHDEM jeweils EDI,ESI,EBX auf dem Stack gesichert wurden. Somit verbraucht eine rekursive Funktion die EAX,EDX,ECX als Register-Parameter benutzt denoch 3 Integer Stack Variablen intern. Es macht also fast keinen Unterschied im Stackverbrauch.

Zitat:

Und wenn ich mich nicht täusche, braucht Quicksort ca. n*log(n) rekursive Schritte (log = 2er-Logarithmus)

Dies ist richtig für die durchschnittliche Anzahl an rekursiven Aufrufen dergleichen QuickSort Funktion, definiert aber NICHT die maximale Rekursionstiefe. Die maximale Verschachtelungsanzahl beträgt dann nämlich nur Ln2(n) = Log(N) wenn Log() der 2er Logarithmus ist. D.h. bei N = 1024 wird die max. Tiefe nur 10 betragen, da 2^10 = 1024. Nur diese Rekursionstiefe bestimmt den Stackverbrauch und würde bei N = 2^32 eben nur maximal 32 sein. Mit N=2^32 stösst man aber schon an die Speichergrenzen heutiger Rechner. QuickSort() ist somit in Punkto Stackverbrauch absolut unkritisch.

Auf dem Stack speichern die Programme ihre Temporären Lokalen Variablen was somit vergleichbar zum normalen Borland Speicher Manager funktioniert. Der Stack arbeitet also für diese lokalen Variablen wie ein sehr schneller Speichermanager. Den Unterschied zwischen solchen Lokalen Variablen und Borland Speichermanager Variablen bezeichnet man auch öffters als den Unterschied zwischen Dynamischen und Statischen Variablen.

Desweiteren wird ganz transparent der Programmfluß der Anwendung suf dem Stack gespeichert. D.h. bei jedem Funktionsaufruf wird der Programpointer an dem das Programm NACH der aufgerufenen Funktion fortsetzen soll auf dem Stack gespeichert. Ausgehend vom Stack könnte man also in Erfahrung bringen auf welchem WEG die derzeitige Funktion aufgerufen wurde. Zu dieser "Programmflußsteuerung" des Stack kann man auch die geschützten Codebereiche zählen. Dies sind also alle lokalen Variablen die das Programm benötigt um die try finally end. und try except end. Konstrukte umzusetzen.

Gruß Hagen