Fehler bei Parallel.For-Implementierung ??

Luccas · Verfasst: Di 23.08.16 18:28

Hallo zusammen

Mein nächstes Problem :wink:

Probiere gerade Parallel.For und habe dazu folgendes, kleines Musterprogrämmchen:

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

            int Anzahl = 0;
            Random Zufall = new Random();
            var AnzKerne = new ParallelOptions { MaxDegreeOfParallelism = 4 };  // anzahl kerne
            Parallel.For(1, 101, AnzKerne, (i, option) =>
            {
                Console.WriteLine("ZZahl Nr: {0} = {1}", i, Zufall.Next());
                Anzahl++;
                if (i == 50)
                    option.Stop();                // vorzeitiger abbruch
            });
            Console.Write("\n\t Anzahl Zufallszahlen: {0}", Anzahl);

Das Programm soll genau 100 Zufallszahlen generieren und nach der 50. Zufallszahl vorzeitig abbrechen.

Leider funktioniert es nicht wie erwartet. Folgende "Merkwürdigkeiten" treten auf:

1. Es wird eine willkürliche Anzahl von Zufallszahlen erzeugt, so ziemlich jede Anzahl zwischen 37 und 100 (viele Tests)
2. Das Programm stoppt nicht nach der Erzeugung der 50. Zufallszahl sondern läuft bis maximal 100 hoch.
3. Nur bei expliziter Vorgabe von genau einem ( = 1) Kern, läuft das Programm korrekt.

Zusatzhinweis: Eine Verzögerung im Main-Thread bringt auch keine Verbesserung.
Die Pflicht zum "Einbau" eines wait() (oder analoges) habe ich auch nirgends entdecken können.

Dass hier eine Compiler-Anomalie vorliegt, ist ja wohl kaum anzunehmen.
Was mache ich falsch?

Gruss
Luccas

papa69 · Verfasst: Di 23.08.16 18:43

Hi,

ohne mich jetzt mit paraller Programmierung auszukennen un deinen Code zu zerlegen:
Aber:

prüfe doch mal in Zeile 9 auf

if (Anzahl == 50)

(Verständnisfrage: Wird i irgendwie instanziiert/deklariert, und wie wir i erhöht?)

Edit: Die Frage mit dem i hat sich nach Recherche geklärt! ;-)

_________________
Daniel Bauer
... fatal ist nur, wenn sich das Licht am Ende des Tunnels als entgegenkommender ICE entpuppt ...

Th69 · Verfasst: Di 23.08.16 18:50

Hallo,

Stop setzt intern nur ein Flag (IsStopped), um keine neue Iteration anzufangen, aber beendet nicht sofort die gesamte For-Schleife - steht auch unter ParallelLoopState.Stop-Methode. Dort im Beispiel wird dann noch zusätzlich auf dieses Flag geprüft.
Also bei deinem Code:

markieren

C#-Quelltext

1:
2:
3:
4:

if (!option.IsStopped)
{
  // bisheriger Code der For-Methode
}

PS: papa69 hat natürlich Recht damit, daß du auf Anzahl == 50 prüfen solltest, denn wenn du die Stop-Methode in der 50. Iteration abbrichst, kann (und wird es in den meisten Fällen) auch so sein, daß die anderen Threads ja noch weiterlaufen und den Anzahl-Wert erhöhen.
Ich würde also eher es so programmieren:

markieren

C#-Quelltext

1:
2:
3:
4:

if (Anzahl < 50)
  Anzahl++;
else
  option.Stop();

Die Frage ist aber natürlich, warum willst du 100 Zufallszahlen generieren, aber trotzdem bei der 50. vorzeitig abbrechen, anstatt einfach nur 50 Zufallszahlen zu erzeugen (Edit: OK - schreibst ja, daß du nur die Parallel.For-Methode ausprobieren willst)?

jfheins · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

Der Vorteil an einer Parallelen for-Schleife ist doch gerade, dass die Iterationen voneinander unabhängig sind.

