Freigeben von Listen durch Threads beschleunigen

[Daniel]

Moin,

also Sachen gibt's ... :gruebel: Ich habe hier eine Liste mit etwa 5-10 Mio. Einträgen. Ab und an muss ich diese Liste freigeben, um sie neu aufzubauen. Die Objekte sind etwas komplexer, so dass selbst das Freigeben dieser Liste eine messbare Zeit benötigt. Im ersten Ansatz bin ich treudoof von vorn nach hinten durch die Liste und habe die Elemente freigegeben. Das funktioniert selbstverständlich absolut zuverlässig.

Nun wollte ich mit zwei Threads daran: Jeder soll sich um eine Hälfte der Liste kümmern und von den Objekten den Destruktor aufrufen. Solange ich dabei nicht die Anzahl an Elementen in der Liste verändere, kann ich ja beliebig darauf herumkaspern - so mein Gedanke. Pustekuchen. Zwei Threads arbeiten länger an der Freigabe der Liste als meine simple Schleife. Mir ist klar, dass Threads einen gewissen Overhead haben, aber ob ich nun eine halbe Mio., 5 Mio. oder 15 Mio. Einträge habe - die Threads sind immer ein wenig langsamer. Da ich nur lesend auf die Liste zugreife und jeder der beiden Threads exklusiv seinen Bereich der Liste für sich hat, habe ich mir jede Form der Synchronisation gespart.


Was übersehe ich da? Eigentlich sollte ich mit Threads doch einen Vorteil erziehen können oder nicht?
Demo anbei, falls es wen interessiert.
Anhang 42631

Delphi-Quellcode:

program FreeWilly;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.SysUtils, System.Classes,
  System.Diagnostics,
  System.Threading,
  System.Generics.Collections;

type
  TMoep = class(TObject);

  TMoepManager = class(TObject)
  private
    FList : TList<TMoep>;
  public
    constructor Create;
    destructor Destroy; override;

    procedure Build;
    procedure Clear1;
    procedure Clear2;
  end;

{ TMoepManager }

procedure TMoepManager.Build;
var
  i : integer;
begin
  for i := 0 to 49999999 do  // fuempfzig mio
  begin
    FList.Add( TMoep.Create );
  end;
end;

procedure TMoepManager.Clear1;
var
  i : integer;
begin
  for i := 0 to FList.Count-1 do
    FList[i].Free;
  FList.Clear;
end;

procedure TMoepManager.Clear2;
var
  LTasks : Tarray<ITask>;
  med : integer;
begin
  med := FList.Count DIV 2;  // etwa die mitte

  SetLength( LTasks, 2 );

  LTasks[0] := TTask.Create(
    procedure
    var
      i : integer;
    begin
      for i := 0 to med do
        FList[i].Free;
    end
  );
  LTasks[1] := TTask.Create(
    procedure
    var
      i : integer;
    begin
      for i := med+1 to FList.Count-1 do
        FList[i].Free;
    end
  );

  LTasks[0].Start;
  LTasks[1].Start;

  TTask.WaitForAll( LTasks );

  FList.Clear;
end;

constructor TMoepManager.Create;
begin
  inherited;

  FList := TList<TMoep>.Create;
end;

destructor TMoepManager.Destroy;
begin
  FList.Free;

  inherited;
end;

var
  m : TMoepManager;
  s : TStopwatch;
begin
  s := TStopwatch.Create;

  m := TMoepManager.Create;

  m.Build;
  s.Start;
  m.Clear1;
  s.Stop;
  WriteLn( 'Clear1: ', s.ElapsedMilliseconds, ' ms' );

  s.Reset;

  m.Build;
  s.Start;
  m.Clear2;
  s.Stop;
  WriteLn( 'Clear2: ', s.ElapsedMilliseconds, ' ms' );

  m.Free;

  ReadLn;
end.

[Daniel]

Mir dünkt, dass FastMM das Problem ist. Da war doch mal was, dass der nicht vollständig skaliert.
Komisch, dass man auf sowas erst kommt, wenn man das Problem niedergeschrieben hat.

[Sir Rufo]

Gibt es einen Grund warum du keine

Delphi-Quellcode:

TObjectList

nimmst? Wenn du die Liste neu aupfbaust, dann kannst du die Liste doch auch einem Thread zum Löschen geben und ein anderer Thread baut eine neue Liste auf.

Hast du übrigens schon mal die Zeit gemessen, die nur das

Delphi-Quellcode:

FList.Clear

benötigt? Das dürfte auch nicht unerheblich sein.

