Seite 2: Hintergründe

Inhaltsverzeichnis

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.