C++ ExPolicy par_unseq bei sort mit Lambda Funktion sicher?

[T_55]

Hallo,

kurze Frage, wäre folgende Zeile sicher?

struct struct_a
{
   double var1;
   int var2;
   std::string var3;
};
// vector sortieren (nach einem Member des Structs):
std::sort(std::execution::par_unseq, v.begin(), v.end(), [](const struct_a &x, const struct_a &y) -> bool {return x.var1 < y.var1);

Diese Lambda Funktion ist nicht von mir, ich sehe da nur den Vergleich, keine Zähler o.ä., weiß aber natürlich nicht was std::sort genau da treibt im parallel mode, daher die Frage ob man die Zeile so beruhigt mit par_unseq nutzen kann?
Zu par_unseq liest man über die Gefahr von data races oder deadlocks. Ich hab die Zeile bisher nur sequenziell genutzt und schaue mir gerade das Thema std::execution mit par und par_unseq das aller erste mal an (was ab C++17 auch viele andere Algos betrifft). Anhand dieses Beispiels hab ich mal das par_unseq ergänzt zum Testen (das es nicht unbedingt zu schnellerer Ausführung kommen muss (gerade bei wenig Daten), ist mir klar (Threads kosten))

Grüße

 

[Tornhoof]

Kommt auf die Implementierung des comparison Ops des struct an. Wenn da drin vector -unsafe code drin steht, dann ist's nicht safe. Also zb einer mit mutexen oder ähnlichem spielt.

 

[T_55]

Verstehe nicht ganz der "comparison Op" ist doch in der Lambda Funktion. Ein Hilfsstruct mit operator() drin ist da nicht nötig. Das Struct hätte nur einfach ein paar Variablen drin, hab oben noch ein Beispiel-Struct hinzugefügt.

 

[Tornhoof]

Naja, du vergleichst x.var1 mit y.var1. was passiert also wenn der Typ von var1 den op überlädt?

In deinem Beispiel wär's sicher, da ist er double

 

[T_55]

Alles klar, dann merke ich mir das mal in etwa so, wenn nichts in/dekrementiert wird, kein lock_guard und sowas dann ist es ok bzw. bei unseq verbieten sich "vectorization-unsafe" Funktionen welche, wie ich es mit meinem Halbwissen verstehe, alle Funktionen sind, die sich mit einer anderen Funktion synchronisieren könnten (wobei da atomics wohl eine Ausnahme bilden...). Nicht gerade trivial das ganze 😅 Hier wird das auch diskutiert:
https://stackoverflow.com/questions...tween-execution-policies-and-when-to-use-them
https://stackoverflow.com/questions/59601859/par-unseq-and-vectorization-unsafe-functions
ps: ist denn std::sort selber "vectorization-safe", dort werden Daten hin und hergeschoben/getauscht, der Ort wo hingeschoben wird muss zb auch irgendwie gelockt werden, dass kein anderer gerade dort was hinschiebt.

 

[striker159]

Es gibt natürlich nur eine Spezialisierung eines Algorithmus für par_unseq, wenn er auch korrekt arbeiten kann, solange der Nutzer die Bedinungen für die Argumente berücksichtigt. Ansonsten wird der Standardalgorithmus als Fallback benutzt. Dahere macht die Frage, ob std::sort "vectorization-safe" ist nicht so viel Sinn.

Für einen parallel sort mit custom comparator könnte zb ein parallel merge sort implementiert sein. Ein Array mit integers ließe sich mit einem parallel radix sort sortieren.

Mit dem nvc++ compiler von nvidia gibt es auch die Möglichkeit, die GPU zum parallelisieren zu benutzen anstatt multi-threading. In der Doku dazu werden auch nochmal die Bedinungen genannt, die zur korrekten Nutzung der execution policies erforderlich sind. https://docs.nvidia.com/hpc-sdk/compilers/c++-parallel-algorithms/index.html


When you use an execution policy other than std::execution::seq, you are communicating two important things to the compiler:

• You prefer but do not require that the algorithm be run in parallel. A conforming C++17 implementation may ignore the hint and run the algorithm sequentially, but a high-quality implementation takes the hint and executes in parallel when possible and prudent.
• The algorithm is safe to run in parallel. For the std::execution:ar and std::execution:ar_unseq policies, any user-provided code—such as iterators, lambdas, or function objects passed into the algorithm—must not introduce data races if run concurrently on separate threads. For the std::execution:ar_unseq policy, any user-provided code must not introduce data races or deadlocks if multiple calls are interleaved on the same thread, which is what happens when a loop is vectorized. For more information about potential deadlocks, see the forward progress guarantees provided by the parallel policies or watch CppCon 2018: Bryce Adelstein Lelbach “The C++ Execution Model”.