这个Clojure函数的运行速度变慢了，是什么原因？

Question

我正在使用Clojure解决欧拉计划第14题。我已经有一个我认为非常好的通用算法，并且得到了正确的结果，但我发现与Java中等效的函数相比，我的函数速度非常慢。以下是我的Clojure函数，用于获取给定起始数字的Collatz链长度：

(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 毫秒，但该 Clojure 代码需要 4220 毫秒。是什么导致了这个瓶颈，我该如何提高 Clojure 代码的性能？

- Kevin

---

哇！真正的程序员在工作。 - Thumbnail

Answer 1

您正在使用盒式数学，因此数字不断地被装箱和拆箱。尝试使用以下方法：

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

- Alex Miller

---

不错！这将我的时间缩短到了一个更合理的“650毫秒”。我注意到你还将我的“/”改成了“quot”，这最终成为了最大的性能提升。为什么“quot”更有效率？ - Kevin

“quot” 被定义为截断整数除法，因此它可以编译成单个 JVM 字节码操作（前提是给出正确的类型提示）。 “/” 返回分数，因此它无法利用那些“^long”类型提示：它必须担心您可能尝试将奇数除以二，在这种情况下，它需要返回一个分数。 - amalloy

基于amalloy上面的评论，我用(zero? (rem x 2))替换了even?，可以使用所有prims，而且速度似乎更快。 - Alex Miller

Answer 2

根据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。

- amalloy

---

不，这是因为您在循环检查中使用了n而不是x。 :) - Alex Miller

啊哈，谢谢@Alex。这就是我在离开吃晚饭之前发布答案的结果。通过进行修复（编辑到我的答案中），我从您的代码中获得了进一步的4倍加速，并且所有的反射和装箱都已经消失：它应该基本上与Java版本扩展出的字节码相同。 - amalloy

有趣的是，在我的机器上，如果我用 bit-shift-right x 1 替换 quot x 2，@amalloy 的代码可以提高 10%。我想知道为什么 JVM / CPU 没有进行优化。 - Diego Basch

@diego 因为对于负数x，它们不是相同的。例如，对于x = -1，移位会产生-1，但quot会产生0（在Java中，整数除法向0舍入）。 - amalloy

我猜CPU无法知道它正在处理有符号还是无符号的值。如果它们保证是无符号的，那么它可以进行优化。另一方面，JVM可以知道在具有正值的循环中除以2可以优化为位移。 - Diego Basch

没关系，这不是一个常量循环，因此JVM需要进行太多的猜测才能知道x始终为正并且可以被视为无符号。 - Diego Basch