为什么我的Scala尾递归比while循环更快？

Question

这里有两个解决方案,在Cay Horstmann的Scala for the Impatient中运用4.9:"写一个函数lteqgt(values:Array [Int],v:Int),它返回一个包含小于v的值的三元组,等于v,并且大于v." 一个使用尾递归,另一个使用while循环.我认为两者都会编译成类似的字节码,但是while循环比尾递归慢了近两倍.这告诉我,我的while方法编写得很糟糕.

import scala.annotation.tailrec
import scala.util.Random
object PerformanceTest {

  def main(args: Array[String]): Unit = {
    val bigArray:Array[Int] = fillArray(new Array[Int](100000000))
    println(time(lteqgt(bigArray, 25)))
    println(time(lteqgt2(bigArray, 25)))
  }

  def time[T](block : => T):T = {
    val start = System.nanoTime : Double
    val result = block
    val end = System.nanoTime : Double
    println("Time = " + (end - start) / 1000000.0 + " millis")
    result
  }

  @tailrec def fillArray(a:Array[Int], pos:Int=0):Array[Int] = {
    if (pos == a.length)
      a
    else {
      a(pos) = Random.nextInt(50)
      fillArray(a, pos+1)
    }
  }

  @tailrec def lteqgt(values: Array[Int], v:Int, lt:Int=0, eq:Int=0, gt:Int=0, pos:Int=0):(Int, Int, Int) = {
    if (pos == values.length)
      (lt, eq, gt)
    else
      lteqgt(values, v, lt + (if (values(pos) < v) 1 else 0), eq + (if (values(pos) == v) 1 else 0), gt + (if (values(pos) > v) 1 else 0), pos+1) 
  }

  def lteqgt2(values:Array[Int], v:Int):(Int, Int, Int) = {
    var lt = 0
    var eq = 0
    var gt = 0
    var pos = 0
    val limit = values.length
    while (pos < limit) {
      if (values(pos) > v)
        gt += 1
      else if (values(pos) < v)
        lt += 1
      else
        eq += 1
      pos += 1
    }
    (lt, eq, gt)
  }
}

根据堆大小调整bigArray的大小.这是一些示例输出:

Time = 245.110899 millis
(50004367,2003090,47992543)
Time = 465.836894 millis
(50004367,2003090,47992543)

为什么while方法比tailrec慢得多？天真的tailrec版本看起来略显不利,因为它必须始终对每次迭代执行3"if"检查,而while版本通常仅执行1或2次测试,因为else构造.(NB逆转我执行两种方法的顺序不会影响结果).

Answer 1

测试结果(将阵列大小减小到20000000后)

在Java下1.6.22我分别得到151 and 122 ms尾递归和while循环.

在Java下1.7.0我得到 55 and 101 ms

所以在Java 6下你的while循环实际上更快; 两者都在Java 7下的性能有所提升,但尾递归版本已经超越了循环.

说明

性能差异是由于在循环中有条件地将总数加1,而对于递归,您总是添加1或0.因此它们不等同.递归方法的等效while循环是:

  def lteqgt2(values:Array[Int], v:Int):(Int, Int, Int) = {
    var lt = 0
    var eq = 0
    var gt = 0
    var pos = 0
    val limit = values.length
    while (pos < limit) {
      gt += (if (values(pos) > v) 1 else 0)
      lt += (if (values(pos) < v) 1 else 0)
      eq += (if (values(pos) == v) 1 else 0)
      pos += 1
    }
    (lt, eq, gt)
  }

这给出了与递归方法完全相同的执行时间(无论Java版本如何).

讨论

我不是专家为什么Java 7 VM(HotSpot)可以比第一个版本更好地优化它,但我猜它是因为它每次都采用相同的路径(而不是沿if/ else if路径分支) ,因此字节码可以更有效地内联.

但请记住,在Java 6中并非如此.为什么一个while循环优于另一个循环是JVM内部的问题.对于Scala程序员来说,令人高兴的是,通过惯用尾递归生成的版本是最新版本JVM中更快的版本.

差异也可能发生在处理器级别.请参阅此问题,该问题解释了如果代码包含不可预测的分支,代码将如何变慢.

Answer 2

这两种结构并不相同.特别是,在第一种情况下你不需要任何跳转(在x86上,你可以使用cmp和setle并添加,而不必使用cmp和jb以及(如果你不跳转)添加.不跳跃更快而不是跳过几乎每一个现代建筑.

所以,如果你有代码看起来像

if (a < b) x += 1

在哪里你可以添加或者你可以跳,而不是

x += (a < b)

(只有在C/C++中才有意义,其中1 =真,0 =假),后者往往更快,因为它可以变成更紧凑的汇编代码.在Scala/Java中,你不能这样做,但你可以这样做

x += if (a < b) 1 else 0

智能JVM应该识别的与x + =(a <b)相同,它具有无跳机器代码转换,通常比跳转更快.更聪明的JVM会认识到这一点

if (a < b) x += 1

再次是相同的(因为添加零不会做任何事情).

C/C++编译器通常会执行这样的优化.无法应用任何这些优化并不是JIT编译器的优势; 显然它可以是1.7,但只是部分(即它不认识到添加零与条件添加一个相同,但它至少会转换x += if (a<b) 1 else 0为快速机器代码).

现在,这些都与尾递归或循环本身无关.使用尾递归,编写if (a < b) 1 else 0表单更自然,但你可以做任何一种; 和while循环你也可以做任何一个.事实上,您选择了一个用于尾递归的表单,另一个用于while循环,使得它看起来像递归与循环是更改而不是两种不同的方式来执行条件.