Hiệu suất Clojure, Cách nhập gợi ý vào r/map

Question

Dưới đây, tôi có 2 hàm tính tổng các bình phương của các đối số của chúng. Cái đầu tiên đẹp và chức năng, nhưng chậm hơn 20 lần so với cái thứ hai. Tôi đoán rằng r/bản đồ không tận dụng lợi thế của aget để lấy các phần tử từ mảng đôi, trong khi tôi rõ ràng làm điều này trong hàm 2.

Có cách nào để tiếp tục gõ hay giúp r/map r/gấp để thực hiện nhanh hơn?

(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

Tại sao không sử dụng areduce:

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

Trên máy tính chạy của tôi:

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

Cung cấp một thời gian thực hiện trung bình của 1,809103 ms, sum-of-squares2 bạn thực hiện các tính toán tương tự trong 1,455775 ms. Tôi nghĩ rằng phiên bản này sử dụng areduce là thành ngữ hơn phiên bản của bạn.

Để ép hiệu suất cao hơn một chút, bạn có thể thử sử dụng toán chưa được kiểm tra (add-unchecked và multiply-unchecked). Nhưng hãy cẩn thận, bạn cần phải chắc chắn rằng tính toán của mình không thể tràn:

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

Chạy cùng một điểm chuẩn cho thời gian thực hiện trung bình là 1.144197 ms. sum-of-squares2 của bạn cũng có thể hưởng lợi từ toán học không được kiểm tra với thời gian thực hiện trung bình là 1.126001 ms.

Answer 2

Trước khi thí nghiệm tôi đã thêm dòng tiếp theo trong project.clj:

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

đo cơ bản:

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

Điều này ít nhiều phù hợp với chênh lệch thời gian trong câu hỏi. Hãy cố gắng không sử dụng các mảng Java (không thực sự là thành ngữ cho Clojure):

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

Gần gấp 2 lần nhanh hơn. Bây giờ, hãy xóa các gợi ý loại:

(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 

Thời gian thực hiện chỉ tăng nhẹ so với phiên bản có gợi ý loại. Bằng cách này, phiên bản với transducers có hiệu suất rất giống nhau và có nhiều bụi:

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

Bây giờ về thêm kiểu gián tiếp. Chúng tôi thực sự có thể tối ưu hóa sum-of-squares thực hiện đầu tiên:

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

Lưu ý # 1: Loại gợi ý về lý luận và trả lại giá trị của sum-of-squares4 và sum-of-squares5 không có lợi ích hiệu suất bổ sung.

Lưu ý # 2: Thường là thực tiễn không tốt để bắt đầu với optimizations. Phiên bản thẳng về phía trước (apply + (map square v)) sẽ có hiệu suất đủ tốt cho hầu hết các trường hợp. sum-of-squares2 là rất xa thành ngữ và sử dụng nghĩa đen không có khái niệm Clojure. Nếu điều này thực sự là mã quan trọng hiệu suất - tốt hơn để thực hiện nó trong Java và sử dụng interop. Mã sẽ sạch hơn mặc dù có 2 ngôn ngữ. Hoặc thậm chí thực hiện nó trong mã không được quản lý (C, C++) và sử dụng JNI (không thực sự bảo trì nhưng nếu được triển khai đúng cách, có thể cung cấp hiệu suất tốt nhất có thể).