Effizientes paralleles Traversieren eines Baumes

Guten Morgen,

ich habe eine Methode, die rekursiv arbeitet.
Als Vergleich nehmen wir einen Ordner, der Subordner hat. Ein Baum.

        public void RecFolder( DirectoryInfo dirInfo )
        {
            foreach ( var dir in dirInfo.EnumerateDirectories( ) )
            {
                RecFolder( dir );
            }
        }

Damit das ganze schneller läuft möchte ich das Parallel umsetzen..
Mir ist klar, dass das mit den Ordnern so keinen Sinn macht, aber ich will damit ja keine Ordner durchsuchen. Es ist nur ein Beispiel.

        public void RecFolder( DirectoryInfo dirInfo )
        {
            var tasks = new List<Task>( );

            foreach ( var dir in dirInfo.EnumerateDirectories( ) )
            {
                var task = Task.Factory.StartNew( ( ) => RecFolder( dir ) );
                tasks.Add( task );
            }

            Task.WaitAll( tasks.ToArray( ) );
        }

Meine Probleme nun:*Laut Profiler brauche ich 90% der Zeit für Task.Waitall(). Wie vermeide ich das? *Es gibt ein Ende, ich weiß nur nicht wann. Daher kann ich keine BlockingCollection verwenden, oder? *Die SyncQueue hier kenne ich. Entspricht aber nicht meinen Vorstellungen.

Danke, Hans18

Indem du das tatsächlich in Threads auslagerst und nicht sequentielles Arbeiten simulierst 🤔

Ich verstehe die Logik gerade nicht. Du machst einen Thread auf und iterierst durch die Verzeichnisse, wartest allerdings bis dieser Thread fertig ist in der selben Methode.

Was hast du vor und warum arbeitest du nicht mit Events?

Das ist Absicht in diesem Fall. Es muss nach außen hin sequentiell sein, der Inhalt soll aber rekursiv und möglichst schnell bearbeitet werden.

Die Variante erspart mir 70% der Zeit, aber ich finde das mit Task.WaitAll() nicht gut.
Es ist ja nicht nur ein Task, sondern es wird für jeden Subordner ein weiterer Task erstellt. Je nach Struktur sind das also sehr viele Tasks, die auch das gewünsche, sehr schnelle Arbeiten umsetzen.

Events gehen nicht, da ich nach außen nicht asynchron arbeiten darf.

Hallo Hans18

du erstellst für jeden Knoten im Baum ja eine neue Task. Das ist ein riesiger Overhead. Da ist WaitAll dein geringstes Problem (weshalb ich auch den Thread-Titel angepasst habe). (Viel) Mehr Tasks als vorhandene Kerne zu erzeugen, macht meistens keinen Sinn. Dazu kommt, dass die Tasks sehr unterschiedliche lange benötigen können, wenn z.B. unter einen Knoten noch ein riesiger Baum lauert und unter einem anderen nichts weiter. Die kurze Task muss dann lange auf die lange warten.

Du solltest dir daher eine Möglichkeit überlegen, wie du die Gesamtaufgabe in (auf Quadcores) vier möglichst gleich große Teile aufteilen kannst. Dann ist ein einmaliges WaitAll kein Problem.

Ich gehe mal davon aus, dass nicht das Durchlaufen an sich das Aufwändige ist, sondern die Verarbeitung pro Knoten. Wenn das stimmt, dann lass eine Task den Baum durchlaufen, und stelle jeden Knoten in eine (von dir ungeliebte) SyncQueue <T> - Eine praktische Job-Queue und starte gleichzeitig drei oder vier Tasks, die sich jeweils den nächsten Knoten aus der Queue holen.

herbivore

Hallo herbivore, danke.

Es werden innerhalb eines Knoten mehrere Abfragen, die über das Netzwerk gehen, durchgeführt. Ich kann nun alle erst mal sammeln und dann erneut eine Schleife durchlaufen, was ich als schlechter finde oder direkt bei einem Treffer die nötigen Informationen holen wie hier. Wenn ich den Betriebssystem-Scheduler richtig verstehe, dann sind mehr Tasks als Kerne durchaus schneller, da neue Tasks erstellt werden, während andere Tasks noch auf die Netzwerk-Antwort warten.
Wenn ich mit nur 16 Tasks (2x 8 Cores) ist es auch messbar langsamer.

Die SyncQueue ist ja nichts anderes als eine BlockingCollection.
Da bleibt immer noch ein Problem: woher, weiß ich, wann das letzte Element gefunden und bearbeitet wurde? Es gibt ein Ende, das erreicht wird, aber ich weiß nicht wann.
Es kann ja eine Action aktiv sein, während aber die Queue schon leer ist.

