Parallelprogrammierung in F# · Vergleich zwischen verschiedenen Programmiersprachen und Plattformen gut eignen. Typische Beispiele sind Quicksort oder Filteroperationen in der Bildverarbeitung

IP-510: Parallelprogrammierung in F#Technische Dokumentation

Adrian Herzog Kevin ZoggWeissacherweg 360 Spittelgasse 105063 Wölflinswil 5105 Auenstein

Betreut durch Prof. Dr. Christoph Stamm

Windisch, Februar 2011

1. Abstract 3

2. Einleitung 4

3. Aufgabenstellung 53.1. Einarbeitung 53.2. Fragestellungen 63.3. Dokumentation 6

4. Einführung in F# 84.1. Merkmale funktionaler Programmiersprachen 84.2. Verbreitung funktionaler Sprachen 84.3. F# lernen: Tutorials & Bücher 94.4. F# Syntax 104.5. F# Datenstrukturen 114.6. Parallelprogrammierung in F# 144.7. Interoperabilität mit C# 16

5. Testprogramme und Performancemessungen 175.1. Zeitmessung 175.2. Mersenne-Primzahlensuche 175.3. Matrix-Multiplikation 185.4. Pythagoras-Tripel 205.5. Lazy Sequenzen 205.6. Einfache Bildverarbeitung 225.7. Arrays erzeugen 26

6. Face Detection Projekt 286.1. Stand der Forschung 286.2. Zielsetzung 286.3. Ablauf 296.4. Erkennung von Hautfarbe 306.5. Tiefpassfilter 326.6. Zusammenhängende Regionen finden 326.7. Plausibilitäts-Prüfungen 336.8. Skalierung der verbleibenden Kandidaten 336.9. Mund-Erkennung 336.10. Augen-Erkennung 346.11. Optimale Mund-Augen-Kombination finden 366.12. Test der Gesichtslokalisierung 37

7. Schlussfolgerungen 39

8. Abbildungsverzeichnis 41

9. Tabellenverzeichnis 41

10. Referenzen 42

Parallelprogrammierung in F# 11.02.2011 2/42

1. Abstract

F# ist eine relativ neue Programmiersprache von Microsoft, welche sowohl funktionale wie auch objektorientierte Programmierung unterstützt und auf dem .NET Framework aufbaut. Die Sprache wird im Allgemeinen und mit speziellem Fokus auf Parallelpro-grammierung untersucht. Zuerst wird eine Einführung in die Sprache und die grundle-gende Syntax gegeben. Danach werden spezielle Datenstrukturen von F# erläutert und verschiedene Möglichkeiten zur Parallelprogrammierung gezeigt. Im folgenden Kapitel werden einige kleinere Programme sowohl in F# wie auch in C# geschrieben, um die Geschwindigkeit und die Lesbarkeit der beiden Sprachen zu vergleichen. Dabei zeigt sich, das F#-Programme genau so schnell sind wie C#-Programme, wenn man ein paar grundlegende Punkte beachtet. Um F# in einem grösseren Projekt zu untersuchen, wird ein Programm zur Gesichtslokalisierung umgesetzt. Dank den Erfahrungen aus den klei-neren Testprogrammen erreicht dieses Programm eine hohe Geschwindigkeit bei einer Erkennungsrate von rund 60 Prozent bei frontalen Gesichtern. F# bewährt sich bei die-sem komplexen Programm mit parallelen Anteilen. Die Algorithmen und Vorgehenswei-sen der Gesichtslokalisierung basieren hauptsächlich auf Ideen aus wissenschaftlichen Artikeln. Zum Schluss werden, aufgrund der Erfahrungen und den gesammelten Infor-mationen, Richtlinien für einen sinnvollen Einsatz von F# formuliert.


2. Einleitung

Programmiersprachen, welche dem funktionalen Paradigma folgen, werden oft als vor-teilhaft für die Parallelprogrammierung bezeichnet. Der Grund dafür ist, dass rein funk-tionale Sprachen keine veränderbaren Variablen kennen, sondern nur unveränderbare (immutable) Werte. Funktionen werden ausgeführt, ohne dass Seiteneffekte entstehen, was bei der Parallelprogrammierung den gleichzeitigen Zugriff auf gemeinsamen Spei-cher minimiert.

Mit F# entwickelte Microsoft eine .NET-basierte Programmiersprache, welche primär funktional ist, jedoch auch objektorientierte Programmierung unterstützt. Durch die .NET Plattform ist es nicht nur möglich, eigenständige F# Programme zu schreiben, sondern es sind auch Applikationen möglich, deren Teile in unterschiedlichen Sprachen wie F#, C# oder VB.NET geschrieben sind. Somit kann jede Sprache dort eingesetzt werden, wo sie am besten geeignet ist.

Da F# nicht ausschliesslich funktional ist, lässt es auch veränderbare Werte zu. Funktio-nen können also auch so programmiert werden, dass sie Seiteneffekte erzeugen, wo-durch die Vorteile bei der Parallelprogrammierung vermindert werden. Andererseits bringt F# gerade für die Parallelprogrammierung interessante Features mit, z.B. zur Im-plementierung asynchroner Methoden oder zur Umsetzung eines Aktoren-Modells, wie es in der Sprache Erlang vorkommt. Auch die volle Unterstützung des .NET Parallel Programming Frameworks ist sehr wertvoll.

Ein erster Schritt dieses Projektes ist das Erlernen der Sprache F#. Dann werden einige kleinere Programme implementiert, um die Geschwindigkeit und die Eleganz des Codes mit C# zu vergleichen. Einige dieser Programme verwenden auch Parallelprogrammie-rung. Durch die gewonnene Erfahrung sind wir danach in der Lage, ein grösseres Pro-jekt mit F# umzusetzen. Wir haben uns für ein Programm zur Gesichtslokalisierung in Bildern (Face Detection) entschieden, da dies einerseits hohe Ansprüche an die Perfor-mance stellt und andererseits auch bestimmte Teile parallel ausgeführt werden können.

Ziel unserer Arbeit ist nicht eine perfekte Face Detection, sondern das Sammeln wert-voller Erfahrung mit der noch jungen Programmiersprache F#. Wir zeigen Vor- und Nachteile auf, welche durch die Verwendung dieser Sprache entstehen können.


3. Aufgabenstellung

3.1. Einarbeitung

Vorbereitung

Fixieren Sie für die Unterrichtszeit alle zwei Wochen und für die unterrichtsfreie Zeit einen wöchentlichen Besprechungstermin mit Ihrem Betreuer. Nutzen Sie diese Bespre-chungen, um Ideen, Vorschläge und Arbeiten zu präsentieren und zu diskutieren.

Bevor Sie mit der Arbeit richtig loslegen, entscheiden Sie sich für einige Algorithmen (Testset) die Sie realisieren wollen und erstellen Sie einen möglichst detaillierten Zeit-plan für die Dauer dieser Projektarbeit. Definieren Sie die wichtigsten Meilensteine.

Infrastruktur und Programmierumgebung

Richten Sie sich eine Arbeitsstation zur Software-Entwicklung ein. Verwenden Sie Visu-al Studio 2010. Als Programmiersprache werden F# und C# verwendet. Für eine pro-duktive Arbeitsweise unter Windows ist ein direkter Zugang zu der MSDN-Library uner-lässlich.

Literatur- und Softwarestudium

Als Einstieg in F# empfehlen wir Ihnen die entsprechenden MSDN-Seiten [F#]. In [Tou10] werden verschiedene Patterns der Parallelprogrammierung und deren Verwen-dung im .NET-Framework 4 unter C# vorgestellt. Studieren Sie dieses Paper, um einen vertieften Einblick in die Parallelprogrammierung mit C# zu erlangen. Suchen Sie sich weitere Literatur (Foren, Fachbücher, englischsprachige Original-Papers, Webseiten usw.) insbesondere zu Themen wie Parallelität in F# und bibliographieren Sie alle wich-tigen Quellen.

Als praktischen Einstieg in die Thematik empfehlen wir Ihnen das Nachvollziehen vor-handener F#-Beispiele und die Entwicklung eigener einfacher Programme.

Testset

Damit Sie die Güte Ihrer laufenden Arbeit ständig selber beurteilen können, benötigen Sie Algorithmen und Datensätze. Diese sollen Sie selber entwickeln – lehnen sie sich dazu an den Unterricht. Implementieren Sie Algorithmen, die sich für den Performance-Vergleich zwischen verschiedenen Programmiersprachen und Plattformen gut eignen. Typische Beispiele sind Quicksort oder Filteroperationen in der Bildverarbeitung. Über-prüfen Sie auch, ob es allfällige Testsets von bekannten Benchmarks gibt.

Besprechen Sie Ihr Testset (auf Papier) mit Ihrem Betreuer.


3.2. FragestellungenGehen Sie den folgenden Fragestellungen detailliert nach. Arbeiten Sie theoretisch und praktisch daran.

Effizienz

Wie verhält es sich mit der Effizienz in F#? Muss bei einer Verwendung von F# anstatt C# mit einem Effizienzverlust gerechnet werden?

Ziele

Sie haben die Effizienz der Programme aus Ihrem Testset studiert und gemessen. Un-terscheiden Sie zwischen sequentiellen und parallelen Algorithmen und betrachten Sie jeweils die Zeit- und Speichereffizienz separat.

Parallelität

Welche unterschiedlichen Möglichkeiten haben Sie in F#, um Parallelität ausnutzen zu können?

Ziele

Studieren Sie alle möglichen Arten der Parallelität in F# und zeigen Sie an konkreten, einfachen Beispielen auf, wie Parallelität sinnvoll genutzt werden kann.

Praxiseinsatz

Implementieren Sie ein grösseres Beispiel in F# eigenständig. Dieses Beispiel soll den praktischen Nutzen von F# evtl. in Kombination mit anderen CLR-Sprachen deutlich ma-chen. Zwei mögliche Aufgabenstellungen wären beispielsweise: a) Lässt sich in F# ein logisches Deduktions- und Resolutionssystem analog zu Prolog einfach und effizient realisieren? b) Können typische Aufgaben aus der Bildverarbeitung funktional elegant und effizient gelöst werden? Wie werden solche Aufgaben in F# angepackt?

Ziele

Sie haben ein grösseres Beispiel von Grund auf selber implementiert.

3.3. Dokumentation

Schriftliche Dokumentation

Dokumentieren Sie schriftlich und elektronisch Ihre Vorgehensweise, Ihre Konzepte, die wichtigsten Punkte der Implementierungen und Ihre Testresultate. Überprüfen Sie auch den geplanten mit dem tatsächlichen Zeitplan und reflektieren Sie Ihre persönlichen Er-lebnisse und Erfahrungen während dieser Arbeit.

Achten Sie unbedingt darauf, dass Sie persönliche Kommentare von Fakten strikte tren-nen. Ein erster Teil der Dokumentation ist vollständig faktenbasiert. Das bedeutet, dass keine Sätze der Art „Dann hatten wir das Problem x und versuchten es mit y zu lö-sen.“ auftreten dürfen. Falls ein solches Problem x aber wirklich existiert und nicht nur Sie damit nicht gleich zu Rande kamen, dann sollen Sie schreiben: „Tests z haben klar gezeigt, dass ein Problem x besteht. Mögliche Ansätze, um das Problem x zu lösen, sind a, b und c. Wir haben uns aus den Gründen e und f für Variante c entschieden.“ Erst in einem zweiten Teil sollen Sie Ihre persönlichen Eindrücke, Erlebnisse, Probleme und dergleichen formulieren.


Wichtig ist auch, dass eine gute Dokumentation auch noch nach vielen Jahren gelesen werden können muss und dass sie dem Leser ein gut abgerundetes Bild vermittelt, auch dann wenn er nicht direkt an der Arbeit beteiligt war. Bitte legen Sie auch grossen Wert auf sprachliche Qualität.

Das Zielpublikum dieser Dokumentation sind die Betreuer und zukünftige Studierende, welche in diesem Bereich weiterarbeiten wollen.

Präsentation

In Absprache mit Ihrem Betreuer und dem Auftragsteller der Arbeit wird von Ihnen eine Präsentation Ihrer Arbeit erwartet. Die Präsentation soll einerseits einen groben Über-blick verschaffen und anderseits ein oder zwei wichtige und interessante Details hervor-heben. Bei den Zuhörern dürfen Sie von einem technisch versierten Fachpublikum aus-gehen.