[Daniel]

Mein echtes Projekt nutzt eine TObjectList, testweise habe ich auch dort mal eine TList versucht. Doch sobald ich sicherstelle, dass alle Destruktoren aufgerufen werden, zeigen die beiden Listenklassen keinen Unterschied in der Laufzeit.

Gleichzeitig freigeben und neu aufbauen habe ich noch nicht versucht, da der Neuaufbau mit n Threads erfolgt und schon alle CPU-Kerne auslastet. DORT habe ich noch Vorteile durch den Einsatz von Threads. ;-)

[BUG]

Üblicherweise ist Speicherverwaltung und mehrere Threads nicht wirklich toll. Im schlimmsten Fall serialisierst du das Freigeben durch einen Lock wieder vollständig (und hast dann noch den Overhead).

Wenn du die Liste eh wieder aufbaust: Kannst du die Objekte wiederverwenden? Die Performance-Leute für Sprachen mit GC machen das auch ganz "gerne".

Bei diesen Dimensionen und je nach Komplexität der Objekte könnte man auch darüber nachdenken, den Speicher für diese Objekte selbst zu verwalten.

EDIT: Wenn das einfach möglich ist, probiere auch mal die Objekte von dem Thread freigeben zu lassen, der sie erstellt hat. Wenn jeder Thread einen eigenen Heap hat (übliche Optimierung), dann solltest du so Konflikten aus dem Weg gehen.

[jaenicke]

Hast du mal versucht zwei komplett getrennte Listen zu benutzen und zu schauen wie lange deren parallele Freigabe dauert? Dort kannst du dann nämlich messen wie der Unterschied zwischen nur eine der Listen (ohne die zweite Liste) freigeben und parallel freigeben ist.
Wenn das dann pro Liste entsprechend länger dauert, bleibt nur noch der Speichermanager als Flaschenhals.

Mir war aber auch so als gäbe es da einen anderen Speichermanager, der genau bei vielen Threads sinnvoller ist, auch wenn er weniger als FastMM kann. Mir fällt nur gerade nicht ein wie der hieß...
Ach doch, kurz Google gefragt, scalemm:
https://code.google.com/p/scalemm/

[Daniel]

Im echten Projekt habe ich eine Baum-Struktur. Im konkreten Testfall mit rund 1.800 Elementen auf unterster Ebene. Diese Elemente haben ihrerseits Unter-Elemente in jeweils eigenen Listen, so dass ich in Summe auf die eingangs beschriebene Größenordnung komme.
Die beiden Threads hätten sich die 1.800 Root-Elemente aufteilen sollen. Das zeitliche Verhalten lässt sich mit einer langen Liste identisch nachstellen, so dass ich den Speichermanager als Flaschenhals vermute. FastMM macht ja im Allgemeinen einen guten Job, so dass ich vorläufig an ihm festhalten möchte.

Das Thema ist nicht kritisch - ich halte fest, dass es nicht "mal eben so" möglich ist, hier spürbare Vorteile zu erzielen. Ein großartiges Umbauen der Datenstruktur kommt vorläufig nicht in Frage - zumindest nicht mit der alleinigen Motivation, lediglich das Freigeben zu beschleunigen. Manchmal ist die serielle Abarbeitung ja auch ganz charmant. ;-) Nun lege ich wenigstens die in einen Thread, so dass die App nicht blockiert.

[Union]

Was für Zeiten hast Du denn wo gemessen?

[Daniel]

Gemessen habe ich wie oben in meinem Beispiel: Den Gesamtaufwand für Clear1 bzw. Clear2. Also inklusive Erzeugen der Thread-Objekte etc. Das war für mich am naheliegensten, da ich wissen will, wie lange es dauert, mich der Daten wieder zu entledigen.

Die konkreten Werte sind natürlich hardware- und projektabhängig. In meinem Testprojekt messe ich konstant um 300ms für das Zerstören der Liste. Das ist ein Wert, der mir - gerade nach den obigen Überlegungen - zu wenig Leidensdruck verschafft, um hier noch mehr Zeit zu investieren. Es war für mich einfach eine neue Erkenntnis, dass da im Kontext des Speichermanagements offenbar Grenzen existieren.

[Union]

10-15 ms kannst Du sparen, wenn Du vorberechnete Werte für die Schleifen verwendest:

Delphi-Quellcode:

procedure TMoepManager.Clear1;
var
  i : integer;
  c : Integer;
begin
  c := FList.Count -1;
  for i := 0 to c do
    FList[i].Free;
  FList.Clear;
end;