Das heißt, deine 100 Iterationen laufen auf einem (hypotetischen) 100 Kern-Prozessor u.U. tatsächlich alle gleichzeitig ab. Wenn du MaxDegreeOfParallelism = 4 setzt, beschränkst du zwar die Anzahl der Threads, du bekommst aber nach wie vor keine Garantie, in welcher Reihenfolge die Iterationen ablaufen.

Mit dieser Info sollte dich das Ergebnis auch nicht überraschen:

Zitat:

1. Es wird eine willkürliche Anzahl von Zufallszahlen erzeugt, so ziemlich jede Anzahl zwischen 37 und 100 (viele Tests)

Das kommt eben ganz drauf an, zu welchem Zeitpunkt die Iterationen wirklich ausgeführt werden. Bei 100 kann es sein, dass der Therad mit der 50. Iteration gerade kurz unterbrochen wurde. Alle anderen Threads haben dann die restlichen Iterationen abgearbeitet und dann kam erst der Stop()-Aufruf

Zitat:

2. Das Programm stoppt nicht nach der Erzeugung der 50. Zufallszahl sondern läuft bis maximal 100 hoch.

Aus der Doku:

Zitat:

Calling Stop informs the for loop that it may abandon all remaining iterations, regardless of whether they're before or after the current iteration, because all required work will have already been completed. However, as with Break, there are no guarantees regarding which other iterations will not execute.

Du sagst damit lediglich an, dass alle weiteren Iterationen sinnlos sind und nicht durchgeführt werden sollen. Wieviele und welche Iterationen bis dahin durchgelaufen sind, ist ein Implementierungsdetail das dir egal sein sollte.

Zitat:

3. Nur bei expliziter Vorgabe von genau einem ( = 1) Kern, läuft das Programm korrekt.

Wel es dann nicht mehr parallel abläuft.

Ergo: Falsl für dich die reale Reihenfolge der Iterationen wichtig ist, solltest du sie nicht Parallel ablaufen lassen. Wenn die Interationen voneinander unabhängig sind (also nur von i abhängen) dann kannst du es machen.

Christian S. · Beiträge: 20451 Erhaltene Danke: 2264 Win 10 C# (VS 2019)

Hallo,

die Instanzmethoden der Random-Klasse sind übrigens auch nicht thread-safe: The System.Random class and thread safety.

Sieht man auch sehr gut im Quelltext: Quelltext der Next- bzw. der davon aufgerufenen InternalSample-Methode

Generell habe ich in der Praxis keine gute Erfahrung damit gemacht, Zufallszahlen multi-threaded zu erzeugen.

Grüße
Christian

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".

Palladin007 · Verfasst: Di 23.08.16 20:29

Zitat:

Generell habe ich in der Praxis keine gute Erfahrung damit gemacht, Zufallszahlen multi-threaded zu erzeugen.

Ist auch völlig überflüssig
10 Million Zufallszahlen zu generieren dauert im Schnitt 154,6 Millisekunden. Hab 100 mal gemessen.

Allerdings wollte Luccas ja nur ausprobieren
Von daher wird dieser Thread wohl hoffentlich den einen oder anderen Aha-Effekt ausgelöst haben und das kleine Test-Programm hat sich damit gelohnt ^^

Parallel ist für etwas gedacht, wo mehrere lang andauernde Aufgaben unabhängig voneinander laufen können.
Es lässt dann (im Idealfall) jede Aufgabe in einem eigenen Thread laufen.
Solange die Aufgaben threadsave sind und nicht auf sowas wie die Festplatte zurück greifen, kann dadurch ein deutlicher Performance-Vorteil erreicht werden.

Luccas · Verfasst: Mi 24.08.16 12:23

Hallo zusammen

Vielen Dank für die schnellen Antworten.