Zusätzlich zur Präsentation wird eine prägnante Demonstration der Benutzung Ihrer Software erwartet.


4. Einführung in F#

In diesem Kapitel geben wir eine kleine Einführung in F#, wobei wir vor allem auf Eigen-heiten eingehen, welche in F# speziell sind.

Gemäss [Sym10] begann die Entwicklung von F# im Jahr 2002 unter der Leitung von Don Syme bei Microsoft Research in Cambridge. Das Ziel war es, eine funktionale Spra-che zu entwerfen, welche wie C# und VB.NET auf der .NET Plattform basiert. F# wurde nicht vollkommen neu entwickelt sondern lehnt sich stark an die Sprache OCaml an, welche seinerseits auf ML basiert. Das Objektmodell orientiert sich stark an C#, um mit der .NET Plattform kompatibel zu sein.

Im April 2010 wurde die Version 2.0 von F# veröffentlicht, welche nun für den produkti-ven Einsatz gedacht ist. In Visual Studio 2010 wird F# erstmals standardmässig mitge-liefert, bei Visual Studio 2008 kann es nachinstalliert werden. Der Quelltext des F# Com-pilers und der Core-Bibliotheken steht unter einer Open Source Lizenz und kann von der Microsoft-Website heruntergeladen werden.1

4.1. Merkmale funktionaler ProgrammiersprachenDie Ideen der funktionalen Programmierung stammen aus dem Lambda-Kalkül, welches in den 1930er Jahren von Alonso Church und Stephen Kleene eingeführt wurde.2

Funktionale Programmiersprachen sind aus Sicht der theoretischen Informatik gleich mächtig wie imperative Sprachen. Das heisst, man kann damit die gleichen Probleme lösen, nicht mehr und nicht weniger. Der Unterschied zwischen imperativen und funktio-nalen Programmiersprachen liegt also in der Herangehensweise, wie Probleme gelöst werden. Viele Funktionale Programmiersprachen, darunter auch F#, haben folgende Ei-genschaften:3

• Funktionen können als Parameter an eine Funktion übergeben werden und als Rückgabewerte zurückgegeben werden (first-class and higher-order functions).

• Indem nur ein Teil der Parameter an eine Funktion übergeben wird erhält man eine neue Funktion als Rückgabewert, welche die restlichen Parameter als Eingabe er-wartet (Currying).

• Unveränderliche Datentypen sind (oft ausschliesslich) vorhanden (immutability).

• Funktionen ohne Seiteneffekte sind möglich (pure functions).

• Endrekursion (tail recursion) wird vom Compiler so optimiert, dass kein Stack ver-wendet wird und somit auch kein Pufferüberlauf möglich ist.

• Es existieren Typen-Systeme, oft kombiniert mit Typinferenz und der Möglichkeit des Pattern Matching.

4.2. Verbreitung funktionaler SprachenDie Internetseite www.langpop.com versucht anhand verschiedener Quellen die Popula-rität von Programmiersprachen festzustellen. Die populärste Sprache, welche funktiona-les Programmieren unterstützt, ist gemäss dieser Seite JavaScript, welches auf Platz 5 der Liste hinter C, Java, C++ und PHP zu finden ist. Auf Platz 6 folgt Python, welches funktionales Programmieren ebenfalls ermöglicht. Die typischen funktionalen Sprachen folgen erst viel später: Lisp (Platz 16), Scheme (Platz 19), Haskell (Platz 20), Erlang

1 http://www.microsoft.com/downloads/en/details.aspx?FamilyID=effc5bc4-c3df-4172-ad1c-bc62935861c52 http://de.wikipedia.org/wiki/Lambda-Kalkül3 http://en.wikipedia.org/wiki/Functional_programming#Concepts


(Platz 28), Scala (Platz 30), OCaml (Platz 31). F# ist leider noch nicht in dieser Statistik enthalten. Der Tiobe-Index4, welcher auch die Popularität von Programmiersprachen ab-schätzt, zeigt ein ähnliches Bild.

