Reducers in Clojure 1.5

Inhaltsverzeichnis

Bedarfsauswertung (Lazy Evaluation) spielt in Clojure eine zentrale Rolle. Viele häufig verwendete Funktionen wie map und filter erzeugen sogenannte Lazy Sequences. Diese sequenziellen Datenstrukturen zeichnet aus, dass Clojure ihre Elemente erst berechnet, wenn eine Funktion auf sie zugreift. Neben der somit möglichen Verarbeitung unendlich langer Lazy Sequences – sofern der Aufrufer nicht alle Elemente konsumiert – lässt sich diese Art von Sequenzen gut zu neuen Funktionen zusammenstellen. Dennoch haben sie auch ihre Kosten, sodass die Anwender sich in einigen Abschnitten ihres Programms eine Alternative wünschen.

Die neuen Reducers, die seit dem Anfang des Jahres erschienenen Clojure 1.5 verfügbar sind, stellen eine solche Alternative dar. Durch die Fokussierung auf das Schweizer Taschenmesser der funktionalen Programmierung – reduce sowie eine geschickte Mischung aus Clojures Metaprogrammierung mit Makros, Javas Interfaces und einer Rückbesinnung auf die wesentliche Abstraktion erlauben die Reducers Performancegewinne durch strikte Evaluation sowie Parallelisierung.

Alle Beispiele im Artikel lassen sich direkt in einer REPL-Sitzung nachvollziehen. Dazu ist eine Entwicklungsumgebung, etwa Emacs und nrepl.el oder das Counterclockwise-Plugin in Eclipse, notwendig. Die Formatierung der REPL-Beispiele orientiert sich an der mittlerweile gängigen Form, den Prompt für die Eingaben (etwa "user>") nicht anzuzeigen, Ausgaben während der Ausführung als Kommentare (erkennbar am Semikolon) und den Rückgabewert einem ";=> " folgend darzustellen. Diese Form wurde zuerst im Buch "The Joy of Clojure" etabliert.

Die Komplexität des Trägen

Das harmlose Konstrukt

;; nicht an der REPL eingeben
(iterate inc 1) 

berechnet durch wiederholte Anwendung der Inkrement-Funktion inc mit einem Startwert von 1 theoretisch alle natürlichen Zahlen. Offensichtlich ist diese Sequenz unendlich lang und bereitet dem Computer damit nicht lösbare Probleme. Die durch die Funktion iterate erzeugte Lazy Sequence lässt sich hingegen speichern und abfragen:

(def natuerliche (iterate inc 1))
(type natuerliche)
;=> clojure.lang.Cons
(type (rest natuerliche))
;=> clojure.lang.LazySeq 
(take 10 natuerliche)
;=> (1 2 3 4 5 6 7 8 9 10)

Für den Anwender weitgehend unsichtbar erzeugt Clojure Objekte ("Cons", "LazySeq"), die immer das Rezept zur Berechnung des nächsten Werts enthalten. Zusätzlich speichert die Lazy Sequence alle berechneten Zahlen und erhöht somit den Speicherbedarf.

Das Cachen der Werte benötigt sowohl Speicher als auch CPU-Zeit, wobei letztere zusätzlich noch einmal durch die Komplexität der Laziness in die Höhe getrieben wird. Wenn die Daten ohnehin im Speicher vorliegen, ist dieser Overhead nicht immer von Nöten.

Als einfaches Beispiel dafür, wie sich Reducer einsetzen lassen und welche Wirkung sie haben, dient folgende Aufgabe: Addiere jeweils die nächsthöhere natürliche Zahl aller ungeraden Zahlen von eins bis einer Million auf. Der folgende Code erzeugt zunächst die benötigten Zahlen und sorgt durch das Verwenden von doall dafür, dass im weiteren Verlauf keine Laziness-Effekte das Ergebnis verfälschen.

(def zahlen (doall (range 1e6)))

Die funktionalen Klassiker filter, map und reduce berechnen das geforderte Ergebnis:

(defn standard [daten]
  (reduce +
          (map inc
               (filter odd? daten))))

An der REPL kann das Makro time die Berechnung durchführen und die dafür notwendige Zeit messen:

(time (standard zahlen))
; "Elapsed time: 168.195122 msecs"
;=> 250000500000

Um im weiteren Verlauf die Funktionen aus der Reducers-Bibliothek verwenden zu können, lädt require die Bibliothek mit dem Kürzel "r" in den aktuellen Namespace:

(require '[clojure.core.reducers :as r])

Ein erster Performancegewinn lässt sich mit geringen Änderungen am Code dadurch erreichen, dass sich bei der Berechnung die ohne Laziness arbeitenden äquivalenten Funktionen aus der Bibliothek einsetzen lassen:

(defn not-lazy [data]
  (reduce +
          (r/map inc
                 (r/filter odd? data))))
(time (not-lazy zahlen))
; "Elapsed time: 121.721544 msecs"
;=> 250000500000

Somit bewirkt alleine das Vermeiden der Laziness eine Steigerung der Geschwindigkeit um etwa 30 Prozent.

Der eigentliche Clou der Reducers-Bibliothek ist die Möglichkeit der automatischen Parallelisierung. Dazu existiert eine dedizierte Funktion, fold. Ein naiver Austausch von reduce durch fold zeigt, dass es keinen nennenswerten Unterschied gibt:

(defn parallel [data]
  (r/fold +
          (r/map inc
                 (r/filter odd? data))))
(time (parallel zahlen))
; "Elapsed time: 128.426658 msecs"
;=> 250000500000

Das ist zunächst etwas enttäuschend, aber verständlich, wie die folgende Betrachtung der Hintergründe der Reducers zeigt.