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;

[himitsu]

Die Werte der For-Schleife sind immmer vorberchnet, da Delphi den Endwert zwischenspeichert.

15ms ... wenn du das mit GetTickCount oder Dregleichen gemessen hast, dann ist das eher ein Messfehler.


TTask?
Warum nimmst du nicht die neue "coole" threaded For-Schleife?


Bezüglich des Threads:
Wenn die FList und deren Objekte nirgendwo dran hängen, also wie z.B. Owner/Parent-Bezieungen zu deiner Basisklasse (TMoepManager). (auch bei TComponent oder Dregleichen aufpassen, daß es nirgendwo weitere globale Listen/Registrierungspunkte gibt)

• eventuelle Beziehungen zur Basisklasse auflösen
• FList mit einer Temp-Variable (nil) tauschen
  oder alternativ nur den Inhalt von FList in eine andere Liste übertragen
• nun die ganze Liste an den Thread/Task übergeben (der gibt das frei)
• fertig und sich nicht weiter drum kümmern

PS: Im Gegenzug, kannst du dann auch das erstellen auch in Threads/Tasks machen, oder die neue Liste schonmal vorher erstellen und dann ebenso austauschen.

[noisy_master]

Moin,

ich bin mir nicht so ganz sicher, wie Delphi die Listen verwaltet. Aber wenn es eine normale verkettete Liste ist könnte es effizienter sein von hinten anzufangen...(auch der Vergleich auf 0 als Endkriterium für eine Schleife ist normalerweise schneller als der Vergleich auf einen festen Wert)

Gruß
Dirk

P.S.: hoffe habe nicht allzu großen Schwachsinn erzählt...

[Der schöne Günther]

Nein, nur leider baut die TList nicht auf eine (doppelt) verkettete Liste auf, sondern auf ein mitwachsendes Array.

[Union]

Zitat:

Zitat von himitsu (Beitrag 1291382)

Die Werte der For-Schleife sind immmer vorberechnet, da Delphi den Endwert zwischenspeichert.

Da hast Du natürlich Recht. In dem Fall ist vielleicht das Aligment Schuld, bei der minimal langsameren Variante ist der Zugriff auf den Schleifenzähler nicht optimal [ebp-$0c] im Gegensatz zu [ebp-$10].

[Daniel]

Zitat:

Zitat von himitsu (Beitrag 1291382)

TTask?
Warum nimmst du nicht die neue "coole" threaded For-Schleife?

Alles schon probiert. Klassischer TThread, TTask oder TParallel - liefert alles das gleiche Ergebnis.

Zitat:

Zitat von himitsu (Beitrag 1291382)

...fertig und sich nicht weiter drum kümmern

Das wäre noch eine Variante, wobei ich auch ein Auge auf den Speicherverbrauch haben muss, denn der Krempel ist empfindlich groß.

[Blup]

Zitat:

Zitat von Der schöne Günther (Beitrag 1291384)

Nein, nur leider baut die TList nicht auf eine (doppelt) verkettete Liste auf, sondern auf ein mitwachsendes Array.

Was in 99% aller Fälle auch sinnvoll ist. In der Praxis sind Listen die intern auf Arrays basieren mindestens ähnlich schnell.
Der Cache heutiger Prozessoren ist eher dafür geeignet große zusammenhängende Speicherbereiche zu verarbeiten.
Passt das gesamte Array in den Cache (Objekte oder Pointer brauchen nur 8 Byte je Element), ist auch das Verschieben der Elemente kein Problem.
Selbst der oft angeführte Fall des häufigen Einfügen oder Entfernen von Objekten inmitten der Liste ist in der Regel bei verketteten Listen nicht spürbar schneller.
Das man erst einmal die richtige Stelle zum Einfügen finden muss, wird bei solchen Vergleichen meist vergessen.

[Der schöne Günther]

Habe ja nicht gesagt dass ich das schlecht finde- Das "leider" bezog sich auf Vermutung "Wenn es eine verkettete Liste ist, dann..." ;-)

Auf jeden Fall wieder was gelernt.

[Blup]

Zum Thema Objekte wiederverwenden:

Dafür könnten diese Methoden der Klasse TMoep überschieben werden:

Delphi-Quellcode:

class function NewInstance: TObject; override;
procedure FreeInstance; override;

Benötigt wird eine globale Liste für verfügbare TMoep-Objekte.
FreeInstance speichert "freigegebenen" Objekte in dieser.
NewInstance kann sich aus der Liste bedienen, so lange noch "freigegebene" Objekte vorhanden sind.

