Auf das Wesentliche reduziert

Einige Dinge Vorab...

OK

Erfahrungen damit, gute Erfahrungen, ...

Nochwas

• Aufzählungspunkte sind so 2000er
• Stattdessen...

Gibt es nur noch einen Punkt pro Slide

Und die Vortragenden klicken sich viel zu schnell durch

So schnell, dass

es kaum noch

möglich ist

dem

Bild

und

Audiovortrag

gleichzeitig zu

folgen

Außerdem geraten bei InfoQ die Dinge so auseinander, dass wir raten müssen, was der Vortragende wohl gerade meint und die Zuschauer gerade sehen.

Vielen Dank auch.

Ankündigung

Das deutsche Clojure-Buch wird in Kürze unter http://www.clojure-buch.de vollständig zu lesen sein.

Sollte es seitens der Gemeinschaft der deutschsprachigen Clojure-Freunde ein Interesse geben, auf dem Material aufzubauen, werden wir das Material gerne unter eine passende offene Lizenz stellen.

"In Kürze" ist dehnbar

Nachdem, das geklärt ist....

Laziness & Seqs

Die Seq Abstraktion

• Es gibt ein erstes Element (first)
• Und es gibt einen Rest (next, rest)
• rest liefert immer eine Seq, potentiell leer, während next am Ende nil liefert und dafür ein Element weiter vorausschauen muss
• Umfangreiche Sammlung von Funktionen für Seqs: map, filter, reduce, mapcat, partition, every?, some, take, drop, remove, ...

Bedarfsauswertung

• Verarbeitung erfolgt aber nur bei Bedarf, d.h. wenn die aufrufende Funktion die Daten abruft
• Zu große Seqs können verarbeitet werden
• Clojure merkt sich nur das Rezept zum Erzeugen des nächsten Elements

(interleave [:a :b :c] (iterate inc 0))
;;=> (:a 0 :b 1 :c 2)
(map + [1 2 3] [10 20 30 40 50 60])
;;=> (11 22 33)
	    

Lazy Seqs erhalten ihre Werte

(def natz (iterate inc 1))

(time (nth natz 1000000))
;; "Elapsed time: 239.345539 msecs"
;;=> 1000001
(time (nth natz 1000000))
;; "Elapsed time: 15.664133 msecs"
;;=> 1000001
	    

Chunks

(defn pinc [i]
  (print (str "<" i ">"))
  (inc i))

(take 2 (map pinc (iterate inc 0)))
;; (<0><1>1 2) 
;; Ausgabe und Rückgabewert vermischt
(take 2 (map pinc [1 2 3 4 5 6 7 8 9]))
;; (<1><2><3><4><5><6><7><8><9>2 3)
;; Vektoren implementieren IChunkedSeq
	    

map

Was macht Clojure hier?

(map inc (range 10))
;;=> (1 2 3 4 5 6 7 8 9 10)
	    

• Erzeuge die Zahlen 0 bis 9
• Addiere jeweils 1
• Gib die Sequenz zurück

Werden dabei Dinge verflochten?

"Verflochten"?

Simple Made Easy

• Simple vs. Easy (simpel, einfach vs. mühelos, trivial)
• "Complect" (verflechten, verwirren)

Werden dabei Dinge verflochten?

(map inc (range 10))
;;=> (1 2 3 4 5 6 7 8 9 10)
	    

• Erzeugung: lazy
• Eingabe und Ausgabe: sequentielle Datenstrukturen
• Verarbeitung: sequentiell

na und??

Zu Risiken und Nebenwirkungen ...

Nebenwirkung: Allozierung

• Lazy Sequences haben einen Overhead
• Lazy Seqs speichern die realisierten Werte

Schlimmere Nebenwirkung: Sequentiell

• Die Verarbeitung erfolgt sequentiell (klassische Implementation mit Rekursion)
• D.h. von Natur aus nicht parallisierbar
• Och manno!

Was macht map eigentlich wirklich?

Was ist die Essenz?

Wende eine Funktion auf jedes Element an

Ist das inhärent nicht parallelisierbar?

Nö
Haben will

filter

Auch filter ist lazy