Es ging tatsächlich nur um ein einfaches Beispiel ohne tieferen Sinn. Ich lerne an einfachen Beispielen immer am besten (hier eben Zufallszahlen erzeugen). Nach Euren Antworten habe den Quellcode wie folgt geändert:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

            int Anzahl = 0;
            Random Zufall = new Random();
            var AnzKerne = new ParallelOptions { MaxDegreeOfParallelism = 4 };  // anzahl kerne
            Parallel.For(1, 101, AnzKerne, (i, option) =>
            {
                Console.WriteLine("ZZahl Nr: {0} = {1}", i, Zufall.Next());
                Anzahl++;
                if (Anzahl == 50)
                {
                    option.Stop();                // vorzeitiger abbruch
                    return;
                }
                //if (option.IsStopped)
                //    return;
            });
            Console.Write("\n\t Anzahl Zufallszahlen: {0}", Anzahl);

Jetzt funktioniert es, jedenfalls in vertretbaren Rahmen:
1. Es war mit klar, dass es parallele Abläufe erzeugt. Womit ich nicht (naiverweise) gerechnet hatte, ist, dass Parallel.For
seine eigene Iterationsvariable i nicht sequenziell bedient (zeigt sich aber in der sprunghaften Monitorausgabe), d.h. i zeigt
praktisch den gerade ausgeführten Lauf aus den parallelen Läufen an.
2. Die "globale" Variable Anzahl wird - im Prinzip (s. 4.) - korrekt bedient. Daher habe ich sie als Abbruchkriterium genommen.
3. Die Terminierung ist mit oder ohne "IsSopped" gleich, aber mit ist mir doch sicherer.
4. Merkwürdig bleibt: für jeden zusätzlich Kern wird eine Zufallszahl mehr erzeugt:
1 Kern -> 50 (logisch)
2 Kerne -> 51 usw.
8 Kerne -> 57

d.h. für jeden zusätzlichen Kern wird noch ein Lauf "drangehängt". Ist aber nach meiner Recherche ein bekanntes Phänomen.
(Text von jfheins)
Ich betrachte damit das Problem für gelöst, habe aber noch ein anderes mit dem angeblichen Effizienzgewinn von Parallel.For,
der sich aber partout nicht einstellen will. Ich weiß aber nicht, ob meine Fragen dem Boardmitgliedern langsam auf den Wecker gehen.

Gruss
Luccas

Palladin007 · Verfasst: Mi 24.08.16 13:21

Dass mit jedem Kern mehr "falsche" Durchläufe dazu kommen, ist nur logisch, dass es genau ein Durchlauf ist, ist aber denke ich keine feste Regel.

Du musst das so verstehen:
Nehmen wir an, Du hast 4 Kerne eingestellt. Diese 4 Kerne können 100% eigenständig arbeiten, es gibt also keine Einflüsse, die einen Thread beeinträchtigen.
Außerdem gehen wir davon aus, dass das Anstoßen eines Threads und der zusätzliche Aufwand in der For-Methode zum Starten genau eine Sekunde dauert.
Das generieren einer Zufallszahl soll ebenfalls eine Sekunde dauern, während die Prüfung, ob abgebrochen werden soll, auch eine Sekunde dauert.
Alle weiteren Abläufe sollen der Einfachheit mal außenvor bleiben.

Dadurch entsteht pro Kern folgender Ablauf:
Die For-Methode starten den neuen Thread und benötigt dafür eine Sekunde
Der Thread selber benötigt zwei Sekunden zum generieren der Zahl und für die Prüfung, ob abgebrochen werden soll
Der Thread endet damit 3 Sekunden nach dem Beginn des Startes des Threads in der For-Methode

Für die ersten vier Zahlen ergibt sich dann folgendes Muster:
Zahl 1 wird auf Kern 1 generiert. Start: 0, Start des Threads: 1, Ende: 3
Zahl 2 wird auf Kern 2 generiert. Start: 1, Start des Threads: 2, Ende: 4
Zahl 3 wird auf Kern 3 generiert. Start: 2, Start des Threads: 3, Ende: 5
Zahl 4 wird auf Kern 4 generiert. Start: 3, Start des Threads: 4, Ende: 6
Grund, weshalb das so aussieht: Die For-Methode muss intern jeden Thread anstoßen und läuft dabei selber synchron. Das Starten eines Threads kostet Zeit.
Wenn Thread 4 gestartet wird, wurden vorher schon 3 andere Threads vorher gestartet.

