为什么我的Scala尾recursion比while循环更快？
这里有两个解决scheme在Cay Horstmann的Scala中为Impatient执行4.9：“编写一个函数lteqgt（values：Array [Int]，v：Int），返回一个三元组，它包含小于v的值，等于v，大于v“。 一个使用尾recursion，另一个使用while循环。 我认为两者都会编译成相似的字节码，但是while循环比尾recursion要慢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版本通常只会执行1次或2次testing，因为else结构。 （注意颠倒顺序我执行这两个方法不会影响结果）。
testing结果 （将数组大小减less到20000000之后）
在Java 1.6.22我分别获得了尾recursion和while循环的151 and 122 ms 。
在Java 1.7.0我得到55 and 101 ms
所以在Java 6下，while循环实际上更快; 在Java 7下性能都有所提高，但是尾recursion版本已经超越了循环。
说明
性能的差异是因为在你的循环中，你有条件地加1总数，而recursion你总是添加1或0.所以他们是不相同的。 recursion方法的等效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) }
这与recursion方法（无论Java版本）是否具有完全相同的执行时间。
讨论
我不是专家，为什么Java 7虚拟机（HotSpot）可以比你的第一个版本更好地优化这个，但我猜测这是因为它每次都通过代码采取相同的path（而不是沿着if / else ifpath），所以字节码可以更有效地内联。
但请记住，在Java 6中情况并非如此。为什么一个while循环胜过另一个是JVM内部问题。 令人高兴的是，对于Scala程序员来说，从惯用的尾recursion产生的版本在JVM的最新版本中是更快的。
这种差异也可能发生在处理器级别。 看到这个问题 ，它解释了如果代码包含不可预知的分支，代码变慢。
这两个结构是不一样的。 特别是在第一种情况下，你不需要任何跳转（在x86上，你可以使用cmp和setle来添加，而不必使用cmp和jb和（如果你不跳的话）添加。几乎每一个现代build筑都跳跃起来。
所以，如果你有看起来像的代码
if (a < b) x += 1
在哪里你可以添加或者你可以跳转，而不是
x += (a < b)
（只有在C / C ++中有意义，其中1 = true且0 = false），后者趋于更快，因为它可以变成更紧凑的汇编代码。 在Scala / Java中，你不能做到这一点，但你可以做到
x += if (a < b) 1 else 0
一个智能的JVM应该识别的是一样的x + =（a <b），它有一个无跳转的机器代码转换，通常比跳转快。 一个更聪明的JVM会认识到这一点
if (a < b) x += 1
是一样的又一次（因为加零不会做任何事情）。
C / C ++编译器经常执行像这样的优化。 无法应用任何这些优化在JIT编译器中并不是一个标志; 显然它可以从1.7开始，但只有部分（即它不认识到加0与条件加1是一样的，但它至less将x += if (a<b) 1 else 0转换成快速机器码）。
现在，这和尾recursion或while循环本身没有任何关系。 使用尾recursion更自然地写if (a < b) 1 else 0forms，但是你也可以做; 和while循环，你也可以做。 恰巧，你select了一种forms的尾recursion，另一种为while循环，使得它看起来像recursion与循环是变化，而不是两种不同的方式来做条件。
