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

Question

一位朋友在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中更快地实现算法.谢谢.

Answer 1

首先,Scala只在你调用它时才优化尾调用-optimise.编辑:如果可以,Scala似乎总是优化尾调用递归,即使没有-optimise.

其次,Stream和Range是两个完全不同的事情.A Range有一个开头和一个结尾,它的投影只有一个计数器和一个结束.A 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

这还比较慢,在这里跑.老实说,我不会期望它运行得更慢,但每次调用都会调用正在传递的函数.一旦你考虑到这一点,与递归版本相比,这是一个非常好的时间.

Answer 2

Clojure的范围没有记忆,Scala的Stream确实如此.完全不同的数据结构具有完全不同的结果.Scala确实有一个非memoizing 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类似语义的unmemoized Range

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

Answer 3

我怀疑这是由于Clojure如何处理尾部优化.由于JVM本身不执行此优化(并且Clojure和Scala都在其上运行),因此Clojure通过recur关键字优化尾递归.来自Clojure网站:

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

编辑:Scala也优化尾调用,只要它们处于某种形式.但是,正如前面的链接所示,Scala只能在非常简单的情况下执行此操作:

实际上,这是Scala编译器的一项称为尾调用优化的功能.它优化了递归调用.但是,此功能仅适用于上述简单情况.例如,如果递归是间接的,则Scala无法优化尾调用,因为JVM指令集有限.

在没有实际编译和反编译代码以查看生成的JVM指令的情况下,我怀疑它不是那些简单的情况之一(正如迈克尔所说,由于必须a.tail在每个递归步骤上获取),因此Scala无法对其进行优化.

Answer 4

描述了你的这个例子,似乎这个类Stream(嗯......一些与之相关的匿名函数 - 忘记了它的名字,因为visualvm在我身上崩溃)占据了大部分堆.这与StreamScala 中的s泄漏内存这一事实有关- 请参阅Scala Trac#692.修复程序应在Scala 2.8中提供..编辑: 丹尼尔的评论正确地指出它与这个错误无关.这是因为" val ints指向Stream头,垃圾收集器无法收集任何东西"[ Daniel ].我发现这个错误报告中的评论很好,但与此问题相关.

在你的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(混合功能,OO和命令性)更多优化.不过我对Clojure不太熟悉.

希望这可以帮助 :)