[himitsu]

Vielleicht fällt dir der Speichermanager auf die Füsse?

Kleine Speicherblöcke legt FastMM doch in mehreren größeren Blöcken an, die durch CriticalSections geschützt sind.
Zwei Threads, die auf den selben Verwaltungsblock zugreifen, sperren sich dann natürlich.


Insgesamt hätte ich dennoch eine Beschleunigung erwartet, außer der Overhead durch die Threads/Tasks hebt das wieder auf.
Auch mehr Threads versucht? (4 oder 8 ... k.A. was du für eine CPU hast)

[Daniel]

Zitat:

Zitat von himitsu (Beitrag 1291404)

Auch mehr Threads versucht? (4 oder 8 ... k.A. was du für eine CPU hast)

Der VM habe ich vier Kerne zugewiesen. Beim Aufbau der Liste passen Theorie und Praxis auch wunnebaaa z'ammen und bei vier Threads habe ich die höchste Performance.

@Blup: Spannende Idee, aber ich sehe mich schon mit Löchern im Strumpf, weil ich mir damit mit hoher Wahrscheinlichkeit selbst in den Fuß schieße. Ich werde das am Wochenende aus Interesse mal ausprobieren, wenngleich ich noch Zweifel habe, ob das der Wartbarkeit des Gesamtprojekts entgegenkommt.

[BUG]

Zitat:

Zitat von Blup (Beitrag 1291402)

Dafür könnten diese Methoden der Klasse TMoep überschieben werden:

Ah, also bietet Delphi da auch Schnittstellen an :thumb:

Zitat:

Zitat von Blup (Beitrag 1291402)

Benötigt wird eine globale Liste für verfügbare TMoep-Objekte.

Wenn du eine globale Liste hast, dann baust du dir vermutlich wieder einen Flaschenhals ein; möglicherweise selbst wenn du lockfreie Datenstrukturen verwenden solltest. Ein Pool pro Thread ist vermutlich günstiger.

Zitat:

Zitat von Daniel (Beitrag 1291407)

Ich werde das am Wochenende aus Interesse mal ausprobieren, wenngleich ich noch Zweifel habe, ob das der Wartbarkeit des Gesamtprojekts entgegenkommt.

Wo hast du da vorbehalte? Im Prinzip ändert sich an der Schnittstelle der Objekte nichts.

Wenn man wirklich ein Muster hat, in der man eine große Datenstruktur erzeugt, dann zerstört und wieder neu aufbaut, dann kann man mit mehr Aufwand noch einiges machen ... z.B. braucht man Objekte nicht einzeln freigeben, sondern verwendet einen Block einfach wieder. Dadurch das der dann wieder leer ist, sind selbst Allokationen supergünstig. Das hat dann natürlich mehr Einfluss auf die Wartbarkeit :mrgreen:

[Namenloser]

Du kannst ja mal ScaleMM ausprobieren. Skalierte zumindest in einem Projekt von mir deutlich besser als FastMM (letzterer skalierte genauer gesagt überhaupt nicht).

Aber ich frage mich, ob es überhaupt Sinn machen kann, das Freigeben durch mehrere Threads zu beschleunigen, da der Arbeitsspeicher der Flaschenhals sein sollte und nicht die CPU. Du kannst noch so viele Threads auf das Problem ansetzen, der Durchsatz des Arbeitsspeichers erhöht sich dadurch ja nicht. Selbst mit einem perfekt skalierenden Speichermanager wird da vermutlich kaum etwas rauszuholen sein, wenn überhaupt.

[himitsu]

Zitat:

Zitat von Namenloser (Beitrag 1291465)

Aber ich frage mich, ob es überhaupt Sinn machen kann,

Kommt drauf an ... theoretisch können mehrere Kerne gleichzeitig auf unterschiedliche Speicherseiten/-bänke/Riegel des RAM zugreifen.
Und dann spielt eventuell noch die eine oder andere Cache mit.

[Bernhard Geyer]

Zitat:

Zitat von Namenloser (Beitrag 1291465)

Du kannst ja mal ScaleMM ausprobieren. Skalierte zumindest in einem Projekt von mir deutlich besser als FastMM (letzterer skalierte genauer gesagt überhaupt nicht).

Oder mal nach "fastmm multithread" googlen. Es gibt einige Diskussionen über alternative Memory-Manager die im Multithread-Bereich viel besser skalieren (bzw. überhaupt skalieren). Auch mit schönen Graphiken wie sich FastMM, ScaleMM und Co. verhalten.