Offensichtlich führen funktionale Sprachen ein Nischendasein. Trotzdem beweisen sich funktionale Sprachen immer wieder auch im alltäglichen Einsatz ausserhalb der akade-mischen Welt. Ein Beispiel dafür ist das Produkt XenServer, eine Server-Virtualisie-rungs-Lösung der Firma Citrix. [Scott10] beschreibt, dass eines der vier Hauptmodule dieser Software hauptsächlich in OCaml geschrieben ist (ca. 130'000 Zeilen Code). Die Verwendung der funktionalen Sprache wird insgesamt als positiv bewertet, wobei die negativen Punkte vor allem das Fehlen bestimmter Libraries und der fehlende Tool-Sup-port sind. [FP03] ist ein weiterer Erfahrungsbericht zu OCaml, diesmal im Zusammen-hang mit dem Filesharing-Programm MLDonkey. Als grösster Nachteil wird das Fehlen von fortschrittlichen Debugging-Tools, z.B. für das Profiling des Speichers, genannt.

Auch mit F# wurden schon erste Erfahrungen im Alltag gesammelt. Zum Beispiel entwi-ckeln bei der Credit Suisse dreissig Programmierer Finanz-Software mit F#.5

4.3. F# lernen: Tutorials & BücherUm F# zu erlernen, gibt es verschiedene Möglichkeiten. Um einen ersten Eindruck zu erhalten, kann man in Visual Studio 2010 unter File > New > Project ein neues „F# Tuto-rial“ Projekt erstellen. Dieses besteht aus einer einzigen Datei, welche einige F# Bei-spiele enthält.

Um einzelne Beispiele aus Tutorials direkt auszuprobieren, ist die F# Interactive Shell sehr hilfreich. Die Shell kann in Visual Studio 2010 über View > Other Windows > F# In-teractive eingeblendet werden. Befehle müssen hier mit einem doppelten Semikolon ab-geschlossen werden.

Im Internet findet man einige einführende Dokumente zu F#. Empfehlenswert ist z.B. die „F# Language Overview“6 von Tomáš Petříček.

Bücher

Wir haben uns zwei Bücher beschafft: „Expert F# 2.0“ von Don Syme, dem F# Chef-De-signer persönlich, und „Programming F#“ von Chris Smith.

„Programming F#“ behandelt auf 416 Seiten alle wichtigen Themen der Programmier-sprache, überspringt aber gewisse fortgeschrittene Themen, wie zum Beispiel Message Passing. Das Buch ist geeignet für Personen ohne Vorwissen in funktionaler Program-mierung, da es mit vielen Beispielen arbeitet und gut verständliche Erklärungen enthält.

„Expert F# 2.0“ ist mit 624 Seiten wesentlich umfangreicher. Auch dieses Buch beginnt bei den Grundlagen von F# und führt diese anhand von Beispielcode, der ausführlich er-klärt wird, ein. Im zweiten Teil folgen Themen wie GUI-Programmierung, Parallelpro-grammierung, Web-Applikationen, Programmierung eines Parsers und Interoperabilität mit C und COM.

Weitere Bücher zu F# tragen Titel wie „Real World Functional Programming“ oder „F# for Scientists“. Wer einen systematischen und umfassenden Einstieg in die Sprache sucht, kommt um ein F# Buch fast nicht herum.

4 http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html 5 http://cufp.org/archive/2008/report.pdf 6 http://tomasp.net/articles/fsharp-i-introduction/article.pdf


Dokumentation

Die MSDN-Library von Microsoft dokumentiert die gesamte .NET Library, inklusive den-jenigen Modulen, welche speziell für F# hinzugefügt wurden. Teilweise fehlt jedoch Bei-spielcode in F# und man muss auf den Code in C# zurückgreifen.

Community im Internet

Obwohl F# noch relativ jung ist findet man viele Ressourcen dazu im Internet. Das Fo-rum unter cs.hubfs.net mit über 10'000 Beiträgen ist wohl die grösste F# Community. Auch stackoverflow.com enthält schon viele Beiträge zu F#. Die Seite fsharpcentral.com bietet regelmässig einen Überblick über Neues aus der F# Welt. Interessant sind auch die Blogs von Don Syme (blogs.msdn.com/b/dsyme) und Tomáš Petříček (tomasp.net).

4.4. F# SyntaxDie Syntax von F# lehnt sich stark an OCaml an und ist sehr schlicht. Semikolons am Ende jeder Zeile oder geschweifte Klammern zur Bildung von Blöcken gibt es nicht. Da-für ist es für den Compiler wichtig, dass jede Zeile korrekt eingerückt ist. F# besitzt un-veränderbare Werte anstelle von Variablen. Solche Werte können entweder Literale sein oder Funktionen. Um einen Wert zu setzen wird das Schlüsselwort let verwendet.

let someAge = 24 // Typ: intlet growOlder years age = age + years // Typ: int -> int -> intlet oneOlder = growOlder 1 // Typ: int -> intlet newAge = oneOlder someAge // Typ: int

Der Compiler erkennt automatisch, welchen Typ ein Wert hat (Typinferenz). Fährt man in Visual Studio mit dem Maus-Zeiger über den Bezeichner eines Wertes, erhält man diese Typinformation unmittelbar.

Konstante Werte unterscheiden sich nur dadurch von Funktionen, dass sie keine Para-meter erwarten und keine Seiteneffekte verursachen können. Wäre F# eine rein funktio-nale Sprache ohne Seiteneffekte, könnte eine Funktion, bei der alle Argumente überge-ben werden, mit einem konstanten Wert gleichgesetzt werden.

Für den Compiler ist nur der Typ eines Wertes wichtig. Deshalb kann überall wo ein be-stimmter Typ als Parameter erwartet wird, anstelle eines fixen Wertes auch eine Funkti-on, die einen Wert dieses Typs zurückgibt, übergeben werden.

Werden nicht alle Parameter an eine Funktion übergeben, erhält man als Rückga-be-Wert eine Funktion, welche die noch fehlenden Parameter verlangt (Currying). Ein Beispiel dafür ist die Funktion oneOlder. Diese entspricht der Funktion growOlder, wobei als erster Parameter der Wert 1 gesetzt wurde, der zweite Parameter jedoch noch frei ist.

Der Funktionsrumpf kann auch mehrzeilig sein kann. Wichtig ist, dass jede Zeile des Rumpfes gleich weit eingerückt ist.

let growYounger age = let doMagic a = a - 1 // Eine innere Funktion doMagic age // Die letzte Zeile ist der Rückgabewert

Innerhalb einer Funktion können weitere Werte definiert werden, die allerdings ausser-halb der Funktion nicht sichtbar sind. In einer älteren, ausführlicheren Syntax von F# wird hinter jeder inneren Definition das Schlüsselwort in geschrieben, welches den Zweck der inneren Definitionen verdeutlicht. Diese sind nur dazu da, in der letzten Zeile der Funktion verwendet zu werden, welche immer den Rückgabewert darstellt. Soll eine


Funktion keinen Rückgabewert besitzen, wird in der letzten Zeile eine öffnende und eine schliessende Klammer geschrieben. Ein leerer Rückgabewert heisst in F# unit.

let sayHello name = printfn "Hello %s" name // Ausgabe auf Konsole () // Kein Rückgabewert

Bei rekursiven Funktionen muss zusätzlich das Schlüsselwort rec verwendet werden.

let rec factorial n = if n = 0 then 1 else n * factorial (n-1)

Falls ein Wert doch mal änderbar sein soll, wird das Schlüsselwort mutable verwendet. Veränderbare Werte sind in F# allerdings nicht sehr effizient und sollen wenn möglich vermieden werden.

let mutable counter = 0 // Veränderbaren Wert initialisierenfor i in 0 .. 10 do counter <- counter + 1 // Wert neu setzen

4.5. F# DatenstrukturenF# bietet neben den aus der .NET Library bekannten Datenstrukturen ein paar eigene Strukturen an, welche über eine vereinfachte Syntax verwendet werden und spezielle Eigenschaften bieten.

Tupel

Ein Tupel gruppiert mehrere Werte, die alle den gleichen Datentyp oder auch unter-schiedliche Datentypen haben können. Tupel sind unter anderem sehr praktisch, wenn eine Funktion mehrere Werte zurückgeben soll.

Ein Tupel hat immer einen Typ, so hat z.B. das folgende Tupel namedPoint den Typ int * int * int * string. Der Stern in der Typenbezeichnung zeigt an, dass die einzelnen Werte in einem Tupel vereint sind.

let namedVector = (1, 2, 3, "F#")

Mit Pattern Matching können die Werte eines Tupels wieder einzelnen Variablen zuge-wiesen werden.

let (x, y, z, _) = namedVector

Nun hat x den Wert 1, y den Wert 2 und z den Wert 3. Mit dem Unterstrich an der vier-ten Position im Tupel können wir diesen Wert ignorieren. Mit diesen Werten kann nun wie gewohnt gerechnet werden. Im folgenden Beispiel ist ein Cast von int zu float nötig, da die Methode sqrt einen float-Wert erwartet und F# nie implizite Casts durchführt.

let vectorLength = sqrt (float (x * x + y * y + z * z))

Listen

Bei F# Listen handelt es sich um einfach verkettete Listen, in denen jedes Element den gleichen Typ hat. Die Implementation ist sehr einfach gehalten: Jedes Element hat eine Referenz, die entweder auf das folgende Element zeigt oder auf die leere Liste, welche das Ende jeder Liste markiert. Eine Liste mit drei Elementen sieht folgendermassen aus:

Abbildung 1: Liste in F#


Eine solche Liste, repräsentiert durch ihr Startelement, ist unveränderbar. Einzelne Ele-mente können also nur vorne an die Liste angehängt werden, so dass der Rest der Liste erhalten bleibt und bestehende Referenzen darauf immer noch die alte Liste sehen. Will man zwei Listen aneinander hängen, muss von einer der beiden Listen eine Kopie er-stellt werden, da ihr letztes Element nun auf das erste Element der anderen Liste zeigen muss.

Listen können auf verschiedene Arten erzeugt werden. Hier einige Beispiele:

let emptyList = [] // Leere Listelet listOne = 123 :: [] // Liste mit einem Integer-Elementlet listTwo = "One" :: "Two" :: [] // Liste mit zwei Stringslet listThree = "Three" :: listTwo // Element an Liste anhängenlet listFour = ["A"; "B"; "C"] // Alternative Schreibweiselet lastList = listThree @ listFour // Listen aneinander hängenlet numbers = [ 1 .. 10 ] // Liste mit Zahlen von 1 bis 10let squares = [ for i in 1 .. 10 -> i*i ] // Liste mit Quadraten von 1 bis 10

Die Iteration über Listen kann effizient mit Pattern Matching gelöst werden. Der folgende Code wendet eine rekursive Funktion loop auf eine Liste an und sammelt die Summe al-ler Elemente im Akkumulator-Parameter acc. Mit dem match-Konstrukt wird die erste Zeile ausgeführt, bei welcher das Muster mit dem erhaltenen Wert übereinstimmt. Aus-serdem erlaubt match die Aufteilung einer Liste in das erste Element (head) und die Rest-Liste (tail). Solange die Liste nicht leer ist, wird die Funktion rekursiv aufgerufen. Erhält loop als Parameter jedoch die leere Liste bedeutet dies dass die gesamte Liste abgearbeitet worden ist und nun die Summe zurückgegeben werden soll.

let sum list = let rec loop list acc = match list with | head :: tail -> loop tail (acc + head) | [] -> acc loop list 0

Die Bibliothek von F# bietet einige Methoden für die Arbeit mit Listen an. Diese Metho-den erwarten typischerweise eine Funktion als Argument, welche dann auf jedes Listen-element angewendet wird. Beispiele solcher Methoden sind List.iter, List.map, List.filter und List.fold. Folgende Beispiele zeigen die unterschiedlichen Semantiken dieser Funk-tionen. Als Ausgangslage nehmen wir eine Liste, welche die Quadrate der Zahlen von 0 bis 10 enthält.

let squares = [for i in 0 .. 10 -> i * i]

List.iter benötigt eine Funktion vom Typ 'T -> unit. Diese Funktion wird für jedes Element einmal aufgerufen und kann z.B. genutzt werden, um die Elemente auf der Konsole aus-zugeben. Eine anonyme Funktion wird mit dem Schlüsselwort fun eingeleitet, danach folgt die Parameterliste und schliesslich hinter einem Pfeil der Funktionsrumpf.

List.iter (fun e -> printfn "Element: %d" e) squares

List.map erzeugt eine neue Liste mit den Elementen, die durch die übergebene Funktion erzeugt werden. Diese neue Liste kann einen anderen Typ haben als die ursprüngliche Liste.

let tenthPart = List.map (fun e -> (float e) / 10.0) squares


List.filter erzeugt eine neue Liste, welche nur noch die Elemente enthält, für welche die Filterfunktion true zurückgibt.

let smallElements = List.filter (fun e -> e < 50) squares

List.fold führt während dem Iterieren über die Liste ein Status-Element mit. Damit kann z.B. eine Liste aufsummiert werden.

let sum = List.fold (fun state e -> state + e) 0 squares

Discriminated Unions

Discriminated Unions sind Typen, welche nur einen Wert aus einer bestimmten endli-chen Menge haben können. Diese Einschränkung erlaubt es dem Compiler zusätzliche Überprüfungen durchzuführen. Beispielsweise wird bei Pattern Matching geprüft, ob auch wirklich alle Fälle abgefangen werden.

Um einen solchen Typ zu definieren wird das Schlüsselwort type verwendet. Wir definie-ren nun für die vier Farben in einem Kartenspiel den Typ Suit. Ein Wert vom Typ Suit kann also nur einen der vier Werte Heart, Diamond, Spade oder Club haben.

type Suit = Heart | Diamond | Spade | Club

Jeder Wert in einer Discriminated Union kann selber einen Typ haben. So können wir einen Typ für alle Karten in einem Kartendeck definieren:

type PlayingCard = | Ace of Suit | King of Suit | Queen of Suit | Jack of Suit | ValueCard of int * Suit

Dank diesen Definitionen kann man jetzt direkt im Code mit den entsprechenden Be-zeichnern arbeiten. Ace(Heart), ValueCard(3, Spade), ValueCard(2, Heart), sind zum Beispiel alles gültige Ausdrücke und repräsentieren jeweils eine Karte.

In C# würde man für den selben Zweck wohl eine Karten-Klasse erzeugen. Dass Discri-minated Unions normalen Klassen in bestimmten Fällen überlegen sind, zeigt sich vor allem im Zusammenhang mit Pattern Matching:

let detectPair (cards:PlayingCard list) = match cards with | [Ace(x); Ace(y)] -> printfn "Two Aces (%A, %A)" x y | [King(x); King(y)] -> printfn "Two Kings (%A, %A)" x y | [Queen(x); Queen(y)] -> printfn "Two Queens (%A, %A)" x y | [Jack(x); Jack(y)] -> printfn "Two Jacks (%A, %A)" x y | [ValueCard(x, s1); ValueCard(y, s2)] when x = y -> printfn "Pair of numbers" | [] | [_] -> failwith "These aren't two cards." | cards when List.length cards > 2 -> failwith "More than two cards." | [first; second] -> printfn "No pair"

Diese Funktion kann bei einer Liste aus zwei Karten feststellen, ob es sich um ein Paar handelt oder nicht. Wird ein Paar gefunden, werden auch die Farben der beiden Karten ausgegeben. In diesem Beispiel verwenden wir die Möglichkeit, einem Parameter expli-zit einen Typen zuzuweisen. Der Typ wird nach einem Doppelpunkt hinter dem Parame-ternamen geschrieben und das Ganze wird in Klammern gesetzt.


Ein weiterer Vorteil von Discriminated Unions ist die Möglichkeit, auf einfachste Weise rekursive Datentypen zu definieren. Ein Binärbaum wird folgendermassen definiert:

type BinaryTree = | Node of int * BinaryTree * BinaryTree | Empty

Ein Wert vom Typ BinaryTree ist entweder ein Knoten mit einem Integer-Wert und zwei Kinder-Bäumen oder er ist leer. Nun ist es möglich, einen Binärbaum folgendermassen zu definieren.

let tree = Node (0, Node (1, Node (2, Empty, Empty), Empty ), Node (3, Node (4, Empty, Empty), Node (5, Empty, Empty) ) )

Der Vorteil dieser Datenstruktur kommt wiederum beim Pattern Matching zum Vor-schein. Für rekursive Datenstrukturen mit Discriminated Unions bieten sich rekursive Funktionen an. Mit folgender Funktion kann die Anzahl Knoten in einem Baum gezählt werden. Wird ein Knoten gefunden, wird der Zähler um eins erhöht und die Funktion wird rekursiv für die beiden Kinder-Bäume aufgerufen.

let getTreeSize (tree:BinaryTree) : int = let rec countNodes (tree:BinaryTree) (counter:int) : int = match tree with | Node (_, left, right) -> countNodes left (countNodes right (counter+1)) | Empty -> counter countNodes tree 0

4.6. Parallelprogrammierung in F#

.NET Parallel Framework

Da F# in die .NET Platform integriert ist sind auch alle parallelen Mechanismen aus der .NET Kernbibliothek verfügbar. Dazu gehört die Task Parallel Library, welche Funk-tionen wie Parallel.For und Parallel.ForEach bietet. Es ist auch möglich PLINQ, die par-allele Version von LINQ, zu verwenden.

Asynchrone Abläufe

Eine Spezialität von F# ist die enge Integration von asynchronen Abläufen. Wichtige Funktionen dazu sind async, use, let!, do! und return!. Das folgende Beispiel aus dem Buch [Sym10] zeigt eine Funktion zur asynchronen Verarbeitung von Bild-Dateien. Durch die Verwendung von asynchronen Lese- und Schreib-Operationen für die Dateien kann ein Thread während dem E/A-Vorgang für andere Aufgaben freigegeben werden. Mit Async.Parallel wird eine asynchrone Aufgabe erstellt, welche die übergebenen Auf-gaben parallel ausgeführt. Schliesslich wird diese asynchrone Aufgabe mit Async.Run-Synchronously ausgeführt und auf das Resultat gewartet.


0

1 3

2 4 5

open System.IOlet numImages = 200let size = 512let numPixels = size * size

let transformImage (pixels, imageNum) = // Manipulate pixels... pixels'

let processImageAsync img = async { use inStream = File.OpenRead(sprintf "Image%d.tmp" img) let! pixels = inStream.AsyncRead(numPixels) let pixels' = transformImage(pixels, img) use outStream = File.OpenWrite(sprintf "Image%d.done" img) do! outStream.AsyncWrite(pixels') }

let processImagesAsync() = let tasks = [ for i in 1 .. numImages -> processImageAsync i ] Async.Parallel tasks |> Async.RunSynchronously |> ignore

Message Passing

Mit einem MailboxProcessor kann ein Message Passing System implementiert werden. Im folgenden Beispiel sind drei verschiedene Nachrichten-Typen möglich. Je nachdem, von welchem Typ die Nachricht ist, führt der MailboxProcessor etwas anderes aus oder ignoriert die Nachricht sogar.

type Message = | Message1 of int | Message2 of string | MessageToIgnore

let agent = MailboxProcessor.Start(fun inbox -> let rec loop() = inbox.Scan(function | Message1(m) -> Some (async { printfn "Message1: %d" m return! loop() }) | Message2(m) -> Some (async { printfn "Message2: %A" m return! loop() }) | MessageToIgnore -> None ) loop())

Um das System zu testen werden folgende Nachrichten versendet. Ausserdem geben wir dem Programm mit Thread.Sleep etwas Zeit, um die Nachrichten abzuarbeiten.

agent.Post (Message1 5)agent.Post (Message2 "Hello!")agent.Post (MessageToIgnore)agent.Post (Message1 12)Thread.Sleep(1000)


Die Ausgabe dieses Beispiels ist folgende:

Message1: 5Message2: "Hello!"Message1: 12

Zukünftige Funktionen für Parallelprogrammierung

Will man einem Wert den Bezeichner parallel geben, erscheint die Meldung, dass dieser Begriff als Schlüsselwort für zukünftige F#-Versionen reserviert ist. Daraus lässt sich schliessen, dass wahrscheinlich noch weitere Funktionen geplant sind, um Parallelpro-grammierung noch einfacher zugänglich zu machen.

