Clojure在简单循环中的性能真的很差,相比之下Java更好

31

警告:本文包含欧拉计划第5题的问题解答。

我正在尝试学习Clojure语言,并且解决了第5题的问题,但Clojure代码运行速度比Java慢了几个数量级(Java为1515毫秒,Clojure为169932毫秒)。我甚至尝试使用类型提示、未检查的数学操作和内联函数等方法,但都无济于事。

为什么我的Clojure代码运行速度如此之慢?

Clojure代码:

(set! *unchecked-math* true)
(defn divides? [^long number ^long divisor] (zero? (mod number divisor)))

(defn has-all-divisors [divisors ^long num]
  (if (every? (fn [i] (divides? num i)) divisors) num false))

(time (prn (some (fn [^long i] (has-all-divisors (range 2 20) i)) (iterate inc 1))))

Java代码:

public class Problem5 {
  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    int i = 1;
    while(!hasAllDivisors(i, 2, 20)) {
      i++;
    }
    long end = System.currentTimeMillis();
    System.out.println(i);
    System.out.println("Elapsed time " + (end - start));
  }

  public static boolean hasAllDivisors(int num, int startDivisor, int stopDivisor) {
    for(int divisor=startDivisor; divisor<=stopDivisor; divisor++) {
      if(!divides(num, divisor)) return false;
    }
    return true;
  }

  public static boolean divides(int num, int divisor) {
    return num % divisor == 0;
  }
}

1
你的Java代码在2-18行,而Clojure代码在2-20行。 - Ankur
抱歉,我已经修复了。我不小心粘贴了错误版本的代码,但是计时对于两个都达到20是准确的。 - gleenn
System.currentTimeMillis()作为基准?这不是认真的。看看http://shipilev.net/talks/devoxx-Nov2013-benchmarking.pdf。 - Puh
我欣赏您的看法@Puh。但我认为在Java中编写天真等效代码,然后在Clojure中编写并发现Clojure的速度要慢10倍是完全合理的。我的测试环境很糟糕,这是一个非常小的微基准测试,JIT可能甚至还没有启动,但谁关心呢? 10倍是疯狂的。如果我尝试学习语言,并且出现了这么明显的性能问题,即使我的方法不是科学的,并且受到不必要或渴望的优化的驱使,我也想知道为什么。 - gleenn
3个回答

56

一些性能问题:

  • (range 2 20) 的调用会为每个i增量创建一个新的惰性数字列表。这很昂贵,导致了大量不必要的垃圾回收。
  • 通过函数调用传递过多的装箱操作。即使是(iterate inc 1)也会在每个增量处进行装箱/拆箱操作。
  • 您正在遍历一系列除数,这比直接使用迭代循环慢。
  • mod在Clojure中实际上并没有得到很好的优化。最好使用rem

您可以通过使用let语句仅定义一次范围来解决第一个问题:

(time (let [rng (range 2 20)]
  (prn (some (fn [^long i] (has-all-divisors rng i)) (iterate inc 1)))))
=> "Elapsed time: 48863.801522 msecs"

您可以使用循环/递归解决第二个问题:

(time (let [rng (range 2 20)
           f (fn [^long i] (has-all-divisors rng i))]
       (prn (loop [i 1] 
              (if (f i)
                i
                (recur (inc i)))))))
=> "Elapsed time: 32757.594957 msecs"

您可以通过使用可行除数的迭代循环来解决第三个问题:

(defn has-all-divisors [^long num]
  (loop [d (long 2)]
    (if (zero? (mod num d))
      (if (>= d 20) true (recur (inc d)))
      false)))

 (time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i))))))
 => "Elapsed time: 13369.525651 msecs"

你可以使用rem来解决最后的问题。

(defn has-all-divisors [^long num]
  (loop [d (long 2)]
    (if (== 0 (rem num d))
      (if (>= d 20) true (recur (inc d)))
      false)))

 (time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i))))))
=> "Elapsed time: 2423.195407 msecs"

正如你所看到的,现在Clojure与Java版本有了一定的竞争力。

通常情况下,只需要花费一点点功夫就可以让Clojure几乎和Java一样快。主要技巧通常包括:

  • 避免使用惰性函数特性。它们很好用,但会增加一些开销,在低级计算密集型代码中可能会出现问题。
  • 使用原始/未检查的数学运算
  • 使用循环/递归而不是序列
  • 确保你没有对Java对象进行反射(即(set! *warn-on-reflection* true)并消除所有发现的警告)

2
我必须说,我觉得这有点令人沮丧。它似乎表明,为了获得性能,必须牺牲功能特性。如果必须编写类似 C 语言的代码才能获得性能,那么编译器需要改进,不是吗? - Hendekagon
12
也许有点可悲,但这就是生活的事实:高级语言特性通常会带来一些成本和开销。我相信编译器可以做得更聪明,但你无法改变这个事实:例如,一个惰性数据结构总是比等效的非惰性结构具有更高的开销。 - mikera
9
另外需要指出的一点是,使用Clojure时您有选择的余地:如果性能不是问题,那么您可以使用惰性序列和所有高级功能编写代码,使您的代码更易读,可能更紧凑。然而,如果您需要性能,则始终可以采用另一种方式,并仍然获得良好的结果... - Daniel Gruszczyk
1
新手问题:惰性函数不是应该通过只在需要时进行评估来减少时间吗? - decached
1
这可能会减少一些计算量,但它也会创建额外的函数调用和对象,并且如果您最终仍然执行所有结果,它并没有帮助。 - gleenn
检查反射对我来说产生了巨大的影响。谢谢你。 - Terje Dahl