[Namenloser]

Zitat:

Zitat von himitsu (Beitrag 1291476)

Und dann spielt eventuell noch die eine oder andere Cache mit.

Bei quer über den Heap verstreuten Objekten sollte Cache aber eher keine Rolle spielen.

Zitat:

Zitat von himitsu (Beitrag 1291476)

Kommt drauf an ... theoretisch können mehrere Kerne gleichzeitig auf unterschiedliche Speicherseiten/-bänke/Riegel des RAM zugreifen.

Geht das? Ich hätte jetzt angenommen, das läuft alles über den gleichen „Bus“ oder wie auch immer (mit der Hardware kenn ich mich nicht so aus). Im Dual-/Triple-Channel-Mode ist der Speicher ja außerdem wohl eh so eine Art RAID-0.

[Daniel]

Die Datenmange kann es kaum sein.
Konkrete Zahlen aus meinem System / Testprojekt:

Das Abbauen der Liste dauert rund 300ms - für einen Rechner als eine durchaus nennenswerte Zeit. Der Taskmanager listet mir für die Anwendung einen Speicherverbrauch von 360 MBytes. Ich weiß, dass der Task-Manager nicht besonders präzise ist, aber für eine grobe Schätzung sollte der Wert langen. Selbst wenn sich das alles in einer VM abspielt, müsste doch mehr an Daten durch den Bus passen. Zudem wird doch gar nicht das komplette Speicher-Abbild durch den Bus gepresst, oder? Ich überschreibe die Bereiche ja nicht mit Nullen oder dgl.

[Namenloser]

Aber außer Speicherzugriffen dürfte doch kaum etwas passieren. Ich wüsste zumindest nicht was. Außer du machst irgendwelche komplizierten Dinge im Destruktor.

[Stevie]

Zitat:

Zitat von Daniel (Beitrag 1291363)

Mir dünkt, dass FastMM das Problem ist.

Das ist absolut richtig.

[jaenicke]

Ich habe gerade mal ScaleMM getestet. Der reserviert deutlich mehr RAM dabei, so dass es ein Out of Memory gibt und ist langsamer...
sapmm z.B. reserviert auch mehr, aber nicht so viel mehr, ist aber auch langsamer, insbesondere mit zwei Threads deutlich.

Ich bekomme so langsam das Gefühl, dass FastMM doch nicht so schlecht ist. ;-)

[himitsu]

FastMM hat von den kleineren Blöcken extra mehrere, so daß bis zu 3 Threads gleichzeitig RAM "bestellen" können,

aber beim Freigeben oder Ändern kann, je Gruppe, natürlich immer nur Einer gleichzeitig, wenn die Speicher zufällig im selben Block liegen.

[BUG]

Zitat:

Zitat von himitsu (Beitrag 1291636)

aber beim Freigeben oder Ändern kann, je Gruppe, natürlich immer nur einer gleichzeitig, wenn die Speicher zufällig im selben Block liegen.

Das ist das Schöne an einer Lösung, wo man für eine konkrete Klasse noch einen Pool dazwischenschalten kann: Ich kann jedes Objekt in jeden Pool stecken, praktisch also auch ganz schnell in meinen Thread-lokalen.

[Stevie]

Zitat:

Zitat von BUG (Beitrag 1291644)

Zitat:

Zitat von himitsu (Beitrag 1291636)

aber beim Freigeben oder Ändern kann, je Gruppe, natürlich immer nur einer gleichzeitig, wenn die Speicher zufällig im selben Block liegen.

Das ist das Schöne an einer Lösung, wo man für eine konkrete Klasse noch einen Pool dazwischenschalten kann: Ich kann jedes Objekt in jeden Pool stecken, praktisch also auch ganz schnell in meinen Thread-lokalen.

Das würde Daniel aber auch nix helfen, die Instanzen gibts schon, die dann noch irgendwo in nem Pool zu verschieben, würde die Sache kaum schneller machen.

Es gibt gewisse Dinge, die kann man ebend nicht mit multithreading schneller machen (manchmal geht das sogar eher nach hinten los).
ScaleMM und Co mögen schneller sein, wenn man innerhalb mehrerer Threads Instanzen erzeugt und wieder freigibt oder mit strings hantiert (siehe Benchmarks) . Aber einmal erstellte Instanzen parallel freigeben, geht auch dort nicht schneller (eher langsamer wie auch meine Tests bestätigen).

[Daniel]

Ich hab' mich jetzt eh an anderer Stelle im Projekt verfuddelt. Da hilft alles nix mehr. ;-)

Threads 1..4 bauen die Datenstruktur auf, Threads 5 und 6 solchen selbige durchsuchen, wenn die ersten vier Threads fertig sind. In der Theorie simpel, in der Praxis ein Deadlock. :mrgreen: Ich glaub' das geht grundsätzlich nicht. *g*

[Stevie]

Zitat:

Zitat von Daniel (Beitrag 1291659)

Ich hab' mich jetzt eh an anderer Stelle im Projekt verfuddelt. Da hilft alles nix mehr. ;-)

Threads 1..4 bauen die Datenstruktur auf, Threads 5 und 6 solchen selbige durchsuchen, wenn die ersten vier Threads fertig sind. In der Theorie simpel, in der Praxis ein Deadlock. :mrgreen: Ich glaub' das geht grundsätzlich nicht. *g*

Ach was, alles ganz einfach mit der PPL! :roll:
Wo genau lockts denn? Grundsätzlich sollten ja für den start von Task 5 und 6 die ersten 4 fertig sind. Also können nur entweder die ersten 4 sich gegenseitig locken oder 5 und 6.

[Daniel]

Das Projekt sollte auch noch für XE4 kompatibel bleiben, daher nutze ich ganz klassisch TThread.
Jetzt eben das war ein unglücklicher Copy&Paste-Fehler aus der Rubrik "Ich probier mal eben was aus.".
;-)

[Dejan Vu]

Ich würde mal schauen, ob Du dir nicht einen eigenen Speichermanager für deine Objekte schreibst. Dem gibst Du einen Block an Speicher und wenn Du deine neuen Objekte bauen willst, dann dann musst Du gar nichts freigeben. Der Block muss halt nur groß genug sein (der Einfachheit halber). Alternativ kann er auch mehrere Blöcke verwalten. Der ist der einzige, der Speicher wirklich anfordert. Deine Sonderobjekte holen sich ihren Speicher von deinem MM.

Wenn deine Objekte nur aufgebaut werden, aber sonst nicht großartig leben, d.h. freigegeben, neu aufgebaut etc. sollte das doch kein Problem sein:

Delphi-Quellcode:

function TMyMM.GetMem (size : Integer) : Pointer;
Begin
  if NextFreeByte+size > maxSizeAvail then
    raise EOutOfMemory.Create; // oder neuen Block anfordern
 
  result := @MyMemoryBlockAsByteArray[NextFreeByte];
  inc (NextFreeByte, size);
end;

function TMyMM.Dispose (p : Pointer; size : Integer);
Begin
  // WTF;
End;

Procedure TMyMM.ClearMemory;
Begin
  NextFreeByte := 0;
End;

Wenn Du deine Objekte dann neu aufbauen willst, Rufst Du ClearMemory auf und fertig ist die Laube. Klar, ist nicht gerade Speicheroptimal, wenn Dispose öfter aufgerufen wird, aber ich sagte eingangs ja: Wenn...

[BUG]

Zitat:

Zitat von Stevie (Beitrag 1291656)

Das würde Daniel aber auch nix helfen, die Instanzen gibts schon, die dann noch irgendwo in nem Pool zu verschieben, würde die Sache kaum schneller machen.

Die Datenstruktur wird wiederholt freigegeben und wieder neu aufgebaut. Wenn man bei der Freigabe, anstelle sich um ein Lock zu kloppen, die Instanz lokal merken kann, könnte das schon was bringen.

Zitat:

Zitat von Daniel (Beitrag 1291659)

Threads 1..4 bauen die Datenstruktur auf, Threads 5 und 6 solchen selbige durchsuchen, wenn die ersten vier Threads fertig sind.

Ein großer Baum, der öfter mal neu erstellt wird und ansonsten von 2 Threads durchsucht wird ... klingt nach einer spannenden Anwendung :mrgreen:

[Sir Rufo]

@Daniel

Du brauchst dazu 7 Threads

Thread 1

• Startet 4 Holt-mal-Daten Threads und wartet bis die fertig sind
• Fasst die Ergebnislisten zusammen / teilt die Ergebnisse für die Such-Threads auf
• Startet 2 Sucht-mal-Daten Threads und wartet bis die fertig sind
• Beendet sich (oder legt sich schlafen)

Macht in Summe 7 Threads und du brauchst somit (aus der Sicht der Anwendung) nur mit einem Thread jonglieren.

[Uwe Raabe]

Klingt wie ein Fall für die Pipeline der OmniThreadLibrary.