Problem mit der Sortierung im VST

[Assertor]

Hi DPler,

ich stehe gerade etwas auf dem Schlauch:

Hintergrundinfo:
Ich zeige über ein VST Felder einer Datenbank an. Nun habe ich mich per Profiler auf die Suche nach Performance Problemen gemacht, nachdem mir auffiel das ab ca. 1,5 bis 2,5 Mio Datensätzen das ganze alle paar Sekunden langsam wird. Langsam bedeutet hier: Aussetzer wenn man z.B. den Scrollbalken schnell bewegt - genau in der Zeit, wo das Tree seine Anzahl prüft und verändert.

Die Ursachen waren schnell ausgemacht: Im OnBeforeItemErase für die Colorierung statt Index den AbsoluteIndex verwendet (kniffliger Performance-Killer) und toAutoSort war true. Die dahinterliegende Datenbank erhält alle paar Sekunden neue Einträge, die auch angezeigt werden sollen. Bisher wird in einem Timer geprüft, ob die VST.RootNodeCount <> DB.RecordCount ist und ggf. der RootNodeCount erhöht. Ein Trigger von Seiten der Datenbank (Push) ist leider nicht möglich, da die Einträge auch extern erfasst werden und es nur eine embedded DB (SQLite3) genutzt wird.

Alles technisch kein Problem - und rasend schnell auch bei mehr als 2.5 Mio Einträge.

Frage:
Wie kann ich eine DB-gerechte Sortierung umsetzen, die kein Performance-Killer ist?

Für die Sortierung wird nur das Feld bzw. die Spalte Index zugelassen, da hier auch der PK liegt und das OnCompare schnell geht. Wenn jetzt aber per RootNodeCount oder AddChild() neue Einträge dazukommen wird mit/ohne .BeginUpdate/.EndUpdate die ganze Tree neusortiert.

Wenn ich die Daten z.B. per

Delphi-Quellcode:

vstMainGrid.Sort(vstMainGrid.AddChild(vstMainGrid.RootNode),
  vstMainGrid.Header.SortColumn, vstMainGrid.Header.SortDirection, True);

anfüge, werden diese trotzdem an der falschen Position eingefügt (z.B. großer Index > kleiner Index, neue große Index dann "dahinter").

Ich weiß, viele Lösungen verbieten bei dynamischen Trees und DB-konnektierung von sich aus die Sortierung (devexpress u.a.). Trotzdem finde ich eine Basissortierung (1>n, n>1) schöner.

Ideen?

Gruß Assertor

[generic]

Sort wird nur aufgerufen, wenn du es aufrufst. Bei hinzufügen von Nodes wird es nicht aufgerufen.

[Assertor]

Hi,

Zitat:

Zitat von generic

Sort wird nur aufgerufen, wenn du es aufrufst. Bei hinzufügen von Nodes wird es nicht aufgerufen.

Natürlich, laß es mich mal umformulieren:

- Wenn toAutoSort verwendet wird, stimmt die Sortierung. Wenn jetzt per AddChild() oder Änderung der RootNodeCount die Anzahl geändert wird, wird durch .EndUpdate eine vollständige Neusortierung (müßte intern ein Mergesort sein) ausgelöst, der sehr lahm ist bei ~ 2 Mio Einträgen
- Mit manuellem Sort für das Einfügen eines einzelnen Childs per AddChild (siehe Sourcebeispiel oben) stimmt die Position des angefügten Eintrags trotz .Sort() nicht

Gruß Assertor

[generic]

2) verwundert mich etwas. Vieleicht ein Fehler in der onCompare Methode?


ggf. selbst die Position suchen und an der richtigen Stellen den Knoten einbinden.
Dann brauchst du überhaupt keine Sortierung vom VST.

[Assertor]

Hi generic,

Danke für Deine Hilfe!

Zitat:

Zitat von generic

2) verwundert mich etwas. Vieleicht ein Fehler in der onCompare Methode?

ggf. selbst die Position suchen und an der richtigen Stellen den Knoten einbinden.
Dann brauchst du überhaupt keine Sortierung vom VST.

Probiere ich seit heute Abend schon. Also toAutoSort aus, manuelle Sortieren per OnHeaderClick und zusätzlich automatische Positionierung neuer Nodes per .InsertNode.

Das geht zwar, aber die Performance ist nur um den Faktor 5 besser als AutoSort. Ohne .InsertNode bzw. ohne Sortierung kann ich 10 Nodes per .AddChild in 0-16ms hinzufügen, das gleiche mit .InsertNode an amInsertBefore dauert ~300ms bei 1 Mio Nodes, ~ 750ms bei 2.5 Mio Nodes bis zu 3.3 Sekunden bei 5 Mio Nodes. Das ganze ist innerhalb eines .BeginUpdate/.EndUpdate Blocks.

