threading Problem

Eine Frage habe ich noch zum urspruenglichen Code:

Warum wird in schedule() (und in run() auch) ein notify_all() verwendet?

void schedule(task& t)
    {
        std::unique_lock<std::mutex> lock(m_mutex);

        m_queue.push(&t);
        m_cond.notify_all();
    }

Ich wuerde ein notify_one() an der Stelle einsetzen, da ja nur fuer einen Thread neue Arbeit da ist.

threader schrieb:

Eine Frage habe ich noch zum urspruenglichen Code:

Der ursprüngliche Code ist schrecklich. Es wimmelt vor std::lock_guard<std::mutex> , auch an Stellen, an denen es gar nicht nötig wäre. Code mit Mutexen ist nicht multithreaded.

Angenommen, der Ansatz wäre so gewollt (was er nicht ist).

Dann:
- Als queue eine lock-free queue nehmen (boost hat da eine)
- Als m_idle und done ein atomic nehmen
- std::lock_guardstd::mutex kann dann aus allen(!) Funktion

Allerdings sind immer noch gravierende Designfehler drin, vor allem dieses "nur 1 Thread pro CPU" ist ideal.

Wer sich nicht auskennt soll vorhandene Libraries nehmen.

trader schrieb:

Der ursprüngliche Code ist schrecklich. Es wimmelt vor std::lock_guardstd::mutex, auch an Stellen, an denen es gar nicht nötig wäre. Code mit Mutexen ist nicht multithreaded.

Das beantwortet leider nicht meine Frage.

trader schrieb:

Wer sich nicht auskennt soll vorhandene Libraries nehmen.

Das mag sein. Aber wer dazu lernen will sollte keine Angst haben, Fragen zu stellen und Fehler zu machen.

knivil

Code mit Mutexen ist nicht multithreaded

Das ist Bullshit.

Als queue eine lock-free queue nehmen

Lock-free wird ueberbewertet. Und wie du bereits an der boost-Doku siehst, steht als Note fast ueberall dabei ... wenn Memoryallocator nicht blockiert.

knivil schrieb:

Und wie du bereits an der boost-Doku siehst, steht als Note fast ueberall dabei ... wenn Memoryallocator nicht blockiert.

Zufälligerweise ist der Default-Allocator nicht std::allocator sondern eine stateful LockFree-Implementation.

knivil schrieb:

Code mit Mutexen ist nicht multithreaded

Das ist Bullshit.

Ist vielleicht etwas übertrieben, aber gelockter Code skaliert nicht schön auf viele CPUs.

Stefan schrieb:

Wichtig ist dass die Algorithmen skalieren. Eines Tages werden Wir Desktop-CPUs mit 128 Kernen haben. Die Parallelisierung hat natürlich einen Overhead der sich bei wenigen Kernen stärker bemerkbar macht.

Der Originalcode wird vermutlich ab 4 CPUs immer langsamer und ist ab 8 CPUs langsamer als auf 1 CPU -- wegen dem Locking und notify_all.

knivil

Ist vielleicht etwas übertrieben, aber gelockter Code skaliert nicht schön auf viele CPUs.

Code mit shared state/Kommunikationsbedarf skaliert nicht schoen auf mehreren CPUs. Wenn ein Thread ein Ergebnis benoetigt, dann muss er drauf warten. Wenn der Kommunuikationsaufwand im Verhaeltnis zur Anzahl der Threads und Arbeitsaufwand konstant bleibt, dann ist das gut/okay.

Kannst gern meine Quick and Dirty Loesung mit dem Threadpool vergleichen.

hustbaer

trader schrieb:

knivil schrieb:

Code mit Mutexen ist nicht multithreaded

Das ist Bullshit.

Ist vielleicht etwas übertrieben, aber gelockter Code skaliert nicht schön auf viele CPUs.

Stefan schrieb:

Wichtig ist dass die Algorithmen skalieren. Eines Tages werden Wir Desktop-CPUs mit 128 Kernen haben. Die Parallelisierung hat natürlich einen Overhead der sich bei wenigen Kernen stärker bemerkbar macht.

Der Originalcode wird vermutlich ab 4 CPUs immer langsamer und ist ab 8 CPUs langsamer als auf 1 CPU -- wegen dem Locking und notify_all.

Ach die Aussage ist doch in der Form auch immer noch Schmarrn^4.

Klar, der Code wird nicht gut damit klarkommen wenn man superkleine Tasks verteilen will.

Wenn die Tasks allerdings "gross" genug sind, sagen wir mal Grössenordnung 1ms oder mehr, dann wird das mit ziemlich vielen CPUs noch ziemlich gut skalieren.

ps: das notify_all gehört natürlich weg, da hast du schon Recht. Nur wird es LANGE nicht so bremsen wie du uns hier weismachen willst. Wenn die Tasks, wie im Originalcode duch die "sleeps" angedeutet, wirklich in der Grössenordnung 100ms liegen, dann wird man auf Maschinen die sich irgendjmd. von uns privat leisten könnte vermutlich nichtmal merken ob notify_all oder notify_one verwendet wird.

hustbaer schrieb:

Wenn die Tasks allerdings "gross" genug sind, sagen wir mal Grössenordnung 1ms oder mehr, dann wird das mit ziemlich vielen CPUs noch ziemlich gut skalieren.

Nein, das ist kein Geflame, da steckt eine mathematische Überlegung dahinter:

knivil schrieb:

Kannst gern meine Quick and Dirty Loesung mit dem Threadpool vergleichen.

Annahme: Der Computer hat unendlich viele CPUs.
Knivils Lösung läuft dann in O(log n) Zeit, weil die Rekursion einen schönen Binärbaum erzeugt und die Zeit gerade die Tiefe ist.
Stefans Lösung läuft in O(n), falls der Task eine feste Grösse hat. Einfach weil pro Task 1x gelockt wird.
Haben die Tasks eine Grösse von $\sqrt{n}$ , ist die Zeit "nur" $O(\sqrt{n})$ (Wurzel n mal locken, Wurzel n für die Ausführung: deshalb ist diese Grösse optimal)

Heutige Rechner haben nicht unendlich viele CPUs. Mit 2 CPUs ist es gut möglich, dass Stefans Ansatz besser ist. Aber ab irgend einer Grenze ist der nicht lockzentrierte Ansatz von Knivil überlegen. Vielleicht erst ab 128 CPUs falls std::async naiv implementiert ist. Vielleicht schon mit 2 CPUs falls std::async einen Threadpool verwendet. Aber ganz sicher skaliert er besser.

Blödes Smilie, keine Ahnung wie das da reingerutscht ist.

trader schrieb:

Annahme: Der Computer hat unendlich viele CPUs.
Knivils Lösung läuft dann in O(log n) Zeit, weil die Rekursion einen schönen Binärbaum erzeugt und die Zeit gerade die Tiefe ist.
Stefans Lösung läuft in O(n), falls der Task eine feste Grösse hat. Einfach weil pro Task 1x gelockt wird.
Haben die Tasks eine Grösse von n−√, ist die Zeit "nur" O(n−√) (Wurzel n mal locken, Wurzel n für die Ausführung: deshalb ist diese Grösse optimal)

M.E. sind beide Loesungen O(n), da alle Zahlen aufaddiert werden. Dass da ein Binaerbaum entsteht, hat nur Einfluss auf die Rekursionstiefe, bzw. die Anzahl Threads. Die ist O(ld n).
Ob nun gelockt wird oder nicht, hat auf die asymptotische Komplexitaet keinen Einfluss. Nur der absolute Overhead veraendert sich.

Im Uebrigen ist das rekursive Starten von Threads gerade kein, oder zumindest ein sehr unguenstiger, Anwendungsfall fuer einen Threadpool.

SeppJ

threader schrieb:

M.E. sind beide Loesungen O(n), da alle Zahlen aufaddiert werden.

In absoluter CPU-Zeit vielleicht, aber ganz bestimmt nicht in Echtzeit! Sonst wäre jede Art von Parallelisierung vollkommen sinnlos.

In absoluter CPU-Zeit vielleicht, aber ganz bestimmt nicht in Echtzeit! Sonst wäre jede Art von Parallelisierung vollkommen sinnlos.

Ob ich parallelisiere oder nicht hat auf die asymptotische Komplelixtaet erst mal keinen Einfluss. Die sagt ja nichts ueber den absoluten Zeitbedarf aus, sondern darueber, wie sich der Zeitbedarf mit der Problemgroesse entwickelt.

O(n) bleibt - bei gleichem Algorithmus - O(n). Die Ausfuehrungszeit reduziert sich durch das parallele Verarbeiten der Daten (jede CPU berechnet nur einen Teil der Daten, aber mit demselben Algorithmus).

Oder platt gesagt:
1000 Werte aufaddieren sind immer 999 Additionen.

Ergaenzung:

Bei 4 CPUs waere O(n) dann O(n/4), was aber wieder als O(n) geschrieben wird.

threader schrieb:

Bei 4 CPUs waere O(n) dann O(n/4), was aber wieder als O(n) geschrieben wird.

Im Idealfall schon, aber der Effekt ist ein anderer:

Absolut(n) = Rechenzeit(CPUs) + Overhead(CPUs)

Bei Stefans Algorithmus:
Rechenzeit(CPUs) = n/CPUs
Overhead = n/Taskgrösse

Also 4 CPUs wären n/4 + n/8
Oder 1000 CPUs wären n/1000 + n/8

Bei fester Anzahl CPUs ist immer jeder Algorithmus O(n), aber bei Stefan gibt es eine obere Grenze an CPUs, bei denen der Algorithmus sinnvoll aufteilen kann. Ich schätze mal 8 CPUs addieren bei ihm schneller als 16 CPUs.