4.7. Interoperabilität mit C#Die Zusammenarbeit zwischen F# und C# Assemblies funktioniert problemlos. Will man in einem C# Projekt eine F# Library verwenden genügt es, eine Referenz auf diese Bi-bliothek hinzuzufügen.

Umgekehrt kann auch eine C# Library aus F# verwendet werden. Da F# einige Speziali-täten mitbringt ist es in gewissen Situationen nötig, in C# zusätzlich die Assembly FSharp.Core zu referenzieren und den Namespace Microsoft.FSharp.Core zu importie-ren. Ein solcher Spezialfall ist der Zugriff auf Objekte vom Typ option<T>, da diese Klas-se in der F# Kernbibliothek definiert ist.


5. Testprogramme und Performancemessungen

Wir implementieren nun einige Testprogramme in F# und vergleichen deren Performan-ce mit einer effizienten C#-Variante.

5.1. ZeitmessungJegliche Messungen werden in der Release-Konfiguration durchgeführt, wobei die Opti-on „Optimize code“ aktiviert ist. In F# Programmen ist zusätzlich die Option „Generate tail calls“ eingeschaltet. Für jeden Messwert werden drei Messungen durchgeführt, wo-bei der kleinste Wert übernommen wird. Alle Messungen werden auf einem Lenovo T400s Notebook mit 32 Bit Windows Vista und Visual Studio 2010 durchgeführt. Das Gerät hat 4 GB RAM und eine Intel Core 2 Duo CPU mit 2.4 GHz. Da der Prozessor zwei Kerne hat, ist bei paralleler Ausführung von Programmen ein Geschwindigkeitsge-winn von bis zu 100 Prozent zu erwarten.

Zur Messung der Geschwindigkeit von Programmen verwenden wir die Stopwatch Klas-se aus dem Namespace System.Diagnostics.

5.2. Mersenne-PrimzahlensucheDer erste Performance-Vergleich zwischen C# und F# ist eine Mersenne-Primzahlen-Suche.7 Für die Suche wird der Lucas-Lehmer-Test für Mersenne-Primzahlen verwen-det:

Sei p ungerade und prim. Die Folge S(k) sei definiert durch:S(1) = 4S(k+1) = S(k)2-2.Dann gilt: Mp = 2p-1 ist genau dann eine Primzahl, wenn S(p–1) durch Mp teilbar ist.8

Beide Implementationen enthalten eine rekursive Methode zur Berechnung von S(k) und eine Methode zum Testen ob Mp prim ist.

Wir speichern nur die Exponenten p ab, mit welchen sich eine Mersenne-Zahl bilden lässt. Zuerst werden die Primzahlen von 2 bis 2000 gesucht und in einer Liste/Sequenz gespeichert. Somit können wir in C# auf LINQ zurückgreifen, um Mersenne-Primzahlen zu finden:

var sData = from num in primes where msc.IsMersenne(num) select num;

Auf jedem Element der Liste primes wird die Methode IsMersenne aufgerufen. Diese lie-fert true zurück, wenn die Zahl eine Mersenne-Zahl ist. Wenn dies der Fall ist, wird der entsprechende Exponent in sData gespeichert. Speziell ist, dass sData nicht evaluiert wird, solange kein Wert aus dieser Collection gebraucht wird. Erst wenn der Zugriff ge-schieht, werden die einzelnen Werte errechnet, der Zeitaufwand geschieht also in den folgenden Zeilen:

foreach (var e in sData) Console.Write(e + " ");

In F# wird die Suche sehr ähnlich implementiert. Anstelle einer List wird eine Sequence verwendet, was eine andere Schreibweise mit anderen Funktionen zur Folge hat. Trotz-7 Projekte MersenneFSharp und Mersenne in der Solution TestCasesZogg8 http://de.wikipedia.org/wiki/Lucas-Lehmer-Test


dem wird auch bei der F#-Implementierung erst beim Zugriff auf die Elemente gerech-net.

let mersenne = Seq.filter IsMersenne primesSeq.iter (printf "%d ") mersenne

Seq.filter liefert eine neue Sequenz welche nur die Elemente enthält, für welche die an-gegebene Funktion IsMersenne true liefert. Seq.iter führt eine Funktion auf jedem Ele-ment der Sequenz aus, in diesem Beispiel gibt sie alle Elemente auf der Konsole aus.

Das in C# bereits standardmässig eingebundene PLINQ erlaubt es, ohne viel Aufwand eine parallele Version dieser Lösung zu schreiben:

(primes.AsParallel().Where<int>(n => msc.IsMersenne(n))) .ForAll(i => Console.Write(i + " "));

Die Verarbeitung wird durch die Verwendung von AsParallel() auf mehrere Threads auf-geteilt. Mit der Funktion ForAll() kann ein Delegate oder ein Lambda-Ausdruck auf jedes Element angewendet werden.

Auch F# kann PLINQ nutzen sobald der Namespace geöffnet ist:

open System.Linq

Die Implementation ist ähnlich wie in C#. Es wäre auch hier möglich, ForAll() zu verwen-den, wir benutzen aber hier Seq.iter() um die Zahlen auszugeben.

let mersenne = primes.AsParallel().Where(IsMersenne)Seq.iter (printf "%O ") mersenne

Neben PLINQ wird auch je eine Implementation mittels Parallel.ForEach() gemacht.

Wir vergleichen nun die Geschwindigkeiten der verschiedenen Varianten (Tabelle 1). Es werden jeweils die Primzahlen zwischen 2 und 2000 getestet und gültige Exponenten ausgegeben. Bei C# muss PLINQ optimiert werden, indem chunk partitioning erzwun-gen wird. Bei F# wird auch ohne diese Optimierung die gleiche Performance erreicht. Die Variante mit Parallel.ForEach() schneidet beinahe so gut ab wie die optimierte PLINQ-Variante. Der Geschwindigkeitsgewinn durch Parallelisierung ist in beiden Spra-chen der gleiche. Dies ist nicht erstaunlich, da in beiden Sprachen auf die gleichen Funktionen der .NET-Bibliothek zurückgegriffen wird. Fraglich bleibt, warum PLINQ in F# ohne Optimierung schneller ist als in C#.

F# C#

Sequentiell 23.6s 23.7s

PLINQ 13.6s 22.5s

PLINQ optimiert 13.5s 13.6s

Parallel.ForEach 14.5s 14.1s

Speed-up 74% 74%

Tabelle 1: Geschwindigkeitsvergleich Mersenne-Primzahlen-Suche

5.3. Matrix-MultiplikationFür den zweiten Vergleich wird in beiden Sprachen eine Matrix-Multiplikation program-miert.9 Diesmal wird die Parallelisierung durch die Verwendung der Funktion Parallel.-

9 Projekte ArrayMatrixFSharp und ArrayMatrixCSharp in der Solution TestCasesZogg


For() erreicht. Zur Speicherung der Matrizen werden Blockarrays benutzt, damit über Pointer auf die einzelnen Werte zugegriffen werden kann.

Die Matrix-Multiplikation besteht jeweils aus drei verschachtelten For-Schleifen, wobei für die parallelen Varianten jeweils die äusserste Schleife durch Parallel.For() ersetzt wird. Der Befehl Parallel.For() führt die Funktion rowTask mit den Werten 0 bis (ne-wHeight - 1) parallel aus. In F# sieht die Variante ohne Pointer so aus:

let rowTask i = let mutable v = 0.0f for j = 0 to newWidth - 1 do v <- 0.0f for k = 0 to size - 1 do v <- v + a.[k, i] * b.[j, k] c.[i, j] <- v ()

Parallel.For(0, newHeight, rowTask) |> ignore

In C# sieht der Programmcode sehr ähnlich aus:

Parallel.For(0, newHeight, delegate(int i){ float v; for (int j = 0; j < newWidth; ++j) { v = 0; for (int k = 0; k < size; ++k) { v += m1[k, i] * m2[j, k]; } c[i, j] = v; }});

Um die Geschwindigkeit nochmals zu steigern, erstellen wir eine weitere Implementation mit Pointern. Durch die Verwendung von Pointern ist der Code nicht mehr so übersicht-lich wie vorher. Einerseits müssen nun die Speicherplätze selber berechnet werden und andererseits erfolgen Pointer-Operationen in F# mit relativ umständlichen Funktionen. Während man in C# sehr elegant mit dem Stern-Operator einen Pointer dereferenzieren kann müssen in F# Operationen wie NativePtr.read und NativePtr.write verwendet wer-den.

Für die Geschwindigkeitstests werden zwei Matrizen multipliziert, wobei eine die Dimen-sion 800x1000 hat und die andere 600x800. Die Ergebnisse sind in Tabelle 2 aufgeführt und zeigen, dass es in diesem Beispiel praktisch keine Performance-Unterschiede zwi-schen den beiden Sprachen gibt.


F# C#


Sequentiell mit Pointern 2.05s 2.10s

Parallel 2.34s 2.51s

Parallel mit Pointern 1.12s 1.15s

Speed-up 83% 82%

Tabelle 2: Geschwindigkeitsvergleich Matrix-Multiplikation

5.4. Pythagoras-TripelPythagoras-Tripel sind ganzzahlige Werte a, b und c für welche a2 + b2 = c2 gilt. Zur Be-stimmung aller Tripel für ein gegebenes a verwenden wir folgende Methode:

Gegeben sei a. Man teile a2 durch eine beliebige Zahl d. Dann sind b = (a2/d - d)/2 und c = b + d die beiden anderen Seiten des Dreiecks.10

Die Parallelisierung erfolgt mittels Parallel.For(). Für die Performance-Messung werden alle Pythagoras-Tripel mit a <= 80'000 gesucht. Die Messwerte in Tabelle 3 zeigen, dass bei diesem Programm beide Sprachen die gleiche Leistung erbringen. Die parallele Ver-sion ist jeweils beinahe doppelt so schnell wie die sequentielle.11

F# C#



Speed-up 90% 92%

Tabelle 3: Geschwindigkeitsvergleich Pythagoras-Tripel

5.5. Lazy SequenzenF# bietet spezielle Sequenzen an, welche erst evaluiert werden, wenn auf die Elemente zugegriffen wird (lazy evaluation).12

Fibonacci kann damit so definiert werden:13

let fib = Seq.unfold (fun (a,b) -> let fibElement = a + b if fibElement < b then None else Some(fibElement, (b, fibElement))) (0,1)

Erst wenn durch die Sequenz fib iteriert wird, wird der dahinter liegende Code ausge-führt. Beim Tupel (a,b) handelt es sich um einen Statuswert, der bei Seq.unfold weiter-gegeben wird. So ist es möglich, mit diesem Wert die beiden letzten Fibonacci-Werte zur Berechnung des nächsten Elementes weiterzugeben.

Damit der Maximalwert eines Integers nicht überschritten wird, haben wir eine Abbruch-bedingung eingeführt. Sobald None zurückgegeben wird, bricht die Sequenz ab. Dem Konstruktor Some() wird als erster Parameter das aktuell erzeugte Element der Se-

10 http://www.arndt-bruenner.de/mathe/scripts/pythagotripel.htm11 Projekte FS_Pythagoras und CS_Pythagoras in der Solution TestCasesHerzog12 Sequenzen in der MSDN: http://msdn.microsoft.com/en-us/library/dd233209.aspx13 Projekte FS_Lazy_Lists und CS_Fibonacci in der Solution TestCasesHerzog


quenz übergeben und als zweiter Parameter der Statuswert, der für die Berechnung des folgenden Elementes verwendet wird.

Da die Sequenz endlich ist kann sie mit einer For-Schleife ausgegeben werden.

for f in fib do printfn "%d" f

Da Fibonacci-Zahlen sehr schnell wachsen, reicht ein Integer nur für wenige Elemente. Für beinahe beliebig grosse Zahlen eignet sich die Klasse BigInteger, so können wir auch die Abbruchbedingung weglassen und erhalten damit eine endlose Sequenz.

let fibBigInt = Seq.unfold (fun (a,b) -> let fibElement = a + b Some(fibElement, (b, fibElement))) (BigInteger(0),BigInteger(1))

Würden wir über diese Sequenz nun mit einer for-Schleife iterieren, würde dies eine Endlosschleife ergeben. Da die Elemente in einer einfachen Sequenz nicht abgespei-chert werden, beschränkt der Speicher die Anzahl Elemente erst, wenn die einzelnen Elemente zu gross werden.