Mit AutoSort dauert das bei Änderung des RootNodeCounts ca. 3.5 Sekunden bei ~ 10 neuen Nodes mit 2.5 Mio Einträgen.

Das würde für automatische UI Aktualisierung ausscheiden, da diese unbedienbar würde (Timer fügt neue DB Einträge alle 2,5-5 Sekunden hinzu). Wie gesagt, ich teste jetzt mit einem sonst leeren Form nur die VST-Funktion - da ist nichts mehr mit DB etc.

Was ich bräuchte, wär ein AddChild welches bei gleicher Performance die optische Position berücksichtigt (ganz oben oder ganz unten hinzufügen). InsertNode ist dafür zu langsam - und vor allen Dingen braucht mehr Zeit je größer der VST.RootNodeCount ist.

Gruß Assertor

[generic]

Ich stell mir die Frage wer soll soviele Eintrag lesen?
Ein Mensch ist für die Menge eher ungeeignet.

Vielleicht solltest du allgemein über die Darstellung nachdenken.
Sprich: zusammenfassen oder den Benutzer die Wahl lassen, was er sehen möchte.
Selektionsmöglichkeiten und/oder Grafiken, wenn es um Messwerte geht.

Niemand schaut sich 2 Mio Daten auf einmal an. Alleine das Durchscrollen durch die Daten würde länger als ein Arbeitstag dauern.

Das mit der Sortierung ist trotzdem merkwürdig. Ich habe im größten VST ca. 500k an Zeilen drin, diese Sortieren ohne Probleme mit manuellen Sort.

[Assertor]

Hi,

Zitat:

Zitat von generic

Das mit der Sortierung ist trotzdem merkwürdig. Ich habe im größten VST ca. 500k an Zeilen drin, diese Sortieren ohne Probleme mit manuellen Sort.

Ja, in der Größenordnung wird das Problem bei heutigen Rechnern absolut nicht sichtbar. Das entspricht auch meinen Tests.

Zitat:

Zitat von generic

Ich stell mir die Frage wer soll soviele Eintrag lesen?
Ein Mensch ist für die Menge eher ungeeignet.

Vielleicht solltest du allgemein über die Darstellung nachdenken.
Sprich: zusammenfassen oder den Benutzer die Wahl lassen, was er sehen möchte.
Selektionsmöglichkeiten und/oder Grafiken, wenn es um Messwerte geht.

Niemand schaut sich 2 Mio Daten auf einmal an. Alleine das Durchscrollen durch die Daten würde länger als ein Arbeitstag dauern.

Das ist natürlich richtig. Aber: Ich denke mir, es darf trotzdem nicht bedeuten, daß das Programm langsam bis hin zur Unbedienbarkeit wird.

Ich will praktisch nur eine Sortierung Aufsteigend/Absteigend. Es geht hier um Bestellungen, die Tree zeigt nur ID/Datum und Bezeichnung. Der Rest wird dann aus einer DB gelesen sobald der Benutzer etwas auswählt. Bei hochgerechneten Durchschnittswerten kommt die Anzahl maximal hin...

Ich überlege auch schon die Daten zu gruppieren, die Frage ist nur, wo man sinnvoll ansetzt. Nach Jahren oder der Anzahl (können ja trotzdem zu viele pro Jahr sein). Oder alternativ mit einem Node mit "... (Archiv)" wäre eine Idee.

Es wundert mich nur, daß es vorwärts (unsortiert) auch bei 5 Mio Datensätzen wenige Millisekunden dauert, bis das Tree aktualisiert... Ich will ja lediglich eine Bottom-Top Sortierung.

Gruß Assertor

[Assertor]

Hi,

mal als Nachtrag für die, die es interessiert: Ich habe das "Problem" gelöst. Da war einfach eine viel zu komplizierte Logik im ursprünglichen Ansatz.

Anforderung
Die Anforderung ist eine Sortierung entweder von 1..n oder n..1, die der Benutzer durch Klick auf den Columnheader der ersten Spalte auswählen kann. Die interne Sortierung im VST mit Hilfe von OnCompareNode ist sehr schnell, aber erreicht bei großen Datenmengen schnell ein Performancelimit. Große Datenmengen sind hier DB-gestützte Trees mit 2,5 - 5 Mio Nodes.

Lösung
Da die Werte alle linear sind, braucht man kein Quicksort o.ä., sondern nur eine Neuzuweisung der vorhandenen Zeilennummern. Es wird also statt zu sortieren einfach die hinterlegte Indexnummer geändert bzw. umgekehrt.

Das einzige Problem war die Benutzerauswahl, also die selektierten Nodes. Hier hatte ich verschiedene Ansätze mit Hilfe von Integer-Arrays und Nodelisten getestet. Es stellte sich jedoch heraus, daß diese viel zu langsam sind (wegen des nötigen Vergleichs ob ein Element im Array ist).

