[X] Parallelisierung mit .NET 4.0 - Teil II
-
Parallelisierung mit .NET 4.0 - Teil 2
Inhalt:
- 1 Kurzer Abriss von LINQ
- 2 Grundlegendes zu Parallel LINQ
- 3 Ordnung halten
- 4 Parallele Abfragen abbrechen
- 5 Ausführungsmodi von Parallel LINQ
- 6 Partitioner verwenden
- 7 Schlussbemerkung
1 Kurzer Abriss von LINQ
LINQ (Language Integrated Query) ist eine flexible und mächtige Abfragesprache, die es seit der Version 3.0 im .NET Framework gibt. Die am Häufigsten verwendete Variante ist vermutlich LINQ to Objects (Namensraum System.Linq), die es dem Programmierer erlaubt, LINQ auf Arrays, Listen usw. anzuwenden bzw. auf alles, dass die Schnittstelle IEnumerable btw. IEnumerable<T> (Namensraum System.Collections.Generic) implementiert. Andere Varianten sind LINQ to XML (Namensraum System.Xml.Linq), LINQ to SQL und LINQ to ADO.NET (beide im Namensraum System.Data.Linq). Syntaktisch sind alle Varianten identisch, nur der Provider (also die Engine, die die Abfragen dann auf die Datenquellen ausführt) ist ein anderer.
LINQ to Objects wird Hauptgegenstand dieses Artikels sein und immer wenn von LINQ gesprochen wird, ist damit LINQ to Objects gemeint.
Um LINQ zu realisieren, waren erhebliche Erweiterungen des .NET Frameworks notwendig. Dazu gehören Erweiterungsmethoden, Lambda-Ausdrücke, Typinferenz und anonyme Typen. Die definierten Erweiterungsmethoden befinden sich in der Klasse Enumerable. Beispiele sind Aggregate, Max, Min, Sum, Reverse, Any, OfType, Take, Skip, Union, Zip, Select, Where und OrderBy. Es gibt noch eine ganze Reihe anderer Erweiterungsmethoden, die meistens mehrfach überladen sind. Beispielsweise gibt es die Erweiterungsmethode Sum in einer grundlegenden, parameterlosen Variante, die numerische Elemente einer Liste mit dem + operator aufzusummiert. Man kann der Methode aber auch ein Delegate mitgeben, das die auzuführende Summierungsoperation definiert.
Wer beim Durchlesen der Erweiterungsmethoden ein Gefühl der Vertrautheit verspürt und sich denkt: "Hey, das habe ich doch in der funktionalen Sprache xyz schon gesehen!", der liegt nicht falsch. In der Tat stand das .NET Framework 3.0 unter dem Stern der funktionalen Programmierung, was sich hier u.a. mit LINQ niederschlägt.
Den einen oder anderen dürfte es aber überraschen, dass IEnumerable bzw. IEnumerable<T> lazy sind. Auch werden LINQ Abfragen erst dann ausgeführt, wenn das Ergebnis tatsächlich benötigt wird.Also, wie sieht LINQ aus?
using System; using System.Linq; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { //Generiere Zahlen von 0-99 var numbers = Enumerable.Range(0, 100); //Selektiere nur die geraden Zahlen mit LINQ - Abfragesyntax var onlyEven = from n in numbers where n % 2 == 0 select n; //Alternative Schreibweise mit Erweiterungssyntax: //var onlyEven = numbers.Where(n => n % 2 == 0).Select(n => n); //Erst hier wird die Abfrage tatsächlich ausgeführt, da das Ergebnis benötigt wird foreach (var n in onlyEven) Console.Out.Write(n + " "); } } }
Der Code erinnert noch stark an SQL, nur dass
select
undfrom
vertauscht wurden (das ermöglicht u.a. IntelliSense für den select-Teil).
Aber LINQ kann auch anders aussehen:var numbers = Enumerable.Range(0, 100); //Generiere Zahlen von 0-99 var squares = numbers.Select(n => n * n); //Quadriere alle Zahlen var primeGroup = numbers.GroupBy(n => IsPrime(n)); //Gruppiere nach Primzahlen/Nicht-Primzahlen foreach (var groups in primeGroup) { if (groups.Key) Console.Out.WriteLine("These numbers are primes:"); else Console.Out.WriteLine("These numbers aren't primes:"); foreach (var num in groups) Console.Out.WriteLine(num); Console.Out.WriteLine(); }
Wer Haskell kennt, den erinnert der Select-Aufruf im letzten Beispiel vermutlich stark an map. Und auch wenn hier keine heroischen Taten vollbracht werden, so deutet sich schon an, dass LINQ ein sehr mächtiges Werkzeug ist, dass zudem äußerst elegant ist.
Das soll es zum reinen LINQ aber auch gewesen sein, schließlich wollen wir uns eigentlich Parallel LINQ widmen. Dieser Abschnitt diente nur als Appetitanreger bzw. als Wiederauffrischung. Für den Rest des Artikels wird angenommen, dass man C# und LINQ beherrscht. Idealerweise hat man auch den ersten Teil gelesen, da es einige Überschneidungen und Déjà-vu-Effekte gibt.2 Grundlegendes zu Parallel LINQ
Um die parallele Ausführung von LINQ zu ermöglichen, wurde die Klasse System.Linq.ParallelEnumerable eingeführt. Diese Klasse enthält alle Erweiterungsmethoden der Enumerable-Klasse und zusätzlich einige Erweiterungsmethoden, welche die Parallelisierung unterstützen.
Betrachten wir dieses - sequentielle - Beispiel:
using System; using System.Linq; namespace ConsoleApplication1 { class Program { static long fibonacci(long n) { if (n < 2) return n; else return fibonacci(n - 1) + fibonacci(n - 2); } static void Main(string[] args) { var numbers = Enumerable.Range(0, 40); var fibNums = from n in numbers select new { Num = n, Fib = fibonacci(n) }; foreach (var n in fibNums) Console.Out.WriteLine(n); } } }
Auf meinem (Core 2 Duo) System kann man ca. ab Num = 34 zuschauen, wie die Ergebnisse eintrudeln. Hier kann man doch bestimmt per Parallelisierung was rausholen, oder? Natürlich geht das:
using System; using System.Linq; namespace ConsoleApplication1 { class Program { static long fibonacci(long n) { if (n < 2) return n; else return fibonacci(n - 1) + fibonacci(n - 2); } static void Main(string[] args) { var numbers = Enumerable.Range(0, 40); //Dieses mal Aufruf von AsParallel var fibNums = from n in numbers.AsParallel() select new { Num = n, Fib = fibonacci(n) }; foreach (var n in fibNums) Console.Out.WriteLine(n); } } }
Alles was zu einer grundlegenden Parallelisierung nötig ist, ist der Aufruf von AsParallel. Dadurch sagen wir dem Compiler, dass wir
select
undfrom
aus der ParallelEnumerable-Klasse wollen.
Allerdings hat sich die Laufzeit nicht gerade extrem verbessert. Zudem kommen die Ausgaben jetzt später, aber dafür schlagartig gleich ein ganzer Haufen. Warum ist das so? Um das zu beantworten, muss erst die Funktionsweise von AsParallel erläutert werden.AsParallel teilt die Datenquelle (hier die Zahlen) in Segmente auf, verteilt die Elemente der Datenquelle auf die Segmente und führt dann die angegebene Operation mit parallelen Threads auf diese Segmente aus. Hierbei wird versucht, alle Kerne des Prozessors zu nutzen. Wie die Elemente der Datenquelle auf die Segmente verteilt werden, legt der Partitioner fest, siehe hierzu auch Abschnitt 6 bzw. Abschnitt 3.3 in Teil I.
Nachdem diese Threads durchgelaufen sind, müssen die Ergebnisse auch wieder zusammengeführt werden, damit man mit ihnen weiterarbeiten kann. Hierbei ist das Standardvorgehen, dass die Ergebnisse "blockweise" zur Verfügung gestellt werden, d.h. es werden n Ergebnisse gepuffert und dann zur Verarbeitung weitergereicht. Damit wäre die "blockartige" Ausgabeweise von unserem Programm erklärt. Abhilfe schafft die Erweiterungsmethode WithMergeOptions, der man einen Parameter vom Typ ParallelMergeOptions mitgibt. Hier bieten sich drei Optionen an:- NotBuffered - Ergebnisse werden sofort zur Verfügung gestellt
- AutoBuffered - Es werden n Ergebnisse gepuffert, die dann zur Verfügung gestellt werden
- FullyBuffered - Es werden alle Ergebnisse gepuffert und erst dann zur Verfügung gestellt
- Default - entspricht AutoBuffered
Bei der Ausführung ist FullyBuffered in der Regel am schnellsten, da hier nur ein einziges mal die Ergebnisse zur Verfügung gestellt werden. Dies muss bei NotBuffered natürlich n mal geschehen, weshalb es auch am langsamsten ist. AutoBuffered ist ein guter Mittelweg.
Ebenso sollte man beachten, dass bei Abfragen mit OrderBy-Klausel das NotBuffered- und AutoBuffered-flag ignoriert wird. Schließlich muss erst das gesamte Ergebnis vorliegen, damit es sortiert werden kann.Da wir aber ungeduldig sind, nicht sortieren müssen und unsere Ergebnisse gleich sehen wollen, ändern wir die Abfrage etwas ab:
var fibNums = from n in numbers.AsParallel().WithMergeOptions(ParallelMergeOptions.NotBuffered) select new { Num = n, Fib = fibonacci(n) };
Nun erhalten wir die Ergebnisse sofort und sie sind auch schon ein bisschen gemischt, bei mir sieht das bei einem Testlauf z.B. so aus:
{ Num = 0, Fib = 0 } { Num = 1, Fib = 1 } { Num = 2, Fib = 1 } { Num = 3, Fib = 2 } { Num = 4, Fib = 3 } { Num = 5, Fib = 5 } { Num = 6, Fib = 8 } { Num = 7, Fib = 13 } { Num = 17, Fib = 1597 } { Num = 8, Fib = 21 } { Num = 24, Fib = 46368 } { Num = 9, Fib = 34 } { Num = 27, Fib = 196418 } { Num = 10, Fib = 55 } { Num = 11, Fib = 89 } { Num = 12, Fib = 144 } { Num = 13, Fib = 233 } { Num = 14, Fib = 377 } { Num = 15, Fib = 610 } { Num = 16, Fib = 987 } { Num = 18, Fib = 2584 } { Num = 19, Fib = 4181 } { Num = 20, Fib = 6765 } { Num = 21, Fib = 10946 } { Num = 22, Fib = 17711 } { Num = 23, Fib = 28657 } { Num = 25, Fib = 75025 } { Num = 26, Fib = 121393 } { Num = 28, Fib = 317811 } { Num = 29, Fib = 514229 } { Num = 30, Fib = 832040 } { Num = 32, Fib = 2178309 } { Num = 31, Fib = 1346269 } { Num = 33, Fib = 3524578 } { Num = 34, Fib = 5702887 } { Num = 35, Fib = 9227465 } { Num = 36, Fib = 14930352 } { Num = 38, Fib = 39088169 } { Num = 37, Fib = 24157817 } { Num = 39, Fib = 63245986 }
Die Fibonacci-Zahlen für 17, 24 und 27 haben sich zu Beginn eingeschlichen und zeigen die Nebenläufigkeit. Auch am Ende werden die Zahlen teilweise in einer gemischten Reihenfolge ausgegeben... hier ackern mehrere Threads an der Berechnung.
Bleibt noch das Problem mit der Laufzeit der Abfrage. Messen wir mal, wie viel Geschwindigkeitszuwachs wir erhalten haben. Gemessen wird folgendermaßen:
using System; using System.Diagnostics; using System.Linq; namespace ConsoleApplication1 { class Program { static long fibonacci(long n) { if (n < 2) return n; else return fibonacci(n - 1) + fibonacci(n - 2); } static void Main(string[] args) { Stopwatch watch = new Stopwatch(); watch.Start(); var numbers = Enumerable.Range(0, 40); var fibNums = from n in numbers select new { Num = n, Fib = fibonacci(n) }; foreach (var n in fibNums) Console.Out.WriteLine(n); watch.Stop(); Console.Out.WriteLine("Elapsed time in ms: " + watch.ElapsedMilliseconds); } } }
Hierbei ergibt sich auf meinem System eine Laufzeit von 3407 ms für die sequentielle Version. Bei der parallelisierten Version aus dem letzten Beispiel (mit NotBuffered) komme ich auf 2582 ms. Immerhin eine Reduktion der Laufzeit um 25% auf meinem "Doppelherz"-System Trotzdem sind mir 25% zu wenig, schließlich sollten theoretisch 50% möglich sein. Das werden wir zwar nicht ganz erreichen, aber wir wollen sehen wie nahe wir an diese magische Marke kommen.
Erinnern wir uns an den letzten Artikel und das Parallelisieren von for-Schleifen. Wir haben gesagt, man soll aufwändige zu verarbeitende Elemente möglichst am Anfang behandeln, damit der Scheduler die CPUs im Anschluss mit einfachen, kleinen Elementen gut auslasten kann und es keinen Leerlauf der CPUs gibt. Können wir dieses Konzept hier auch anwenden? Klar können wir, schließlich braucht die Fibonacci-Methode länger zur Berechnung, je höher die Eingabezahl ist. Mit der Erweiterungsmethode Reverse() drehen wir den Spieß herum:
var fibNums = from n in numbers.Reverse().AsParallel().WithMergeOptions(ParallelMergeOptions.NotBuffered) select new { Num = n, Fib = fibonacci(n) };
Neue Laufzeit auf meinem System: 1769 ms. Damit hätten wir fast eine Halbierung der ursprünglichen, sequentiellen Variante erreicht.
Wie viel würde es wohl ausmachen, wenn man FullyBuffered als MergeOption angibt? Bei mir reduziert sich die Laufzeit damit auf 1743 ms. Wenn man also ein bisschen auf die Ergebnisse warten kann, holt man hier noch ein klein wenig Performance raus. Im vorliegenden Fall ist es aber eher unsinnig, da es die 26 ms nicht rausreißen.Das Zusammenführen der Ergebnisse nach Beendingung der Abfrage können wir auch umgehen, und zwar mit der Erweiterungsmethode ForAll:
//Alt: //foreach (var n in fibNums) // Console.Out.WriteLine(n); //Neu: fibNums.ForAll(n => Console.Out.WriteLine(n));
Diese Methode erlaubt es uns die Ergebnisse parallel zu verarbeiten, ohne dass sie vorher zusammengeführt werden. Logischerweise wird beim Aufruf dieser Methode aber der Aufruf an WithMergeOptions ignoriert, schließlich wird gar nicht zusammengeführt.
Jedenfalls sinkt die Laufzeit auf 1720 ms bzw. ~50.5% der ursprünglichen Laufzeit.Damit wäre uns der erfolgreiche Einstieg in die Welt von Parallel LINQ gesichert.
3 Ordnung halten
Der letzte Abschnitt hat gezeigt, dass eine Abfrage mit einem AsParallel-Aufruf bereits parallelisiert ist. Leider ist es damit aber nicht immer getan und man muss zusätzliche Maßnahmen treffen, um ein korrektes Ergebnis zu erzielen.
Nehmen wir an, wir wollen aus allen Benutzern von c-plusplus.net die ersten 400 Benutzer herausfiltern, die mehr als 100 Beiträge geschrieben haben. Außerdem haben wir erst kürzlich irgendwo was von Parallel LINQ gelesen und wollen das hier mal ausprobieren. Also könnte der erste Versuch so aussehen:
var x = (from u in GetCppUserList().AsParallel() where u.PostCount > 100 select u).Take(400); x.ForAll(u => Console.WriteLine("Name: '{0}', Posts: {1}", u.Name, u.PostCount));
Überlegen wir uns, was hier passiert. Die Liste aller Benutzer wird in Segmente zerteilt und Parllel LINQ lässt mehrere Threads loslaufen. Die Ergebnisse dieser Threads werden in keiner definierten Reihenfolge an die Erweiterungsmethode Take weitergegeben. Es kann zwar sein, dass die Ergebnisse zufällig in der richtigen Reihenfolge ankommen, verlassen sollte man sich darauf jedoch nicht.
Im Endeffekt bekommen wir also nicht die ersten 400 Benutzer mit mehr als 100 Beiträgen sondern irgendwelche 400 Benutzer mit mehr als 100 Beiträgen.Glücklicherweise ist die Lösung des Problems nur eine Erweiterungsmethode entfernt: AsOrdered.
Wenn diese in den Code eingebaut wird, wird Parallel LINQ die Reihenfolge der Datenquelle berücksichtigen und unser Ergebnis wird korrekt sein:var x = (from u in GetCppUserList().AsParallel().AsOrdered() where u.PostCount > 100 select u).Take(400); x.ForAll(u => Console.WriteLine("Name: '{0}', Posts: {1}", u.Name, u.PostCount));
Natürlich geht dies mit einem Performanceverlust einher, schließlich muss Parallel LINQ bei der Segmentierung auf die Reihenfolge achten, jedoch ist der vertretbar, wenn man berücksichtigt dass man im Gegenzug richtige Ergebnisse bekommt Bei großen Abfragen kann man die Reihenfolge daher mit der Erweiterungsmethode AsUnordered auch wieder ignorieren:
//Durchschnittliche Anzahl an Posts berechnen (from u in GetCppUserList().AsParallel().AsOrdered() where u.PostCount > 100 select u) .Take(400).AsUnordered() .Average(u => u.PostCount);
Nicht nur durch den Aufruf von AsOrdered wird Parallel LINQ gezwungen, in folgenden Abfragen bzw. Methoden die Reihenfolge zu berücksichtigen, sondern auch durch die Verwendung von OrderBy, OrderByDescending, ThenBy und ThenByDescending.
Außerdem gibt es noch eine ganze Reihe von Regeln (Sektion "Query Operators and Ordering"), die bei einer Beachtung bzw. Nichtbeachtung der Reihenfolge ihre Anwendung finden.Da die Beispiele in diesem Abschnitt eher abstrakter Natur waren, zeigen wir das Verhalten nochmal am Fibonacci-Code auf:
using System; using System.Linq; namespace ConsoleApplication1 { class Program { static long fibonacci(long n) { if (n < 2) return n; else return fibonacci(n - 1) + fibonacci(n - 2); } static void Main(string[] args) { var numbers = Enumerable.Range(0, 40); var fibNums = from n in numbers.AsParallel() select fibonacci(n); var zipped = numbers.Zip(fibNums, (a, b) => new { Num = a, Fib = b }); foreach (var n in zipped) Console.Out.WriteLine(n); } } }
Anstatt die Zahlenpaare gleich in der Abfrage in Tupel zusammenzufassen, machen wir das dieses mal mit der Erweiterungsmethode Zip (die ist übrigens neu in .NET 4.0). Das Ergebnis ist ein fürchterlicher Mix aus Zahlen, die hinten und vorne nicht stimmen. Fügt man AsParallel den Aufruf von AsOrdered an, stimmen die Ergebnisse wieder.
4 Parallele Abfragen abbrechen
Genau wie parallele Schleifen und Tasks kann es auch vorkommen, dass man parallele Abfragen abbrechen möchte. Und genau wie bei parallelen Schleifen und bei Tasks verwenden wir auch hier das CancellationToken bzw. die WithCancellation-Erweiterungsmethode:
using System; using System.Linq; using System.Threading; using System.Threading.Tasks; namespace ConsoleApplication1 { class Program { static long fibonacci(long n) { if (n < 2) return n; else return fibonacci(n - 1) + fibonacci(n - 2); } static void Main(string[] args) { CancellationTokenSource cts = new CancellationTokenSource(); //Simuliert den Abbruch durch den (ungeduldigen) Benutzer und bricht nach 1000 ms ab Task.Factory.StartNew(() => { Thread.Sleep(1000); cts.Cancel(); }); var numbers = Enumerable.Range(0, 100); //100 Fibonacci Zahlen zu berechnen... try { var fibNums = from n in numbers .AsParallel() .WithMergeOptions(ParallelMergeOptions.NotBuffered) .WithCancellation(cts.Token) select new { Num = n, Fib = fibonacci(n) }; foreach (var n in fibNums) Console.Out.WriteLine(n); } catch (OperationCanceledException ex) { Console.Error.WriteLine("Operation canceled: " + ex.Message); } catch (AggregateException aex) { foreach (var ie in aex.InnerExceptions) { if (ie is OperationCanceledException) Console.Error.WriteLine("Operation canceled: " + ie.Message); else throw; } } } } }
Das Beispiel erinnert stark an die anderen Beispiele zum Abbrechen von Schleifen oder Tasks, was nicht verwundert, schließlich basiert es auf dem gleichen Konzept des CancellationTokens. Vorsicht ist beim Exceptionhandling gefragt. Tritt in einer Abfrage die mit AsParallel und WithCanellation ausgeführt wird eine oder mehrere OperationCanceledException(s) auf, kommt bei uns immer nur genau eine an. Es werden also auch mehrere OperationCanceledExceptions nicht in eine AggregateException gewrappt.
Wirft die Abfrage aber irgendeine andere Exception, z.B. die NullReferenceException, wird diese zusammen mit anderen Exceptions (auch OperationCanceledExceptions) in eine AggregateException gewrappt. Aus dem Grund ist ein feiners Exceptionhandling als sonst erforderlich.5 Ausführungsmodi von Parallel LINQ
Hinter diesem etwas sperrig betitelten Abschnitt verbirgt sich nicht weniger als die Frage, wann Parallel LINQ eine Abfrage parallel ausführt und wann sie sequentiell ausgeführt wird. An der Stelle wird eventuell der eine oder andere denken: "Na, wenn ich AsParallel aufrufe, dann wird sie auch parallel ausgeführt.". Das trifft aber nicht zu.
Parallel LINQ analysiert eine Abfrage vor der Ausführung und entscheidet dann ob es besser ist, sie sequentiell oder parallel auszuführen.
Eine Abfrage die z.B. auf eine kleine Datenmenge ausgeführt wird und bei der select kein oder ein "günstiges" (performancetechnisch) Delegate ausführt, wird durch den Overhead einer parallelen Ausführung (Segmente erstellen, Threads aufrufen, Segmente zusammenführen etc.) eventuell langsamer laufen als die sequentielle Variante.Nun kann es vorkommen, dass Parallel LINQ eine Abfrage nicht parallel, sondern sequentiell ausführt, obwohl man als Programmierer überzeugt ist, die parallele Ausführung ist besser. Dies kann man mit WithExecutionMode und dem Parameter ForceParallelism erreichen:
var foo = from b in bar.AsParallel().WithExecutionMode(ParallelExecutionMode.ForceParallelism) select b;
Weitere Informationen zum Thema "Was bremst Parallel LINQ aus?" gibt es in der MSDN.
Die Erweiterungsmethode AsSequential will ich an dieser Stelle auch erwähnen. Sie legt fest, dass die Abfrage sequentiell ausgeführt werden soll und kann benutzt werden, eine bisher parallel ausgeführt Abfrage ab diesem Punkt sequentiell auszuführen.
6 Partitioner verwenden
Genau wie bei parallelen for- und foreach-Schleifen kann man auch bei Parallel LINQ mit der Partitioner-Klasse arbeiten. Die Grundlagen von Partitionern wurden bereits im letzten Artikel behandelt, deshalb gibt es hier nur ein kleines Beispiel:
var numbers = Enumerable.Range(0, 1000); var partitioner = Partitioner.Create(numbers); var fibNums = from n in partitioner.AsParallel() select fibonacci(n);
Wie bei ForEach-Schleifen dient ein Partitioner auch hier als Datenquelle, ansonsten bleibt alles beim Alten.
7 Schlussbemerkung
In diesen zwei Artikeln wurde Parallelisierung mit dem .NET Framework 4.0 erläutert. Mit den neuen Mitteln an der Hand sollte es erheblich leichter fallen, parallelisierte Programme zu entwickeln, ohne dabei schon im Ansatz graue Haare zu bekommen.
-
Auch hier bitte inhaltliches Feedback
-
Dieser Thread wurde von Moderator/in GPC aus dem Forum Die Redaktion in das Forum Archiv verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.