Es ist möglich, auf beliebige Elemente einer Sequenz zuzugreifen:

let res = Seq.nth 150000 fibBigIntCache

Sequenzen können bei Bedarf gecachet werden, so dass die Werte ab dem zweiten Zu-griff nicht mehr neu berechnet werden müssen. Der Preis dafür ist ein erhöhter Zeitbe-darf beim ersten Durchlaufen der Sequenz und eine Beschränkung der Sequenzgrösse durch den Arbeitsspeicher. Um die ersten 150'000 Fibonacci-Elemente zu speichern werden rund 900 MB RAM benötigt.

let fibBigIntCache = Seq.cache fibBigInt

Um die Performance von Sequenzen zu untersuchen, verwenden wir zum Vergleich eine rekursive Variante der Fibonacci-Folge.

let rec fibBigIntRecursive n a b = if n > 0 then fibBigIntRecursive (n-1) b (a+b) else b

In C# führt die rekursive Implementierung zu einer StackOverflowException. In F# ist dies nicht der Fall, da der F#-Compiler Endrekursion erkennt und durch iterativen Code ersetzt.

Tabelle 4 zeigt für verschiedene Szenarien die Zugriffszeit zur Berechnung des 150'000sten Elements der Fibonacci-Folge. Daraus ist ersichtlich dass die Verwendung einer Sequenz nur geringfügig langsamer ist als die rekursive Variante in F# oder die iterativen Versionen in C# und F#. Es gibt auch praktisch keinen Unterschied zwischen der rekursiven und der iterativen Implementation in F#. Das Aufbauen des Caches re-sultiert in diesem Beispiel in einer mehr als doppelt so langen Ausführungszeit, dafür ist danach der Zugriff auf ein schon berechnetes Element viel schneller. Der Cache scheint als verlinkte Liste implementiert zu sein, denn der Zugriff auf das erste Element ist viel schneller als der Zugriff auf das letzte Element.


F# C#

Ohne Cache 2.09s -

Mit Cache, 1. Durchlauf 4.85s -

Mit Cache, 2. Durchlauf 0.078s -

Rekursiv 1.98s -

Iterativ 2.00s 1.99s

Tabelle 4: Geschwindigkeitsvergleich Fibonacci

Gemäss MSDN ist es möglich, eine gecachte Sequenz aus mehreren Threads zu ver-wenden. So könnte z.B. ein Thread neue Elemente berechnen und andere Threads kön-nen schon berechnete Elemente konsumieren.

5.6. Einfache BildverarbeitungUm zu untersuchen ob F# bei Bildverarbeitungs-Aufgaben mit C# mithalten kann, imple-mentieren wir in beiden Sprachen eine Inverter- und eine Filter-Funktion.14 Für das GUI, welches in C# programmiert ist, verwenden wir WPF (Windows Presentation Foundati-on). Somit kann auch die Interoperabilität zwischen den beiden Sprachen untersucht werden.

Die Bildverarbeitungs-Operationen werden direkt auf dem Buffer des WPF-Bildes durch-geführt, welches eine Instanz der Klasse WriteableImage ist. Während bei der Invertie-rung direkt das Originalbild bearbeitet wird, ist beim Filter eine Kopie nötig.

In F# erscheint bei der Verwendung von Zeigern die Warnung, dass dies zu nicht-verifi-zierbarem IL-Code15 führt. Diese Warnung kann mit folgender Direktive am Anfang einer Datei deaktiviert werden.

#nowarn "9"

Um in C# mit Pointern arbeiten zu können ist jeweils ein Unsafe-Block notwendig.

Invertieren

Für die Zeitmessung wird ein ca. 8 MB grosses Foto mit einer Abmessung von 4670 x 2000 Pixeln verwendet.16 Wie schon bei früheren Versuchen wird jede Aktion drei mal für jede Sprache ausgeführt und es wird jeweils die beste Zeit verwendet. So könnten die Sprachen jeweils gleichberechtigt ein Caching ausnutzen. Die beobachteten Unter-schiede zwischen dem ersten Aufruf und den weiteren Aufrufen sind allerdings sehr ge-ring.

14 Projekte FS_Image_02_Color und CS_ImageLibColor in der Solution TestCasesHerzog15 Intermediate Language Code (kann auf der .NET Common Language Runtime ausgeführt werden)16 Datei: Hong Kong Night Skyline.jpg


F# C#

Ohne Optimierung 0.047s 1.07s

Schleifenbedingungausgelagert

0.047s 0.039s

Rekursiv 0.035s -

Rekursiv, mit Closure-Kontext

0.038s -

Mit Pointer-Sequenz 2.94s -


Parallel, mit Rekursion 0.022s -

Speed-up 59% 85%

Tabelle 5: Geschwindigkeitsvergleich Bild-Invertierung

Tabelle 5 zeigt die Geschwindigkeit für verschiedene Varianten des Inverters in F# und C#. Auffällig ist die schlechte Performance der ersten C#-Version, welche folgende zwei Schleifen besitzt:

for (int i = 0; i < wb.PixelHeight; ++i){ for (int j = 0; j < wb.PixelWidth * 4; ++j) { *p = (byte)(255 - *p); ++p; }}

Werden nun Teile der Schleifenbedingungen ausgelagert, wird der Code massiv schnel-ler.

int maxHeight = (wb.PixelHeight);int maxWidth = (wb.PixelWidth) * 4;for (int i = 0; i < maxHeight; ++i){ for (int j = 0; j < maxWidth; ++j) { *p = (byte)(255 - *p); ++p; }

}

Bei der F#-Version der gleichen Schleifen bringt die selbe Optimierung überhaupt kei-nen Unterschied in der Geschwindigkeit. Es scheint also, dass F# diese Optimierung selber vornimmt, d.h. die Schleifenbedingung wird in F# nicht jedes mal neu berechnet.

In F# ist die rekursive Variante schneller als die iterative, wobei man das beste Ergebnis erzielt, wenn alle benötigten Werte als Parameter und nicht über den Closure-Kontext übergeben werden.

Eine weiterer Ansatz für F# ist das Erzeugen einer Sequenz, welche für jeden Pixel einen Pointer enthält. Diese Variante ist jedoch sehr langsam.


Die Parallelisierung erfolgt in beiden Sprachen indem mit Parallel.For() über die Zeilen iteriert wird. Die iterative C#-Implementation ist praktisch gleich schnell wie die rekursive F#-Version. Bei F# ist der Performancegewinn prozentual etwas geringer als bei C#, da in F# die sequentielle Version schon sehr schnell ist.

Beide Sprachen erreichen schliesslich etwa die gleiche Geschwindigkeit. Entscheiden-der als die Sprache ist mehr die Art der Implementation und das Performance-Tuning. Experten könnten die Geschwindigkeit des Codes möglicherweise noch weiter steigern.

Die Interoperabilität mit C# funktioniert problemlos. Eine F# Library wird unter C# genau gleich verwendet wie eine C# Library. Wüsste man nicht, in welcher Sprache die Library programmiert ist, so könnte man den Unterschied nicht auf Anhieb feststellen.

Filter

Für einen weiteren Vergleich werden in beiden Sprachen Filter-Algorithmen implemen-tiert, welche einen X-Y-separierten Filter auf ein Farbbild anwenden. Für die Tests wer-den folgende beiden Filter verwendet, wobei die X- und die Y-Komponenten jeweils gleich sind:

Kantendetektierungs-Filter:

-1.0; -1.0; 0.0; 1.0; 1.0

Gauss-Weichzeichner, entsprechend folgendem C#-Code:

double[] filter = new double[(radius*2)+1];for (int i = -radius; i < radius + 1; i++){ filter[i + radius] = Math.Exp(-(Math.Pow(i, 2.0) / (2.0 * Math.Pow(radius, 2.0))));}

F# C#

Kantendetektierung 5.53s 2.02s

Gauss-Filter 10.32s 2.50s

Tabelle 6: Geschwindigkeitsvergleich Filter

In Tabelle 6 sind die Ergebnisse der Performance-Messungen festgehalten, welche mit dem gleichen Bild durchgeführt wurden wie schon bei der Invertierung.F# ist bei diesen Messungen etwa um den Faktor 2 bis 4 langsamer. Die Frage ist nun, woher dieser Unterschied rührt. Die beiden Algorithmen sind von der Struktur her sehr ähnlich aufgebaut und arbeiten beide mit Zeigern. Der C#-Code ist praktisch eine Über-setzung des F# Codes. Dort wo in F# Funktionen übergeben werden, wird in C# auf De-legates zurückgegriffen.

Dass Zeigerarithmetik in F# genau so effizient funktioniert wie in C# haben wir schon im Inverter-Beispiel gezeigt, also muss die schlechte Performance einen anderen Grund haben.

Der Verdacht kommt auf, dass veränderbare Werte in F# nicht so performant sind wie Variablen in C#. Um dies zu prüfen implementieren wir verschiedene Varianten von ein-fachen Zählern, welche bis 2 Milliarden zählen.17

17 Projekte FS_Counter und CS_Counter in der Solution TestCasesHerzog


Die erste Variante in F# ist iterativ und verwendet einen veränderbaren Wert.

let mutable v = 0for i = 1 to 2000000000 do v <- v + 1

Die zweite Variante in F# ist rekursiv und benötigt deshalb keinen veränderbaren Wert.

let rec inc num countdown = if countdown > 0 then inc (num + 1) (countdown – 1) else numlet w = inc 0 2000000000

In C# ist nur eine iterative Variante mögliche.

int n = 0;for (int i = 0; i < 2000000000; ++i) n = n + 1;

Der Test zeigt, dass in F# die rekursive Variante viel effizienter ist als die iterative Vari-ante mit einem veränderbaren Wert. Die C#-Version ist nochmals etwas schneller als F# (Tabelle 7). Daraus können wir schliessen, dass veränderbare Werte in F# nicht ver-wendet werden sollten, wenn diese sehr oft verändert werden müssen.

F# C#

Zähler iterativ 5.07s 0.84s

Zähler rekursiv 1.13s -

Tabelle 7: Geschwindigkeitsvergleich Counter-Test

Das Eliminieren von veränderbaren Werten durch das Verwenden von rekursiven Funk-tionen bringt nicht den erwünschten Effekt, die Geschwindigkeit ist immer noch gleich. Der grosse Geschwindigkeitsunterschied im Counter-Beispiel ist in der Praxis nicht so entscheidend. Wenn die Arbeit pro Schleifendurchgang wesentlich grösser ist als das Inkrementieren des Zählers, kann die Zeit des Zählers vernachlässigt werden. Ausser-dem wird wohl eine rekursive Lösung auch weniger schnell, wenn viele Parameter wei-tergegeben werden.

Der grosse Unterschied zwischen den beiden Sprachen lässt uns keine Ruhe und wir publizieren das Problem auf stackoverflow.com.18 Schon nach wenigen Stunden erhal-ten wir die ersten Antworten und nach zwei Tagen findet jemand den entscheidenden Unterschied. Während C# mit einer einzigen IL-Anweisung (conv.r8) eine Konversion von Byte zu Float64 durchführt wird der Cast bei F# in zwei Schritten durchgeführt. Zu-erst wird der Byte-Wert nach Float32 umgewandelt (conv.r.un) und erst dann nach Float64 (conv.r8). Wir melden dieses Problem an Microsoft, wo uns bestätigt wird, dass es sich dabei um einen Bug handelt. In einer zukünftigen Versionen von F# wird das Problem behoben sein.

Der langsame F#-Code sieht folgendermassen aus:

acc <- acc + (float (NativePtr.read b)) * (NativePtr.read f)

Mit einem Workaround kann der Umweg über Float32 verhindert werden:

acc <- acc + (float (int16 (NativePtr.read b))) * (NativePtr.read f)

Nun wird der Filter-Algorithmus parallel implementiert, unter Verwendung der Parallel.-For Funktion. Die Messergebnisse der verschiedenen Versionen sind in Tabelle 8 und Tabelle 9 aufgeführt. Nach der Optimierung ist F# geringfügig schneller als C#. Durch

18 http://stackoverflow.com/questions/4739723/f-image-manipulation-performance-problem


