Im gestrigen Türchen wurden Erlang, Elixir und ein Projekt zur Primfaktorzerlegung vorgestellt. Dank funktionaler Programmierkonstrukte wie Streams und Pattern Matching konnte eine recht elegante Lösung gefunden werden. Eine andere grosse Stärke von Erlang/Elixir wurde jedoch noch nicht ausgenutzt: Die auf leichtgewichtigen Prozessen basierende Nebenläufigkeit. Diese soll Thema des heutigen Türchens sein.
Mehrere Zahlen faktorisieren
Eine Aufgabe ist dann am einfachsten zu parallelisieren, wenn Sie aus mehreren Teilaufgaben besteht, die unabhängig voneinander erledigt und am Schluss zu einem Gesamtergebnis zusammengeführt werden können. Ist die Faktorisierung einer einzigen Zahl nur schwer zu parallelisieren, geht es mit mehreren Zahlen ganz einfach.
Das Modul Factorizer (lib/factorizer.ex) bietet die Funktion factorize/1 an, welche eine Sequenz von zu faktorisierenden Zahlen erwartet:
Code: Alles auswählen
defmodule Factorizer do
def factorize(numbers) do
Enum.map(numbers, fn n ->
{n, PrimeFactors.factorize(n)}
end)
|> Map.new()
end
end
Das Modul kann folgendermassen interaktiv mit iex ausprobiert werden (hier mit einer Reihe von vier Zahlen und einer Range von fünf grösseren Zahlen):
Code: Alles auswählen
$ iex -S mix
iex(1)> Factorizer.factorize([10, 123, 948, 1024])
%{
10 => [2, 5],
123 => [3, 41],
948 => [2, 2, 3, 79],
1024 => [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
}
iex(2)> Factorizer.factorize(100000..100004)
%{
100000 => [2, 2, 2, 2, 2, 5, 5, 5, 5, 5],
100001 => [11, 9091],
100002 => [2, 3, 7, 2381],
100003 => [100003],
100004 => [2, 2, 23, 1087]
}
Bevor die Faktorisierung mehrerer Zahlen nun parallelisiert wird, soll noch eine Messvorrichtung eingeführt werden. Die parallele Abarbeitung soll ja am Ende schneller laufen als die sequenzielle, was mit einer Stoppuhr überprüft werden soll.
Das Modul Stopwatch (lib/stopwatch.ex) bietet die Funktion timed/1 an, welche als Parameter eine aufzurufende Funktion entgegennimmt:
Code: Alles auswählen
defmodule Stopwatch do
def timed(fun) do
{time, value} = :timer.tc(fun)
seconds = time / 1.0e6
IO.puts("#{seconds}s")
value
end
end
Die Zeitmessung lässt sich nun mithilfe einer anonymen Funktion folgendermassen verwenden:
Code: Alles auswählen
$ iex -S mix
iex(1)> Stopwatch.timed(fn -> Factorizer.factorize(1_001_000_000..1_001_000_004) end)
5.581279s
%{
1001000000 => [2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 7, 11, 13],
1001000001 => [3, 17, 19627451],
1001000002 => [2, 1013, 494077],
1001000003 => [83, 12060241],
1001000004 => [2, 2, 3, 167, 457, 1093]
}
Parallelisierung mit Prozessen
Erlang/OTP bietet mächtige und fehlertolerante Konstrukte an, womit Aufgaben einfach und zuverlässig parallelisiert werden können. Diese lassen sich auch von Elixir aus verwenden. Hier soll es jedoch um die Grundlagen der Nebenläufigkeit in Erlang bzw. Elixir gehen, wofür leichtgewichtige Prozesse verwendet werden sollen.
Die drei grundlegendsten Konstrukte hierfür sind:
- Die Funktion spawn/1 erwartet eine Funktion zur parallelen Ausführung, startet einen neuen Prozess und gibt als Rückgabewert die Prozess-ID (PID) des neuen Prozesses zurück.
- Die Funktion send/2 erwartet als ersten Parameter eine PID und als zweiten Parameter eine Nachricht.
- Mit dem Schlüsselwort receive wird auf eingehende Nachrichten gewartet, die auf ein bestimmtes Muster passen. Hier ist wieder Pattern Matching im Einsatz, ähnlich wie beim Funktionsaufruf.
Code: Alles auswählen
$ iex
iex(1)> doubler = spawn(fn -> receive do {caller, number} -> send(caller, number * 2) end end)
iex(2)> printer = spawn(fn -> receive do number -> IO.puts(number) end end)
iex(3)> send(doubler, {printer, 7})
14
- Es wird ein Prozess gestartet, dessen PID als doubler zwischengespeichert wird. Die Funktion wartet auf eine Nachricht der Struktur {caller, number} und schickt dem Aufrufer eine Nachricht bestehend aus der verdoppelten Zahl zurück.
- Es wird ein weiterer Prozess gestartet, dessen PID als printer zwischengespeichert wird. In diesem Prozess wird auf eine Zahl gewartet, die dann ausgegeben wird.
- Der Prozess doubler erhält die Nachricht {printer, 7}, wodurch er angewiesen wird die Zahl 7 zu verdoppeln und das Ergebnis dieser Berechnung an den Prozess printer zu senden.
Parallele Primfaktorzerlegung
Zur nebenläufigen Verarbeitung einer Aufgabe, die sich in mehrere Unteraufgaben aufteilen lässt, ist das Vorgehen Divide and Conquer sinnvoll. Die Aufgabe wird zuerst in mehrere Unteraufgaben aufgeteilt, die sich dann einfacher bewältigen lassen. Das anschliessende Zusammenfügen der Teilergebnisse kann jedoch bei der nebenläufigen Programmierung eine Herausforderung darstellen.
Im Falle der nebenläufigen Primfaktorzerlegung erfolgt die Abarbeitung in den folgenden Schritten:
- Es wird eine Reihe von Unterprozessen aufgestartet. Dies kann in einer Sprache mit leichtgewichtigen Prozessen wie Erlang/Elixir (oder auch Go) problemlos ein Unterprozess pro Teilaufgabe (d.h. pro zu faktorisierender Zahl) sein.
- Die einzelnen Zahlen werden zur Faktorisierung an den jeweiligen Prozess delegiert. Die Prozesse berechnen die Primfaktoren der jeweiligen Zahl und melden das Ergebnis inklusive der ursprünglichen Zahl zurück.
- Die gefundenen Primfaktoren zu jeder Zahl werden eingesammelt und zu einer Map zusammengefügt. Der Schlüssel ist die ursprüngliche Zahl, der Wert sind die gefundenen Primfaktoren.
Code: Alles auswählen
defmodule ParallelFactorizer do
def factorize(numbers) do
pids_by_number =
Enum.map(numbers, fn n ->
pid = spawn(&handle/0)
{n, pid}
end)
|> Map.new()
Enum.each(pids_by_number, fn {number, pid} ->
send(pid, {self(), number})
end)
Enum.reduce(numbers, %{}, fn _, acc ->
receive do
{number, factors} -> Map.put(acc, number, factors)
end
end)
end
defp handle() do
receive do
{caller, number} ->
send(caller, {number, PrimeFactors.factorize(number)})
end
end
end
- Prozesse starten: Die Zahlen werden mit Enum.map/2 in eine Sequenz von Zweiertupeln bestehend aus der jeweiligen Zahl und der PID eines eigens dafür mit spawn/1 aufgestarteten Prozesses umgewandelt. Die Sequenz wird mit Map.new/1 in eine Map umgewandelt, bei der PIDs (Werte) nach den zu faktorisierenden Zahlen (Schlüssel) nachgeschlagen werden können.
- Die private Funktion handle/0 wartet auf eine Nachricht der Struktur {caller, number} und beantwortet diese dem Aufrufer mit einer Zweiertupel bestehend aus der originalen Zahl und den mithilfe von PrimeFactors.factorize/1 ermittelten Primfaktoren davon.
- Aufgaben delegieren: Mit Enum.each/2 wird nun die Map der Zahlen und PIDs abgearbeitet. Jede PID bekommt mit send/2 eine Nachricht zugestellt, die dann von der Logik von handle/0 abgearbeitet wird.
- Ergebnisse einsammeln: Mit Enum.reduce/3 sollen die Zahlen zu einer neuen Map %{} zusammengetragen werden. Der Funktionsaufruf erhält neben der Zahl, die hier ignoriert wird, den Akkumulator acc als weiteren Parameter. (Die Zahl kann ignoriert werden, weil die Antwort alle Informationen enthält. Es wird mit einer Iteration über die ursprünglichen Zahlen gearbeitet, damit man die richtige Anzahl an Nachrichten erwartet.) Der Akkumulator (eine Map) soll dann um ein eingehendes Ergebnis ergänzt werden. Hierzu werden Nachrichten der Form {number, factors} erwartet, wovon dann number als Schlüssel und factors als Wert in die Map geschrieben werden.
- Das Ergebnis der Operation ist eine Map bestehend aus Zahlen (Schlüssel) und deren Primfaktoren (Werte).
Wie sieht es nun mit der Performance aus ‒ ausgeführt auf einer virtuellen Maschine mit zwei CPUs?
Code: Alles auswählen
$ iex -S mix
iex(1)> Stopwatch.timed(fn -> ParallelFactorizer.factorize(1_001_000_000..1_001_000_004) end)
3.812785s
%{
1001000000 => [2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 7, 11, 13],
1001000001 => [3, 17, 19627451],
1001000002 => [2, 1013, 494077],
1001000003 => [83, 12060241],
1001000004 => [2, 2, 3, 167, 457, 1093]
}
Fazit
Nachdem gestern eine Zahl mit Elixir faktorisiert worden ist, wurde heute zuerst eine Reihe von Zahlen sequenziell in ihre Primfaktoren zerlegt. Mithilfe der Concurrency-Primitiven von Erlang/Elixir und einem Vorgehen in drei Schritten ‒ Prozesse starten, Aufgaben delegieren, Ergebnisse einsammeln ‒ erläutert und umgesetzt.
Ausblick
Wer sich in die Materie vertiefen möchte, kann sich weitere Implementierungen in meinem GitHub-Repository factorizer anschauen. Ein sehr ausführlicher englischsprachiger Artikel erklärt die verschiedenen Implementierungen im Detail.
Übungen
Wer sich in Elixir vertiefen und einmal nebenläufige Sprachkonstrukte ausprobieren möchte, kann sich an folgenden Übungen versuchen:
- Wie verhält sich die nebenläufige Implementierung auf anderen Setups? Versuche das Projekt nachzubauen und experimentiere mit verschiedenen Zahlenbereichen herum. Unter welchen Umständen kann eine Zeitersparnis um den Faktor Anzahl CPUs (annährend) erreicht werden?
- Anstelle von einem Prozess pro Teilaufgabe soll nur noch ein Prozess pro verfügbare CPU aufgestartet werden. Die Aufgaben sollen dann mithilfe des Round-Robin-Verfahrens an die verschiedenen Prozesse verteilt werden. Tipp: Mit System.schedulers_online/0 kann die Anzahl verfügbarer Scheduler ermittelt werden, welche der Anzahl verfügbarer CPUs entspricht. Mit dem Modulo-Operator kann ein Zahlenindex auf einen Prozessindex heruntergerechnet werden.
