threading Problem

[SIGSEGV]

otze schrieb:

Wenn man weiß was man tut, auf single core schon alles rausgeholt hat und das Problem überhaupt parallelisierbar ist, dann ja.

Das Problem, das er hier lösen möchte (große Mengen an Zahlen akkumulieren) ist sogar "embarrassingly parallel". Sicherlich gibt es dafür (angefangen vom kleinen Gauß für 1 bis n) andere Methoden, aber er schreibt doch, dass er rumspielt und lernen möchte. Was sollen also diese ganzen demotivierenden Beiträge?

Niemand schreibt, dass der resultierenden Code produktiv eingesetzt werden soll. Von daher sind jegliche Argumente die aufs Ersparen von (Arbeits-/Lern-)Aufwand hinauslaufen unbedeutend. Wenn er etwas lernen will, muss er eben einen gewissen Aufwand betreiben.

Stefan, du solltest mal überprüfen, weshalb dein Programm abstürzt.

Valgrind (auch mit --tool=helgrind und --tool=drd) ist hierbei sehr hilfreich, gibt es aber glaube ich nicht für Windows. Notfalls mal in einer Linux-VM ausprobieren. Hast du eventuell einen GCC 4.8 zur Verfügung? Damit könntest du dein Programm auch mit ThreadSanitizer und/oder AddressSanitizer kompilieren. Beim ersteren handelt es sich um einen bei Google entwickelten Datarace-Detektor. Weiß aber auch nicht, ob die unter Windows funktionieren. Unter Linux wird ein x86-64-System benötigt.

Das sind so die einfachen Ansätze, die dir schnelle Ergebnisse bringen, mit bedeutend weniger Aufwand als bei einem General-Purpose-Debugger wie GDB oder dem Microsoft-Debugger nötig wäre.