Wenn nun nur drei Zahlen generiert werden sollen, dann wird im Thread, der auf Kern 3 läuft, das Flag gesetzt, dass der Vorgang abgebrochen werden soll.
Dieser Thread startet ab Sekunde 2 seine Arbeit, generiert eine Sekunde die Zahl und prüft darauf noch eine Sekunde, ob abgebrochen werden soll.
Tatsächlich steht also erst während Sekunde 4 fest, dass abgebrochen werden soll, zu dem Zeitpunkt wurde das Generieren der Zahl 4 aber schon gestartet und kann nicht mehr abgebrochen werden.

So ungefähr sieht der theoretische Ablauf in einer minimalisierten Umgebung ohne andere Einflüsse aus.
In Echt kommen aber noch andere Einflüsse dazu, wie z.B. das Windows, das gerne auch mal etwas Zeit auf einem Kern haben will - bzw. es nimmt sie sich einfach, dein Zahlen-Generier-Thread muss dann einfach warten. Wenn dieser Thread, der warten soll, der für Zahl 3 ist, dann dauert es noch länger, bis das Stoped-Flag gesetzt wird und es startet sogar der Thread für Zahl 5.

Aus diesem Grund ist dein Vorhaben nicht möglich, egal wie Du es versuchst.

Zitat:

[...] habe aber noch ein anderes mit dem angeblichen Effizienzgewinn von Parallel.For, der sich aber partout nicht einstellen will.

Wie sieht das Problem aus?
Der Vorteil stellt sich nur ein, wenn jeder einzelne Ablauf vollständig eigenständig auf einem Kern arbeiten kann und auch so lange dauert, dass es messbar ist.
Um die Beschreibung von oben aufzugreifen und zu sagen, dass das Generieren der Zahl 10 Sekunden dauert, dann sieht das so aus:

Zahl 1 wird auf Kern 1 generiert. Start: 0, Start des Threads: 1, Ende: 11
Zahl 2 wird auf Kern 2 generiert. Start: 1, Start des Threads: 2, Ende: 12
Zahl 3 wird auf Kern 3 generiert. Start: 2, Start des Threads: 3, Ende: 13
Zahl 4 wird auf Kern 4 generiert. Start: 3, Start des Threads: 4, Ende: 14

Die letzte Zahl wurde hier also bei Sekunde 14 generiert.
Machst Du das nicht parallel, dann fällt der Aufwand in der For-Methode für das Starten eines Threads zwar weg, das Generieren der Zahl dauert trotzdem 10 Sekunden, was bedeuten würde, dass der ganze Vorgang nicht 14, sondern 40 Sekunden dauert.

So zumindest mein Verständnis davon.
Ich hab die For-Methode jetzt nicht auseinander genommen, aber vielleicht hat ja noch jemand eine Korrektur, wenn notwendig.

Palladin007 · Verfasst: Mi 24.08.16 14:14

Ich hab mal ein kleines Konsolen-Programm geschrieben, was das hoffentlich etwas besser veranschaulicht.
Vor dem Parallel-For-Aufruf starte ich eine Stopwatch.
Jeder einzelne Durchlauf greift zu Beginn die Zeit von der Stopwatch ab, wartet 10 Millisekunden und greift erneut die Zeit ab. Anschließend schreibt es die Zeit in ein Array.
Ich messe 20 Durchläufe, von 1 bis 4 Kernen jeweils einmal.
Die Durchläufe sind nach dem Index, den ich von der For-Methode bekomme, sortiert.
Ich habe vier logische Kerne.
Die Test fand nicht im Debug-Mode statt, ich habe die Exe direkt gestartet.

Quellcode gibt's unten.

Zitat:

