AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Delphi Fehler beim Auflösen und Freigeben eines dynamischen Tree's

Fehler beim Auflösen und Freigeben eines dynamischen Tree's

Ein Thema von noob2k9 · begonnen am 10. Mär 2012 · letzter Beitrag vom 11. Mär 2012
Antwort Antwort
noob2k9

Registriert seit: 1. Aug 2008
13 Beiträge
 
Delphi XE2 Starter
 
#1

Fehler beim Auflösen und Freigeben eines dynamischen Tree's

  Alt 10. Mär 2012, 15:02
Hi DP-User,

ich habe einen Fehler identifiziert der mir nun schon einige Stunden Kopfzerbrechen bereitet.

Während der Laufzeit meines Programmes führe ich eine vollständige Enumeration (mit diversen Abbruchbedingungen) durch und generiere so in einem rekursiven Algorithmus einen Baum dessen Blätter immer auf die übergeordneten Äste/Elemente (Parents) zeigen.
Die Verknüpfung wird nur in eine Richtung "bottom-up" realisiert.

Die Blätter werden in dem Array variations gespeichert, so dass jede gefundene Lösung rekonstruiert werden kann in dem von dem Blatt jedes Parent zurückverfolgt wird bis man bei dem Root-Element ankommt.
Das Root-Element besitzt als Parent einen Pointer auf nil um so dass Ende zu markieren.

Nun stehe ich vor folgendem Problem: Wenn ich versuche den Speicher der durch den entstandenen Baum belegt wird freizugeben erhalte ich eine Zugriffsverletzung beim Schreiben auf den Speicher.
Ich habe die Ursache bereits soweit zurückverfolgt dass ich sagen kann wo der Fehler auftritt, nämlich sobald der Ast bereits "abgesägt" wurde - also ein anderes Child (Blatt) einen ähnlichen Pfad hatte und durch die while ... do - Schleife bis zum Parent/Root aufgelöst wurde.

Ergo: Das Record wurde bereits aufgelöst und der Zeiger zeigt nun irgendwo ins Nirvana.

Ich hoffe ich konnte das Problem ausreichend beschreiben.
Nun zur eigentlichen Frage: Gibt es eine Möglichkeit wie ich dies verhindern kann oder gar eine bessere Möglichkeit den Tree aufzulösen?

Delphi-Quellcode:
type
  T_Container_2D = record
    parent: Pointer;
    x1: Integer;
    y1: Integer;
    x2: Integer;
    y2: Integer;
  end;

type
  T_Variations_2D = Array of Pointer;

procedure Clear();
var
  i, l: Integer;
  now, next: P_Container_2D;
begin
  // Init
  i := 0;
  l := Length(variations) - 1;

  for i := l downto 0 do begin
    now := variations[i];
    while now <> nil do begin
      if now^.parent <> nil then begin
        next := now^.parent;
        FreeMemory(now);
        now := nil;
        now := next;
      end
      else begin
        now := nil;
      end;
    end;
  end;

  SetLength(variations, 0);
end;

