什麼是減緩這種Clojure功能下降？

我正在使用Clojure的Project Euler problem 14。我有我覺得是一個很好的通用算法，並且我得到了正確的結果，但我正在努力理解爲什麼我的函數與Java中相當於Java的等價函數相比（我認爲是如此之慢）。這是我的Clojure函數從給定的起始編號獲得在Collatz鏈的長度：什麼是減緩這種Clojure功能下降？

(defn collatz-length 
    [n] 
    (loop [x n acc 1] 
    (if (= 1 x) 
     acc 
     (recur (if (even? x) 
       (/ x 2) 
       (inc (* 3 x))) 
      (inc acc)))))

，這裏是我的Java功能，做同樣的事情：

public static int collatzLength(long x) { 
    int count = 0; 
    while (x > 1) { 
     if ((x % 2) == 0) { 
      x = x/2; 
     } else { 
      x = (x * 3) + 1; 
     } 
     count++; 
    } 
    return count; 
}

到時候這些功能的性能，我用下面的Clojure代碼：

(time (dorun (map collatz-length (range 1 1000000))))

而且Java代碼：

long starttime = System.currentTimeMillis(); 

int[] nums = new int[1000000]; 
for (int i = 0; i < 1000000; i++) { 
    nums[i] = collatzLength(i+1); 
} 

System.out.println("Total time (ms) : " + (System.currentTimeMillis() - starttime));

Java代碼在我機器上的304 ms中運行，但Clojure代碼需要4220 ms。什麼導致了這個瓶頸，我怎樣才能提高我的Clojure代碼的性能？

來源

2014-10-01 Kevin

哇！真正的程序員在工作。 – Thumbnail 2014-10-02 11:34:56

你正在使用盒裝數學，所以數字不斷被裝箱和拆箱。嘗試是這樣的：

(set! *unchecked-math* true) 
(defn collatz-length 
    ^long [^long n] 
    (loop [x n acc 1] 
    (if (= 1 x) 
     acc 
     (recur (if (zero? (rem x 2)) 
       (quot x 2) 
       (inc (* 3 x))) 
      (inc acc))))) 
(time (dorun (loop [i 1] (when (< i 1000000) (collatz-length i) (recur (inc i))))))

來源

2014-10-01 22:31:18

不錯！這將我的時間縮短到更合理的「650毫秒」。我注意到你也把我的'/'換成了''''，這是最大的性能提升。爲什麼'''更有效率？ – Kevin 2014-10-01 23:01:30

「quot」被定義爲截斷整數除法，所以它可以編譯成單個JVM字節碼操作（只要給出正確的提示）。 '/'返回分數，所以它不能利用那些'^ long'類型提示：它必須擔心你可能會嘗試將奇數除以2，在這種情況下，它需要給你一小部分。 – amalloy 2014-10-02 01:29:23

基於上面的amalloy評論，我用'（零？（rem x 2））'替換了'even？'''，它可以使用所有的prim，而且似乎更快。 – 2014-10-02 01:50:11

根據Alex的答案，就可以加快速度更由調用內聯到even?（該功能不支持未裝箱的整數）位：

(defn collatz-length 
    ^long [^long n] 
    (loop [x n acc 1] 
    (if (= 1 x) 
     acc 
     (recur (if (zero? (bit-and x 1)) 
       (quot x 2) 
       (inc (* 3 x))) 
      (inc acc)))))

僅供參考，https://www.refheap.com/cfd421430653cf786177f3cfe是由你的java方法產生的字節碼（改爲使用long而不是int），以及由我的clojure函數產生的字節碼。它們看起來非常非常相似，除了一個介紹性節，其中clojure版本將輸入參數n複製到x中，其中java版本剛剛覆蓋現有的n。

來源

2014-10-02 01:39:02 amalloy

不，這是因爲您使用n而不是x來進行循環檢查。 :) – 2014-10-02 01:51:02

啊哈，謝謝@亞歷克斯。這就是我在離開吃晚餐時發佈正確答案的原因。有了這個修復（編輯到我的答案），我得到了從你的代碼進一步4倍加速，所有的反射和裝箱消失了：它應該基本上是java版本擴展到相同的字節碼。 – amalloy 2014-10-02 02:59:36

有趣的是，在我的機器上，如果我用'bit-shift-right x 1'代替'quot x 2'，我會在@ amalloy的代碼上得到10％的改進。我想知道爲什麼jvm/cpu沒有優化它。 – 2014-10-02 04:38:22

什麼是減緩這種Clojure功能下降？

回答

相關問題