Dlaczego rekurencja rekina Scala jest szybsza niż pętla while?

Question

Oto dwa rozwiązania do wykonania 4.9 w Scali Cay Horstmanna dla Niecierpliwych: "Napisz funkcję lteqgt (wartości: Array [Int], v: Int), która zwraca potrójny zawierający wartości mniejsze niż v, równe v i większe niż v. " Jeden używa rekurencji ogona, drugi używa pętli while. Myślałem, że oba będą kompilować się do podobnego kodu bajtowego, ale pętla while jest wolniejsza niż rekursja ogona o czynnik prawie 2. Sugeruje to, że moja metoda while jest źle napisana.

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) 
    } 
} 

Dostosuj rozmiar bigArray zgodnie z rozmiarem sterty. Oto przykładowe dane wyjściowe:

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

Dlaczego ta metoda jest o wiele wolniejsza od metody tailrec? Naiwnie wersja tailrec wygląda na nieco wadę, ponieważ zawsze musi wykonywać 3 "jeśli" sprawdza dla każdej iteracji, podczas gdy wersja while często wykonuje tylko 1 lub 2 testy z powodu innej konstrukcji. (Uwaga: odwrócenie kolejności, w której wykonuję dwie metody, nie ma wpływu na wynik). Wynika

Answer 1

testu (po zmniejszeniu rozmiaru tablicy do 20000000)

Zgodnie Java 1.6.22 uzyskać 151 and 122 ms załadowczej rekursji i gdy pętla odpowiednio.

Pod Java 1.7.0 uzyskać 55 and 101 ms

Więc pod Java 6 chwilę pętli jest faktycznie szybszy; oba poprawiły wydajność w Javie 7, ale wersja rekurencyjna ogona wyprzedziła pętlę.

Wyjaśnienie

różnica Spektakl jest ze względu na fakt, że w pętli, to warunkowo dodać 1 do sumy, a dla rekursji zawsze dodać 1 lub 0. Dlatego nie są one równoważne. Równowartość podczas pętli do rekurencyjnej metody jest:

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) 
    } 

a to daje dokładnie ten sam czas wykonania metody rekurencyjnej (niezależnie od wersji Java).

Dyskusja

Nie jestem ekspertem, dlaczego Java 7 VM (HotSpot) można zoptymalizować ten lepszy niż pierwsza wersja, ale ja myślę, że to dlatego, że bierze tę samą ścieżkę za pomocą kodu za każdym razem (zamiast rozgałęziać się po ścieżkach if/else if), aby kod bajtowy mógł być lepiej zaznaczony.

Należy jednak pamiętać, że tak nie jest w Javie 6. Dlaczego jedna pętla while while przewyższa drugą, jest kwestią wewnętrznych elementów JVM. Szczęśliwie dla programisty Scala wersja wyprodukowana z idiomatycznej rekurencji ogona jest szybsza w najnowszej wersji JVM.

Różnica może również występować na poziomie procesora. Zobacz: this question, która wyjaśnia, jak kod zwalnia, jeśli zawiera nieprzewidywalne rozgałęzienia.

Answer 2

Te dwa konstrukty nie są identyczne. W szczególności, w pierwszym przypadku nie potrzebujesz żadnych skoków (na x86 możesz używać cmp i setle i dodawać, zamiast używać cmp i jb oraz (jeśli nie skaczesz) dodawać.Nieskrępowanie jest szybsze niż skakanie praktycznie we wszystkich nowoczesnych architekturach.

Tak więc, jeśli masz kod, który wygląda

if (a < b) x += 1 

gdzie może dodać lub może skok zamiast vs.

x += (a < b) 

(który ma sens tylko w C/C++, gdzie 1 = prawda i 0 = fałsz), ta ostatnia wydaje się być szybsza, ponieważ może zostać przekształcona w bardziej zwarty kod zespołu. W Scala/Java, nie można tego zrobić, ale może zrobić

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

której inteligentne JVM powinny uznać to samo co x + = (a < b), która ma jump-bezpłatny tłumaczenie kodu maszynowego, które zwykle jest szybsze niż przeskakiwanie. Jeszcze bardziej inteligentna maszyna JVM rozpoznałaby, że ponownie jest taka sama jak poprzednio (ponieważ dodanie zera nic nie daje).

Kompilatory C/C++ rutynowo wykonują takie optymalizacje. Nieumiejętność zastosowania żadnej z tych optymalizacji nie była oznaką przysługi kompilatora JIT; najwyraźniej może to być 1.7, ale tylko częściowo (tj. nie rozpoznaje, że dodanie zera jest takie samo jak warunkowe dodanie, ale przynajmniej przekształca x += if (a<b) 1 else 0 w szybki kod maszynowy).

Nic z tego nie ma nic wspólnego z rekurencją ogona lub pętlami per se. Przy rekurencji ogona bardziej naturalne jest pisanie formularza if (a < b) 1 else 0, ale możesz to zrobić; a także z pętlami while można również wykonać. Tak się złożyło, że wybrałeś jedną formę rekurencji ogona i drugą pętlę while, dzięki czemu wygląda ona tak, jakby rekurencja w porównaniu do pętli była zmianą zamiast dwóch różnych sposobów wykonywania warunków.