Prestazioni Cloquage, Come digitare hint su r/mappa

Question

Di seguito, ho 2 funzioni che calcolano la somma dei quadrati dei loro argomenti. Il primo è bello e funzionale, ma 20 volte più lento del secondo. Presumo che la r/map non stia sfruttando aget per recuperare elementi dal doppio array, mentre lo sto facendo esplicitamente nella funzione 2.

C'è un modo per poter ulteriormente digitare o aiutare r/map r/piega per eseguire più velocemente?

(defn sum-of-squares 
    "Given a vector v, compute the sum of the squares of elements." 
    ^double [^doubles v] 
    (r/fold + (r/map #(* % %) v))) 

(defn sum-of-squares2 
    "This is much faster than above. Post to stack-overflow to see." 
    ^double [^doubles v] 
    (loop [val 0.0 
     i (dec (alength v))] 
    (if (neg? i) 
     val 
     (let [x (aget v i)] 
     (recur (+ val (* x x)) (dec i)))))) 

(def a (double-array (range 10))) 
(quick-bench (sum-of-squares a)) 

800 ns

(quick-bench (sum-of-squares2 a)) 

40 ns

Answer 1

perché non utilizzare areduce:

(def sum-of-squares3 ^double [^doubles v] 
    (areduce v idx ret 0.0 
      (let [item (aget v idx)] 
      (+ ret (* item item))))) 

Sulla mia macchina in funzione:

(criterium/bench (sum-of-squares3 (double-array (range 100000)))) 

dà un tempo di esecuzione media di 1.809103 ms, il vostro sum-of-squares2 esegue lo stesso calcolo in 1.455775 ms. Penso che questa versione che usa areduce sia più idiomatica della tua versione.

Per spremere un po 'di più le prestazioni si può provare a usare la matematica non controllata (add-unchecked e multiply-unchecked). Ma attenzione, è necessario essere sicuri che il vostro calcolo non può traboccare:

(defn sum-of-squares4 ^double [^doubles v] 
    (areduce v idx ret 0.0 
      (let [item (aget v idx)] 
      (unchecked-add ret (unchecked-multiply item item))))) 

esegue lo stesso punto di riferimento dà un tempo di esecuzione media di 1.144197 ms. Il tuo sum-of-squares2 può anche beneficiare della matematica non controllata con un tempo di esecuzione medio di 1.126001 ms.

Answer 2

Prima di esperimenti che ho aggiunto nella riga successiva project.clj:

:jvm-opts ^:replace [] ; Makes measurements more accurate 

misure di base:

(def a (double-array (range 1000000))) ; 10 is too small for performance measurements 
(quick-bench (sum-of-squares a)) ; ... Execution time mean : 27.617748 ms ... 
(quick-bench (sum-of-squares2 a)) ; ... Execution time mean : 1.259175 ms ... 

Questo è più o meno coerente con la differenza di tempo nella domanda. Cerchiamo di non utilizzare array Java (che non sono realmente idiomatica per Clojure):

(def b (mapv (partial * 1.0) (range 1000000))) ; Persistent vector 
(quick-bench (sum-of-squares b)) ; ... Execution time mean : 14.808644 ms ... 

quasi 2 volte più veloce. Ora rimuoviamo i suggerimenti del tipo:

(defn sum-of-squares3 
"Given a vector v, compute the sum of the squares of elements." 
[v] 
(r/fold + (r/map #(* % %) v))) 

(quick-bench (sum-of-squares3 a)) ; Execution time mean : 30.392206 ms 
(quick-bench (sum-of-squares3 b)) ; Execution time mean : 15.583379 ms 

Tempo di esecuzione aumentato solo marginalmente rispetto alla versione con suggerimenti tipo. Tra l'altro, la versione con transducers ha prestazioni molto simili ed è molto più pulito:

(defn sum-of-squares3 [v] 
    (transduce (map #(* % %)) + v)) 

Ora circa ulteriore tipo hinting. anzi possiamo ottimizzare primo sum-of-squares implementazione:

(defn square ^double [^double x] (* x x)) 

(defn sum-of-squares4 
    "Given a vector v, compute the sum of the squares of elements." 
    [v] 
    (r/fold + (r/map square v))) 

(quick-bench (sum-of-squares4 b)) ; ... Execution time mean : 12.891831 ms ... 

(defn pl 
    (^double [] 0.0) 
    (^double [^double x] (+ x)) 
    (^double [^double x ^double y] (+ x y))) 

(defn sum-of-squares5 
    "Given a vector v, compute the sum of the squares of elements." 
    [v] 
    (r/fold pl (r/map square v))) 

(quick-bench (sum-of-squares5 b)) ; ... Execution time mean : 9.441748 ms ... 

Nota # 1: tipo di suggerimenti su argomenti e valore di ritorno di sum-of-squares4 e sum-of-squares5 non hanno ulteriori vantaggi prestazionali.

Nota n. 2: In genere è una cattiva pratica iniziare con optimizations. La versione straight-forward (apply + (map square v)) avrà prestazioni sufficienti per la maggior parte delle situazioni. sum-of-squares2 è molto lontano dall'idiomatico e non utilizza letteralmente concetti di Clojure. Se questo è davvero un codice critico per le prestazioni - meglio implementarlo in Java e usare l'interoperabilità. Il codice sarà molto più pulito nonostante abbia 2 lingue. O addirittura implementarlo in codice non gestito (C, C++) e utilizzare JNI (non molto manutenibile ma se correttamente implementato, può fornire le migliori prestazioni possibili).