MaxDegreeOfParallelism = 1
Test start at 0ms
Run on Thread # 1: Start at 6ms, End at 17ms
Run on Thread # 1: Start at 17ms, End at 27ms
Run on Thread # 1: Start at 27ms, End at 37ms
Run on Thread # 1: Start at 37ms, End at 48ms
Run on Thread # 1: Start at 48ms, End at 59ms
Run on Thread # 1: Start at 59ms, End at 70ms
Run on Thread # 1: Start at 70ms, End at 81ms
Run on Thread # 1: Start at 81ms, End at 93ms
Run on Thread # 1: Start at 93ms, End at 103ms
Run on Thread # 1: Start at 103ms, End at 114ms
Run on Thread # 1: Start at 114ms, End at 124ms
Run on Thread # 1: Start at 124ms, End at 135ms
Run on Thread # 1: Start at 135ms, End at 146ms
Run on Thread # 1: Start at 146ms, End at 157ms
Run on Thread # 1: Start at 157ms, End at 168ms
Run on Thread # 1: Start at 168ms, End at 179ms
Run on Thread # 1: Start at 179ms, End at 190ms
Run on Thread # 1: Start at 190ms, End at 201ms
Run on Thread # 1: Start at 201ms, End at 212ms
Run on Thread # 1: Start at 212ms, End at 223ms
Test end at 223ms
==========

MaxDegreeOfParallelism = 2
Test start at 0ms
Run on Thread # 1: Start at 0ms, End at 10ms
Run on Thread # 1: Start at 10ms, End at 21ms
Run on Thread # 1: Start at 21ms, End at 32ms
Run on Thread # 1: Start at 32ms, End at 43ms
Run on Thread # 1: Start at 43ms, End at 54ms
Run on Thread # 1: Start at 54ms, End at 65ms
Run on Thread # 1: Start at 65ms, End at 76ms
Run on Thread # 1: Start at 77ms, End at 87ms
Run on Thread # 1: Start at 87ms, End at 98ms
Run on Thread # 1: Start at 98ms, End at 109ms
Run on Thread # 3: Start at 0ms, End at 10ms
Run on Thread # 3: Start at 10ms, End at 21ms
Run on Thread # 3: Start at 21ms, End at 32ms
Run on Thread # 3: Start at 32ms, End at 43ms
Run on Thread # 3: Start at 43ms, End at 54ms
Run on Thread # 3: Start at 54ms, End at 65ms
Run on Thread # 3: Start at 65ms, End at 76ms
Run on Thread # 3: Start at 76ms, End at 87ms
Run on Thread # 3: Start at 87ms, End at 98ms
Run on Thread # 3: Start at 98ms, End at 109ms
Test end at 110ms
==========

MaxDegreeOfParallelism = 3
Test start at 0ms
Run on Thread # 1: Start at 0ms, End at 10ms
Run on Thread # 1: Start at 10ms, End at 21ms
Run on Thread # 1: Start at 21ms, End at 32ms
Run on Thread # 1: Start at 32ms, End at 43ms
Run on Thread # 1: Start at 43ms, End at 54ms
Run on Thread # 1: Start at 54ms, End at 65ms
Run on Thread # 5: Start at 0ms, End at 11ms
Run on Thread # 5: Start at 11ms, End at 22ms
Run on Thread # 5: Start at 22ms, End at 33ms
Run on Thread # 5: Start at 33ms, End at 44ms
Run on Thread # 5: Start at 44ms, End at 55ms
Run on Thread # 5: Start at 55ms, End at 66ms
Run on Thread # 3: Start at 0ms, End at 11ms
Run on Thread # 3: Start at 11ms, End at 22ms
Run on Thread # 3: Start at 22ms, End at 33ms
Run on Thread # 3: Start at 33ms, End at 44ms
Run on Thread # 3: Start at 44ms, End at 55ms
Run on Thread # 3: Start at 55ms, End at 66ms
Run on Thread # 1: Start at 65ms, End at 76ms
Run on Thread # 1: Start at 76ms, End at 86ms
Test end at 86ms
==========

