'stack overflow' ??

der organist · Verfasst: Mi 16.07.08 20:39

Tja, dumm gelaufen, wenn man nicht weiss, was mach ein Fehler nun genau bedeuten soll. Deshalb, meine lieben MitProgrammierer, frage ich euch um ein Stückchen schlauer zu werden:

was ist ein:

Project ballspiel.exe raised exeption Class EStackOverflow with message 'Stack overflow'.

Moderiert von Tino: Topic aus VCL (Visual Component Library) verschoben am Mi 16.07.2008 um 20:47

Tino · Beiträge: 9839 Erhaltene Danke: 45 Windows 8.1 Delphi XE4

Ein "Stack-Overflow" kommt häufig im Zusammenspiel mit Rekursionen und fehlerhaften Abbruchbedingungen zustande.

An welcher Stell im Code tritt die Exception auf?

Gruß
Tino

der organist · Verfasst: Mi 16.07.08 20:47

entweder bin ich immer noch blind oder ich weiss es einfach nicht oder es steht da nich. Wo soll ich das genau herausfinden? Wenn ich das weiss, werde ich morgen mehr liefern können.

Xentar · Verfasst: Mi 16.07.08 20:52

Du musst doch wissen, was passiert, bevor der Fehler auftritt.
Klickt der Anwender auf einen Button, brauchen wir z.B. den Code hinter diesem ButtonClick..

Und wenn nicht: Wenn der Fehler auftritt, zeigt der Compiler dir doch normalerweise die Stelle an, wo das Problem auftritt.

Tilman · Verfasst: Mi 16.07.08 21:07

Stack Overflow ist eigentlich eine typische Erscheinung bei rekursivem Aufruf... also du rufst eine Prozedur in sich selbst auf. (Es gibt natürlich viele weitere Ursachen; dies ist aber die häufigste).

(sry tino, hatte deinen post einfach überlesen)

_________________
Bringe einen Menschen zum grübeln, dann kannst du heimlich seinen Reis essen.
(Koreanisches Sprichwort)

Timosch · Beiträge: 1314 Debian Squeeze, Win 7 Prof. D7 Pers

Ganz einfach ausgedrückt: Es gibt eine Art Stapel (Stack) auf dem Daten abgelegt werden können. Wenn zu viel drauf liegt, kann er überlaufen (u.U. in andere Bereiche des Programmes, z.B. den Programmcode, was dann eine Sicherheitslücke darstellt). Warum das bei dir vllt. auftaucht, wurde ja schon von anderen beschrieben.

_________________
If liberty means anything at all, it means the right to tell people what they do not want to hear. - George Orwell

der organist · Verfasst: Mi 16.07.08 22:16

ok, ich denke, ich habs. Das war wohl eine Rekursion (bei Tino hab ich das überlesen). Des weiteren kann man das hier eher weniger festestellen, das trat immer mitten in meinem Ballspiel (siehe Freeware) auf, da war eig. immer der gleiche Vorgang.

thx für die schnelle Beantwortung

Ralf107 · Hält's aus hier Beiträge: 4

Tilman hat folgendes geschrieben :

Stack Overflow ist eigentlich eine typische Erscheinung bei rekursivem Aufruf... also du rufst eine Prozedur in sich selbst auf. (Es gibt natürlich viele weitere Ursachen; dies ist aber die häufigste).

Ich habe genau dieses Problem: Stack overflow bei rekursivem Aufruf (QuickSort).

Gibt es eine Möglichkeit, vor dem rekursiven Aufrauf die Größe des freien Stacks abzufragen?

alzaimar · Verfasst: Di 14.10.08 12:15

Wegen eines korrekt implementierten Quicksorts gibt es keinen Stackoverflow. Ich vermute, Du übergibst das zu sortierende Array nicht als VAR-Parameter.

Zeig mal deinen Code.

_________________
Na denn, dann. Bis dann, denn.

Ralf107 · Hält's aus hier Beiträge: 4

Ralf107 hat folgendes geschrieben :

Gibt es eine Möglichkeit, vor dem rekursiven Aufrauf die Größe des freien Stacks abzufragen?

Ich bin bei der Lösung des Problems ein kleines Stück weiter gekommen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

procedure TForm1.Rekursion;
var 
  nESP : Cardinal;
begin
  asm
    MOV nESP,ESP
  end;
  if nESP > MinStack then Rekursion;
end;

Was mir noch fehlt, ist der richtige Wert für MinStack.

Bei meinem Testprogramm beginnt nESP bei $0012F614 und zählt in $20-Schritten herunter. Die Exception EStackOverflow tritt jedoch nicht erst bei nESP < $20 sondern schon bei nESP = $341F4 auf.
Die Stackgröße ist in den Projektoptionen auf $00004000 - $00100000 eingestellt.

Moderiert von matze: Code- durch Delphi-Tags ersetzt

alzaimar · Verfasst: Di 14.10.08 12:22

Willst Du einen Stack-Overflow vermeiden, oder nur damit rumspielen?

_________________
Na denn, dann. Bis dann, denn.

Ralf107 · Hält's aus hier Beiträge: 4

alzaimar hat folgendes geschrieben :

Wegen eines korrekt implementierten Quicksorts gibt es keinen Stackoverflow.

Quatsch. Quicksort arbeitet nun mal rekursiv und ist damit anfällig für einen Stack overflow. Besonders kritisch ist dabei der Fall, wenn die Eingangsdaten bereits sortiert sind.

alzaimar hat folgendes geschrieben :

Ich vermute, Du übergibst das zu sortierende Array nicht als VAR-Parameter.

Arrays werden immer als Referenz übergeben, daher spielt es für den Stack keine Rolle, ob das Array als var oder const übergeben wird. Das Schlüsselwort const führt nur zu einer Fehlermeldung des Compilers, wenn versucht wird, das Array innerhalb der Subroutine zu verändern.

alzaimar · Verfasst: Di 14.10.08 13:34

Ralf107 hat folgendes geschrieben :

alzaimar hat folgendes geschrieben :

Wegen eines korrekt implementierten Quicksorts gibt es keinen Stackoverflow.

Quatsch. Quicksort arbeitet nun mal rekursiv

Quicksort ist auch iterativ implementierbar, das mal am Rande. Aber stimmt, wenn ich den Worst case nehme und den Algorthmus mit einem großen Array starte, könnte es sein, das es knallt. Im Übrigen muss das nicht sein, wenn ich einen Random- oder Fibbionacci-Quicksort implementiere, aber das hast Du sicherlich nicht. Beim Random-QS gibt es keinen determinierbaren Worst-Case, sodaß sich diese Variation für die Realität am Besten eignet.

alzaimar hat folgendes geschrieben :

Ich vermute, Du übergibst das zu sortierende Array nicht als VAR-Parameter.

Ralf107 hat folgendes geschrieben :

Arrays werden immer als Referenz übergeben

Hier etwa auch?Procedure Quicksort (MyArray : TStaticIntegerArray; aLeft, aRight : Integer);
Denn darauf wollte ich hinaus: Array als 'call by value' und der Compiler sollte das Array in Gänze auf den Stack packen. Ein beliebter Tippfehler bei Anfängern ist das Fehlen des 'Var'.

Ach, noch ein beliebte Ursache für einen Stackoverflow:

markieren

Delphi-Quelltext

1:
2:
3:

Procedure Stoopid;
Var
  BigStuff : Array [0..1234567] of TSomething;

Lokale Variablen sind auf dem Stack, ergo ergibt sich bei wenigen rekursiven Aufrufen ein Stackoverflow.

Und wg.

Ralf107 hat folgendes geschrieben :

Ich habe genau dieses Problem: Stack overflow bei rekursivem Aufruf (QuickSort).

wiederhole ich also meine Frage: Willst Du beim Quicksort den Stackoverflow vermeiden oder nur mit der Stackgröße rumspielen?

_________________
Na denn, dann. Bis dann, denn.

Ralf107 · Hält's aus hier Beiträge: 4

alzaimar hat folgendes geschrieben :

Aber stimmt, wenn ich den Worst case nehme und den Algorthmus mit einem großen Array starte, könnte es sein, das es knallt.

Genau das passiert gelegentlich bei Arrays > 16k.

alzaimar hat folgendes geschrieben :

Im Übrigen muss das nicht sein, wenn ich einen Random- oder Fibbionacci-Quicksort implementiere, aber das hast Du sicherlich nicht. Beim Random-QS gibt es keinen determinierbaren Worst-Case, sodaß sich diese Variation für die Realität am Besten eignet.

Der worst Case (sortierte Eingangsdaten) ist in dem vorliegenden Fall ausgeschlossen.

alzaimar hat folgendes geschrieben :

Ich vermute, Du übergibst das zu sortierende Array nicht als VAR-Parameter.

Ralf107 hat folgendes geschrieben :

Arrays werden immer als Referenz übergeben

Hier etwa auch?Procedure Quicksort (MyArray : TStaticIntegerArray; aLeft, aRight : Integer);
Denn darauf wollte ich hinaus: Array als 'call by value' und der Compiler sollte das Array in Gänze auf den Stack packen.

Array als 'call by value' gibt es nicht, bei keinem Compiler, egal ob Delphi, C(++/#), ...

Beispiel:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

procedure a ( const x : array of integer );
begin
end;

procedure b;
var 
  y : array of integer;
  z : array [0..123] of integer;
begin
  setlength(y,123456);
  a(y);
  a(z);
end;

Die lokale Variable y ist eine Referenz auf ein dynamisches Array. setlength(y,123456) weist dem dynamischen Array 123456 Speicherplätze zu. Die Referenz y liegt auf dem Stack, das Array selbst wird auf dem Heap angelegt.

Die lokale Variable z ist ein Array, das auf dem Stack liegt.

Sowohl der Aufruf a(y) als auch a(z) erfolgt 'call by reference'! In beiden Fällen werden nur die Länge des Arrays und die Adresse des ersten Elementes auf den Stack gelegt.

alzaimar hat folgendes geschrieben :

Willst Du beim Quicksort den Stackoverflow vermeiden oder nur mit der Stackgröße rumspielen?

Ich will Quicksort abbrechen, bevor der Stack Overflow auftritt.

alzaimar · Verfasst: Di 14.10.08 15:44

Ralf107 hat folgendes geschrieben :

Array als 'call by value' gibt es nicht, bei keinem Compiler, egal ob Delphi, C(++/#), ...

Doch (Wirth-Pascal, UCDS-Pascal, jeder C-Compiler kennt nur 'call by value' usw.), is aber egal, weil wir über Delphi reden.

Dein Beispiel ist übrigens am Thema vorbei, da Du (1) das 'Const' in der Parameterliste hast und (2) ein dynamisches Array als Parameter deklarierst. Das ist in jedem Fall Call-By-Reference mit Read-Only-Schutz im Compiler.

Dessenungeachtet hast Du aber Recht, denn es wird in der Tat in jedem Fall ein 'Call by Reference' kompiliert, obwohl das falsch ist, also ein Bug von Delphi. Denn wenn ich ein Call by Value will, dann soll das gefälligst so kompilieren, geht bei Strings ja schließlich auch.

Habe deine Behauptung, bei einem sortieren Array würde QS die maximale Rekursionstieve erreichen, geprüft. Stimmt nicht. Dann dauert es nur maximal lang, aber zumindest beim Quicksort von TStringList das auf eine Rekursion verzichtet ist die Rekursionstiefe ca. log n, zumindest im Fall des sortierten Arrays.

Das Array muss schon sehr spezifisch sein, um die maximale Rekursionstiefe zu provozieren (z.B. '1 4 6 8 2 5 3 7' bei einem Array mit 8 Elementen)

Ich würde eine iterative Lösung implementierung. Dann ist Ruhe.

_________________
Na denn, dann. Bis dann, denn.

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Natürlich werden Arrays "by value" übermittelt, es sei denn, man verwendet einen dynamischen Array-Typ oder arbeitet mit const bzw. var.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

uses SysUtils, Dialogs;

type
  TIntegerArray = array of Integer;

procedure Test1(A: array of Integer);
begin
  A[0] := 2;
end;

procedure Test2(A: TIntegerArray);
begin
  A[0] := 2;
end;

var
  X1: array of Integer;
  X2: TIntegerArray;
begin
  SetLength(X1, 1);
  X1[0] := 1;
  Test1(X1);

  SetLength(X2, 1);
  X2[0] := 1;
  Test2(X2);

  ShowMessage(Format('%d %d',[X1[0],X2[0]])); // Shows "1 2"
end.

Zu Stackoverflows: Wenn du einen Stackoverflow hast, hast du ziemlich sicher entweder eine unendliche Rekursion produziert, oder eine Rekursion alloziert zu viel Speicher auf dem Stack. In allen Fällen solltest du die Implementation ändern und nicht die Compilereinstellungen.

alzaimar · Verfasst: Di 14.10.08 17:49

Probier mal das hier:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

Type
  TStaticArray = Array [0..9] Of Integer;


Procedure Foo (StaticArray : TStaticArray);
Begin
  StaticArray[0] := 1;
End;


Procedure Bar;
Var
  A : TStaticArray;

Begin
  A[0] := 0;
  Foo(A);
  Showmessage(IntToStr(A[0])); // Kommt '1' heraus und das bei 'Call By Value' ?? Muh?
End;

Mir scheint, das ist ein Fehler von Delphi.
[edit] Ich verwende hier Delphi 6, bei anderen Versionen scheint das nicht (mehr) zu stimmen bzw. korrekt kompiliert zu werden[/edit]

Stack Overflow: Mein Reden.

_________________
Na denn, dann. Bis dann, denn.

Marc. · Verfasst: Di 14.10.08 18:00

alzaimar hat folgendes geschrieben :

Probier mal das hier:

markieren

Delphi-Quelltext

1:	Showmessage(IntToStr(A[0])); // Kommt '1' heraus und das bei 'Call By Value' ?? Muh?

Mir scheint, das ist ein Fehler von Delphi.

Bei mir kommt '0' heraus. :gruebel:

Pardon, es existiert tatsächlich ein Fehler...

alzaimar · Verfasst: Di 14.10.08 18:02

Ich verwende Delphi 6 und da kommt 1 heraus.

_________________
Na denn, dann. Bis dann, denn.

Marc. · Verfasst: Di 14.10.08 18:14

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

Type
  TStaticArray = Array [0..9] Of Integer;

Procedure FooSt(StaticArray : TStaticArray);
Begin
  StaticArray[0] := 1;
End;

Procedure BarSt;
Var
  A : TStaticArray;
Begin
  A[0] := 0;
  FooSt(A);
  Showmessage(IntToStr(A[0])); //  <--- 0
End;

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Type
  TDynArray = Array Of Integer;

Procedure FooDy(DynArray : TDynArray);
Begin
  DynArray[0] := 1;
End;

Procedure BarDy;
Var
  A : TDynArray;
Begin
  SetLength(a,1);
  A[0] := 0;
  FooDy(A);
  Showmessage(IntToStr(A[0])); //  <--- 1
end;

Verwendet wurde Delphi7. Mal sehen, was das CPU-Fenster dazu sagt.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme