Den Optimierer optimieren

Im letzten Post haben wir den Downhill Simplex Algorithmus in F# implementiert. In dieser Woche werden wir die Performance unserer Implementierung vergleichen mit einer gleichwertigen Implementierung in C. Die C Implementierung wird uns als Grundlinie dienen bei den Vergleichen.

Zum Profilen verwenden wir den Visual Studio Performance Profiler.

Die verwendete C Implementierung verwendet einige Abkürzungen und trifft einige Vereinfachungen, so dass der Vergleich sicherlich nicht fair ist. Nichts destotrotz zeigt es die absolut kürzeste Laufzeit, so dass wir zumindest einschätzen können wie gut sich unsere F# Implementierung schlägt.

Initialer Vergleich

Für unseren initialen Vergleich führen wir einen Micro-Benchmark durch. Konkret heißt das, wir lassen den Optimierer über 50 Iterationen laufen und wiederholen das 100-mal. Am Ende betrachten wir die Laufzeiten.

ImplementierungDurschnitt [ms]Min [ms]Max [ms]
C3,93,55,2
F#100,090,0149,0

 

Beide Programme wurden mit den Einstellungen für x64 / Release kompiliert und auf einem Intel Core i7-6600U ausgeführt.
Auch wenn der Benchmark nicht vollständig vertrauenswürdig ist und der zugrundeliegende Vergleich die C Implementierung bevorteilt, können wir dennoch hoffen im Durchschnitt um eine Größenordnung schneller zu werden.

Hotspots

Nach den Profilen sind zwei Funktionen hervorgestochen:

Diese beiden Funktionen sind jeweils 92 Millionen mal ausgeführt wurden. Zusammen machen sie 36% der Laufzeit aus. Die schlechteste Funktion, die zum Algorithmus selbst gehört, ist die iterations Funktion mit 0,07%.
Die Zahlen deuten darauf hin, dass wir nicht den Optimierer selbst optimieren müssen, sondern die vom Optimierer optimierte Funktion.

Im Grunde gibt es nun zwei Dinge die wir genauer betrachten müssen. Die Funktion selbst und deren Diskretisierung durch simple.

Die Optimierung der ausgewerteten Funktion

pow entfernen

In diesem Schritt haben wir den Operator ** (pow) durch Multiplikation ersetzt, da der Exponent immer ganzzahlig war, d.h. aus x ** 2.0 wurde x * x.

ImplementierungDurschnitt [ms]Min [ms]Max [ms]
F#50,047,085,0

Bei der Berechnung der Kosten durch die kleinsten Fehlerquadrate wurde pow ebenfalls benutzt. Nachdem wir es dort ebenfalls ersetzt haben, gab es nochmal einen großen Geschwindigkeitsschub.

ImplementierungDurschnitt [ms]Min [ms]Max [ms]
F#14,011,259,4

Die Optimierung der Diskretisierung

Parallelisierung

In diesem Schritt haben wir einfach Array.map durch Array.Parallel.map ersetzt, damit die Diskretisierung parallel durchgeführt wird.

ImplementierungDurschnitt [ms]Min [ms]Max [ms]
F#25,022,382,6

Diese Änderung hat unser Ergebnis verschlechtert. Die Ursache dafür habe ich nicht weiter untersucht. Vielleicht ist es der zusätzliche Overhead, der entsteht, wenn die Arbeit zu sehr verteilt wird. Diese Änderung habe ich daher wieder rückgängig gemacht.

SIMD

Durch die Nutzung des System.Numerics.Vector Pakets über die F# SIMD Array Adapter bekommen wir folgende Ergebnisse.

ImplementierungDurschnitt [ms]Min [ms]Max [ms]
F#13,09,956,3

Eigentlich hätten wir eine größere Verbesserung um den Faktor 4 erwartet, anstatt dieser nur minimalen Veränderung, da wir 4 Werte simultan berechnen können. Auch hier habe ich die Ursache vorerst nicht weiter untersucht und die Änderungen rückgängig gemacht.

Zusammenfassung

Ich war ehrlich gesagt überrascht, dass unsere typsichere, nicht optimierte Implementierung des Downhill Simplex Algorithmus so gut wie gar keinen Einfluss hat auf die Ergebnisse unseres Benchmarks. Stattdessen war es die zu optimierende Funktion, die über 90 Millionen Mal ausgeführt wird, bei 50 Iterationen über 100 Durchläufe.

Profilen hat sich also mal wieder als der korrekte Weg bestätigt, anstatt sich vom Bauchgefühl leiten zu lassen. Und dass nicht nur um die Probleme zu finden, sondern auch um zu prüfen, ob eine Optimierung auch wirklich eine Verbesserung ist, wie in unserem Fall beim Parallelisieren. So haben wir unsere Problemstelle – den pow Operator – zielsicher gefunden. Am Ende kamen wir sogar relativ nah an die Laufzeiten der C Implementierung.

Ihr findet den optimierten Quellcode im optimizing Branch und die C Implementierung hier.

Danke fürs Lesen.