なぜ私のScalaのテール再帰はwhileループより速いのですか？

Question

Cay Horstmann's ImpalaのScalaで4.9を試してみるには、次の2つの解決策があります：v v未満の値のカウントを含むトリプルを返す関数lteqgt（values：Array [Int]、v：Int） 、およびvより大きい。 1つはテール再帰を使用し、もう1つはwhileループを使用します。私は両方とも同様のバイトコードにコンパイルすると思ったが、whileループはtailの再帰よりも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) 

なぜテールレックより遅いのですか？純粋にテールレックバージョンはわずかな欠点があるように見えます。なぜなら、すべての繰り返しに対して3つの "if"チェックを常に実行しなければならないのに対して、whileバージョンはelse構造のために1つまたは2つのテストしか実行しないことが多いからです。 （NBは2つの方法を実行する順序を逆にしても結果には影響しません）。

Answer 1

テストは、Java 1.6.22下

（20000000の配列のサイズを低減した後に）私は末尾再帰ため151 and 122 msを取得し、whileループをそれぞれもたらします。私はJava 6のあなたのwhileループの下55 and 101 ms

だから、取得するJava 1.7.0の下

は、実際に高速です。どちらもJava 7ではパフォーマンスが向上していますが、テール再帰バージョンではループを凌駕しています。

説明

は、パフォーマンスの違いは、再帰のためにあなたがいつもそこで彼らは同じではありません1または0を追加しながら、あなたのループの中で、あなたは条件付きで、合計に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) { 
     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バージョンの）とまったく同じ実行時間を与える：あなたの再帰的な方法にwhileループと等価です。

ディスカッション

私は、Java 7 VM（ホットスポット）があなたの最初のバージョンよりも、この優れたを最適化することができる理由の専門家でないんだけど、私はそれがコードを同じパスを取っているので、それはだと思うだろう（if/else ifパスに沿って分岐するのではなく）毎回、バイトコードをより効率的にインライン化することができます。

しかし、これはJava 6では当てはまりません.1つのwhileループが他のものより優れているのは、JVM内部の問題です。 Scalaプログラマにとってうれしいことに、慣用的なtail-recursionから生成されたバージョンは、最新バージョンのJVMでより高速なものです。

この違いは、プロセッサレベルでも発生している可能性があります。 this questionを参照してください。予測できない分岐が含まれているとコードがどのように遅くなるのかについて説明しています。

Answer 2

2つの構築物は同一ではない。特に、最初の場合、ジャンプは必要ありません（x86では、cmpとjbを使用する代わりにcmpとsetleとaddを使用し、ジャンプしない場合は追加できます）。ジャンプすることは、現代のアーキテクチャのほとんどすべてを飛び越すよりも速いです。だから、

、あなたが

あなた が追加したり、あなた が代わりにジャンプし、対のみCに理にかなって

x += (a < b) 

（かもしれ

if (a < b) x += 1 

ようなコードを持っている場合/ C++の場合、1 =真かつ0 =偽）、コンパクトなアセンブリコードに変換できるので、後者のほうが高速になる傾向があります。スカラ座/ Javaでは、あなたはこれを行うことはできませんが、あなたはスマートJVMを認識しなければならないん

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

はジャンプ・フリーを持っているのx + =（< b）は、同じであることができますマシンコードの変換は通常はジャンプより速いです。もっとスマートなJVMであれば、ゼロを追加することで何もしないので、

if (a < b) x += 1 

が同じことが分かります。

C/C++コンパイラは、このような最適化を日常的に実行します。これらの最適化を適用することができないということは、JITコンパイラにとって有利な点ではありませんでした。明らかにそれは1.7であるが、部分的にしかできない（すなわち、ゼロを加えることは条件付き加算と同じであることを認識しないが、少なくともx += if (a<b) 1 else 0を高速機械コードに変換する）。

ここでは、テール再帰またはwhileループ自体とは関係がありません。末尾再帰では、if (a < b) 1 else 0フォームを書くのが自然ですが、いずれかを行うことができます。 whileループでもどちらかを行うことができます。それはちょうどテール再帰のための1つのフォームとwhileループのためのもう一つのフォームを選んだので、再帰対ループのように見えるのは、条件を行う2つの異なる方法ではなく、変更でした。