die Parallelisierung kann bei beiden Sprachen eine Beschleunigung von über 90% er-reicht werden.

F# C#


Sequentiell optimiert 1.68s -


Speed-up 93% 96%

Tabelle 8: Geschwindigkeitsvergleich Kantendetektierung

F# C#


Sequentiell optimiert 2.33s -


Speed-up 94% 93%

Tabelle 9: Geschwindigkeitsvergleich Gauss-Filter

Dieses Beispiel bringt uns folgende Erkenntnisse:

• Es ist für die Geschwindigkeit meist nicht entscheidend, ob in F# mit Rekursion oder mit veränderbaren Werten gearbeitet wird. Da das Eine oder das Andere in be-stimmten Fällen etwas schneller sein kann, lohnt es sich aber, damit zu experimen-tieren.

• Je öfter ein Codestück ausgeführt wird, desto wichtiger ist es, dass dieser Code effi-zient ist.

• Es gibt eine funktionierende Community um F#, welche bei schwierigen Problemen helfen kann (z.B. auf stackoverflow.com).

• Die Tatsache dass der Quellcode der F#-Core-Bibliotheken freigegeben ist, kann bei der Lösungssuche äusserst aufschlussreich sein.

• F# hat noch Potential für gewisse Verbesserungen wobei die Community aktiv zu diesen Verbesserungen beitragen kann (z.B. indem das F# Team unter [email protected] kontaktiert werden kann).

5.7. Arrays erzeugenWir untersuchen zwei unterschiedliche Arten, wie ein Array in F# erzeugt werden kann.19 Zu Testzwecken füllen wir die Arrays mit Zufallszahlen (r.Next() liefert jeweils die nächs-te Zahl).

Die elegantere Variante verwendet eine For-Schleife, um die Werte zu initialisieren:

let array = [| for i in 1..50000000 -> r.Next() |]

19 Projekte FS_Array und CS_Array in der Solution TestCasesHerzog


In der zweiten Variante wird ein Array vorerst mit Nullen initialisiert und erst danach wer-den die Werte gesetzt.

let array2 = Array.zeroCreate 50000000for i in 0 .. array2.Length - 1 do Array.set array2 i (r.Next())

In C# muss auch zuerst ein leeres Array erzeugt werden, bevor die Werte gesetzt wer-den können.

int ArraySize = 50000000;int[] intArray = new int[ArraySize];for (int i = 0; i < ArraySize; i++) intArray[i] = r.Next();

Die elegantere F#-Variante schneidet etwa um den Faktor zehn schlechter ab als die beiden anderen Varianten (Tabelle 10). Schuld daran ist die Tatsache, dass der Code for i in 1..50000000 eine Sequenz erzeugt, welche danach mit der Funktion Seq.toArray in ein Array umgewandelt wird. Diese Umwandlung erfolgt unter Verwendung einer Ar-ray-Liste (System.Collections.Generic.List), welche intern ein Array verwaltet, das in ein grösseres Array kopiert wird, sobald es voll ist. Die Array-Liste wird schliesslich noch-mals in ein neues Array kopiert, welches exakt die Länge der ursprünglichen Sequenz hat.

Wir möchten mit diesem Beispiel, welches auf den ersten Blick trivial erscheinen mag, zeigen, dass eine elegantere Codierung nicht immer gleich schnell ist, wie eine etwas umständliche. Nur das Wissen über die Implementierung, die dahinter liegt, erlaubt es dem Entwickler, sich jeweils für die richtige Variante zu entscheiden.

F# C#

Werte direkt setzen 8.08s -

Werte nachträglich setzen 0.81s 0.78s

Tabelle 10: Geschwindigkeitsvergleich Array erzeugen


6. Face Detection Projekt

Mit den gesammelten Erfahrungen aus den gezeigten Testprogramm wollen wir nun ein grösseres Projekt in F# umsetzen. Dabei handelt es sich um ein Programm, welches in digitalen Bildern Gesichter finden kann (Face Detection). Die genauere Analyse von Ge-sichtern zur Identifikation von Personen (Face Recognition) gehört nicht zur geplanten Funktionalität dieses Programms.

6.1. Stand der ForschungDie DBLP-Datenbank20 der Universität Trier findet zum Stichwort „face detection“ 820 Publikationen, wobei alleine im Jahr 2009 75 Papers erschienen sind. Beim Studium dieser Arbeiten fällt auf, dass sich einige wenige Methoden für die Gesichtslokalisierung etabliert haben.

Sehr oft werden Systeme verwendet welche mit Machine Learning Techniken wie z.B. Neuronalen Netzwerken arbeiten. Diese Systeme müssen mit Positiv- und Negativbei-spielen trainiert werden, damit sie lernen, wie ein Gesicht charakterisiert ist. Nach der Trainingsphase kann ein solches System dann für beliebige Bildausschnitte bestimmen, ob es sich eher um ein Gesicht handelt oder nicht. Mittels geeigneter Optimierungen kann dieses System recht effizient implementiert werden. Soll das System neben Fron-talaufnahmen auch Profilbilder erkennen, muss es dafür speziell trainiert werden, ist dann aber auch in diesem Fall sehr erfolgreich [Schnei00]. Ansätze welche auf Machine Learning basieren können gute Ergebnisse erzielen, sind aber für die beschränkte Zeit, welche uns zur Verfügung steht, zu komplex.

Eine zweite Methode, welche immer wieder beschrieben wird, ist die Gesichtslokalisie-rung durch die Suche von hautfarbenen Bereichen. Da nicht nur das Gesicht Hautfarbe haben kann, sind weitere Überprüfungen nötig, um Bereiche zu verwerfen, welche wahr-scheinlich keine Gesichter sind. Dies kann z.B. durch die Suche von Augen und Mund innerhalb der hautfarbenen Bereiche geschehen. Der Vorteil der farbbasierten Metho-den ist, dass sie relativ einfach invariant gegenüber rotierten Gesichtern implementiert werden können.

6.2. ZielsetzungUm den Aufwand im Rahmen zu halten, implementieren wir eine Gesichts-Lokalisierung mit folgenden Eigenschaften.

• Zum Auffinden von Gesichtskandidaten werden Regionen mit Hautfarbe ge-sucht. Die Kandidaten werden dann auf weitere Merkmale geprüft, um herauszu-finden, ob es sich mit hoher Wahrscheinlichkeit um ein Gesicht handelt.

• Es können nur Gesichter von bekleideten Personen gefunden werden. Wenn ein Gesicht mit anderen Haut-Regionen überlappt, funktioniert die Erkennung nicht.

• Gesichter auf schlecht belichteten oder stark verfremdeten Bildern müssen nicht erkannt werden.

• Gesichter werden nur erkannt wenn sie mehr oder weniger frontal aufgenommen sind. Das heisst, es müssen beide Augen gut erkennbar sein.

20 http://dblp.mpi-inf.mpg.de/dblp-mirror/index.php#query=face%20detection


6.3. AblaufDer gesamte Prozess der Gesichts-Lokalisierung ist in Abbildung 2 dargestellt. Die ein-zelnen Schritte werden in den folgenden Kapiteln erklärt. Der komplette Quelltext ist auf der beiliegenden CD zu finden.


Abbildung 2: Prozess zur Gesichtslokalisierung

6.4. Erkennung von HautfarbeWir untersuchen verschiedene Methoden, die in wissenschaftlichen Artikeln zur Erken-nung von Hautfarbe vorgeschlagen werden. Zusätzlich zeigen wir eine eigene Methode. Die verschiedenen Techniken sind in Tabelle 11 zusammengestellt. Die letzte Spalte dieser Tabelle enthält die Geschwindigkeit für ein Testbild21 von 3648 mal 2736 Pixeln.

Quelle Farbraum Bedingung für Hautfarbe Geschwindigkeit

[Pai06] RGB 0.5R - 0.419G - 0.081B liegt zwischen 10 und 45

0.15s

[Kovac03] RGB R > 95 und G > 40 und B > 20 undmax{R,G,B} - min{R,G,B} > 15 und|R - G| > 15 und R > G und R > B

0.14s

[Hsu02] YCbCr Ellipsenförmige Region mit Hautfarbe in einem nichtlinear transformierten YCbCr Farbraum.

6.0s

EigeneMethode

YCbCr 135 < Cr < 164 und 94 < Cb < 122 2.0s

Tabelle 11: Methoden zur Erkennung von Hautfarbe

[Pai06] [Kovac03]

[Hsu02] Eigene Methode

Tabelle 12: Erkennung von Hautfarbe bei einem Testbild

21 Testbild 1.jpg


Da unser Programm auf Bildern im RGB Farbraum arbeitet, sind Methoden, welche im YCbCr Farbraum arbeiten, mit einem Mehraufwand verbunden. In Tabelle 12 ist ersicht-lich, welche Regionen von welcher Methode als Haut erkannt wurden.

Versuche mit verschiedenen Testbildern haben gezeigt, dass [Kovac03] rein subjektiv die besten Ergebnisse liefert und am tolerantesten gegenüber unterschiedlichen Belich-tungssituationen ist. Ausserdem ist dies eine sehr schnelle Methode. Aus diesen Grün-den wählen wir diese Methode, um Hautfarbe zu erkennen.

Die Bedingungen in der Methode von [Kovac03] werden so umgeordnet, dass diejenige Bedingung zuerst steht, welche am meisten Pixel ausschliesst. Experimente zeigen, dass die beiden Bedingungen r > g und r > b schon eine beachtliche Anzahl Nicht-Haut-Pixel erkennen können. Deshalb stellen wir diese beiden Bedingungen an den Anfang. Dadurch kann max(r,g,b) vereinfacht werden, da wir nun schon wissen dass r das Maxi-mum der drei Komponenten ist. Auch min(r,g,b) wird vereinfacht, da das Minimum ent-weder g oder b ist. Bei |r - g| > 15 kann die Betragsoperation weggelassen werden, da die erste Bedingung schon sicherstellt dass r > g gilt.

Die beiden Bedingungen g > 40 und b > 20 tragen praktisch nichts zur Hauterkennung bei, deshalb werden sie nach hinten geschoben. Die Bedingung r - min(g,b) > 15 sollte dazu dienen, graue Flächen zu eliminieren. Nach unseren Erfahrungen kommt die Be-dingung aber praktisch nie zum Zug, deshalb setzen wir sie ganz an den Schluss. Die Methode sieht nun folgendermassen aus:

let extractFaceColorKovac2003 (wb:WriteableBitmap) : WriteableBitmap = createGreyscaleFrom3ChannelParallel wb (fun (b,g,r) -> if r > g && r > b && r > 95uy && r - g > 15uy && g > 40uy && b > 20uy && r - (min g b) > 15uy then 255uy else 0uy)

Um den Code in der Methode createGreyscaleFrom3ChannelParallel etwas lesbarer zu gestalten definierten wir die folgenden Funktionen:

let read = NativePtr.readlet write = NativePtr.write

Bei den Performance-Messungen fällt uns auf, dass diese Indirektion sehr zeitaufwändig ist. Die Hautfarberkennung beansprucht bei der Verwendung von read anstelle von Nati-vePtr.read etwa drei mal so viel Zeit. Werden die beiden Funktionen mit dem Parameter ergänzt, ist die Hautfarberkennung nur noch geringfügig langsamer.

let read p = NativePtr.read plet write p = NativePtr.write p

Durch die Verwendung des Schlüsselwortes inline fällt die Geschwindigkeit gleich aus wie bei der direkten Verwendung von NativePtr.read. Dieses Schlüsselwort weist den Compiler an, an jeder Stelle wo die Funktion read aufgerufen wird nicht einen Funktions-aufruf zu machen, sondern den Code dieser Funktion direkt dort einzufügen.

let inline read p = NativePtr.read plet inline write p = NativePtr.write p


Wie es der Name der Funktion createGreyscaleFrom3ChannelParallel andeutet, nutzt diese Methode Parallelisierung. Dies wird durch die Verwendung von Parallel.For er-reicht.

6.5. TiefpassfilterUm hochfrequentes Rauschen zu entfernen, wenden wir einen Tiefpassfilter an, wie er in [Pai06] vorgeschlagen wird. Anstatt jedoch eine fixe Filtergrösse von 5x5 Pixeln zu verwenden, wird die Seitenlänge des Filterquadrates abhängig von der Bildgrösse be-stimmt:

let lowPassFilterSize = (max wb.PixelHeight wb.PixelWidth) / 300

Das Bild wird in Quadrate von der Grösse des Filters unterteilt, wobei ein Quadrat nur dann weiss eingefärbt wird, wenn mindestens die Hälfte der Pixel im Quadrat weiss sind. In Tabelle 13 sind die Auswirkungen dieses Filters zu sehen.

Ohne Tiefpassfilter Mit Tiefpassfilter

Tabelle 13: Tiefpassfilter

6.6. Zusammenhängende Regionen findenMit einem Flood Filling Algorithmus werden zusammenhängende Regionen markiert. Dabei wird die Tatsache ausgenutzt, dass das Bild schon Tiefpassgefiltert ist. Für jede Region von der Grösse des Tiefpassfilters muss nur ein Pixel untersucht und markiert werden, da die restlichen Pixel die gleiche Farbe haben (Abbildung 3). Würde man bei unserem Testbild jedes einzelne Pixel untersuchen, dauert das Markieren 0.77 Sekun-den. Wird nur ein Pixel pro Tiefpassfilter-Region untersucht, reduziert sich die benötigte Zeit auf 0.009 Sekunden. Der Tiefpassfilter hat die Dimension 12x12 Pixel.

Abbildung 3: Markierte Pixel nach Flood Filling


Das Flood Filling wird iterativ mit einer Queue ausgeführt. Eine rekursive Implementie-rung ist nicht möglich, da der Algorithmus nicht Endrekursiv ist. Durch die hohe Rekursi-onstiefe würde eine rekursive Variante zu einem Pufferüberlauf führen.

Da für spätere Operationen alle Hautpixel mit einer Markierung versehen sein müssen, werden nun alle weissen Quadrate mit dem Wert, den das Pixel oben links im Quadrat hat, aufgefüllt. Dadurch erhöht sich der Zeitbedarf für das Testbild wieder auf 0.013 Se-kunden. Das Ergebnis ist nun genau gleich wie beim ursprünglichen Verfahren, ist aber für dieses Beispiel um den Faktor 60 schneller.

Aus den markierten Regionen wird eine Liste von Gesichtskandidaten erstellt. Kandida-ten, die nicht mindestens einen Hundertstel der Bildhöhe und der Bildbreite aufweisen, werden sofort verworfen.

Da für die Markierung Byte-Werte verwendet werden, können nur 254 Regionen unter-schiedlich markiert werden. Falls es mehr Regionen gibt, wird für die übrigen Regionen der Byte-Wert 254 verwendet. Hier besteht noch Verbesserungspotential, da dies in späteren Schritten zu Problemen führen kann.

6.7. Plausibilitäts-PrüfungenDie Liste der Gesichtskandidaten wird nun verkleinert, indem Kandidaten, die nicht be-stimmte Bedingungen erfüllen, entfernt werden. Folgende Bedingungen werden geprüft:

• Mindestens 30% des Kandidatenrechtecks müssen Hautfarbe haben.

• Die Breite des Rechtecks muss mindestens ein Dreissigstel der Bildbreite sein.

• Die Höhe des Rechtecks muss mindestens ein Dreissigstel der Bildhöhe sein.

• Die Höhe des Rechtecks geteilt durch die Breite muss einen Wert zwischen 0.33 und 3.0 ergeben.

6.8. Skalierung der verbleibenden KandidatenFür die weiteren Schritte werden nur noch rechteckige Bilder der Gesichtskandidaten benötigt. Um auch bei grossen Bildern eine hohe Geschwindigkeit zu erreichen, werden Kandidaten, die mindestens 300 Pixel breit sind, skaliert. Der Skalierungsfaktor ist die Breite des Kandidaten geteilt durch 150.

6.9. Mund-ErkennungUm Mund-Kandidaten zu finden wird zuerst eine Mouth Map nach der Methode von [Hsu02] erstellt. Enthält diese Map mindestens ein Pixel, das einen Wert höher als 40 hat, wird weiter nach Mund-Kandidaten gesucht, ansonsten bleibt die Liste der Mund-Kandidaten leer.

Um vereinzelte Mund-Pixel zu grösseren Flächen zusammenzufügen wird eine Graustu-fen-Dilation durchgeführt. Das Strukturelement besteht aus lauter Nullen, ist quadratisch und hat die Seitenlänge 5. Nun wird eine Schwellwertfunktion verwendet, um die Mund-Pixel zu bestimmen. Der Schwellwert wird auf 80% des maximalen Grauwertes in der Mouth Map festgelegt. Durch Markierung der weissen Pixel werden die Mund-Kandida-ten bestimmt. Die Kandidaten werden grob gefiltert, wobei mindestens ein Drittel des Kandidaten-Rechtecks aus Mundfarbe bestehen muss und die Seitenlängen des Recht-ecks in beiden Dimensionen kleiner als ein Fünftel sein müssen. Die verbleibenden Kan-didaten werden im Gesichtskandidaten abgespeichert.

Tabelle 14 zeigt die Mouth Map auf verschiedenen Stufen der Mundkandidaten-Suche.


Mouth Map Nach Dilation Nach Schwellwertfunktion

Tabelle 14: Suchen von Mund-Kandidaten

6.10. Augen-ErkennungDie Erkennung der Augen wird wird gemäss [Hsu02] durchgeführt. Dabei werden, aus-gehend von einem YCbCr-Bild, zwei Maps generiert (Tabelle 15). Die EyeMapC wird aus den beiden Chrominanzkanälen erzeugt. Dabei wird die Beobachtung genutzt, dass rund um die Augen ein hoher Cb-Anteil und ein tiefer Cr-Wert zu finden ist. In einem zweiten Schritt wird die EyeMapL erstellt, welche auf dem Luminanzkanal des Bildes ba-siert. Sie soll die Augen aufgrund des starken Hell-Dunkel-Unterschiedes erkennen. An-schliessend werden die beiden EyeMaps zusammengeführt um in der resultierenden Map mögliche Augen zu erhalten. Da möglicherweise mehr als zwei Augenkandidaten gefunden werden, müssen diese später in Kombination mit den Mund-Kandidaten gefil-tert werden.

EyeMapC EyeMapL Kombinierte EyeMap

Tabelle 15: EyeMaps zur Suche von Augen-Kandidaten


EyeMapC

Die Formel für die Map der Chrominanz sieht folgendermassen aus:

Jede der drei Komponenten wird auf eine Skala von 0 bis 255 normalisiert. Ist Cb grös-ser als Cr wird die dritte Komponente (Cb/Cr) multipliziert mit 255 zu gross. Wenn dies eintritt, wird für diese Komponente der Maximalwert 255 verwendet.

EyeMapL

Die EyeMapL ist das entsprechende Graustufenbild, welches von der Luminanz des Ur-sprungsbildes ausgeht.

In dieser Formel werden sowohl Dilation als auch Erosion auf Graustufenbilder benötigt. Diese beiden Operationen brauchen relativ viel Zeit. Man kann jedoch nicht auf sie ver-zichten, da sonst sehr viel mehr inkorrekte Augenkandidaten gefunden würden.

Das mit der Dilaton verarbeitete Bild wird durch das erodierte geteilt, wodurch eine kom-plett neue Menge an möglichen Werten entsteht. Es ist deshalb notwendig, dass am Ende ein Histogrammausgleich auf die EyeMapL angewendet wird. Dieser sorgt dafür, dass die Helligkeitsunterschiede drastischer werden und damit bei der Kombination mit der EyeMapC eindeutiger ausfallen. Dadurch kann der Grenzwert für die Augenfilterung besser angepasst werden, damit möglichst wenig falsche Augenkandidaten gefunden werden.

Kombination & Schwellwertfunktion

Die Kombination der zwei EyeMaps wird durch eine Multiplikation gelöst. Anschliessend wird das Resultat auf den Bereich von 0 bis 255 normalisiert.

Das entstandene Bild hat noch sehr viele helle Bereiche ausserhalb des Gesichtes, wel-che im späteren Verlauf falsche Augenkandidaten ergeben würden. Um dies zu verhin-dern, maskieren wir das Bild, so dass alles ausserhalb des Gesichtes schwarz einge-färbt wird.

Nun wird auf der kombinierten Eye-Map ein Histogrammausgleich durchgeführt. Mit ei-ner Grenzwertfunktion werden danach alle Pixel weiss eingefärbt, welche einen Wert von mindestens 250 haben. Durch Markierung der weissen Pixel werden die Augenkan-didaten gefunden.


Dilation & Erosion

Die bei der Augensuche verwendete Dilation und Erosion wird mit einer 5x5 Maske nach folgendem Muster durchgeführt:

0 1 1 1 0

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

0 1 1 1 0

Dilation und Erosion sind relativ aufwändige Operationen. Deshalb werden sie möglichst effizient implementiert. Ein wichtiger Faktor ist dabei die Verwendung eines Block-Ar-rays für das Strukturelement, damit ein Zugriff über Zeiger möglich ist. Um einen Pointer auf das erste Element eines Arrays zu erhalten wird in F# der folgende Code verwendet:

let pStructElem = &&structElem.[0,0]

6.11. Optimale Mund-Augen-Kombination findenAlle potentiellen Augen und Mundkandidaten werden im Anschluss gefiltert und auf eini-ge Kriterien geprüft. Dadurch sollen falsche Augen und unmögliche Augen-Mund-Kom-binationen eliminiert werden. Dies wird mit allen Kombinationen durchgeführt und am Ende wird die bestmögliche Kombination zurückgegeben, falls eine übrig bleibt. Diese wird dann auch im Bild gezeichnet.

Proportion und Position prüfen

Als Erstes wird geprüft, ob der Abstand von Auge zu Auge mit dem Abstand von Augen zu Mund ein vernünftiges Verhältnis ergibt. In unseren Tests haben wir den Wert zwi-schen 0.4 und 1.0 als akzeptabel definiert. Dies ist eine sehr einfache Überprüfung, wel-che nur wenige mathematische Operationen benötigt und daher schnell durchgeführt ist.

Als nächstes wird die Position des Mundes validiert. Dabei wird nur überprüft ob der Mund zwischen den Augen liegt. Dadurch verlieren wir auch korrekte Gesichtskandida-ten, wenn die Gesichter gedreht sind. Da wir aber nur frontale Gesichter suchen ist dies nicht schlimm. Durch diese einfache Überprüfung können wir viele Mundkandidaten ausschliessen, welche sich ausserhalb des Gesichtes befinden.

Augen-Mund-Dreieck evaluieren

Um eine sinnvolle Bewertung zu den Dreiecken zu machen, werden die drei Winkel im Augen-Mund-Dreieck berechnet. Falls alle Winkel kleiner als 90 Grad sind, wird diese Augen-Mund-Kombination als gültig angesehen, anderenfalls wird sie verworfen. Die gültigen Dreiecke werden anhand von zwei Kennzahlen bewertet, wovon dann die Kom-bination mit den besten Werten ausgewählt wird.

Die erste dieser Zahlen ist der Quotient der beiden Dreiecksschenkellängen, die vom Mund ausgehen. Dabei wird die längere Seite durch die kürzere geteilt. Ein optimales Augen-Mund-Dreieck ist annähernd gleichschenklig, daher wird ein Dreieck besser be-wertet, wenn dieser Wert möglichst klein ist.


Die zweite Kennzahl ist der Winkel beim Mund, welcher sowieso kleiner als 90° sein muss. Unsere Augenerkennung markiert teilweise die Augenbrauen oder andere Berei-che als mögliche Kandidaten, welche sich oberhalb der eigentlichen Augen befinden. In den meisten Fällen ist das Augenpaar, mit dem geringsten Abstand zum Mund, das rich-tige. Daher wird eine Kombination besser bewertet, je grösser der Winkel beim Mund ist.

Jede gültige Kombination wird genau dann als besser empfunden, wenn beide Kenn-zahlen besser sind. Ist nur eine davon besser, wird diese Kombination nicht gewählt.

Für eine möglichst effiziente Implementierung werden die Listen der Augen- und Mund-kandidaten in Arrays umgewandelt. Danach können mit wenig Code alle benötigten Au-gen-Mund-Kombinationen generiert werden. Dieser Code ist rund 20 Prozent schneller als eine rekursive Variante, die mit Listen arbeitet.