Dieses zweite Problem konnte ich lösen, in dem ich die Nodeauswahl mit Hilfe einer Swap Funktion umkehre (also erstes und letzes Element, dann 2. und vorletztes, ... bis zur Hälfte des Trees). Natürlich nur, falls der Auswahlstatus vsSelected bei den Nodes unterschiedlich ist.

Das Hinzufügen der Nodes erfolgt nun im Betrieb per RootNodeCount wenn die Sortierung sdAscending ist und per InsertNode mit amInsertBefore, wenn ein Node vor dem ersten Eintrag benötigt wird (Sortierung sdDescending). Damit die Indexnummer wieder stimmt, wird der Node hier Reinitialisiert und der korrekte Wert zugewiesen.

Zeiten
Ursprüngliche Zeiten:
~3500ms - Sortierung von 2,5 Mio Nodes mit dem VST AutoSort / OnCompareNode
~3500ms - Hinzufügen von 10 Nodes zu dem 2,5 Mio Nodes - Tree (bei genutztem VST AutoSort)

Meine Zeiten:
~94ms - "Sortierung" von 2,5 Mio Nodes (Selection wird dabei auch angepasst und bleibt erhalten)
~0-100ms - Hinzufügen von 10 Nodes zu den 2,5 Mio Nodes (korrekte Nummerierung, davor oder dahinter eingefügt)

Das ganze auf einem langsamen T7xxx Laptop getestet. Selbst bei 25 Mio Nodes sind die Zeiten ok (~ 1,5 Sek).

Also, geht doch :)

Gruß Assertor

[generic]

:thumb:

[Assertor]

Hi generic,

Zitat:

Zitat von generic

:thumb:

Danke!

:hello: und natürlich :dp:

Gruß Assertor

[richard_boderich]

Hallo Assertor,

"(korrekte Nummerierung, davor oder dahinter eingefügt)" bedeutet was genau?

Ich gehe mal davon aus das du damit den Node index meinst? Funktioniert das auch wenn ich
gerade im Baum sagen wir mal nach Strings oder nach einen Datum korrekt einsortieren muss?

Wenn ja, könnte man dies ins offfizielle VST zu integrieren? :)

[Assertor]

Hi Richard,

Zitat:

Zitat von richard_boderich

"(korrekte Nummerierung, davor oder dahinter eingefügt)" bedeutet was genau?

Ich gehe mal davon aus das du damit den Node index meinst?

Richtig, damit meine ich den NodeIndex.

Zitat:

Zitat von richard_boderich

Funktioniert das auch wenn ich gerade im Baum sagen wir mal nach Strings oder nach einen Datum korrekt einsortieren muss?

Wenn ja, könnte man dies ins offfizielle VST zu integrieren? :)

Leider nein, wenn die Daten nicht vorhersagbar sind - also wie in Deinem Beispiel verschiedene Datumsangaben oder beliebige Strings - geht es nicht.

Prinzipiell sind alle nötigen Funktionen für das Einfügen schon im VST. Es handelt sich bei meiner Nutzung um einen Sonderfall, der hierbei sehr viel Zeit spart.

Als Anregung mal mein Code (Auszugsweise).

Gruß Assertor

Delphi-Quellcode:

//
// die üblichen Verdächtigen des VST...
//

procedure TfrmMain.vstTestGridGetNodeDataSize(Sender: TBaseVirtualTree;
  var NodeDataSize: Integer);
begin
  inherited;
  TVirtualStringTree(Sender).NodeDataSize := SizeOf(TGridNodeData);
end;

procedure TfrmMain.vstTestGridInitNode(Sender: TBaseVirtualTree; ParentNode,
  Node: PVirtualNode; var InitialStates: TVirtualNodeInitStates);
var
  NodeData: PGridNodeData;
begin
  inherited;
  NodeData := Sender.GetNodeData(Node);
  if Assigned(NodeData) then
    NodeData^ := Node.Index + 1; // Anzeige startet bei 1, nicht 0
end;

procedure TfrmMain.vstTestGridGetText(Sender: TBaseVirtualTree;
  Node: PVirtualNode; Column: TColumnIndex; TextType: TVSTTextType;
  var CellText: String);
var
  NodeData: PGridNodeData;
  DatabaseRecord: PDatabaseRecord;

  function GetDBRecord: Boolean;
  begin
    // hier wird der Eintrag aus der Datenbank geholt
   ...
    Result := Assigned(DatabaseRecord);
  end;

begin
  inherited;
  NodeData := Sender.GetNodeData(Node);
  if Assigned(NodeData) then
  begin
    CellText := '-'; // default for invalid data
    case Column of
      0:  CellText := IntToStr(NodeData^);
      1:  if GetDBRecord then
            CellText := DatabaseRecord^.MeinDatenbankFeld1;
      2:  if GetDBRecord then
            CellText := DatabaseRecord^.MeinDatenbankFeld2;
      4:  if GetDBRecord then
            CellText := DatabaseRecord^.MeinDatenbankFeld3;
     ...    
    end;
  end;
end;

procedure TfrmMain.vstTestGridHeaderClick(Sender: TVTHeader;
  Column: TColumnIndex; Button: TMouseButton; Shift: TShiftState; X,
  Y: Integer);
begin
  inherited;
  // handle sorting changes
  if Button = mbLeft then
  begin
    vstTestGrid.BeginUpdate;
    try
      with Sender do
      begin
        if SortColumn <> Column then
           SortColumn := Column;
        if SortDirection = sdAscending then
          SortDirection := sdDescending
        else
          SortDirection := sdAscending;
        QuickSortTree(True);
      end;
    finally
      vstTestGrid.EndUpdate;
    end;
  end;
end;

//
// jetzt wird es interessant
//

procedure MyUpdateGrid;
begin
  BeginUpdate;
  try
    if (DBCount > 0) then
    begin
      if (Header.SortDirection = sdAscending) then
        RootNodeCount := DBCount // Aufsteigend, wir müssen nichts machen
      else
      begin
        if (DBCount > VSTCount) then
        begin
          for i := VSTCount+1 to DBCount do
          begin
            Node := vstTestGrid.InsertNode(nil, amInsertBefore); // vorher einfügen
            if Assigned(Node) then
            begin
              vstTestGrid.ReinitNode(Node, False); // Node Initialisierung erzwingen
              Int64(vstTestGrid.GetNodeData(Node)^) := i; // korrekten Wert zuweisen (wäre sonst 1, wegen vstTestGridInitNode)
            end;
          end;
        end;
      end;
      end
      else
        ...
  finally
    vstTestGrid.EndUpdate;
  end;
end;

//
// was noch fehlt: die "Sortierung"
//

procedure TfrmMain.QuickSortTree(ForceSort: Boolean = False);
var
  Grid: TVirtualStringTree;
  Node: PVirtualNode;
  sd: TSortDirection;
  IndexNo: Int64;

  procedure SwapSelection;
  begin
    // hier gehe ich alle Nodes durch, um die Auswahl (Selection)
   // des Benutzers umzukehren
   
   LeftNode := Grid.GetFirst;
    RightNode := Grid.GetLast;

    if not (Assigned(LeftNode) and Assigned(RightNode)) then
      Exit;

    // get starting values
    LeftValue := Int64(Grid.GetNodeData(LeftNode)^);
    RightValue := Int64(Grid.GetNodeData(RightNode)^);

    // swap values if needed
    if LeftValue > RightValue then
    begin
      i := RightValue;
      RightValue := LeftValue;
      LeftValue := i;
    end;

    // Note: We use LeftValue and RightValue to sort only up to the first half
    // of the tree (otherwise we would reset our own swap)

    // iterate through the tree nodes
    while (Assigned(LeftNode) and Assigned(RightNode)) and
      ((RightNode <> LeftNode) and (LeftValue < RightValue)) do
    begin
      // get current selection states
      LeftSelected := vsSelected in LeftNode.States;
      RightSelected := vsSelected in RightNode.States;
      // swap selection
      if (LeftSelected <> RightSelected) then
      begin
        Grid.Selected[LeftNode] := RightSelected;
        Grid.Selected[RightNode] := LeftSelected;
      end;
      // get next nodes
      LeftNode := LeftNode.NextSibling;
      RightNode := RightNode.PrevSibling;
      // adjust iteration helper
      Inc(LeftValue);
      Dec(RightValue);
    end;
  end;

begin
  Grid := vstTestGrid;
  Assert(Assigned(Grid));  
  
  // set sorting options
  sd := Grid.Header.SortDirection;
  if (sd = sdAscending) and (not ForceSort) then
    Exit;

  if sd = sdAscending then
    IndexNo := 1
  else
    IndexNo := Grid.RootNodeCount;

  // assign new index values
  Node := Grid.GetFirst;
  while Assigned(Node) do
  begin
    Int64(Grid.GetNodeData(Node)^) := IndexNo;
    if sd = sdAscending then
     Inc(IndexNo)
    else
     Dec(IndexNo);
    Node := Grid.GetNext(Node);
  end;

  // swap node selection
  if (Grid.SelectedCount > 0) then
    SwapSelection;
end;

Das war jetzt nur der Entwurf, die Zuweisung der Selection kann man natürlich über logische Operatoren viel schöner machen. Wichtig war einen Code, der zum Testzeitpunkt verständlich ist (Fehlersuche).

Der Boolean ForceSort der Prozedur QuickSortTree steuert die Vollständigkeit der Sortierung (wird nur im HeaderClick benötigt).