Clojure Performance,如何输入提示到r/map

Question

下面,我有2个函数计算其参数的平方和.第一个是好的和功能性的,但比第二个慢20倍.我假设r/map没有利用aget从双数组中检索元素,而我在函数2中明确地这样做.

有什么方法可以进一步输入提示或帮助r/map r/fold来更快地执行吗？

(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

在实验之前,我在project.clj中添加了下一行:

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

基本测量:

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

这或多或少与问题中的时差一致.让我们尝试不使用Java数组(这对Clojure来说不是真正的惯用法):

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

几乎快2倍.现在让我们删除类型提示:

(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

与具有类型提示的版本相比,执行时间仅略微增加.顺便说一句,带换能器的版本具有非常相似的性能,并且更加清洁:

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

现在关于额外的类型提示.我们确实可以优化首次sum-of-squares实施:

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

注意#1:键入关于参数的提示和返回值,sum-of-squares4并且sum-of-squares5没有额外的性能优势.

注意#2:从优化开始通常是不好的做法.直接版本(apply + (map square v))在大多数情况下都具有足够好的性能.sum-of-squares2与惯用语相距甚远,并且几乎没有使用Clojure概念.如果这是真正的性能关键代码 - 更好地用Java实现它并使用interop.尽管有2种语言,但代码将更加清晰.或者甚至在非托管代码(C,C++)中实现它并使用JNI(不是真正可维护但如果正确实现,可以提供最佳性能).

Answer 2

为什么不使用areduce：

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

在我的机器上运行：

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

平均执行时间为 1.809103 毫秒，您sum-of-squares2在 1.455775 毫秒内执行相同的计算。我认为这个版本areduce比你的版本更惯用。

为了提高性能，您可以尝试使用未经检查的数学（add-unchecked和multiply-unchecked）。但要注意，您需要确保您的计算不会溢出：

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

运行相同的基准测试的平均执行时间为 1.144197 毫秒。您sum-of-squares2还可以从平均执行时间为 1.126001 毫秒的未经检查的数学中受益。