(defn podd? [i]
  (print (str "(" i ")"))
  (odd? i))

(take 2 (filter podd? (iterate inc 0)))
;; ((0)(1)(2)(3)1 3)
(take 2 (filter podd? (range 9)))
;; ((0)(1)(2)(3)(4)(5)(6)(7)(8)1 3)
	    

... alles wie gehabt: lazy, sequentiell

Parallisierbar? Nein. Inhärent? Auch nicht.

Haben will? Aber sicher!

Fokus für heute

• Datenstrukturen, die in den Speicher passen
• performant verarbeiten
• idealerweise parallel

reduce

Iteration mit Akkumulator

;; (reduce red-fn init? coll)

(reduce + [1 2 3 4])
;;=> 10
(reduce (fn [acc x] 
          (assoc acc x (inc (get acc x 0)))) 
        {} "Hallo Welt") 
;;=> {\t 1, \e 1, \W 1, \space 1, \o 1, \l 3, \a 1, \H 1}
(reductions + [1 2 3 4])
;;=> (1 3 6 10)
	    

reduce ist anders

• Erzeugung: nicht lazy ("eager")
• Eingabe: Seq; Ausgabe: beliebig
• Verarbeitung: immer noch sequentiell

reduce ist noch mehr

• map, filter, etc kennen die Datenstrukturen nicht
• Ebensowenig Funktionen wie inc
• Nur die Datenstrukturen selbst wissen, wie sie navigiert werden
• Seit Clojure 1.3 ist reduce ein Zugangspunkt in die Datenstrukturen
• Abstraktion: reduzierbar (reducible)

reduce als Backend?

Lassen sich map, filter & Co. alternativ auf Basis von reduce implementieren?

Fokus: im Speicher, Performanz

Anwendungsfall: danach wird reduce verwendet.

(reduce + (map inc (filter odd? (range 10))))
	    

Ja, das funktioniert

Appetithappen

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

(def zahlen (doall (range 1e7)))

(defn standard [daten]
  (reduce + (map inc
                 (filter odd? daten))))
(time (standard zahlen))
;; "Elapsed time: 1107.320599 msecs"
;;=> 25000005000000

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

Implementation

Das hier ist doch der SourceTalk?

1. Verlagerung in die Reducing-Funktion

• Die Reducing-Funktion ist das erste Argument von reduce
• Die Mapping-Funktion ist das Argument von map
• Untenstehendes mapping verschiebt die Auswertung in die Reducing-Funktion
• Aber noch unnatürlich in der Anwendung: steht an der falschen Stelle
• filtering entsprechend

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

(defn filtering [pred]
  (fn [red-fn]
    (fn [acc element]
      (if (pred element)
        (red-fn acc element)
        acc))))
;; (reduce ((mapping inc +) 0 [1 2 3]))
;;=> 9
	    

2. Schritt: Noch reducer als bisher

• Protocols sind vergleichbar zu Java Interfaces
• reduce verwendet das Protocol CollReduce
• CollReduce kann für Datenstrukturen erweitert werden
• r/map liefert ein Objekt, das CollReduce implementiert
• Dieses Objekt delegiert intern an die Datenstruktur

(seq (.getInterfaces
      (class (r/map inc [1 2]))))
;;=> (clojure.core.reducers.CollFold clojure.core.protocols.CollReduce 
;;    clojure.lang.IObj)
(defn reducer
  ([coll xf]
     (reify clojure.core.protocols/CollReduce
       (coll-reduce [_ f1 init]
         (clojure.core.protocols/coll-reduce coll (xf f1) init)))))
	    

3. Schritt: Makros

Boilerplate-Code wird von passenden Makros hinweggefegt

Zusammenfassung

• Datenstrukturen können sich selbst reduzieren
• Dazu verwendet reduce seit Clojure 1.3 ein Protocol
• Passende Makros und Funktionen höherer Ordnung verlagern Evaluation von etwa map auf die Reducing-Funktion
• Das Protocol delegiert an die Datenstrukturen
• Elegantes Zusammenspiel
• Öh, und die echte Implementation sieht leider anders aus. :-/

