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.

Hintergründe

Was dahinter steckt

Wie so oft steht vor einer Verbesserung ein Schritt zurück und die Überlegung, was an einer Operation das Wesentliche ist. Bei der Betrachtung der klassischen map-Implementierung kommen verschiedene Aspekte zum Vorschein:

• Rekursion ist in der Regel das Mittel der Wahl für die Implementierung von map.
• Das Bearbeiten einer Liste von Werten erfolgt sequenziell.
• Das Ergebnis ist "lazy".

Die zentrale Aufgabe von map ist jedoch, eine Funktion auf jedes einzelne Element anzuwenden. Ähnliche Betrachtungen lassen sich für andere Funktionen wie filter oder mapcat anstellen.

Mit der Funktion reduce existiert ein Mechanismus, der für die Anwender unbemerkt seit Clojure 1.3 durch ein mit Java-Interfaces arbeitendes "Protocol" (Protokoll) implementiert ist. Das erlaubt den Datenstrukturen, eigene performante Implementierungen für reduce anzubieten. Ein Beispiel für eine derartige Struktur sind Clojures persistente Vektoren.

Wenn nun in einem Programm ein map mit abschließendem reduce existiert, kann map die Details seiner Implementierung auf den Reduce-Schritt abwälzen. Somit widmet sich die Funktion map im Zusammenspiel mit reduce wieder ihrer eigentlichen Aufgabe, dem Anwenden einer Funktion auf jedes Element einer Sequence. In einem Konstrukt wie

(reduce + 0 (map inc [1 2 3]))
;=> 9

lässt sich das gleiche Ergebnis erzielen, wenn der Inkrement-Schritt in die Reducing-Funktion verlagert wird. Eine neue Funktion mapping ermöglicht das:

(defn mapping [map-fn]
  (fn [red-fn]
    (fn [acc element]
      (red-fn acc (map-fn element)))))

Sie nimmt die anzuwendende Funktion (map-fn) als Argument und liefert eine neue Reducing- Funktion. Diese erwartet als Argument die ursprüngliche Reducing-Funktion (red-fn) und bewirkt die kombinierte Anwendung von red-fn und map-fn beim Ausführen von reduce.

(reduce ((mapping inc) +) 0 [1 2 3])
;=> 9

In diesem Beispiel erhält mapping die Funktion inc als map-fn und im inneren Teil ist red-fn die Funktion +. Es handelt sich hier um eine im Vergleich zur tatsächlichen Implementierung leicht vereinfachte Darstellung der Arbeitsweise von mapping, die den Aufruf von reduce mit einem initialen Wert 0 verlangt.

Die Reducers-Bibliothek hat jedoch das Ziel, dass der Anwender seinen Code nicht umstrukturieren muss, was in obigem Beispiel der Fall war. Eine solche Anpassung können selbst die sonst so wirksamen Lisp-Makros nicht alleine auf Code-Ebene realisieren. Zur Laufzeit liefert r/map daher ein spezielles Objekt, das das passende Protokoll implementiert. Das verlagert die Auswertung in die Reducing-Funktion.

Der folgende Aufruf zeigt, welche Interfaces das von r/map erzeugte Objekt implementiert.

(seq (.getInterfaces  
      (class (r/map inc [1 2]))))
;=> (clojure.core.reducers.CollFold
;=>  clojure.core.protocols.CollReduce
;=>  clojure.lang.IObj)

Fold, zweiter Teil

Diese Liste suggeriert, dass es nicht nur ein Protokoll für reduce gibt, sondern auch eines für fold ("CollFold"). Nachdem der erste Einsatz des potenziell parallelen fold so enttäuschend verlief, wird durch die bisherige Betrachtung deutlich, dass die Parallelisierung nur für passende Datenstrukturen erfolgt. In Clojure 1.5 implementieren die persistenten Vektoren das Protokoll mit Parallelisierung.