MaxDegreeOfParallelism = 4
Test start at 0ms
Run on Thread # 1: Start at 0ms, End at 11ms
Run on Thread # 1: Start at 11ms, End at 22ms
Run on Thread # 1: Start at 22ms, End at 33ms
Run on Thread # 1: Start at 33ms, End at 44ms
Run on Thread # 1: Start at 44ms, End at 55ms
Run on Thread # 5: Start at 0ms, End at 11ms
Run on Thread # 5: Start at 11ms, End at 22ms
Run on Thread # 5: Start at 22ms, End at 33ms
Run on Thread # 5: Start at 33ms, End at 44ms
Run on Thread # 5: Start at 44ms, End at 55ms
Run on Thread # 4: Start at 0ms, End at 11ms
Run on Thread # 4: Start at 11ms, End at 22ms
Run on Thread # 4: Start at 22ms, End at 33ms
Run on Thread # 4: Start at 33ms, End at 44ms
Run on Thread # 4: Start at 44ms, End at 55ms
Run on Thread # 3: Start at 0ms, End at 11ms
Run on Thread # 3: Start at 11ms, End at 22ms
Run on Thread # 3: Start at 22ms, End at 33ms
Run on Thread # 3: Start at 33ms, End at 44ms
Run on Thread # 3: Start at 44ms, End at 55ms
Test end at 55ms

Ich denke, da kann man in erster Linie folgende Dinge sehr deutlich erkennen:

Die Abläufe werden auf die verfügbaren parallelen Abläufe aufgeteilt. Durchläufe, die keinen Platz fanden, werden später erneut angestoßen, wie man bei Test 3 gut sieht.
Ein späterer Durchlauf kann deutlich früher als ein früherer Durchlauf enden.
Es kann eine echte Parallelität erreicht werden. Besonders gut sichtbar ist es bei Test 2 und 4, wo die Durchläufe vollständig parallel sind. Unterschiede unterhalb einer Millisekunde nicht beachtet
Die Performance-Verbesserung ist nicht immer gleichmäßig. Bei Test 3 muss später einer der drei Threads erneut gestartet werden, was einen geringeren Performance-Anstieg im Vergleich zu Test 2 und 4 bringt.

Ich schreibe nochmal extra dazu: Die Tests fanden nicht im Debug-Mode statt, da der Debugger die Tests deutlich verfälscht hat.

Der Source zu dem Test:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:

static void Main(string[] args)
{
    for (int i = 1; i <= 4; i++)
    {
        Console.WriteLine();
        Console.WriteLine($"MaxDegreeOfParallelism = {i}");
        StartTest(i);
        Console.WriteLine(new string('=', 10));
    }

    Console.ReadKey();
}

private static void StartTest(int maxDegreeOfParallelism)
{
    var watch = new Stopwatch();

    var threadInfoStrings = Enumerable.Range(0, 20).Select(i => "").ToArray();

    watch.Start();
    Console.WriteLine($"Test start at {watch.ElapsedMilliseconds}ms");
    var options = new ParallelOptions()
    {
        MaxDegreeOfParallelism = maxDegreeOfParallelism
    };
    Parallel.For(0, threadInfoStrings.Length, options, i =>
    {
        TimeSpan startTime, endTime;

        startTime = watch.Elapsed;
        Thread.Sleep(10);
        endTime = watch.Elapsed;

        threadInfoStrings[i] += $"Run on Thread #{Thread.CurrentThread.ManagedThreadId,3}: Start at {startTime.Milliseconds,5}ms, End at {endTime.Milliseconds,5}ms";
    });
    watch.Stop();

    foreach (var item in threadInfoStrings)
    {
        Console.WriteLine(item);
    }
    Console.WriteLine($"Test end at {watch.ElapsedMilliseconds}ms");
}

Luccas · Verfasst: Mi 24.08.16 16:46

Hallo Palladin

Super Beispiel. Hab es kopiert, gestartet und liefert praktisch exakt die gleichen Zeiten wie in Deinem Muster.
Auf meinem System gab es keinen Unterschied zwischen Debug-Lauf und Exe-Lauf. Die Laufzeiten waren praktisch identisch.

vielen Dank noch mal allen - wieder was gelernt

Für mein nächste Laufzeitproblem mache ich ein neues Thema auf.

Gruss
Luccas

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme