clojure"for"与"loop"的性能差异

Question

以下两个函数都从2到(sqrt n),如果n是非素数,则一旦检测到它们就会停止

(defn is-prime-for? [n]
  (empty? (for [i (range 2 (math/sqrt (inc n)))
                :when (= 0 (rem n i))]
            i)))

(defn is-prime-loop? [n]
  (loop [i 2]
    (cond (> i (math/sqrt (inc n))) true
          (zero? (rem n i)) false
          :else (recur (inc i)))))

那么为什么我们会看到它们之间的巨大性能差异呢？"循环"版本花费了近4倍的时间(在我的桌面上)

project-euler.prob010> (time (dorun (map is-prime-for? (range 200000))))
"Elapsed time: 3267.613099 msecs"
;; => nil
project-euler.prob010> (time (dorun (map is-prime-loop? (range 200000))))
"Elapsed time: 12961.190032 msecs"
;; => nil

Answer 1

这样的微基准测试通常没有意义,因为它们没有考虑可能影响特定代码片段性能的各种因素(例如JVM预热,优化......).如果想获得可靠的结果,应该使用像标准这样的基准测试库.

话虽这么说,你的两个版本有一些重大差异,将反映在结果中:

• for创建一个懒惰的序列,其维护成本高于所做的loop/recur.
• 该loop版本计算(Math/sqrt (inc n))在每个迭代上,该for版本只有一次.
• zero?有一个层次的间接超过(= 0 ...).

显然,编译器可能能够优化这些,但还有更多因素可以改变结果(Java版本,OpenJDK与Oracle,Clojure版本......).所以,这里我的基准测试结果在Oracle JDK 1.7.0_67上使用Clojure 1.6.0运行:

(criterium.core/quick-bench (mapv is-prime-for? (range 200000)))
Evaluation count : 6 in 6 samples of 1 calls.
             Execution time mean : 1.942423 sec
    Execution time std-deviation : 36.768207 ms
   Execution time lower quantile : 1.912171 sec ( 2.5%)
   Execution time upper quantile : 1.984463 sec (97.5%)
                   Overhead used : 8.986692 ns

(criterium.core/quick-bench (mapv is-prime-loop? (range 200000)))
Evaluation count : 6 in 6 samples of 1 calls.
             Execution time mean : 724.077492 ms
    Execution time std-deviation : 5.695680 ms
   Execution time lower quantile : 716.547992 ms ( 2.5%)
   Execution time upper quantile : 730.173992 ms (97.5%)
                   Overhead used : 8.986692 ns

因此,在我的机器上,loop版本比for一个版本快3倍.