(def zahlen-v (vec (range 1e6)))
(time (standard zahlen-v))
; "Elapsed time: 154.737774 msecs"
;=> 250000500000
(time (not-lazy zahlen-v))
; "Elapsed time: 135.502804 msecs"
;=> 250000500000
(time (parallel zahlen-v))
; "Elapsed time: 68.257371 msecs"
;=> 250000500000

Wie erwartet bewirkt fold bei einem Vektor aus Zahlen eine signifikante Beschleunigung. Sie wird hinter den Kulissen durch das Fork-Join-Framework hervorgerufen, Leonardo Borges beschreibt dessen Wirkungsweise im Zusammenhang mit den Reducers anschaulich in einem Vortrag.

Voraussetzung für die Anwendbarkeit von Fork-Join ist, dass das Bearbeiten der Elemente sowohl auf beliebigen Teilmengen als auch in beliebiger Reihenfolge erfolgen kann. Das Zusammenführen der Zwischenergebnisse erfordert in der Regel eine separate Combine-Funktion. Diese ist optional und kann mit der Reducing-Funktion identisch sein. Neben dem Zusammenführen der Teilergebnisse ist die Combine-Funktion für die Initialisierung der einzelnen Teilschritte verantwortlich.

Somit muss fold einige Anforderungen an die Combine-Funktion stellen:

• Ein Aufruf der Funktion ohne Argumente liefert ein sogenanntes "neutrales Element" für die Initialisierung.
• Die Funktion ist assoziativ, die Reihenfolge der Anwendung spielt keine Rolle.
• Die Funktion muss auch zwei Argumente akzeptieren und in dem Fall die Zusammenführung der Teilergebnisse definieren.

Wie viele Klammern hat Clojure?

Die Frage, wie viele Klammern in Clojures Implementierung enthalten sind, veranschaulicht die Anwendung der Combine-Funktion. Zunächst lädt der folgende Code den Inhalt von core.clj zeichenweise in einen Vektor:

(def core (-> "clojure/core.clj"
              clojure.java.io/resource
              slurp
              vec))

Im zweiten Schritt zählt reduce in einer Hash-Map das Vorkommen einzelner Zeichen, wobei diese mit dem Keyword :all einen Zähler für die gesamte Anzahl von Zeichen erhält.

(defn zaehl [string]
  (reduce
   (fn [acc zeichen]
     (update-in
      (assoc acc zeichen
             (inc (get acc zeichen 0)))
      [:all] inc))
   {:all 0}
   string))

Die Reducing-Funktion erfüllt nun nicht mehr die Anforderungen, die fold verlangt. Daher ist es notwendig, eine Combine-Funktion zu bestimmen. Deren Definition erfolgt mit der Hilfsfunktion monoid aus der Reducers-Bibliothek. Diese nimmt zwei Funktionen entgegen, eine für den Kombinationsschritt und eine für die Initialisierung. Der Rückgabewert ist eine neue Funktion, die entweder kein oder zwei Argumente entgegennimmt. Die Initialisierung ohne Argumente liefert eine Hash-Map, in der :all mit 0 vorbelegt wird. Die Kombination zweier Unterergebnisse verwendet merge-with mit +.

(merge-with + {:a 2} {:a 4})
;=> {:a 6}
 

Der Einsatz von partial liefert eine neue Funktion auf Basis von merge-with, bei der das erste Argument mit + vorbelegt ist.

((partial merge-with +) {:a 2} {:a 4})
;=> {:a 6}
 

Die Reducing-Funktion kommt unverändert zum Einsatz.

(defn zaehl-fold [string]
  (r/fold
   (r/monoid (partial merge-with +)
             (constantly {:all 0}))
   (fn [acc el]
     (update-in
      (assoc acc el (inc (get acc el 0)))
      [:all] inc))
   string))

Eine kleine Auswertungsfunktion fasst die Daten schließlich zusammen und stellt dabei sicher, dass sich die beiden Ergebnisse nicht unterscheiden.