let eyes = List.toArray(fc.EyeCandidates)let mouths = List.toArray(fc.MouthCandidates)for i = 1 to eyes.Length do for j = i+1 to eyes.Length do for m = 1 to mouths.Length do best <- (checkFaceTriangle eyes.[i-1] eyes.[j-1] mouths.[m-1] best)

6.12. Test der GesichtslokalisierungUm den Gesichtslokalisierungs-Algorithmus zu testen werden 60 Bilder von der Inter-netseite usgang.ch verwendet. Diese Bilder enthalten insgesamt 156 frontale Gesichter.

Wir testen den Algorithmus auf verschiedenen Stufen und zählen jeweils manuell die Anzahl korrekt identifizierter Gesichter und die Anzahl fälschlicherweise erkannter Ge-sichter (Tabelle 16). Ein Gesicht gilt nach unserer Definition als korrekt identifiziert, wenn es mit einem Rahmen umgeben ist und sich keine weiteren Gesichter in diesem Rahmen befinden.

Auf Stufe 1 werden Regionen als Gesichtskandidaten markiert, welche Hautfarbe ha-ben. Die hohe Anzahl an False Positives die hier auftritt rührt von der Hautfarbe anderer Körperteile und von weiteren Flächen im Bild, die Hautfarbe haben.

Auf der nächsten Stufe werden diese Kandidaten aufgrund der Seitenverhältnisse, der Grösse und des Anteils an Hautfarbe gefiltert. Dadurch können praktisch ohne Verlust an korrekten Gesichtskandidaten rund 20 Prozent der Fehlerkennungen eliminiert wer-den.

Auf der dritten Stufe sind nur noch Kandidaten vorhanden, bei denen ein Augen-Mun-d-Dreieck gefunden wird. Dadurch fallen etwa 90 Prozent der falschen Gesichtskandida-ten aus Stufe 2 weg. Von den korrekten Gesichtskandidaten verlieren wir in diesem Schritt rund 20 Prozent.

Schliesslich werden 60 Prozent der Gesichter korrekt gefunden und es verbleiben 21 fälschlicherweise erkannte Gesichter (13 Prozent).

Korrekt False Positives

Stufe 1 119 76% 315 202%

Stufe 2 118 76% 254 163%

Stufe 3 94 60% 21 13%

Tabelle 16: Erfolgsquote und False Positives bei 60 Testbildern


Durch die Parallelisierung an wichtigen Stellen erreicht das Programm eine hohe Ge-schwindigkeit. Tabelle 17 enthält die gemessenen Zeiten für das grosse Testbild22 und für die 60 kleineren Testbilder, welche schon zur Messung der Erkennungsrate benutzt wurden. Die je 30 Bilder in den beiden Testsets haben eine Grösse zwischen 400x600 und 533x800 Pixel.

Zeit für Gesichtslokalisierung

Grosses Testbild 0.23s

Testset 1 (30 Bilder) 2.28s (0.076s pro Bild)

Testset 2 (30 Bilder) 2.29s (0.076s pro Bild)

Tabelle 17: Geschwindigkeit Gesichtslokalisierung

Tabelle 18 zeigt vier Beispiele aus den 60 Testbildern.

Tabelle 18: Bilder mit gefundenen Gesichtern

22Testbild 1.jpg


7. Schlussfolgerungen

Die verschiedenen Testprogramme in Kapitel 5 und die damit durchgeführten Zeitmes-sungen zeigen, dass in F# genau so schnelle Programme entwickelt werden können wie in C#. Folgende Erkenntnisse erachten wir in diesem Zusammenhang als wertvoll:

• Elegante Code-Konstrukte (Syntactic Sugar) können Geschwindigkeitseinbussen mit sich bringen. Deshalb sind solche Konstrukte genau zu prüfen, falls die Ge-schwindigkeit wichtig ist. Da der Quelltext von F# frei zugänglich ist, ist dies pro-blemlos möglich.

• Wird eine Funktion sehr oft in kurzer Zeit aufgerufen, sollte diese als inline dekla-riert werden.

• F# läuft zwar sehr stabil, ist aber noch relativ jung. Deshalb ist es nicht ausge-schlossen, dass man irgendwann einen kleinen Fehler in den F# Kernbibliothe-ken findet. Das F# Team ist per E-Mail gut erreichbar und nimmt Anregungen zu Verbesserungen gerne entgegen.

• Für Bildverarbeitungs-Funktionen erreicht man auch in F# die beste Geschwin-digkeit durch Verwendung von Zeigern.

• Ob man für das Iterieren über eine Menge Schleifen oder Rekursion verwendet spielt für die Geschwindigkeit keine wesentliche Rolle. Somit kann jeweils dieje-nige Methode verwendet werden, welche für ein Problem natürlich scheint.

Abgesehen von der Geschwindigkeit finden wir folgende Erfahrungen erwähnenswert:

• F# Code ist im Vergleich zu C# kompakter, das heisst, man benötigt oft etwas weniger Code um das gleiche Ergebnis zu erzielen.

• Durch Typinferenz spart man einerseits Code und muss andererseits bei einem Refactoring weniger Anpassungen machen. Visual Studio zeigt die ermittelten Typen zu jedem Wert an, wenn man mit der Maus darüber fährt. Probleme, die durch unpassenden Typen entstehen, werden meist durch eine aufschlussreiche Compiler-Meldung angezeigt.

• Die Organisation von Code wird in F# durch Namespaces und Module ermög-licht.

Im Vergleich zu bestehenden funktionalen Sprachen hat F# bestimmte Vor- und Nach-teile.

• Ein grosser Vorteil von F# ist, dass die Sprache auf der .NET Plattform basiert und dadurch eine nahtlose Integration mit bestehendem .NET Code möglich ist. So kann funktionale Programmierung gezielt dort eingesetzt werden, wo diese einen Mehrwert bringt.

• Weil die Syntax von F# hauptsächlich von OCaml übernommen wurde, ist es für OCaml-Programmierer leicht, F# zu erlernen. Auch für die übrigen Programmie-rer ist die schlichte Syntax von F# schnell erlernbar. Etwas schwieriger könnte der Einstieg für Personen sein, die nicht mit funktionaler Programmierung ver-traut sind.

• Mit Visual Studio ist für F# eine ausgereifte Entwicklungsumgebung verfügbar, welche viele Werkzeuge mitbringt, die bei anderen funktionalen Sprachen ver-misst werden (wie in [FP03] und [Scott10] beschrieben).

• Im Moment gibt es erst wenige Programmierer, die mit F# vertraut sind.


• Da F# nicht rein funktional ist, kann man durch schlechten Programmierstil ge-wisse Vorteile der rein funktionalen Programmierung verlieren, wie z.B. die Mög-lichkeit, Code ohne grossen Aufwand zu parallelisieren. Verwendet man verän-derbare Werte jedoch mit Bedacht, bleiben die Vorteile erhalten.

Für welche Art von Programmen ist F# geeignet?

• F# ist vor allem für Code geeignet, der hauptsächlich funktional oder imperativ ist. Für komplexe Objekt-Hierarchien würden wir F# weniger empfehlen, müssen aber auch zugeben, in diesem Bereich erst wenig Erfahrung gesammelt zu ha-ben.

• F# eignet sich sehr gut für schnelles Prototyping von Algorithmen, da der Code sehr schlank ist und einfach umgebaut werden kann.

• GUI-Programmierung, z.B. mit WPF, ist möglich, jedoch gibt es zur Zeit noch keinen visuellen Editor, wie er für C# existiert. Deshalb ist es empfehlenswert, das GUI (noch) nicht in F# zu schreiben.

• F# eignet sich gut zur Implementation von mathematischen Algorithmen und Funktionen.

• Parallelprogrammierung ist in F# mindestens so gut möglich wie in C#. Durch Asynchrone Blöcke und Message Passing bietet F# zusätzliche Werkzeuge für bestimmte Aufgaben. Ob es mit F# einfacher ist, sequentiellen Code zu paralleli-sieren, hängt vor allem vom Applikations-Design ab. Wir haben aber das Gefühl, dass die funktionale Natur von F# zu einem Design führt, welches meist Vorteil-haft für Parallelprogrammierung ist.


8. Abbildungsverzeichnis

Abbildung 1: Liste in F#.................................................................................................11Abbildung 2: Prozess zur Gesichtslokalisierung.............................................................29Abbildung 3: Markierte Pixel nach Flood Filling..............................................................32

9. Tabellenverzeichnis

Tabelle 1: Geschwindigkeitsvergleich Mersenne-Primzahlen-Suche.............................18Tabelle 2: Geschwindigkeitsvergleich Matrix-Multiplikation............................................20Tabelle 3: Geschwindigkeitsvergleich Pythagoras-Tripel...............................................20Tabelle 4: Geschwindigkeitsvergleich Fibonacci............................................................22Tabelle 5: Geschwindigkeitsvergleich Bild-Invertierung.................................................23Tabelle 6: Geschwindigkeitsvergleich Filter...................................................................24Tabelle 7: Geschwindigkeitsvergleich Counter-Test......................................................25Tabelle 8: Geschwindigkeitsvergleich Kantendetektierung............................................26Tabelle 9: Geschwindigkeitsvergleich Gauss-Filter........................................................26Tabelle 10: Geschwindigkeitsvergleich Array erzeugen.................................................27Tabelle 11: Methoden zur Erkennung von Hautfarbe.....................................................30Tabelle 12: Erkennung von Hautfarbe bei einem Testbild..............................................30Tabelle 13: Tiefpassfilter................................................................................................32Tabelle 14: Suchen von Mund-Kandidaten....................................................................34Tabelle 15: EyeMaps zur Suche von Augen-Kandidaten...............................................34Tabelle 16: Erfolgsquote und False Positives bei 60 Testbildern...................................37Tabelle 17: Geschwindigkeit Gesichtslokalisierung........................................................38Tabelle 18: Bilder mit gefundenen Gesichtern...............................................................38


10. Referenzen

[Hsu02] Hsu, Rein-Lien; Abdel-Mottaleb, Mohamed; Jain, Anil K. (2002): „Face Detection in Color Images“. In: IEEE Transactions on Pattern Analysis and Machine Intelligence (2002), Vol. 24, No. 5.

[Kovac03] Kovač, Jure; Peer, Peter; Solina, Franc (2003): „Human Skin Colour Clustering for Face Detection“. In: EUROCON 2003. Computer as a Tool. The IEEE Region 8 (2003), Vol. 2, S. 144-148.

[FP03] Le Fessant, Fabrice; Patarin, Simon (2003): „MLdonkey, a Multi-Net-work Peer-to-Peer File-Sharing Program“. In: Research Report RR-4797, INRIA (2003).

[Pai06] Pai, Yu-Ting; Ruan, Shanq-Jang; Shie, Mon-Chau; Liu, Yi-Chi (2006): „A Simple and Accurate Color Face Detection Algorithm in Complex Background”. In: 2006 IEEE International Conference on Multimedia and Expo (2006), S. 1545-1548.

[Schnei00] Schneiderman, Henry; Kanade, Takeo (2000): „A Statistical Method for 3D Object Detection Applied to Faces and Cars“. In: IEEE Conference on Computer Vision and Pattern Recognition, 2000. Proceedings (2000), Vol. 1, S. 746-751.

[Scott10] Scott, David; Sharp Richard; Gazagnaire, Thomas; Madhavapeddy, Anil (2010): „Using Functional Programming within an Industrial Pro-duct Group: Perspectives and Perceptions“. In: The 15th ACM SIG-PLAN International Conference on Functional Programming (2010).

[Smi09] Smith, Chris (2009): Programming F#. Sebastopol: O'Reilly.

[Sym10] Syme, Don; Granicz, Adam; Cisternino, Antonio (2010): Expert F# 2.0. New York, Apress.

[Viola04] Viola, Paul; Jones, Michael J. (2004): „Robust Real-Time Face Detecti-on“. In: International Journal of Computer Vision (2004). Vol. 57, Nr. 2, S. 137–154.


Documents

Parallelprogrammierung in F# · Vergleich zwischen verschiedenen Programmiersprachen und Plattformen gut eignen. Typische Beispiele sind Quicksort oder Filteroperationen in der Bildverarbeitung