stacküberlauf beseitigen

[moppedfahrer]

Moin moin
ich habe gerade die wunderbar rekursiven "Türme von Hanoi" programmiert.
dabei ist mir aufgefallen, dass er bei größeren Türmen ein out-of-memory anzeigt. Ich hab ver sucht mich mit meinem halbwissen damit auseinanderzusetzen, um das ganze effektiver zu machen (also für mehr Türme). Das ist das Ergebnis meiner suche:
Der Stack ist überlastet und man sollte ihn mithilfe von registern entlasten.

Jaaa... warum ist der denn überlastet (nur wegen der parameter bei der rekursion?), und was ist ein register??

[Nils_13]

Ohne Code wird dir wohl keiner helfen können.

[3_of_8]

Ein Register ist eine Speichereinheit im Prozessor. Allerdings ist dein Suchergebnis unbrauchbar in diesem Fall. Das Problem ist höchstwahrscheinlich, dass du eine Endlosrekursion gebastelt hast, also du hast keine korrekte Abbruchbedingung.

Wenn du eine Funktion aufrufst, werden die Parameter und die Rücksprungadresse auf den Stack gepackt, und wenn der Stack dann mal voll ist, gibts nen Stacküberlauf. Das passiert entweder bei ner Endlosrekursion oder bei einer sehr stark verschachtelten Rekursion. (Oder wenn du extrem große statische Arrays anlegst)

[mkinzler]

Es scheint so, ob deine Abbruchbedingung fehlerhaft ist.

[Nils_13]

Ich habe seit über 6 Stunden mit einem Stacküberlauf zu kämpfen und ich kann nur sagen: man kann nur Vermuten, aber rauszufinden woran es liegt, kann Ewigkeiten dauern.

[3_of_8]

Ähm... Nachdenken? So viele Möglichkeiten gibt es ja gar nicht, was da falsch sein kann. Einfach mal die rekursiven Funktionen auf Abbruchbedingungen checken, paar Breakpoints setzen, mit dem Stackview und dem Evaluator drüberbügeln, dann findet man das eigentlich recht schnell.

[Nils_13]

Na gut, der Unterschied ist zu meinem Problem ist eben, dass ich keinen Debugger benutzen kann, da ich mit Öffnen mit.. via Explorer arbeite.

[mkinzler]

Warum nicht in der IDE?

[Nils_13]

1. Habe ich das vergessen.
2. Sind das hier so derbe Fehler (kein Overflow mehr), dass mir der Debugger nicht viel bringen würde.

[mkinzler]

Dann für halt mal einen Schreibtischtest durch

[Nils_13]

Es gibt insgesamt zwei Möglichkeiten:
1. Stackoverflow raus, dafür massig andere Fehler, sogar Buildfehler. :kotz:
2. Keinen Fehler, aber wieder einen Overflow. :kotz:
Overflows treten eben nur auf, wenn ich was aus dem Explorer heraus öffnen will. :kotz: :kotz: :kotz:

Es scheint an einem Timer zu liegen. Wenn man ihn abschaltet, da er bei Öffnen mit oder Doppelklick einen Overflow veranstaltet (bei normalen Start nicht), dann gibt es eine AV (unerklärlich) und einen Buildfehler, da eine Meldung auftaucht, die schon seit längerer Zeit nicht mehr im Code ist (habe sogar nochmal nachgeschaut).

[mkinzler]

Vielleicht solltest du mal deinen eigenen Tip aus #2 beherzigen

[Nils_13]

Ok, dann hier ein kleiner Ausschnitt:

Delphi-Quellcode:

procedure TfrmMain.FormCreate(Sender: TObject);
var Mem        : TMemIniFile;
    Ini        : TIniFile;
    i, j       : Integer;
    FileType   : String;
    ArrayIndex : Integer;
    ffile      : String;