(defn zeichen-zaehlen [string]
  (let  [auswert (time (zaehl string))
         auswert-f (time (zaehl-fold string))
         nur-chars (dissoc auswert :all)]
    (println "Gleich: "  
             (= auswert auswert-f))
    (println "Zeichen gesamt: "  
             (:all auswert))
    (print "Top: ")
    (prn (last (sort-by val nur-chars)))
    (print "Klammern: ")
    (prn (select-keys nur-chars [\( \)]))
    (println "Verschiedene:"  
             (count auswert))))

(zeichen-zaehlen core)
; "Elapsed time: 278.217432 msecs"
; "Elapsed time: 108.543598 msecs"
; Gleich: true
; Zeichen gesamt: 231405
; Top: [\space 57224]
; Klammern: {\) 5991, \( 5991}
; Verschiedene: 95
;=> nil
 

Auch bei dieser sehr schnellen Operation ist durch die Parallelisierung mit fold ein erheblicher Geschwindigkeitsvorteil erkennbar.

Kritik und Fazit

Fehlerquellen und Kritik

Wenn sich beim Entwickeln Verwunderung einstellt, dass der Einsatz von fold keinen Geschwindigkeitszuwachs zur Folge hat, liegen die Daten oft nicht in Vektoren vor. Bislang existieren Reducers-Varianten von map, mapcat, filter, remove, flatten, take-while, take und drop. Diese Funktionen lassen sich miteinander kombinieren, arbeiten aber nicht mit den Core-Funktionen wie partition zusammen, die "lazy" vorgehen. Zu solchen Zusammenstellungen kommt es gelegentlich, wenn bestehender Code auf die Reducers-Varianten portiert werden soll, um den Prozess zu beschleunigen. Die fehlende Kombinierbarkeit mit den Lazy-Core-Funktionen könnte sich als eine Hürde erweisen.

Im Rahmen seiner Vorträge zum Thema Reducers hat Spracherfinder Rich Hickey als eine Motivation angeführt, dass einmal geschriebene Programme bei neuen Rechnergenerationen wieder schneller werden, wie aus der Zeit der immer höheren Taktraten bekannt. Der Einsatz von fold erfolgt allerdings punktuell, und inwieweit der Einsatz eine generelle Beschleunigung durch mehr Kerne erlaubt, ist fraglich. Zudem zerlegt die aktuelle Implementierung das Problem unabhängig von der Anzahl der verfügbaren Kerne.

Ein weiterer Kritikpunkt ist, dass Anwender der Reducers-Bibliothek teilweise Implementierungsdetails anderer Funktionen kennen müssen. Beispielsweise lassen sich etwa die neuen Funktionen mit into verwenden, da into mit reduce implementiert ist, was Anwendern nicht unbedingt bewusst ist.

Fazit

Die neue Reducers-Bibliothek in Clojure 1.5 bietet das Potenzial, bestehende und reduce verwendende Operationen zu beschleunigen. Der erste Schritt ist das Vermeiden von Overhead für die gewöhnlich eingesetzte Bedarfsauswertung, der zweite eine Parallelisierung der Verarbeitung für Daten, die in Form von Vektoren vorliegen. Clojure-Programmierern steht somit ein weiteres Werkzeug für die Entwicklung auf Mehrkernarchitekturen zur Verfügung. Inwieweit sich die Reducers-Bibliothek verbreitet, bleibt abzuwarten.

Stefan Kamphausen
ist Director DevOps & NLP bei der Firma Acrolinx in Berlin. Er ist Autor des deutschen Clojure Buchs und ein langjähriger Liebhaber der Familie der Lisp-artigen Programmiersprachen.

Onlinequellen

• Rich Hickey; Anatomy of a reducer
• Carin Meier; Baba Yaga and the Clojure Reducers
• David Liebke; From Concurrency to Parallelism

(jul)