Hallo Hans18,

Es werden innerhalb eines Knoten mehrere Abfragen, die über das Netzwerk gehen, durchgeführt.

sicher, wenn die meisten Tasks auf I/O warten, kann es sinnvoll sein, (viel) mehr Task als Kerne zu starten.

Ich kann nun alle erst mal sammeln und dann erneut eine Schleife durchlaufen, was ich als schlechter finde oder direkt bei einem Treffer die nötigen Informationen holen wie hier.

Warum? Es ist offensichtlich besser. Zumal die erste Abfrage bei meinem Vorschlag ebenfalls sofort beginnt und nicht erst, wenn der gesamte Baum durchlaufen wurde.

Die SyncQueue ist ja nichts anderes als eine BlockingCollection.

Ja, ich weiß. So steht es auch in dem verlinkten Thread. Wenn du .NET 4.0 und höher benutzt, spricht nichts gegen eine BlockingCollection und einiges dafür.

Es gibt ein Ende, das erreicht wird, aber ich weiß nicht wann.

In die Queue müsstest du natürlich für jede Task eine Ende-Nachricht stellen, damit sie weiß, dass keine Aufträge mehr folgen und sie sich selbst beenden kann.

Es kann ja eine Action aktiv sein, während aber die Queue schon leer ist.

Offensichtlich tut Task.WaitAll genau, was du willst. Wie ich schon sagte, ein einmaliges WaitAll am Ende ist sicher nicht das Problem.

herbivore

Offensichtlich tut Task.WaitAll genau, was du willst. Wie ich schon sagte, ein einmaliges WaitAll am Ende ist sicher nicht das Problem.

Nein, und doch.
Sobald Task.WaitAll(taskList.toArray()) erreicht wird werden auf neue Tasks in "taskList" nicht gewartet!

In die Queue müsstest du natürlich für jede Task eine Ende-Nachricht stellen, damit sie weiß, dass keine Aufträge mehr folgen und sie sich selbst beenden kann.

Das sieht wie aus? Ich weiß eventuell nicht, was Du meinst.
Aus einer BlockingCollection wird das Element direkt genommen, sodass es dieses nicht mehr kenn.
Auf IsEmpty kann ich also nicht warten, weil der Task noch laufen und neue Elemente gefunden werden könnten.
Müsste also zwei Listen pflegen: anstehende und laufende Tasks..?

Hallo Hans18,

Sobald Task.WaitAll(taskList.toArray()) erreicht wird werden auf neue Tasks in "taskList" nicht gewartet!

bei meinem Vorschlag werden alle Tasks einmal zu Anfang gestartet. Daher sind alle bekannt und das Warten auf sie ist kein Problem.

Das sieht wie aus?

Das wird in dem verlinkten Thread ausführlich diskutiert. Verschiedene Listen braucht man nicht, nur eine Quit-Nachricht für jede Task.

herbivore

bei meinem Vorschlag werden alle Tasks einmal zu Anfang gestartet. Daher sind alle bekannt und das Warten auf sie ist kein Problem.

Damit kann ich mich irgendwie nicht zufrieden geben, da ich glaube, dass Du nicht zuende denkst.
Wenn ich nur 4 Unterknoten habe, dann macht es keinen Sinn am Anfang 500 Tasks zu schedulen. Wenn ich 5000 Unterknoten habe, macht es eventuell mehr Sinn statt nur 4 Tasks eben übertriebene 300 zu starten - eben wegen dem IO-Verhalten.

Du sprichst zwar von mehr Tasks als Cores, aber nicht wie Du die Anzahl ermittelst geschweige denn deren Antwort mit einer Nachricht bestätigst.

Es ist toll, dass Du mir hilfst, danke auch.
Aber die paar Brotstücke, die Du mir gibst, helfen auch nur bedingt. Es wäre also sehr nett, wenn Du mir vollständig erklärst, was Du überhaupt meinst.

Das ist eben nicht ganz trivial und da hilft mir auch der SyncQueue-Thread nicht. Da schreibst Du auch nur, dass eine Quit-Nachricht null sein kann oder nicht und man dieses eben definieren muss; aber im Sinne eines Pattern wird dort nichts erklärt.

Hallo Hans18,

in meinem ursprünglichen Vorschlag bin ich davon ausgegangen, dass drei oder vier Tasks gestartet werden. Wenn das unnötigerweise erfolgt, ist es kein Beinbruch. Wenn du bis zu 500 Tasks starten willst, würde ich das natürlich auch nur tun, wenn es nötig ist. Die erste Task traversiert ja den Baum. Diese könnte die anderen Tasks erst bei Bedarf starten, also z.B. eine Task für jeden (oder jeden n-ten) Knoten, den sie findet, und zwar bis die gewünschte maximal(*) Anzahl von Tasks erreicht ist. Oder in Abhängigkeit vom aktuellen Füllstand der Queue weitere Tasks. Die erste Task kennt dann alle anderen Tasks und kann, wenn sie mit dem Traversieren fertig ist, ein entsprechendes WaitAll absetzen. Dann reicht ein weiteres WaitAll für die erste (die Traversier-)Task, um zu wissen, wann die Gesamtaufgabe fertig ist.

So schwer ist das nun wirklich nicht. Und es waren mehr als nur Brotstücke. Also denk mal selber statt mir zu unterstellen, ich würde es nicht tun. [EDIT]Per PM geklärt und ausgeräumt.[/EDIT]

herbivore

(*) Eine sinnvolle Obergrenze muss man im Zweifel empirisch ermitteln.

Es ist eben ähnlich einem Dateisystem, und daher funktioniert Dein Vorschlag so nicht:
Ich habe einen Ordner, und will den kompletten Inhalt wissen, wobei ich diesen bei Beginn eben nicht kenne: Order durchsuche ich weiter, Dateien füge ich einer Liste hinzu.
Da dies parallel einfach schneller geht, da über Netzwerk, eröffne ich für jeden Ordner einen Task.

Ich kenne weder die Anzahl der Treffer, noch die Anzahl der Knoten bei Beginn.
Es ist nicht klar, wie ich die Menge der Tasks ermittle, oder bei einer BlockingCollection zum korrekten Zeitpunkt CompleteAdding ausführen kann, da ich nicht weiß, wo das Ende ist.

Ich habe also:

• am Anfang einen suchenenden Task, für jeden Treffer neue suchende Tasks, da dies einfach schneller ist (Producer)
• mehrere Consumer brauche ich eigentlich nicht, da das Consumieren der gefundenen Informationen (in diesem Beispiel die Dateien) an einer anderen Stelle ist.

Die Frage ist also:

• wie kann ich bei mehreren suchenden Tasks feststellen, wann das Ende erreicht wurde und auf Task.Waitall() verzichten?

Ich habe noch eine Möglichkeit gefunden, indem ich einen ChildThread an das Parent "attache" damit spar ich das Wait.
Wirklich schön ist das aber auch nicht.

Hallo Hans18,

Ich kenne weder die Anzahl der Treffer, noch die Anzahl der Knoten bei Beginn.

du kannst threadsichere Zählvariable n verwenden. Start n=1. Wurzelknoten in die Queue. Mindestens eine Task, die aus der Queue liest; weitere können jederzeit nach Bedarf (also z.B. dem erreichen Füllstand der Queue) erstellten werden. Jede Task sucht direkte Unterknoten. Für jeden gefunden Unterknoten wird n um eins erhöht und der Knoten in die Queue gestellt. Sind alle direkten Unterknoten eines Knoten gefunden, wird n um eins vermindert. Ist n == 0 ist alles fertig.

Mit der passenden Queue kommt man sogar um das explizite Mitrechnen im Klienten-Code herum.

Im sequentiellen Fall wäre es ja sowieso ganz einfach. Wenn die Queue leer ist, ist man fertig. Zumindest wenn man die Abfrage durchführt, bevor man versucht, das nächste Element zu holen und damit automatisch nach Ende der Bearbeitung des vorigen Elements.

Bei einer parallelen Verarbeitung ist das Problem, dass man das aktuelle Element zu früh herausholt, nämlich bevor dessen Verarbeitung beginnt und nicht erst, wenn dessen Verarbeitung abgeschlossen ist.

Wenn nun die Queue beim Dequeue das Element nicht gleich entfernt, sondern nur beiseite packt - eigentlich ist nur wichtig, dass Count nicht reduziert wird -, sondern das Element erst entfernt bzw. den Count erst reduziert, wenn eine zusätzliche Methode z.B. DequeueComplete oder ElementProcessed o.ä. aufgerufen wurde, hat man alles in der Queue gekapselt und die Tasks müssen sich um nichts weiter kümmern, als die Methode aufzurufen, nachdem alle neuen direkten Kinder zur Queue hinzugefügt wurden. Wenn eine Task nach dem Aufruf der neuen Methode feststellt, dass Count == 0 ist, sind alle Knoten verarbeitet.

Aber auch wenn die Tasks selbst den Zähler mitrechnen würden, würde ich darin kein Hilfsmittel oder Workaround sehen. Der Zähler gibt zu jedem Zeitpunkt die Anzahl der bereits bekannten, noch zu verarbeiten Elemente an. Also etwas sehr klares, nachvollziehbares.

herbivore