Parallelverarbeitung

Jetzt endlich

fold

• Neue Funktion: fold
• Kann parallel arbeiten; hängt von Datenstruktur ab
• Verwendet das Fork/Join-Framework (Bild folgt)
• Chunk-Size in der Hand des Anwenders

Erneut das kanonische Beispiel

(defn parallel [data]
  (r/fold + (r/map inc
                   (r/filter odd? data))))
;; Zur Erinnerung
(time (not-lazy zahlen))
;; "Elapsed time: 699.521045 msecs"
(time (parallel zahlen))
;; "Elapsed time: 689.899531 msecs"

;; meh?
	    

Wieso funktioniert das hier nicht?

Das kanonische Beispiel mit Vektor

(def zahlen-v (vec zahlen))

(time (standard zahlen))   ;; "Elapsed time: 1021.680964 msecs"
(time (not-lazy zahlen))   ;; "Elapsed time: 705.568693 msecs"
(time (parallel zahlen))   ;; "Elapsed time: 693.122998 msecs"

(time (standard zahlen-v)) ;; "Elapsed time: 1054.37094 msecs"
(time (not-lazy zahlen-v)) ;; "Elapsed time: 723.872857 msecs"
(time (parallel zahlen-v)) ;; "Elapsed time: 205.894815 msecs"
	    

Reine Reducing-Funktion

• Beispiele mit + sind trivial, denn + hat zwei wichtige Eigenschaften
• ein neutrales Element
• Assoziativität

(+)
;;=> 0
(= (+ 4 (+ 5 6)) (+ (+ 4 5) 6))
;;=> true
	    

• Kann sowohl den initialen Wert für eine Teil-Reduktion liefern
• als auch die Teilergebnisse zu einem neuen Wert kombinieren
• reduce unterstützt solche Reducing-Funktionen durch die passende Arity

Combine-Funktion

• Komplexere Beispiele benötigen eine Combine-Funktion mit folgenden Eigenschaften:
• Ohne Argument aufgerufen liefert sie ein neutrales Element für die Initialisierung einer Teil-Reduktion.
• Mit zwei Argument aufgerufen kombiniert sie zwei Teilergebnisse.

Fork/Join

+--------------------------------------------------------------+
|                                                              |
+--------------------------------------------------------------+
+-----------------------------+ +------------------------------+
|                             | |                              |
+-----------------------------+ +------------------------------+
+--------------+ +------------+ +-------------+ +--------------+
|              | |            | |             | |              |
+--------------+ +------------+ +-------------+ +--------------+

 +----+  +----------+       /-------\       +----+  +----------+
 |Init|  |   data   |   -> | combine | <-   |Init|  |   data   |
 +----+  +----------+       \-------/       +----+  +----------+
	    

Combine konkret

Beispiel: zählen von Elementen (frequencies)

(defn freqs-fold [items]
  (r/fold
   (r/monoid (partial merge-with +)
             (constantly {}))
   (fn [acc el]
     (assoc acc el (inc (get acc el 0))))
   items))
	    

WT.?

Combine konkret Detail

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

;; mono-was?
(def mo (r/monoid + (constantly 0)))

(mo)
;;=> 0
(mo 1 2)
;;=> 3
	    

Mehr Beispiel

Ein Haufen XML

• Ein Stück Software produziert in einem Ausgabeverzeichnis viele XML-Dateien
• Zwischenzeitlich ändert sich etwas am Versuchsaufbau
• XML enthält Laufzeitinformationen wie Timestamps
• Alles andere soll auf Unterschiede untersucht werden
• Zunächst müssen die Paare gefunden werden
• Dazu lässt sich ein Fingerprint anhand ausgewählter XML-Tags berechnen
• XML langsam, parallel gut

Fazit

• Motivation: Performance
• Anwendungsfälle: Kombination mit reduce; häufig?
• Gefühle Implementation: sehr elegant
• Tatsächliche Implementation: deutlich komplizierter
• Kritik: Implementationsdetails (into)

Acrolinx

Danke

Copyright (c) 2013 Stefan Kamphausen

reveal.js, libraries etc. see LICENSE file