为什么Clojure在递归加法函数上比Scala快得多？

Question

为什么Clojure在递归加法函数上比Scala快得多？

scalaclojureperformancetail-recursiontail-call-optimization

22

我的朋友给了我这个Clojure的代码片段

(defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
(time (sum (range 1 9999999) 0))

他问我它与类似的Scala实现相比如何表现。

我编写的Scala代码如下：

def from(n: Int): Stream[Int] = Stream.cons(n, from(n+1))
val ints = from(1).take(9999998)

def add(a: Stream[Int], b: Long): Long = {
    if (a.isEmpty) b else add(a.tail, b + a.head)
}

val t1 = System.currentTimeMillis()
println(add(ints, 0))
val t2 = System.currentTimeMillis()
println((t2 - t1).asInstanceOf[Float] + " msecs")

总之，Clojure代码在我的电脑上运行约1.8秒，使用的堆内存不到5MB；而Scala代码则需要约12秒，512MB的堆内存不足（如果将堆设置为1GB，则可以完成计算）。

因此，我想知道为什么Clojure在这种情况下要快得多且更加精简？您是否有类似于速度和内存使用方面的行为的Scala实现？

请勿发表宗教言论，我的兴趣主要在于找出Clojure在这种情况下的速度优势是什么，以及是否有更快的Scala算法实现。谢谢。

- Li Lo

4个回答

28

Clojure的range函数不会做记忆，而Scala的Stream函数则会。这是两种完全不同的数据结构，所以得到的结果也完全不同。虽然Scala也有非记忆型的Range结构体，但在这种简单递归的情况下使用起来比较麻烦。以下是我的观点。

在一台旧电脑上使用Clojure 1.0版，速度较慢，需要3.6秒。

user=> (defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
#'user/sum
user=> (time (sum (range 1 9999999) 0))
"Elapsed time: 3651.751139 msecs"
49999985000001

Scala的字面翻译需要我编写一些代码。

def time[T](x : => T) =  {
  val start = System.nanoTime : Double
  val result = x
  val duration = (System.nanoTime : Double) - start
  println("Elapsed time " + duration / 1000000.0 + " msecs")
  result
}

确保正确无误是非常重要的

scala> time (Thread sleep 1000)
Elapsed time 1000.277967 msecs

现在我们需要一个未记忆化的范围，其语义类似于Clojure的范围。

case class MyRange(start : Int, end : Int) {
  def isEmpty = start >= end
  def first = if (!isEmpty) start else error("empty range")
  def rest = new MyRange(start + 1, end)
}

从那个“添加”直接跟随

def add(a: MyRange, b: Long): Long = {
    if (a.isEmpty) b else add(a.rest, b + a.first)
}

在同一台设备上，它的运行速度比Clojure快得多

scala> time(add(MyRange(1, 9999999), 0))
Elapsed time 252.526784 msecs
res1: Long = 49999985000001

使用Scala标准库的Range，您可以进行折叠操作。虽然不如简单的原始递归快，但是它的代码量较少，并且仍然比Clojure递归版本更快（至少在我的电脑上）。

scala> time((1 until 9999999 foldLeft 0L)(_ + _))
Elapsed time 1995.566127 msecs
res2: Long = 49999985000001

与记忆化流相比，折叠的效果不同。

time((Stream from 1 take 9999998 foldLeft 0L)(_ + _)) 
Elapsed time 3879.991318 msecs
res3: Long = 49999985000001

- James Iry

为什么使用foldLeft比原始递归慢得多？ - Noel Yap

5

我猜测这是由于Clojure如何处理尾递归优化。由于JVM不会本地执行此优化（而Clojure和Scala都在其上运行），因此Clojure通过recur关键字优化尾递归。从Clojure网站中可以看到：

在函数式语言中，循环和迭代通过递归函数调用来替换/实现。许多这样的语言保证在尾部位置调用的函数不会消耗堆栈空间，因此递归循环利用恒定空间。由于Clojure使用Java调用约定，因此它不能也不会提供相同的尾调用优化保证。相反，它提供了recur特殊操作符，通过重新绑定并跳转到最近的封闭循环或函数框架来进行常量空间递归循环。虽然不像尾调用优化那么通用，但它允许大多数相同的优雅构造，并且具有检查对recur的调用只能发生在尾部位置的优点。

编辑：Scala也优化尾调用，只要它们处于某种形式中。然而，正如前面的链接所示，Scala只能对非常简单的情况进行优化：

实际上，这是Scala编译器的一个特性，称为尾调用优化。它优化掉了递归调用。但是，这个特性只在像上面那样简单的情况下有效。如果递归是间接的，例如，Scala无法优化尾调用，因为JVM指令集受限。

没有实际编译和反编译代码以查看产生的JVM指令，我怀疑这不是那些简单情况之一（正如Michael所说，由于每个递归步骤都要获取a.tail），因此Scala无法对其进行优化。

- Chris Bunch

我正在使用scala 2.7.5，我认为它应该在我使用的场景中执行尾递归优化。 - Li Lo

2

那你最好确保它是这样的 :-) - Vinko Vrsalovic

根据下面的反编译字节码，看起来正在执行尾递归优化。 public long add(scala.Stream, long); Code: 0: aload_1 1: invokeinterface #103, 1; //InterfaceMethod scala/Seq.isEmpty:()Z 6: ifeq 11 9: lload_2 10: lreturn 11: aload_1 12: invokevirtual #106; //Method scala/Stream.tail:()Lscala/Stream; 15: lload_2 16: aload_1 17: invokevirtual #110; //Method scala/Stream.head 20: invokestatic #114; //Method scala/runtime/BoxesRunTime.unboxToInt 23: i2l 24: ladd 25: lstore_2 26: astore_1 27: goto 0 - Li Lo

5

我为您翻译如下内容，这段文本涉及IT技术，我会尽力使其更加易懂。

在您提供的示例中，类Stream（或者与之相关的某个匿名函数——因为visualvm崩溃了我忘记它的名称）占用了大部分堆空间。这是由于Scala中的Stream确实存在内存泄漏的问题——请参见Scala Trac #692。此问题将在Scala 2.8中得到修复。编辑：Daniel的评论指出这与该错误无关。原因是"val ints指向Stream头部，垃圾收集器无法回收任何内容" [Daniel]。但是，对于理解这个问题，我认为这个Bug报告中的评论非常有意思。

在您的add函数中，您持有对a.head的引用，因此垃圾收集器无法回收头部，导致最终产生一个持有9999998个元素的流，这些元素不能被GC。

[小插曲]

您也可能保留您一直传递的尾部的副本，我不确定Stream如何处理这种情况。如果您使用一个列表，尾巴就会被复制而产生问题。例如：

val xs =  List(1,2,3)
val ys = 1 :: xs
val zs = 2 :: xs

这里，ys和zs都“分享”着相同的尾巴，至少在堆方面是这样的（ys.tail eq zs.tail，也就是说引用相等会得到true）。

[这个小插曲是为了说明，在原则上传递许多尾巴并不是真正的坏事：），它们没有被复制，至少对于列表来说]

另一种实现方法（非常快，并且我认为比纯函数方法更清晰）是使用命令式方法：

def addTo(n: Int, init: Int): Long = {
  var sum = init.toLong
  for(i <- 1 to n) sum += i
  sum
}

scala> addTo(9999998, 0)

在Scala中，使用命令式方法是可以的，这可以提高性能和可读性（至少对我来说，这个版本的add更能清晰地表达它的意图）。为了更简洁，你甚至可以写成以下形式：

(1 to 9999998).reduceLeft(_ + _)

运行速度会稍慢一些，但仍然合理，不会导致内存飙升。

我认为Clojure可能会更快，因为它是完全函数式的，因此比Scala（混合了函数式、面向对象和命令式）更容易进行优化。但我对Clojure并不是很熟悉。

希望这能帮到您 :)

- Flaviu Cipcigan

5

这与bug无关。因为“val ints”指向“Stream”头部，所以垃圾回收器无法回收任何东西。 - Daniel C. Sobral

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel C. Sobral · Accepted Answer

首先，Scala只有在使用-optimise时才会优化尾调用。编辑：似乎Scala在不使用-optimise的情况下也会始终优化尾调用递归。

其次，Stream和Range是两个非常不同的东西。一个Range有一个起点和一个终点，它的投影只有一个计数器和终点。一个Stream是一个将会按需计算的列表。由于您正在添加整个ints，因此您将计算并分配整个Stream。

更接近实际的代码应该是：

import scala.annotation.tailrec

def add(r: Range) = {
  @tailrec 
  def f(i: Iterator[Int], acc: Long): Long = 
    if (i.hasNext) f(i, acc + i.next) else acc

  f(r iterator, 0)
}

def time(f: => Unit) {
  val t1 = System.currentTimeMillis()
  f
  val t2 = System.currentTimeMillis()
  println((t2 - t1).asInstanceOf[Float]+" msecs")
}

正常运行：

scala> time(println(add(1 to 9999999)))
49999995000000
563.0 msecs

在Scala 2.7中，您需要使用“elements”而不是“iterator”，并且没有“tailrec”注释--该注释仅用于在无法使用尾递归优化定义时发出警告--因此您需要从代码中删除“@tailrec”以及“import scala.annotation.tailrec”。

此外，关于替代实现的一些考虑：最简单的方法：

scala> time(println(1 to 9999999 reduceLeft (_+_)))
-2014260032
640.0 msecs

经过多次运行，平均而言速度较慢。它也不正确，因为它只适用于Int。正确的代码：

scala> time(println((1 to 9999999 foldLeft 0L)(_+_)))
49999995000000
797.0 msecs

这里运行的速度更慢了。老实说，我本来没想到它会跑得比递归版本还慢，但每次迭代都要调用传递的函数。一旦你考虑到这一点，与递归版本相比，这是一个相当不错的时间。