Ab wann macht std::async Sinn

Ich habe vor einer Weile zahlreiche Tests in dieser Richtung durchgeführt. Wenn mich mein Gedächtnis nicht täuscht, dann kostete das Starten eines neues Threads 100,000 Zyklen, das Aufwecken eines bestehenden Threads via condition variable 70,000 Zyklen und mit bestimmten Arten von busy waiting bekommt man eine Latenz (Dispatch bis Eintreffen des Ergebnisses) von minimal 2000 Zyklen hin.

Tatsächlich kann man relativ ungeniert einige tausend Threads pro Sekunde starten und wieder beenden, ohne dass das zu einem nennenswerten Overhead aufläuft. Ein Programm, das ich anfangs aufgrund seiner eher synchronen Natur für nur schlecht parallelisierbar gehalten habe, skaliert jetzt trotzdem fast perfekt mit Anzahl der CPU-Kerne - eben gerade weil man auch sehr kleine Tasks gut asynchron ausführen kann.

Das dürfte aber auch stark von Betriebssystem, Hardware und dem Wetter abhängen (bzw. eher vom aktuellen Zustand kernel-interner Strukturen). Die Kosten für das Starten eines Threads änderten sich z.B. nach jedem Reboot (unter Linux getestet). Daher sollte man selbst Tests auf der Maschine durchführen, auf der das Programm später laufen soll, bzw. auf einem "typischen" Gerät, wenn es sich um Endnutzeranwendungen handelt.

Tatsächlich kann man relativ ungeniert einige tausend Threads pro Sekunde starten und wieder beenden, ohne dass das zu einem nennenswerten Overhead aufläuft.

100,000 Zyklen ist bei dir kein nennenswerter Overhead?

Threaderzeugung sind noch kostspieliger als Speicher Allokationen, deswegen nutzt man für sehr kurz kleine Aufgaben häufig Thread-Pools, bei seiner 17-20ms Laufzeit wird das wohl schnell relevant wie lange das starten kostet

und die Frage ist ob er überhaupt wirklich parallelisieren kann
- ohne das alles zu gelockt wird

@axels.

Was von deinem Algorithmus braucht denn die 17-20ms - hast du mal einen sinnvollen Benchmark für deinen Berechnung erstellt? z.B. Mio von Durchläufen, Profile laufen lassen, ohne GUI/Allokationen usw. - damit du überhaupt sehen kannst wo deine Kosten herkommen

axels.

Gast3 schrieb:

Was von deinem Algorithmus braucht denn die 17-20ms - hast du mal einen sinnvollen Benchmark für deinen Berechnung erstellt? z.B. Mio von Durchläufen, Profile laufen lassen, ohne GUI/Allokationen usw. - damit du überhaupt sehen kannst wo deine Kosten herkommen

Nach einem akuellen profiling sieht es so aus als ob die meiste Zeit des Algorithmus beim einlesen der Punktdaten verloren geht. Da ich hier von einen std::string auf einen double Wert kommen muss. Das scheint mir noch relativ ineffizient zu sein.

wob

Zu Umwandeln von strings/int gibt es nen interessanten Vortrag von Alexandrescu hier: https://www.youtube.com/watch?v=o4-CwDo2zpg. Sollte das wirklich dein Flaschenhals sein, dann schau dir das mal an.

Gast3 schrieb:

100,000 Zyklen ist bei dir kein nennenswerter Overhead?

Das ist nirgendwo ein nennenswerter Overhead, nicht nur bei mir. Es handelt sich etwa um 30us. Wir reden gerade von Tasks, deren Laufzeit in die Millisekunden geht.

deswegen nutzt man für sehr kurz kleine Aufgaben häufig Thread-Pools, bei seiner 17-20ms Laufzeit wird das wohl schnell relevant wie lange das starten kostet

Das ist ein Trugschluss. Einen bestehenden Thread eines Threadpools z.B. mittels von pthread_cond_signal aufzuwecken dauert länger, als einen neuen Thread zu starten. Es wäre schon sachdienlich, wenn du deine Theorien auch testen würdest.

Skym0sh0

;arf schrieb:

Das ist ein Trugschluss. Einen bestehenden Thread eines Threadpools z.B. mittels von pthread_cond_signal aufzuwecken dauert länger, als einen neuen Thread zu starten. Es wäre schon sachdienlich, wenn du deine Theorien auch testen würdest.

Das kann ich mir nur schwerlich vorstellen, denn sonst würde Task-Based Parallelism wie z.B. in OpenMP keinerlei Sinn machen.

Wobei wir gerade bei dem Thema sind, Intel empfiehlt für TBB die Tasks möglichst größer als 10000 Zyklen zu granulieren, um den Management Overhead nicht dominieren zu lassen.

Skym0sh0 schrieb:

Das kann ich mir nur schwerlich vorstellen, denn sonst würde Task-Based Parallelism wie z.B. in OpenMP keinerlei Sinn machen.

Es gibt ja auch andere Methoden. Speziell das in solchen Szenarien gern verwendete pthread_cond_signal ist unverhältnismäßig teuer, aber pthread_cond_broadcoast kostet schon weniger, ein normaler Mutex noch weniger. Und wie ich schon erwähnt hatte, sind mit spinlocks 2.000 Zyklen möglich (also die Zeit, die vergeht, bis das Ergebnis des anderen Threads im aktuellen Thread zur Verfügung steht, inkl. task dispatch). Aber busy waiting ist nicht immer angebracht und eine generische Threadpool-Implementation wird das auch nicht machen.

Man muss sich überlegen, was im aktuellen Anwendungsszenario angemessener ist und vielleicht generell weniger nachdenken und mehr messen. Auch jenseits von Multithreading eine gute Idee.

Man muss den Thread ja nicht für jeden Auftrag aufwecken sondern nur wenn sich der Zustand von "Leere Queue" nach "Gefüllte Queue" wechselt. Also sehr selten, wenn der Thread immer was zu tun hat.

Nach einem akuellen profiling sieht es so aus als ob die meiste Zeit des Algorithmus beim einlesen der Punktdaten verloren geht

also wenn du noch so viel Zeit im import verbringst lohnen sich Threads noch nicht
Frage 1: wie hast du rausgefunden das die Zeit dort verloren geht, Profiler?

Die Berechnung fällt immer dann an wenn der Nutzer einen Parameter ändert.

Frage 2: wieso werden denn beim Ändern von Parametern Punktedaten in strings geschrieben die dann noch nach double konvertiert werden muessen?

kannst du nicht auf die Konvertierung verzichten und ohne direkt mit den Daten arbeiten?

oder ist dein Szenario nur schlecht beschrieben?

axels.

Gast3 schrieb:

Frage 2: wieso werden denn beim Ändern von Parametern Punktedaten in strings geschrieben die dann noch nach double konvertiert werden muessen?

kannst du nicht auf die Konvertierung verzichten und ohne direkt mit den Daten arbeiten?

oder ist dein Szenario nur schlecht beschrieben?

Es gibt genau genommen zwei szenairen. Einmal die Darstellung vorhandener Punkte, eingelesen aus einer Datei, und die Berechnung einer Funktion, mit verschiedenen variablen Parameter, aus dem Funktionsterm.

Bei der Darstellung von Punkten und deren Auswertung ist ganz klar das Einlesen mein Flaschenhals. Das bekomm ich auch in absehbarer Zeit nicht schneller hin. Deswegen versuche ich durch Parallelisierung alles andere möglichst schnell zu gestalten um die verlorene Zeit "aufzuholen".

Bei der Berechnung aus dem Funktionsterm heraus ist der Parser meine Engstelle. Diesen kann ich nicht parallelisieren da ich dessen Berechnung für jeden Schnitt komplett brauche.
Somit versuche ich das Update der UI bei einer Änderung des Parameters, was zwangsläufig nötig ist, Parallel zu machen um nicht die ganze Anwendung zu blockieren.

Bei der Darstellung von Punkten und deren Auswertung ist ganz klar das Einlesen mein Flaschenhals. Das bekomm ich auch in absehbarer Zeit nicht schneller hin.

Weil du keine Zeit für die Optimierung hast oder keine Idee hast wie man das (auch ohne Threads) beschleunigen könnte?

Bei der Berechnung aus dem Funktionsterm heraus ist der Parser meine Engstelle. Diesen kann ich nicht parallelisieren da ich dessen Berechnung für jeden Schnitt komplett brauche.

Und der Parser arbeitet schon "optimal"?

Somit versuche ich das Update der UI bei einer Änderung des Parameters, was zwangsläufig nötig ist, Parallel zu machen um nicht die ganze Anwendung zu blockieren.

du musst deinen Import- und Term-Parser optimieren - dann wird es schon schneller, aber den GUI-Abtrenn-Thread brauchst du meistens trotzdem

axels.

Gast3 schrieb:

Und der Parser arbeitet schon "optimal"?

Für mich gibt es an ihm nichts mehr zu optimieren. Evtl. müsse man den Erstellen hier aus dem Forum fragen, ob er da noch Möglichkeiten sieht.

du musst deinen Import- und Term-Parser optimieren - dann wird es schon schneller, aber den GUI-Abtrenn-Thread brauchst du meistens trotzdem

Soweit bin ich gedanklich auch schon.
Danke!

Für mich gibt es an ihm nichts mehr zu optimieren.

weil der maximal schnell ist oder warum?

bei dem Import könntest du z.B. auch schnellere string->double Konvertierungsfuntkionen nutzen (https://github.com/miloyip/dtoa-benchmark)

Evtl. müsse man den Erstellen hier aus dem Forum fragen, ob er da noch Möglichkeiten sieht.

warum nur ihn?

sorry ich hab das falsche Projekt bei string->double gepostet - bin noch am suchen

Es kann bei string->double konvertierung sehr relevant sein was du nutzt, scanf, iostream,strtod...

wob

Hallo Gast3, meinst du ggf. https://github.com/google/double-conversion?

Hallo Gast3, meinst du ggf. https://github.com/google/double-conversion?

bin mir nicht sicher - ich dachte da wäre eine Benchmark-Übersicht dabei gewesen