Geändert von noob2k9 (10. Mär 2012 um 17:20 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Bummi
Bummi

Registriert seit: 15. Jun 2010
Ort: Augsburg Bayern Süddeutschland
3.470 Beiträge
 
Delphi XE3 Enterprise
 
#2

AW: Fehler beim Auflösen und Freigeben eines dynamsichen Tree's

  Alt 10. Mär 2012, 16:32
Delphi-Quellcode:
procedure Clear();
var
  i, l: Integer;
  now, next: P_Container_2D;
begin
  // Init
  i := 0;
  l := Length(variations) - 1;

  for i := l downto 0 do FreeMemory(variations[i]);
  SetLength(variations, 0);
end;
Thomas Wassermann H₂♂
Das Problem steckt meistens zwischen den Ohren
DRY DRY KISS
H₂ (wenn bei meinen Snipplets nichts anderes angegeben ist Lizenz: WTFPL)
  Mit Zitat antworten Zitat
noob2k9

Registriert seit: 1. Aug 2008
13 Beiträge
 
Delphi XE2 Starter
 
#3

AW: Fehler beim Auflösen und Freigeben eines dynamsichen Tree's

  Alt 10. Mär 2012, 16:41
Auf diese Weise werden aber (wenn ich jetzt keinen groben Schnitzer habe) nicht die Parents mit aufgelöst? In dem Array variations werden wie bereits erwähnt nur die Childs der letzten Ebene gespeichert.

Edit: Im Anhang eine fixe Visualisierung des Trees
Miniaturansicht angehängter Grafiken
visu.png  

Geändert von noob2k9 (10. Mär 2012 um 16:49 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Bummi
Bummi

Registriert seit: 15. Jun 2010
Ort: Augsburg Bayern Süddeutschland
3.470 Beiträge
 
Delphi XE3 Enterprise
 
#4

AW: Fehler beim Auflösen und Freigeben eines dynamischen Tree's

  Alt 10. Mär 2012, 22:57
sorry, hatte ich falsch verstanden.
Dann in Deinem "Löschlauf" nicht die Parents löschen, sondern in einer weiteren Liste Unique sammeln. Aus dieser Liste löschen.
Thomas Wassermann H₂♂
Das Problem steckt meistens zwischen den Ohren
DRY DRY KISS
H₂ (wenn bei meinen Snipplets nichts anderes angegeben ist Lizenz: WTFPL)
  Mit Zitat antworten Zitat
noob2k9

Registriert seit: 1. Aug 2008
13 Beiträge
 
Delphi XE2 Starter
 
#5

AW: Fehler beim Auflösen und Freigeben eines dynamischen Tree's

  Alt 11. Mär 2012, 00:10
So simpel dass ich es selbst übersehen habe - werde mich mal an die Umsetzung machen und berichten.
  Mit Zitat antworten Zitat
noob2k9

Registriert seit: 1. Aug 2008
13 Beiträge
 
Delphi XE2 Starter
 
#6

AW: Fehler beim Auflösen und Freigeben eines dynamischen Tree's

  Alt 11. Mär 2012, 00:42
Ok, der Algorithmus funktioniert soweit dennoch stoße ich vor das nächste Problem: Die einzelnen Äste können unterschiedliche Längen aufweissen so dass es dennoch passieren kann (und auch passiert) dass ein Pointer bereits früher zurückgesetzt wird und anschließend in einem längeren Ast erneut versucht wird zurückzusetzen - was natürlich wieder zu einem Speicher-Leck führt.

Ich glaube ich komme nicht drum herum erst alle Äste komplett zu durchlaufen und ein Unique Array zu erzeugen und im Anschluss daran alle Elemente zu löschen. Dies kann im Worst-Case (~4 Mio. Leafs mit einer Tiefe bis zu ~25) allerdings recht aufwändig werden.
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#7

AW: Fehler beim Auflösen und Freigeben eines dynamischen Tree's

  Alt 11. Mär 2012, 08:13
Oder mit Referenzzählung.

Referenzzählung = Beim Anlegen und darauf verweisen wird der Zähler erhöht. Beim Entfernen eines 'Childs' wird der Zähler des Parents erniedrigt. Wenn der Zähler bei 0 ist, ist der Knoten nicht mehr in Verwendung => Löschen => Rekursiver Aufruf.

Oder gleich mit Interfaces arbeiten, die haben das nämlich eingebaut.

Bei 4 Mio Knoten würde ich allerdings alle Knoten von Anfang an in einer Liste verwalten (TObjectList). Im Konstruktor und Destruktor eines Knotens baust Du einfach eine einzige Zeile ein:
Delphi-Quellcode:
Constructor TMyNode.Create;
Begin
  ...
  ListOfNodes.Add(Self);
End;

Destructor TMyNode.Destroy;
Begin
  ...
  ListOfNodes.Remove(Self);
End;

Class Procedure TMyNode.KillAllNodes;
Begin
  ListOfNodes.Clear;
End;

initialization
  ListOfNodes := TObjectList.Create(True);
finalization
  KillAllNodes; // Hier eigentlich überflüssig, aber anschaulich.
  ListOfNodes.Free
End.
Leider ist die TObjectList nicht sonderlich schnell, sodaß eine Dictionary hier sicherlich besser geeignet wäre.
  Mit Zitat antworten Zitat
Benutzerbild von Bummi
Bummi

Registriert seit: 15. Jun 2010
Ort: Augsburg Bayern Süddeutschland
3.470 Beiträge
 
Delphi XE3 Enterprise
 
#8

AW: Fehler beim Auflösen und Freigeben eines dynamischen Tree's

  Alt 11. Mär 2012, 08:33
Wo kommen denn die Daten her, bzw. wie navigierst Du von der Wurzel durch den Baum?
Kannst Du nicht beim Aufbauen bereits eine Liste aller Knoten anlegen.
Thomas Wassermann H₂♂
Das Problem steckt meistens zwischen den Ohren
DRY DRY KISS
H₂ (wenn bei meinen Snipplets nichts anderes angegeben ist Lizenz: WTFPL)
  Mit Zitat antworten Zitat
noob2k9

Registriert seit: 1. Aug 2008
13 Beiträge
 
Delphi XE2 Starter
 
#9

AW: Fehler beim Auflösen und Freigeben eines dynamischen Tree's

  Alt 11. Mär 2012, 17:12
Zitat:
Wo kommen denn die Daten her, bzw. wie navigierst Du von der Wurzel durch den Baum?
Erst einmal noch ein paar mehr Infos: Der Algorithmus soll die Anordnung von (kleineren, gleichbleibenden) Rechtecken in einer größeren Fläche vornehmen. Dabei wird durch Rotation und Translation versucht rekursiv die Lösung zu verbessern. Wird in einer Rekursion kein besseres Ergebnis als dass bis dahin erreichte Maximum erzielt bricht der Algorithmus die Berechnung an dieser Verzweigung natürlich ab und verwirft bis dahin gespeicherte Zweige. Das funktioniert soweit auch ganz gut.

Zitat:
Kannst Du nicht beim Aufbauen bereits eine Liste aller Knoten anlegen.
Das speichern aller Knoten in einem extra Array habe ich auch schon versucht - doch dann stieg der Speicherverbrauch beim letzten Versuch exhorbitant an. Ich habe den Speicherverbrauch seit dem aber weiter senken können indem ich während des Rechenlaufs bereits beginne Speicher freizugeben wenn die Leafs verworfen werden. - Also werde ich diesen Ansatz evtl. nochmals testen.

Zitat:
Leider ist die TObjectList nicht sonderlich schnell, sodaß eine Dictionary hier sicherlich besser geeignet wäre.
Listen möchte ich nicht nutzen da diese von der Performance her nicht so der Brüller sind - es werden unnötige Klassen / Objekte erzeugt die Speicherplatz und Rechenzeit kosten. So gesehen ist der Baum ja auch eine auf das Nötigste reduzierte Liste nur eben mit einer unidirektionalen (und manuell festgelegten) Verknüpfung der Knoten.

Aktuell bin ich wieder auf diesen Ansatz zurück gefallen:
Fehler entstehen bei FreeMem(now); obwohl now auf eine gültige Adresse mit gültigem Datensatz verweisst. (Details weiter unten)
Delphi-Quellcode:
procedure Clear();
var
  i, j, l, c: Integer;
  now, last: P_Container_2D;
  hProcess: THandle;
begin
  // Init
  i := 0;
  l := Length(variations);

  QuickSortPointers(variations, 0, Length(variations) - 1);

  i := 0;
  last := nil;
  if l > 0 then begin
    while i < l do begin
      now := variations[i];
      if (now <> last) then begin
        if Assigned(now) then begin
          last := now;
          FreeMem(now);
        end;
        now := nil;
      end;
      Inc(i);
    end;
  end;

  SetLength(variations, 0);
  variations := nil;

  hProcess := OpenProcess(PROCESS_SET_QUOTA, false, GetCurrentProcessId);
  try
    SetProcessWorkingSetSize(hProcess, $FFFFFFFF, $FFFFFFFF);
  finally
    CloseHandle(hProcess);
  end;
end;
Programmablauf:

1. Vorher:
Code:
Name   Value
now   $2DDC700
parent   $2DDC6E8
x1   30
y1   50
x2   80
y2   70
2. Aufruf von FreeMem(now);

3. Fehlermeldung und Exception: Exception class EInvalidPointer with message 'Invalid pointer operation'.

4. Nachher:
Code:
Name      Value
i      48547632
l      4213291
now      nil
   parent   Inaccessible value
   x1   Inaccessible value
   y1   Inaccessible value
   x2   Inaccessible value
   y2   Inaccessible value
last      $4E1B80
   parent   $FC6163E8
   x1   -1064582145
   y1   -1957210541
   x2   -1946514471
   y2   -1949594640
Edit: Anmerkung: SetProcessWorkingSetSize() nutze ich um den Speicher wieder freizugeben. FastMM4 mit FullDebug-Option berichtet mir keine Speicherlecks.

Edit2: Soeben noch entdeckt das nach dem Aufruf von FreeMem() (bzw. mittlerweile durch Dispose() ersetzt) die ganzen lokalen Variablen der Prozedur verdreht sind ... irgendwo muss ich da einen mächtigen Denkfehler drin haben. i und l nehmen utopische Werte an, und der Pointer auf last ändert sich auch wie durch magische Hand.

Geändert von noob2k9 (11. Mär 2012 um 17:52 Uhr)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#10

AW: Fehler beim Auflösen und Freigeben eines dynamischen Tree's

  Alt 11. Mär 2012, 18:13
Das speichern aller Knoten in einem extra Array habe ich auch schon versucht - doch dann stieg der Speicherverbrauch beim letzten Versuch exhorbitant an.
dann hast Du etwas falsch gemacht. Benötigt werden pro Objekt 4 Bytes.
Listen möchte ich nicht nutzen da diese von der Performance her nicht so der Brüller sind - es werden unnötige Klassen / Objekte...
Falsch.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 09:58 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf