Entwickler-Ecke :: Thema anzeigen

der organist - Mi 16.07.08 20:39
Titel: 'stack overflow' ??

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

Ralf107 - Di 14.10.08 11:47

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?

Ralf107 - Di 14.10.08 12:16

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:

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

Ralf107 - Di 14.10.08 13:20

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

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?

Ralf107 - Di 14.10.08 15:12

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

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

Beispiel:

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 - 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.

delfiphan - Di 14.10.08 17:42

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

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 - Di 14.10.08 17:49

Probier mal das hier:

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.

Marc. - Di 14.10.08 18:00

alzaimar hat folgendes geschrieben :

Probier mal das hier:

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...

Marc. - Di 14.10.08 18:14

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;

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. ;)

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!