Performance della biblioteca dei riduttori di clojure

Question

Perché la mappatura / riduzione della libreria dei riduttori ha prestazioni peggiori della normale mappa / ridotta?

user=> (time (reduce + (map inc (range 100000000))))
"Elapsed time: 14412.627966 msecs"
5000000050000000

user=> (time (reduce + (r/map inc (range 100000000))))
... (C-c)

user=> (time (r/reduce + (r/map inc (range 100000000))))
....(C-c)

.

Avevo due uccisioni più tardi mentre ci vogliono a tempo indeterminato.Cosa c'è di sbagliato qui?

Modifica: Sembra che anche altre lingue abbiano problemi simili.Scala sembra essere infrantata a un milione. Perché le collezioni Scala Parallel a volte causano uno outochoryError? .Mentre i riduttori di cloudo sono più veloci del normale a un milione.

Answer 1

Per completare la risposta @ a-webb, questo è un bug del compilatore e uno coinvolto per risolvere davvero.( Vedi questo post per maggiori dettagli.>

Un altro modo per aggirare il problema è usare un fusibile :

(defn once-seq
  "Returns a sequence on which seq can be called only once."
  [coll]
  (let [a (atom coll)]
    (reify clojure.lang.Seqable
      (seq [_]
        (let [coll @a]
          (reset! a nil)
          (seq coll))))))

.

E poi:

=> (time (r/reduce + (r/map inc (once-seq (range 100000000)))))
"Elapsed time: 3692.765 msecs"
5000000050000000

.

Answer 2

Le prestazioni si stanno arrestando in quanto la memoria viene esaurita.Se continui ad aspettare, molto probabilmente avresti probabile che incontrasse un errore di memoria.La creazione di un riduttore tiene la testa della raccolta in una chiusura.Quindi, l'enorme sequenza pigra lega la memoria mentre diventa realizzata.

Ecco cosa sta succedendo, distillato

user=> (def n 100000000)
#'user/n

user=> (time (dorun (range n)))
"Elapsed time: 12349.034702 msecs"

.

Ora lo stesso, ma da una chiusura

user=> (defn foo [x] (fn [f] (f x)))
#'user/foo

user=> (time ((foo (range n)) dorun))
OutOfMemoryError GC overhead limit exceeded ... (sometime later)

.

Confronta a

(time (do (doall (range n)) nil))
OutOfMemoryError GC overhead limit exceeded ... (sometime later)

.

La chiusura sospetta in riduttori

user=> (source r/folder)
(defn folder
  "Given a foldable collection, [...]"
  {:added "1.5"}
  ([coll xf]
     (reify
      clojure.core.protocols/CollReduce
      (coll-reduce [_ f1]
                   (clojure.core.protocols/coll-reduce coll (xf f1) (f1)))
   ...

.

Christophe Grand ha un Bel post su come comporre i riduttori in modo pigro.

Answer 3

I riduttori non funzionano davvero con gli elenchi pigri mentre la riduzione normale.

Per ottenere il vero vantaggio dai riduttori hai bisogno di una collezione non pigra, ad es.Un vettore e devi usare piega invece di ridurre.

 (def v (into [] (range 10000000)))
 (time (reduce + (map inc v)))
 ;; "Elapsed time: 896.79 msecs"
 (time (reduce + (r/map inc v)))
 ;; "Elapsed time: 671.947 msecs" 
 (time (r/fold + (r/map inc v)))
 ;; "Elapsed time: 229.45 msecs"

.

I riduttori funzionano con il quadro della forcella / join che richiede grandi blocchi di dati.In una sequenza pigra (grossa) non hai questi pezzi grandi, quindi forchetta / unire non può funzionare bene.

C'è un discorso con un ricco hickey sui riduttori che spiegano i concetti davvero bene: https://vimeo.com/45561411