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

Question

这是在Cay Horstmann的Scala中针对不耐烦的练习4.9的两种解决方案:“编写一个函数lteqgt(values:Array [Int]，v:Int)，该函数返回一个三元组，其中包含小于v，等于v的值的计数，以及大于v。”一个使用尾部递归，另一个使用while循环。我以为两者都可以编译为相似的字节码，但是while循环比尾部递归慢了将近2倍。这向我表明我的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版本由于else构造通常只执行1或2个测试。 (注意，我执行这两种方法的顺序颠倒不影响结果)。

Answer 1

测试结果(将数组大小减小到20000000后)

在Java 1.6.22下，我分别获得了用于尾递归和while循环的151 and 122 ms。

在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最新版本中速度更快的版本。

差异也可能发生在处理器级别。请参阅 this question，它解释了如果代码包含不可预测的分支，代码将如何降低速度。