Ansonsten kann ich dir zum Lernen für einen Überblick das Perfbook ("Is Parallel Programming Hard, And, If So, What Can You Do About It?) empfehlen. Gibt es hier kostenlos. Ansonsten die üblichen Bücher über Betriebssysteme und Synchronisationsprobleme. Vorsicht bei Beispielcode von irgendwelchen Websites. In diesem Bereich ist der öfter falsch als richtig. "Es funktioniert" ist in der nebenläufigen Programmierung noch weniger ein Zeichen für Korrektheit als bei C und C++ ohnehin schon.

Wenn alles nichts hilft und du nicht weiterkommst, mach eine Pause und guck dir deinen Code danach nochmal in Ruhe an und denke jede Möglichkeit durch. Was anderes wird dir oft nicht bleiben. Dazu musst du natürlich erstmal wissen was zu erwarten ist.

[mt'ler]

warum löst den jetzt nicht endlich jemand die fehler in seinem konkreten code wenn multithreading doch angeblich so einfach ist

[Kellerautomat]

mt'ler schrieb:

warum löst den jetzt nicht endlich jemand die fehler in seinem konkreten code wenn multithreading doch angeblich so einfach ist

Weil es eben vermutlich doch nicht so einfach ist, und vor allem mit viel Arbeit verbunden.

@TE: Ich kann dir das Buch C++ Concurrency in Action empfehlen, in dem auf genau solche Aufgabenstellungen wie deine eingegangen wird. Die Erklaerungen sind sehr ausfuehrlich.

Ansonsten hab ich gerade nicht die Zeit, mir dein Problem genauer anzusehen.

[__Stefan__]

Der Threadpool läuft jetzt mit std::packaged_task anstatt meiner eigenen Taskklasse. Soweit scheint jetzt alles stabil zu sein.

[knivil]

Warum nicht einfach futures benutzen anstatt seine eigene Threadklassen zu basteln?

Angenommen, es laufen 8 Threads, wie wird sichergestellt, dass nur einer gleichzeitig diese Variable veraendert (jaja, ints etc. sollen ja atomic sein). Angenommen val ist kein int ...

if(std::distance(start, end) == 1) 
    { 
        val = *start; 
        std::this_thread::sleep_for(std::chrono::milliseconds(100)); 
        return; 
    }

[__Stefan__]

knivil schrieb:

Warum nicht einfach futures benutzen anstatt seine eigene Threadklassen zu basteln?

Ich hatte eben gedacht, ich kann das auch
Jetzt verwende ich ja packaged_task zusammen mit future. Es erfordert etwas mehr Tipparbeit bei der Verwendung, aber zumindest läuft es sauber.

[knivil]

aber zumindest läuft es sauber.

Nein, tut es nicht, weil du mit sum einen shared state hast, dessen Zugriff nicht synchronisiert ist (eigentlich).

[__Stefan__]

knivil schrieb:

Warum nicht einfach futures benutzen anstatt seine eigene Threadklassen zu basteln?

Angenommen, es laufen 8 Threads, wie wird sichergestellt, dass nur einer gleichzeitig diese Variable veraendert (jaja, ints etc. sollen ja atomic sein). Angenommen val ist kein int ...

if(std::distance(start, end) == 1) 
    { 
        val = *start; 
        std::this_thread::sleep_for(std::chrono::milliseconds(100)); 
        return; 
    }

Ich habs mal kommentiert. Ansonsten bitte nicht den Sinn des Algos hinterfragen.

template<class Iter, class T> 
void accumulate(Iter start, Iter end, T& val, thread_pool& tp) 
{ 
    if(start == end) return; 

    if(std::distance(start, end) == 1) 
    { 
        val = *start; 
        std::this_thread::sleep_for(std::chrono::milliseconds(100)); 
        return; 
    } 

    if(std::distance(start, end) == 2) 
    { 
        val = 0; 
        val += *start++; 
        val += *start; 
        std::this_thread::sleep_for(std::chrono::milliseconds(200)); 
        return; 
    } 

    Iter mid = start; 
    std::advance(mid, std::distance(start, end) / 2); 

// Temporäre objekte für rekursive Aufrufe
    T a = 0, b = 0; 
// range wird in zwei Teile geteilt, rekursiver Aufruf von accumulate für beide
// Teile.
// rekursiver Aufruf 1. Hälfte von Range. Threaded wenn thread verfügbar.
    task t(accumulate<Iter, T>, start, mid, std::ref(a), std::ref(tp)); 
    tp.run(t); 
// rekursiver Aufruf 2. Hälfte von Range.
    accumulate(mid, end, b, tp); 

    t.wait(); 

    val = a + b; 
}

[knivil]

Es erfordert etwas mehr Tipparbeit bei der Verwendung

Nicht bei mir. So haette ich es gemacht (quick and dirty), keine extra Klassen fuer Task, Threadpool etc:

#include <algorithm>
#include <numeric>
#include <thread>
#include <future>
#include <iostream>
#include <vector>
#include <chrono>

template<typename T>
int acc(T start, T end)
{
    int sum = 0;
    for(auto it = start; it != end; ++it)
    {
        sum += *it;
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
    return sum;

    //return std::accumulate(start, end, 0);
}

template<typename T>
int para_acc(T start, T end, int split_count)
{
    //return acc(start, end);
    if (split_count != 0)
    {
        auto mid = start + std::distance(start, end)/2;
        auto v1 = std::async(para_acc<T>, start, mid, split_count-1);
        auto v2 = std::async(para_acc<T>, mid, end, split_count-1);
        return v1.get() + v2.get();
    }
    else
        return acc(start, end);
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<int> vec(100,1);
    std::cerr << para_acc(vec.begin(), vec.end(), 3) << '\n';
    return 0;
}

// Temporäre objekte für rekursive Aufrufe 
    T a = 0, b = 0;

Diese Zeile habe ich wohl uebersehen.

[__Stefan__]

@knivil

Weshalb verwendest du überhaupt Rekursion? Du gibst ja die die Threadanzahl durch split_count direkt vor: n = 2^split_count.
Ausserdem erzugst du so Threads, die nichts machen ausser zu warten, abgesehen davon dass Threaderzeugung einen Overhead hat, den man mit Pools vermeiden kann.

Ich will 1 Thread pro CPU-Kern haben, nicht mehr, und die sollen immer schön gefüttert werden.

Dann musst du bedenken, dass die Abarbeitung eines sub-ranges schneller gehen kann als die eines anderen, das heisst Workerthreads können frei werden, während der Algo läuft. Der Algorithmus soll den frei werdenden Worker an anderer Stelle verwenden können.

Wenn man async verwendet, sollte man das so machen, ansonsten geht die Parallelität möglicherweise flöten:

std::async(std::launch::async, ...);

Übrigens läuft dein Algo nur mit random access Iteratoren.

[knivil]

Eine Antwort auf deine Fragen: Quick and dirty.

1.) Rekursion: Jeder hat seine eigenen lokalen Variablen, was du mit a und b haendisch einbaust. Divide and Conquer Ansatz ist sehr einfach zu parallelisieren.
1a.) Ich brauche keinerlei Synchronisationsprimitive, d.h. keine Deadlock, keine Threads denen ein Signal geschickt wird, keine Mutex/Conditions, ... It is a no-brainer.
2.) async launch policy: Ich lasse das System entscheiden. Auch sollte die default policy asynchron sein. Es gibt pathologische Faelle aber ich hoffe sie werden vom ueberarbeiteten Standard revidiert.
3.) Threads, die nichts machen: Normalerweise sollte der Rechenaufwand im Vergleich zur Erzeugung sehr gross sein. Bei deinem Spielzeugbeispiel kann das schlecht demonstriert werden. Die paar zusaetslichen Hardwarethreads sind jetzt nicht so wild. Auch kannst du gern erst die Bereiche festlegen, und in einer Schleife fuer jeden Bereich einen Thread starten.
4.) Threadpools: Threadpools haben andere Probleme.

Deine Argumentation laeuft Richtung PPL (parallel pattern library) oder TBB (threading building blocks). Schau dir die doch mal an.

Übrigens läuft dein Algo nur mit random access Iteratoren.

Mir egal, da ansonsten sowieso die Parallelisierung durch std::distance und std::advance aufgefressen wird.

Was mich hauptsaechlich stoert ist, dass bei dir Algorithmus und Parallelisierung sehr verschachtelt sind. Das kann manchmal nicht vermieden werden, aber in diesem Fall ist Parallelisierungsstrategie und Algorithmus sehr gut trennbar.

[SeppJ]

Stefan schrieb:

Übrigens läuft dein Algo nur mit random access Iteratoren.

Dein ursprüngliches

std::advance(mid, std::distance(start, end) / 2);

mag zwar technisch gesehen mit allen Arten von Iteratoren funktionieren, aber wirklich machen will man das auch nur mit random access.

[knilch]

Stefan schrieb:

Ich will 1 Thread pro CPU-Kern haben, nicht mehr, und die sollen immer schön gefüttert werden.

War vielleicht früher so. Bei Threads gilt lieber zu viel als zu wenig.

[__Stefan__]

SeppJ schrieb:

Stefan schrieb:

Übrigens läuft dein Algo nur mit random access Iteratoren.

Dein ursprüngliches

std::advance(mid, std::distance(start, end) / 2);

mag zwar technisch gesehen mit allen Arten von Iteratoren funktionieren, aber wirklich machen will man das auch nur mit random access.

Ach komm, das holst du durchs Multithreading wieder rein. Wie willst du sonst z.B. ein paralleles for_each implementieren, das mit einer Liste läuft?

[knilch]

Stefan schrieb:

SeppJ schrieb:

Stefan schrieb:

Übrigens läuft dein Algo nur mit random access Iteratoren.

Dein ursprüngliches

std::advance(mid, std::distance(start, end) / 2);

mag zwar technisch gesehen mit allen Arten von Iteratoren funktionieren, aber wirklich machen will man das auch nur mit random access.

Ach komm, das holst du durchs Multithreading wieder rein. Wie willst du sonst z.B. ein paralleles for_each implementieren, das mit einer Liste läuft?

lol? Du schreibst 2x std::distance(linkedlist.begin(), linkedlist.end()), da wird die Linkedlist pro Funktion 2x vollständig durchlaufen, insg. 4x. Das heißt dass dein Programm mind. 4x so lahm ist wie eine einthreadige Abarbeitung.

[knivil]

Klar kannst du ein paralleles Sort fuer Listen implementieren. Und? Die Liste ist fuer parallele Anwendungen eine ungeeignete Struktur. D.h. wuerde ich keine Liste zur Parallelisierung verwenden. Arrays oder Baeume sind besser.

Das heißt dass dein Programm mind. 4x so lahm ist wie eine einthreadige Abarbeitung.

Start/End sind lokal anders und beziehen sich nicht immer auf die gesammte Liste. Und der Speedup haengt vom Arbeitsaufwand der einzelnen Threads ab.

Ansonsten ist die Aussage natuerlich sehr naiv:

Ach komm, das holst du durchs Multithreading wieder rein.

There is no silver bullet. And there is no spoon.

[knilch]

knivil schrieb:

Das heißt dass dein Programm mind. 4x so lahm ist wie eine einthreadige Abarbeitung.

Start/End sind lokal anders und beziehen sich nicht immer auf die gesammte Liste.

Aber zu Beginn schon. Einmal 2 ganze Durchläufe (2), einmal 2 halbe (1), dann 1/2, dann 1/4 (wird alles sequenziell abgelaufen), macht insgesamt 4 volle Durchläufe nacheinander angenommen es ist perfekt auf unendlich CPUs verteilt.

[__Stefan__]

knivil schrieb:

Klar kannst du ein paralleles Sort fuer Listen implementieren. Und? Die Liste ist fuer parallele Anwendungen eine ungeeignete Struktur. D.h. wuerde ich keine Liste zur Parallelisierung verwenden. Arrays oder Baeume sind besser.

Wieseo Bäume? Die haben doch auch kein random access.

knivil schrieb:

Ansonsten ist die Aussage natuerlich sehr naiv:

Ach komm, das holst du durchs Multithreading wieder rein.

There is no silver bullet. And there is no spoon.

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.

[SeppJ]

knilch schrieb:

knivil schrieb:

Das heißt dass dein Programm mind. 4x so lahm ist wie eine einthreadige Abarbeitung.

Start/End sind lokal anders und beziehen sich nicht immer auf die gesammte Liste.

Aber zu Beginn schon. Einmal 2 ganze Durchläufe (2), einmal 2 halbe (1), dann 1/2, dann 1/4 (wird alles sequenziell abgelaufen), macht insgesamt 4 volle Durchläufe nacheinander angenommen es ist perfekt auf unendlich CPUs verteilt.

Was übrigens noch toller wird, wenn man bedenkt, dass der Zweck der hier gezeigten Parallelisierung ist, dass man das Ablaufen der gesamten Liste verteilt. Stattdessen hätte man (ohne random access) das Ablaufen der gesamten Liste vervielfacht.
Diese Idee der Parallelisierung bringt daher nur etwas, wenn die Iteratoren random access sind, es ist daher ungerechtfertigt, sich zu beschweren, dass knivils Lösung diese voraussetzt.

Stefan schrieb:

knivil schrieb:

Klar kannst du ein paralleles Sort fuer Listen implementieren. Und? Die Liste ist fuer parallele Anwendungen eine ungeeignete Struktur. D.h. wuerde ich keine Liste zur Parallelisierung verwenden. Arrays oder Baeume sind besser.

Wieseo Bäume? Die haben doch auch kein random access.

Aber logarithmisch ist immer noch viel besser als linear. Außerdem bietet sich die Baumstruktur ganz natürlich für Divide & Conquer an.

Wichtig ist dass die Algorithmen skalieren.

Und wir sagen dir, dass du es ordentlich machen musst, damit es skaliert. Paralleisierung ist kein Zauberspruch, der alles schneller macht, wenn man nur genügend Kerne hat. Im Gegenteil, es kann ganz leicht passieren, dass etwas langsamer wird (zum Beispiel dein Programm), wenn man es nicht ordentlich macht.

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.

Du hast es genau falsch rum. Je mehr du parallelisierst, desto mehr Overhead hast du. Das heißt, du musst ganz besonders gut skalierende Algorithmen haben. Das heißt, die obigen Kritikpunkte an deiner Lösung wiegen viel schwerer.

[__Stefan__]

Ich glaube ich werde es mal messen.