Clojure Performance, Jak wpisać podpowiedź do r/map

Question

Poniżej, mam 2 funkcje obliczające sumę kwadratów ich argumentów. Pierwszy jest ładny i funkcjonalny, ale 20 razy wolniejszy niż drugi. Zakładam, że r/map nie korzysta z agetu do pobierania elementów z podwójnej tablicy, podczas gdy ja jawnie robię to w funkcji 2.

Czy jest jakikolwiek sposób, w jaki mogę dalej napisać lub pomóc r/map r/fold, aby wykonać szybciej?

(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

Dlaczego nie skorzystać areduce:

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

Na mojej pracy maszyny:

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

daje średni czas realizacji wynosi 1.809103 ms, Twój sum-of-squares2 wykonuje te same obliczenia w 1.455775 ms. Myślę, że ta wersja używająca areduce jest bardziej idiomatyczna niż twoja wersja.

Aby wycisnąć nieco więcej wydajności, możesz spróbować użyć niezaznaczonej matematyki (add-unchecked i multiply-unchecked). Ale uwaga, trzeba mieć pewność, że wyliczenie nie przepełnić:

(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))))) 

Running ten sam wzorzec daje średni czas realizacji wynosi 1.144197 ms. Twój sum-of-squares2 może również skorzystać z niezaznaczonej matematyki ze średnim czasem wykonania 1.126001 ms.

Answer 2

Przed eksperymentów dodałem kolejną linię w project.clj:

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

podstawowe pomiary:

(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 ... 

Jest to mniej więcej zgodne z różnicą czasu w pytaniu. Spróbujmy nie używać tablic Java (które nie są naprawdę idiomatyczne dla Clojure):

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

prawie 2 razy szybciej. Teraz usuńmy podpowiedzi typu:

(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 

Czas realizacji zwiększył się nieznacznie w porównaniu do wersji z podpowiedziami typu. Nawiasem mówiąc, wersja z transducers ma bardzo podobną wydajność i jest znacznie czystsze:

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

Teraz o dodatkowy typ podpowiadania. Możemy rzeczywiście zoptymalizować pierwszy sum-of-squares realizacji:

(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 ... 

Uwaga # 1: typ wskazówek na temat argumentów i wartości zwracanej sum-of-squares4 i sum-of-squares5 mieć żadnych dodatkowych korzyści z wydajnością.

Uwaga # 2: Na ogół złą praktyką jest rozpoczynać od optimizations. Prosta wersja (apply + (map square v)) będzie miała wystarczająco dobrą wydajność w większości sytuacji. sum-of-squares2 jest bardzo daleki od idiomatycznego i nie używa dosłownie żadnych koncepcji Clojure. Jeśli jest to naprawdę krytyczny pod względem wydajności kod - lepiej go zaimplementować w Javie i używać współdziałania. Kod będzie znacznie czystszy pomimo posiadania 2 języków. Lub nawet zaimplementować go w niezarządzanym kodzie (C, C++) i używać JNI (nie bardzo konserwowalny, ale jeśli poprawnie zaimplementowany, może dać najlepszą możliwą wydajność).