begin
  pause    := False;
  opshown  := False;
  Spectrum := TSpectrum.Create(pbSVis.Width, pbSVis.Height);
  Height   := pbSVis.Height div 2;

  DoubleBuffered := True;

  op := True;

  Ini := TIniFile.Create(ExtractFilePath(Application.ExeName) + 'settings.ini');
  with Ini do
  begin
    frmMain.Top       := ReadInteger('Settings', 'frmMain_Top', 0);
    frmMain.Left      := ReadInteger('Settings', 'frmMain_Left', 0);
    OPM               := ReadBool('Settings', 'OPM', True);
    OPS               := ReadBool('Settings', 'OPS', False);
    eqTb1.Position    := ReadInteger('Settings', 'Eq1', 15);
    eqTb2.Position    := ReadInteger('Settings', 'Eq2', 15);
    eqTb3.Position    := ReadInteger('Settings', 'Eq3', 15);
    eqReverb.Position := ReadInteger('Settings', 'EqReverb', eqReverb.Max);
    llPL              := ReadBool('Settings', 'llPL', False);
    Bumpimage         := ReadString('Settings', 'ImgBumperPic', 'imgbumper.bmp');
    Trans             := ReadInteger('Settings', 'Trans', 255);
    Self.AlphaBlendValue := Trans;
    if Trans = 255 then
      frmMain.AlphaBlend := False
    else
      frmMain.AlphaBlend := True;
    if llPL then
    begin
      if FileExists('pl.dpl') then
        LoadFiles(LoadDPL('pl.dpl', nil));
      if lbList.Count = 0 then
        lbListCount.Caption := 'No files in playlist'
      else
      if lbList.Count = 1 then
        lbListCount.Caption := '1 file in playlist'
      else
      if lbList.Count > 1 then
        lbListCount.Caption := IntToStr(lbList.Count) + ' files in playlist';
      if lbList.Items.Count > 0 then
      begin
        xiScrollV.Max := lbList.Items.Count;
        if lbList.Count > 17 then
        begin
          lbList.Width      := 181;
          xiScrollV.Visible := True
        end else
        begin
          lbList.Width      := 200;
          xiScrollV.Visible := False;
        end;
      end;
    end;
    Free;
  end;

  for i:= 0 to pmTray.Items.Count-1 do
  begin
    pmTray.Items[i].OnDrawItem := pmTrayDrawItem;
    for j := 0 to pmTray.Items[i].Count-1 do
    begin
      pmTray.Items[i].Items[j].OnDrawItem := pmTrayDrawItem;
    end;
  end;

  Mem := TMemIniFile.Create(ExtractFilePath(Application.ExeName) + 'settings.ini');
  try
    iVis := Mem.ReadInteger('Settings', 'vis', 0);
    None1.Checked          := iVis = 0;
    Oscilloscope1.Checked  := iVis = 1;
    SpectrumLines1.Checked := iVis = 2;
    SpectrumSolid1.Checked := iVis = 3;
    ImageBumper.Checked    := iVis = 4;
    X1.Checked             := iVis = 5;

    pa                     := Mem.ReadString('Settings', 'ImgBumperPic', 'imgbumper.JPG');
    xiVolume.Position      := Mem.ReadInteger('Settings', 'volume', 50);
    xiVolumeS.Position     := Mem.ReadInteger('Settings', 'volume', 50);
    rbSeq.Checked          := Mem.ReadBool('Settings', 'sequence', True);
    rbRandom.Checked       := Mem.ReadBool('Settings', 'random', False);
    rbLoop.Checked         := Mem.ReadBool('Settings', 'loop', False);
  finally
    Mem.Free;
  end;

  xiPMainS.Top := xiPMain.Top;

  BASS_Init(1, 44100, 0, Application.Handle, nil);
  BASS_SetConfig(BASS_CONFIG_BUFFER,1000);
  BASS_PluginLoad('basswma.dll', 0);

  fgc            := False;
  v              := False;

  FadeAbort      := False;
  aFade          := True;
  bFade          := False;
  PlayWCrossfade := False;
  Fading         := False;
  FlagScroll     := True;
  fNext          := False;
  lbNOTOK        := False;

  DrawSkin;

  Ini := TIniFile.Create(ExtractFilePath(Application.ExeName) + 'settings.ini');
  with Ini do
  begin
    M                 := ReadBool('Settings', 'M', True);
    if M then
      xiMain.ColorGrad := clGreen
    else
      xiMain.ColorGrad := clRed;

    EQ                := ReadBool('Settings', 'EQ', True);
    if EQ then
      xiEQ.ColorGrad := clGreen
    else
      xiEQ.ColorGrad := clRed;

    PL                := ReadBool('Settings', 'PL', True);
    if PL then
      xiPL.ColorGrad := clGreen
    else
      xiPL.ColorGrad := clRed;

    cVS;

    Free;
  end;

  xiBg.Height := frmMain.Height;

  if (ParamCount > 0) and (FileExists(ParamStr(1))) then
  begin
    ffile := ParamStr(1);

    FileType  := LowerCase(Trim(ExtractFileExt(ffile)));
    for ArrayIndex := 0 to High(FileExt) do
      if FileExt[ArrayIndex] = FileType then
        Break;
    if FileType <> '' then
    begin
      case ArrayIndex of
        // Audio/Video
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10:
        begin
          AddSingleFile(ffile);
          last := lbList.Items.Count;
          xiPlayClick(Sender);
        end;
        // Playlist
        11: LoadFiles(LoadM3U(ffile));
        12: LoadFiles(LoadASX(ffile));
        13: LoadFiles(LoadDPL(ffile, nil));
      end;
      xiScrollV.Max := lbList.Items.Count;
      if lbList.Count > 17 then
      begin
        lbList.Width      := 181;
        xiScrollV.Visible := True
      end else
      begin
        lbList.Width      := 200;
        xiScrollV.Visible := False;
      end;
      if lbList.Count = 0 then
        lbListCount.Caption := 'No files in playlist'
      else
        if lbList.Count = 1 then
          lbListCount.Caption := '1 file in playlist'
        else
          if lbList.Count > 1 then
            lbListCount.Caption := IntToStr(lbList.Count) + ' files in playlist';
    end;
  end;
end;

procedure TfrmMain.DrawSkin;
var
  Skin : TIniFile;  //sRT
  s : String;
  i, j : Integer;
  Colors : Array [1..49] of TColor;
  MainC  : TColor;
  EQC    : TColor;
  PLC    : TColor;
  sLT    : String; // Lauftext
begin
  with TIniFile.Create(ExtractFilePath(ParamStr(0)) + 'settings.ini') do
  begin
    if DirectoryExists(ExtractFilePath(Application.ExeName) + 'skins\') then
      s := ExtractFilePath(Application.ExeName) + 'skins\' + ReadString('Settings', 'Skin', 'blue.dpsf')
    else
      Application.Terminate;
    Free;
  end;
  MainC := xiMain.ColorGrad;
  EQC   := xiEQ.ColorGrad;
  PLC   := xiPL.ColorGrad;
  sLT   := lLauftext.Text;

  if FileExists(s) then
  begin
    Skin := TIniFile.Create(s);
    try
      ...
      if FileExists(Skin.ReadString('Runningtext', 'File', ExtractFilePath(Application.ExeName)+'skins\rt_blue.bmp')) then
      begin
        lLauftext.Skin.LoadFromFile(Skin.ReadString('Runningtext', 'File', 'skins\rt_blue.bmp'));
        lLauftext.Text := 'Dark Player II                                                           ';
        lLauftext.Color := StringToColor(Skin.ReadString('Backgrnd', 'Grad', 'clSkyBlue'));
        lLauftextS.Skin.LoadFromFile(Skin.ReadString('Runningtext', 'File', 'skins\rt_blue.bmp'));
        lLauftextS.Text := 'Dark Player II                                                           ';
        lLauftextS.Color := StringToColor(Skin.ReadString('Backgrnd', 'Grad', 'clSkyBlue'));
        lPLL.Skin.LoadFromFile(Skin.ReadString('Runningtext', 'File', 'skins\rt_blue.bmp'));
        lPLL.Text  := '                               ';
        lPLL.Color := StringToColor(Skin.ReadString('Backgrnd', 'Grad', 'clSkyBlue'));
        lPLL2.Skin.LoadFromFile(Skin.ReadString('Runningtext', 'File', 'skins\rt_blue.bmp'));
        lPLL2.Text := '                               ';
        lPLL2.Color := StringToColor(Skin.ReadString('Backgrnd', 'Grad', 'clSkyBlue'));
      end else
      begin
        MsgBox('Runningtexts not found!');
        Application.Terminate;
      end;
      vC  := StringToColor(Skin.ReadString('Vis', 'Color', 'clBlack'));
      vF  := StringToColor(Skin.ReadString('Vis', 'Font', 'clBlack'));

      pmTrayFont     := StringToColor(Skin.ReadString('Tray', 'Font', 'clRed'));
      pmTrayBg       := StringToColor(Skin.ReadString('Tray', 'BgColor', '$00FF0301'));
      pmTrayOver     := StringToColor(Skin.ReadString('Tray', 'OverColor', 'clBlack'));
      pmTrayOverFont := StringToColor(Skin.ReadString('Tray', 'OverFont', '$00000000'));

      for i:= 0 to pmSVis.Items.Count-1 do
      begin
        pmSVis.Items[i].OnDrawItem := pmTrayDrawItem;
        for j := 0 to pmSVis.Items[i].Count-1 do
        begin
          pmSVis.Items[i].Items[j].OnDrawItem := pmTrayDrawItem;
        end;
      end;
      xiMain.ColorGrad  := MainC;
      xiEQ.ColorGrad    := EQC;
      xiPL.ColorGrad    := PLC;
      lLauftext.Text    := sLT;
      with Spectrum do
      begin
        PenColor  := StringToColor(Skin.ReadString('Vis', 'Color', 'clBlack'));
        PeakColor := StringToColor(Skin.ReadString('Vis', 'Peak', 'clBlack'));
      end;
    finally
      Skin.Free;
    end;
    tColors.Enabled := True;
  end else
  begin
    MsgBox('Skinfile not found!');
    Exit;
  end;
  Application.HintColor := xiBg.ColorFace;
  Screen.HintFont.Color := xiCaptionBar.Font.Color;
end;

procedure TfrmMain.tListTimer(Sender: TObject);
begin
  if aFade then
  begin
    if tb1.Position = tb1.Max - frmSetting.FadeTime then
    begin
      aFade := False;
      if frmSetting.Crossfade then
        Crossfade;
    end;
  end;
  if not tb1.Max - tb1.Position = tb1.Max then
    ZufallsGen;
  if tb1.Position = tb1.Max then
  begin
    tList.Enabled         := False;
    tb1.Position          := 0;
    tb1S.Position         := 0;
    ZufallsGen;
    tList.Enabled         := True;
  end;
  if xiPMainS.Visible then
  begin
    lLauftextS.Text   := lLauftext.Text;
    lLauftextS.Active := True;
  end;
end;

[moppedfahrer]

Ok also das hier is wohl das entscheidende, denke ich :lol: :

Delphi-Quellcode:

procedure speichern(woher,wohin:integer);
begin
setlength(rec,length(rec)+1);
rec[high(rec)].X:=woher;
rec[high(rec)].Y:=wohin;
if form1.zeit.checked=false then
 form1.listbox1.items.Add('  '+inttostr(rec[high(rec)].X)+' --> '+inttostr(rec[high(rec)].Y));
end;
                 
procedure hanoi(hoch,woher,wohin:integer);
begin
if hoch=1 then speichern(woher,wohin)
 else begin
       hanoi(hoch-1,woher,woher xor wohin);
       speichern(woher,wohin);
       hanoi(hoch-1,wohin xor woher,wohin)
      end;
end;

[mkinzler]

Delphi-Quellcode:

if hoch<=1 then speichern(woher,wohin)

Weil die Funktion ja 2 Mal sich selbst aufruft und dann kann es Passieren das der Wert 1 übersprungen wird
@Nils: Hast du mal versucht die Funktionalität mal zum testen einzuschränken?

[Khabarakh]

Zitat:

Zitat von mkinzler

Delphi-Quellcode:

if hoch<=1 then speichern(woher,wohin)

Weil die Funktion ja 2 Mal sich selbst aufruft und dann kann es Passieren das der Wert 1 übersprungen wird

Wie soll das denn bitte geschehen :shock: ?

[moppedfahrer]

neee funzt immer noch net :gruebel:
aber das macht ja bis zu ner höhe von 27 auch keine probleme.
dann hängt das wohl mit dem zu-sehr-Verzweigten zusammen, oder???
Aber kann man das nicht irgendwie umgehen?
Ich hab schon programmiert, dass er schritte, die er schon kennt, nicht nochmal rekursiv berechnet. Das macht er dann zwar bis 28, is aber tierisch lahm :(.

[mkinzler]

Zitat:

Zitat von Khabarakh

Zitat:

Zitat von mkinzler

Delphi-Quellcode:

if hoch<=1 then speichern(woher,wohin)

Weil die Funktion ja 2 Mal sich selbst aufruft und dann kann es Passieren das der Wert 1 übersprungen wird

Wie soll das denn bitte geschehen :shock: ?

Zitat:

Delphi-Quellcode:

    hanoi(hoch-1,woher,woher xor wohin); // das 1. mal
       speichern(woher,wohin);
       hanoi(hoch-1,wohin xor woher,wohin) // das 2. Mal

[moppedfahrer]

würd das helfen, wenn ich auf der festplatte und nich im arbeitsspeicher speicher ???
is dieser stack überhaupt im arbeitsspeicher ???

[Khabarakh]

@mkinzler: Du weißt, was der Unterschied zwischen Call by value und Call by reference ist?

@moppedfahrer: 2^28 Teilrekursionen sind aber auch etwas extrem ;) . Solltest du es trotzdem für sinnvoll erachten :stupid: , könntest du entweder den Stack in den Projektoptionen vergrößern oder auf die iterative Variante umsteigen. Und ja, der Stack liegt im Arbeitsspeicher, sonst wäre dein Programm noch langsamer als die Mönche.

[moppedfahrer]

Gut DANKE
langsamer als ein mönch möchte ich dann doch nicht sein ^^. :mrgreen: :mrgreen: :mrgreen:
Danke für die schnellen antworten!!!
:dp: