Stack Overflow
Stack Overflow
Hi,
gibts einigermassen gute Tricks zum vermeiden von Stack Overflows?
Sind verschachtelte If's ein Problem? Belasten Structured Lists den Stack? Was sind sonst so NoNo's?
danke im voraus
Amon
gibts einigermassen gute Tricks zum vermeiden von Stack Overflows?
Sind verschachtelte If's ein Problem? Belasten Structured Lists den Stack? Was sind sonst so NoNo's?
danke im voraus
Amon
-
- Beiträge: 6291
- Registriert: 29.08.2004 08:37
- Computerausstattung: Hoffentlich bald keine mehr
- Kontaktdaten:
Re: Stack Overflow
Verschachtelte Prozeduren führen auch dazu(also mehr Spaghetticode erstellen
).

Angenommen es gäbe einen Algorithmus mit imaginärer Laufzeit O(i * n), dann gilt O((i * n)^2) = O(-1 * n^2) d.h. wenn man diesen Algorithmus verschachtelt ist er fertig, bevor er angefangen hat.
Lokale Variablen belasten ja auch den Stack, also kann manDeeem2031 hat geschrieben:Du musst eigentlich nur bei rekursiven Proceduren darauf achten das die früh genug aufhören. Ansonsten wirst du warscheinlich nie an die Grenzen des Stacks kommen.
auch dort einsparen.
Der folgende Code crasht bei mir:
Code: Alles auswählen
#MYSIZE = 3047
Structure myStruct
long.l[#MYSIZE]
EndStructure
Procedure xyz()
a.myStruct
a\long[#MYSIZE-1] = 2
MessageRequester("INFO","Test")
EndProcedure
xyz()
beendet ohne das die MessageBox kommt.
Allerdings sieht das nicht aus wie der Stacküberlauf den ich
eigentlich haben wollte, da der Stack 1MiB ist.
Hier gibt es dann die richtige Exception (Ausnahmefehler):
Code: Alles auswählen
Structure myStruct
long.l[250]
EndStructure
Procedure Rekursiv(a)
x.myStruct
If a = 1000
MessageRequester("INFO","a = "+Str(a))
Else
Rekursiv(a+1)
EndIf
EndProcedure
Rekursiv(0)
die Werte ein bissl erhoehen, z.B. a = 2000)
Das geht also schneller als man denkt, wenn man nicht
darauf achtet oder man nicht weiß wie ein Rechner auf
unterster Ebene funktioniert (z.B. Beginner).
Der Stack ist standardmaessig bei den meisten Compilern
auf 1MiB eingestellt. Das kann aber meist ganz einfach durch
ein Linker-Flag geändert werden, wenn man bei tiefer Rekursion
usw. mal mehr braucht.
Als Tipp für Rekursion könnte man also sagen: So wenig
wie möglich lokale Variablen in der Rekursionsprozedur.
Lokale Variablen, wenn nötig, so klein wie möglich nehmen.
So wenig Argumente wie möglich an die Prozedur übergeben.
Rekursionstiefe so klein wie möglich.
Selbst ein rekursives Scannen aller Verzeichnisse auf einer
Festplatte kann schnell zum Stacküberlauf führen, wenn die
Tiefe groß genug ist und man noch lokale Variablen verwendet.
Das ist also ein Problem was Jedem schnell passieren kann,
wenn man das nicht im Hinterkopf hat. Selbst mit kleinsten
Codes geht das schnell.
cya,
...Danilo
"Ein Genie besteht zu 10% aus Inspiration und zu 90% aus Transpiration" - Max Planck
...Danilo
"Ein Genie besteht zu 10% aus Inspiration und zu 90% aus Transpiration" - Max Planck
Ich habe jetzt mal einige verschachtelte If's rausgegeben, rufe die benötigte library nur mehr einmal auf, und habe die pointer zu den library funktionen in globale variablen gelegt, rekursion verwende ich keine.
Mein Programm öffnet mittels der zlib1.dll eine komprimierte datei, entpackt deren Inhalt in einen Speicherbereich und liest dann mittels Peek Befehlen die Datenstruktur aus und speichert deren Inhalte in strukturierten Listen ab (wobei gleich auch eine normalisierung der Daten durchgeführt wird - also Redundanzen beseitigt werden).
Die Anzahl der Datensätze schwankt zwischen 40k bis 5000k. (Geschwindigkeit erstaunlicherweise erträglich
)
Dann kann man in gewissen Rahmen diese Daten manipulieren, und dann wieder abspeichern, wobei die Daten wieder in eine Datei mittels der zlib1.dll gestreamt werden (gzwrite).
Aufmerksam geworden bin ich durch vereinzelt auftretende "Illegal Memory Access" bei dem Aufruf von OpenFileReq. bzw. SaveFileReq.
Kann es sein das es an meiner Art der Library aufrufen liegt?
Ich habe jetzt mal sämtliche Aufrufe von CallFunctionFast auf CallCFuctionFast umgeschrieben, mal sehen ob das eine Besserung bringt
einige aufrufe...
Mein Programm öffnet mittels der zlib1.dll eine komprimierte datei, entpackt deren Inhalt in einen Speicherbereich und liest dann mittels Peek Befehlen die Datenstruktur aus und speichert deren Inhalte in strukturierten Listen ab (wobei gleich auch eine normalisierung der Daten durchgeführt wird - also Redundanzen beseitigt werden).
Die Anzahl der Datensätze schwankt zwischen 40k bis 5000k. (Geschwindigkeit erstaunlicherweise erträglich

Dann kann man in gewissen Rahmen diese Daten manipulieren, und dann wieder abspeichern, wobei die Daten wieder in eine Datei mittels der zlib1.dll gestreamt werden (gzwrite).
Aufmerksam geworden bin ich durch vereinzelt auftretende "Illegal Memory Access" bei dem Aufruf von OpenFileReq. bzw. SaveFileReq.
Kann es sein das es an meiner Art der Library aufrufen liegt?
Ich habe jetzt mal sämtliche Aufrufe von CallFunctionFast auf CallCFuctionFast umgeschrieben, mal sehen ob das eine Besserung bringt

einige aufrufe...
Code: Alles auswählen
dateinr.l = CallCFunctionFast(*F_gzopen, datei.s, mode.s)
ergebnis.l = CallCFunctionFast(*F_gzread, dateinr.l, *destmem.l, dest.l)
ergebnis.l = CallCFunctionFast(*F_gzwrite, dateinr.l, @karte()\x, 2)
ergebnis.l = CallCFunctionFast(*F_gzwrite, dateinr.l, @temp_fg.s, l_fg)
Ist zwar schon ein paar Tage her, aber vielleicht interessiert es doch noch den Einen oder Anderen.
Zum vermeiden von Stack Overflows bei Rekursion :
Zum vermeiden von Stack Overflows bei Rekursion :
Code: Alles auswählen
; Stack Overflow Test - uweb
; Interessant finde ich sowohl,
; daß für Rekursion1 und Rekursion2 die gleichen Grenzen gelten
; als auch,
; daß es für beide keinen Unterschied macht ob ich Zahl erzeuge oder nicht.
; Die Lösung ist die 3. Procedure : PseudoRekursion()
Global MaxEbenen
Global MaxChilds
Global Anzahl
Global E
Global C
DebugLevel = 0
Procedure Rekursion1(Ebene, Child)
Zahl = Anzahl
If Ebene < MaxEbenen
Debug "Rekursion1 - Ebene "+Str(Ebene),2
Debug "Rekursion1 - MaxEbenen "+Str(MaxEbenen),2
If Child < MaxChilds
Debug "Rekursion1 - Child "+Str(Child),2
Debug "Rekursion1 - MaxChilds "+Str(MaxChilds),2
Child + 1
Anzahl+1
Rekursion1(Ebene, Child)
Else
Child = 0
Ebene + 1
Anzahl+1
Rekursion1(Ebene, Child)
EndIf
EndIf
EndProcedure
Procedure Rekursion2()
Zahl = Anzahl
If E < MaxEbenen
If C < MaxChilds
C + 1
Anzahl+1
Rekursion2()
Else
C = 0
E + 1
Anzahl+1
Rekursion2()
EndIf
EndIf
EndProcedure
Procedure PseudoRekursion()
Dim Zahl(MaxEbenen*MaxChilds+MaxEbenen-1)
For E = 0 To MaxEbenen-1
Zahl(Anzahl) = Anzahl
Anzahl+1
Debug "PseudoRekursion - Ebene "+Str(E),1
Debug "PseudoRekursion - MaxEbenen "+Str(MaxEbenen),1
For C = 0 To MaxChilds-1
Zahl(Anzahl) = Anzahl
Anzahl+1
Debug "PseudoRekursion - Child "+Str(C),1
Debug "PseudoRekursion - MaxChilds "+Str(MaxChilds),1
Next
Next
EndProcedure
MaxEbenen = 147 ; Zählung beginnt bei 0 aber Abfrage erfolgt über "kleiner als"
MaxChilds = 147 ; Zählung beginnt bei 0 aber Abfrage erfolgt über "kleiner als"
Anzahl = 0
Rekursion1(0,0)
Debug "Anzahl "+Str(Anzahl)
MaxEbenen = 147 ; Zählung beginnt bei 0 aber Abfrage erfolgt über "kleiner als"
MaxChilds = 147 ; Zählung beginnt bei 0 aber Abfrage erfolgt über "kleiner als"
Anzahl = 0
E = 0
C = 0
DisableDebugger
Rekursion2()
EnableDebugger
Debug "Anzahl "+Str(Anzahl)
MaxEbenen = 247 ; Zählung beginnt bei 0 aber Schleife läuft bis MaxEbenen-1
MaxChilds = 247 ; Zählung beginnt bei 0 aber Schleife läuft bis MaxChilds-1
Anzahl = 0
PseudoRekursion()
Debug "Anzahl "+Str(Anzahl)
End
- remi_meier
- Beiträge: 1078
- Registriert: 29.08.2004 20:11
- Wohnort: Schweiz
Um Stack Overflows abzufangen ist die OnErrorLib im Moment leider (fast)
völlig unbrauchbar:
Programm schaltet einfach ab
Mit PBOSL gibts eine saubere Lösung:
Das nur mal um zu zeigen, wie man solch einen Fehler sogar mit PB ab-
fangen kann
greetz
Remi
völlig unbrauchbar:
Code: Alles auswählen
DisableDebugger
Structure myStruct
long.l[350]
EndStructure
Procedure Rekursiv(a)
x.myStruct
If a = 1000
MessageRequester("INFO","a = "+Str(a))
Else
Rekursiv(a+1)
EndIf
ProcedureReturn
error:
MessageRequester("Exception", GetErrorDescription())
ClearError()
Return
EndProcedure
OnErrorGosub(?error)
Rekursiv(0)
MessageRequester("Fertig", "Mich siehst du wohl nicht... :(")

Mit PBOSL gibts eine saubere Lösung:
Code: Alles auswählen
DisableDebugger
Structure myStruct
long.l[350]
EndStructure
Procedure Rekursiv(a)
x.myStruct
If a = 1000
MessageRequester("INFO","a = "+Str(a))
Else
If TryError()
Rekursiv(a+1)
Else
#EXCEPTION_STACK_OVERFLOW = $C00000FD
MessageRequester("Exception", "Stack Overflow: " + Hex(GetTryErrorCode()) + " " + Hex(#EXCEPTION_STACK_OVERFLOW))
EndTryError()
ProcedureReturn
EndIf : EndTryError()
EndIf
EndProcedure
Rekursiv(0)
MessageRequester("Fertig", "Ich verabschiede mich ganz normal ;)")
fangen kann

greetz
Remi
Ist vermeiden nicht besser als abfangen ?
Ich zähle mich zwar immer noch zu den Anfängern (weil ich einfach zu wenig Zeit investiere). aber wenn ich richtig informiert bin ist die Stack-Größe statisch.
Meine Methode läßt sich leicht auf AllocateMemory() umschreiben, dann weiß man bei einem Rückgabewert von 0 gleich im voraus, daß es eng wird.
Wenn nicht sicher ist, daß die Grenzwerte erreicht werden, kann man AllocateMemory() ja immer noch in den Schleifen aufrufen.
Dann haben unsere Lösungen zwar gemeinsam, daß wir ggf. scheitern wenn wir schon unterwegs sind (beim Ändern von Daten nicht so toll), die Grenzen meiner Methode sind aber immer noch weiter.
Ich sage ja auch nicht, daß das an PureBasic liegt.
Im Gegenteil ich liebe es !
Es liegt wohl eher daran, daß ein Compiler ein Compiler ist.
Die Stack-Größe wird im voraus bestimmt.
Ich habe also das Problem nicht gelöst, sondern habe eine Möglichkeit gefunden es zu umgehen.
Nachtrag :
Ich habe mein Beispiel eben mit
ohne Probleme laufen lassen.
Ich zähle mich zwar immer noch zu den Anfängern (weil ich einfach zu wenig Zeit investiere). aber wenn ich richtig informiert bin ist die Stack-Größe statisch.
Meine Methode läßt sich leicht auf AllocateMemory() umschreiben, dann weiß man bei einem Rückgabewert von 0 gleich im voraus, daß es eng wird.
Wenn nicht sicher ist, daß die Grenzwerte erreicht werden, kann man AllocateMemory() ja immer noch in den Schleifen aufrufen.
Dann haben unsere Lösungen zwar gemeinsam, daß wir ggf. scheitern wenn wir schon unterwegs sind (beim Ändern von Daten nicht so toll), die Grenzen meiner Methode sind aber immer noch weiter.
Ich sage ja auch nicht, daß das an PureBasic liegt.
Im Gegenteil ich liebe es !
Es liegt wohl eher daran, daß ein Compiler ein Compiler ist.
Die Stack-Größe wird im voraus bestimmt.
Ich habe also das Problem nicht gelöst, sondern habe eine Möglichkeit gefunden es zu umgehen.
Nachtrag :
Ich habe mein Beispiel eben mit
Code: Alles auswählen
MaxEbenen = 14700
MaxChilds = 14700