爲什麼我的Scala尾遞歸比while循環更快？

Question

這裏有兩個解決方案在Cay Horstmann的Scala中練習4.9爲Impatient：「編寫一個函數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版本通常只會執行1次或2次測試，這是由於else結構。 （NB逆轉我執行這兩種方法的順序不會影響結果）。

Answer 1

測試結果

在爪哇1.6.22（減小陣列大小至20000000之後）我得到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（熱點）可以優化比你的第一個版本，這更好的專家，但我想這是因爲它是通過代碼以相同的路徑每次（而不是沿着if/else if路徑分支），所以可以更有效地內聯字節碼。

但請記住，這不是在Java 6中的情況。爲什麼一個while循環勝過另一個是JVM內部問題。令人高興的是，對於Scala程序員來說，從慣用尾遞歸產生的版本是JVM最新版本中速度更快的版本。

差異也可能發生在處理器級別。請參閱this question，它解釋了代碼如果包含不可預知的分支時代碼如何變慢。

Answer 2

這兩個構造不相同。特別是，在第一種情況下，您不需要任何跳轉（在x86上，您可以使用cmp和setle並添加，而不必使用cmp和jb和（如果您不跳轉）添加。不是跳躍比幾乎每個現代建築跳躍都快。

所以，如果你有一些代碼看起來像

if (a < b) x += 1 

在那裏你可以添加或者你可能跳代替，與

x += (a < b) 

（它纔有意義，用C/C++，其中1 =真，0 =假），後者趨於更快，因爲它可以變成更緊湊的彙編代碼。在斯卡拉/ Java的，你不能這樣做，但你可以做

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

其智能JVM應該認識是相同的X + =（一< B），其中有一個自由跳轉，機器代碼翻譯，通常比跳轉更快。一個更聰明的JVM會認識到，

if (a < b) x += 1 

是一樣的再次（因爲加零不會做任何事情）。

C/C++編譯器經常執行像這樣的優化。無法應用任何這些優化在JIT編譯器中並不是一個標誌;顯然它可以是1.7，但只有部分（即它不認識到加0與條件加1是一樣的，但它至少將x += if (a<b) 1 else 0轉換成快速機器碼）。

現在，這與尾遞歸或while循環本身沒有任何關係。通過尾遞歸，編寫if (a < b) 1 else 0表單更自然，但你也可以做;和while循環，你也可以做。恰巧，你選擇了一個表單來進行尾遞歸，另一個用於while循環，使得它看起來像遞歸與循環是變化，而不是兩種不同的方式來執行條件。