Parallelisieren von Algorithmen standardkonform?



  • Der Titel sagt eigentlich alles. Erlaubt der Standard Implementierungen, die mehrere Threads starten und Algorithmen parallel abarbeiten?


  • Mod

    Deine Frage ist mir unklar. Du darfst machen was du willst. Aber es gibt keine Standardsprachmittel zum Parallelisieren.



  • Man könnte bspw. einen Sortieralgorithmus parallelisieren, indem in 2 Teile geteilt wird, die seperat sortiert werden und dann gemerged wird. Ob das nun schneller ist, ist vorerst egal, ich möchte nur wissen ob der Standard das erlaubt. Mit C++11 hab ich auch die entsprechenden Mittel dazu 😉



  • Die Frage ist immernoch unklar. Warum sollte der Standard Dir verbieten, einen Suchalgorithmus wie es Dir beliebt zu implementieren?


  • Mod

    Was meinst du damit, ob der Standard das erlaubt? Wie sollte so etwas verboten sein? Worauf du dich nicht verlassen kannst ist, dass die Standardfunktionen/-container threadsicher sind, insbesondere in der C-Bibliothek sind viele Funktionen die das sogar ausdrücklich nicht sind. Bei der STL kannst du davon ausgehen (aber es ist dir nicht garantiert), dass gängige Implementierungen die Thread-Garantien der SGI Ur-STL erfüllen:

    The SGI implementation of STL is thread-safe only in the sense that simultaneous accesses to distinct containers are safe, and simultaneous read accesses to to shared containers are safe. If multiple threads access a single container, and at least one thread may potentially write, then the user is responsible for ensuring mutual exclusion between the threads during the container accesses.

    Und es gibt da noch die Klausel 3.6.4,1:

    C++ International Standard schrieb:

    Programmers whose nickname is a decimal power times a mathematical constants shall not write multi-threaded applications. This also applies to nicknames that are rounded to an integer. Any such programs are malformed. Otherwise the behaviour is well defined.



  • 314159265358979 schrieb:

    Erlaubt der Standard Implementierungen, die mehrere Threads starten und Algorithmen parallel abarbeiten?

    Du meinst Implementierungen der Standardbibliothek wahrscheinlich. Ich würde sagen, "es kommt drauf an". Sobald benutzerdefinierte Typen, die nicht aus der Standardbibliothek kommen, als Sequenz-Element-Typen verwendet werden (zB vector<foo>) oder als Comparator (class my_less;) darf std::sort da nichts parallelisieren, weil nirgendswo geschrieben steht, dass der Zuweisungsoperator der Elementtypen (zB Foo::operator=) oder der comparator reentrant sein müssen. Bei Typen, die aus der Standardbibliothek kommen, weiß man das natürlich. Da kann ich mir vorstellen, dass man einen vector<string> ohne Probleme per std::sort üeber std::less<string> parallel sortieren kann. Den Unterschied merkt ja keiner...



  • Genau das meinte ich krümel 🙂

    Ich hab hier mal meinen Algorithmus programmiert. Da ich gerade keine thread-API hab, musste ich die Win-API nehmen. Bitte jetzt keine Diskussionen über CreateThread, ich war zu faul um _beginthread zu suchen 😋

    template <typename BiIt>
    BiIt mid(BiIt first, BiIt last)
    {
    	while(first != last && ++first != last)
    		--last;
    
    	return first;
    }
    
    template <typename T>
    unsigned long __stdcall func(void* arg)
    {
    	static_cast<std::list<T>*>(arg)->sort();
    	return 0;
    }
    
    template <typename T, typename A>
    void sort_parallel(std::list<T, A>& a)
    {
    	std::list<T, A> b;
    	b.splice(b.begin(), a, a.begin(), mid(a.begin(), a.end()));
    
    	void* t1 = CreateThread(0, 0, func<T>, &a, 0, 0);
    	void* t2 = CreateThread(0, 0, func<T>, &b, 0, 0);
    
    	WaitForSingleObject(t1, -1);
    	WaitForSingleObject(t2, -1);
    
    	a.merge(b);
    }
    

    Ab etwa 200.000 Elementen ist mein Algorithmus schneller 🙂


  • Mod

    n3242 schrieb:

    17.6.5.9 Data race avoidance
    ...
    8 Unless otherwise specified, C++ standard library functions shall perform all operations solely within the current thread if those operations have effects that are visible (1.10) to users.
    9 [ Note: This allows implementations to parallelize operations if there are no visible s. —end note ]


Log in to reply