1

我无法复制1500毫秒的性能。编译成uberjar后,Clojure代码似乎比Java版本快两倍。

Now timing Java version
    232792560
"Elapsed time: 4385.205 msecs"

Now timing Clojure version
    232792560
"Elapsed time: 2511.916 msecs"

我将Java类放在resources/HasAllDivisors.java中。

public class HasAllDivisors {

    public static long findMinimumWithAllDivisors() {
        long i = 1;
        while(!hasAllDivisors(i,2,20)) i++;
        return i;
    }

    public static boolean hasAllDivisors(long num, int startDivisor, int stopDivisor) {
        for(int divisor = startDivisor; divisor <= stopDivisor; divisor++) {
            if(num % divisor > 0) return false;
        }
        return true;
    }

    public static void main(String[] args){
        long start = System.currentTimeMillis();
        long i = findMinimumWithAllDivisors();
        long end = System.currentTimeMillis();
        System.out.println(i);
        System.out.println("Elapsed time " + (end - start));
    }

}

而在Clojure中

(time (prn (HasAllDivisors/findMinimumWithAllDivisors)))

(println "Now timing Clojure version")
(time
    (prn
        (loop [i (long 1)]
            (if (has-all-divisors i)
                i
                (recur (inc i))))))

即使在命令行上,Java类也不能复制快速速度。

$ time java HasAllDivisors
  232792560
Elapsed time 4398

real   0m4.563s
user   0m4.597s
sys    0m0.029s

我根本没有使用打包的代码。也许你正在使用一个性能更好的Clojure新版本?听到事情朝着更好的方向发展总是很好的。 - gleenn
我想再添加一个数据点。在我的机器上,运行您的Java代码(不使用Clojure)在独立的JAR文件中几乎瞬间返回(372ms),而mikera帖子中优化的Clojure uberjar(1.8或1.9)代码需要约2300ms。 OP的原始功能代码与mikera的第一个修复(范围定义一次)产生了更慢的24390ms。所有结果来自2017 MBP。 - nogridbag

0

我知道这是一个老问题,但我遇到了类似的情况。看起来OP的说法,Clojure在简单循环上比Java差得多,是正确的。我按照这个线程中的过程进行操作,从OP的代码开始,然后添加性能改进。最终,Java代码运行时间约为300毫秒,优化后的Clojure代码运行时间约为3000毫秒。使用lein创建uberjar可以将Clojure代码缩短到2500毫秒。

由于我们知道给定代码的答案,因此我使用它让Clojure代码仅仅循环次数而不进行mod/rem计算。它只是通过循环。

(def target 232792560)

(defn has-all-divisors [divisors ^long num]
    (loop [d (long 2)]
        (if (< d 20) (recur (inc d)))))

(time (let [rng (range 2 20)
            f (fn [^long i] (has-all-divisors (range 2 20) i)) ]
    (prn (loop [i 1] 
            (if (< i target)
                (do (f i) (recur (inc i))))))))

得出的时间大致与进行计算相同,即3000毫秒。因此,Clojure花费了那么长时间仅仅是遍历那么多循环。


没有实际运行您的代码,一个立即的问题是您没有使用您的“rng”变量。 - gleenn
不,这不是真的。Clojure在简单循环上并不比Java差,只是你没有做一个简单的循环。你正在进行递归。这意味着函数调用和堆栈帧的创建。如果你实际上查看生成的字节码,你会发现Clojure版本有大约三倍的函数调用。通常在Lisp中解决这个问题的方法是支持尾调用优化,然后进行尾调用消除。这意味着尾部位置的递归调用被转换为循环,并具有相同的性能。在Project Loom完成之前,Java不会有这个功能。 - krzyzowiec
在Clojure中唯一的循环方式是使用loop/recur,因此,在实现一个简单循环算法时,Clojure比Java更差。我已经在其他Lisp(chicken、racket和common lisp)中实现过这个问题,它们都有同样的问题,所以尾递归优化并不能达到本地循环性能的水平。 - Rich
这不是Clojure中的简单循环,这就是我的观点。公平的比较应该让Java像Clojure一样进行递归。至于其他Lisp方言,你怎么知道问题出在循环性能上?你是否尝试过使用任何其他算法进行大量递归以进行比较? - krzyzowiec
不,这不是一个公平的比较。这是人为地将Java减慢到Clojure的水平。该算法是循环一系列数字直到找到解决方案。如果您有能够像Java一样高效地完成此操作的Clojure代码,我真的很想看看。到目前为止,我还没有能够找到,其他人也是如此。关于其他Lisp,您不需要另一个算法。在这个问题上,直接递归比TCO更糟糕。TCO仍然不如迭代语言中的循环好。对于其他算法,Racket、CL等可以与C相媲美。但不包括紧密循环。 - Rich

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接