Perché la mia Scala ricorsione della coda è più veloce del ciclo while?

Question

Ecco due soluzioni per l'esercizio 4.9 in Scala per impaziente di Cay Horstmann: "Scrivi una funzione lteqgt (valori: Array [Int], v: Int) che restituisce una tripla contenente i conteggi di valori inferiori a v, uguale a v e maggiore di v. " Uno usa la ricorsione di coda, l'altro usa un ciclo di tempo. Ho pensato che entrambi sarebbero stati compilati con un bytecode simile, ma il ciclo while è più lento della ricorsione della coda di un fattore di quasi 2. Questo mi suggerisce che il mio metodo while è scritto male.

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

Regolare la dimensione di bigArray in base alle dimensioni dell'heap. Ecco alcuni esempi di output:

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

Perché il metodo while è molto più lento del tailrec? Ingenuamente la versione di tailrec sembra essere leggermente svantaggiata, poiché deve sempre eseguire 3 "se" per ogni iterazione, mentre la versione while spesso esegue solo 1 o 2 test a causa del costrutto else. (NB invertendo l'ordine che eseguo i due metodi non influisce sul risultato).

Answer 1

Risultati delle prove (dopo aver ridotto dimensione dell'array a 20000000)

Sotto Java 1.6.22 ottengo 151 and 122 ms tail-ricorsione e rispettivamente ciclo while.

Sotto Java 1.7.0 ottengo 55 and 101 ms

Così sotto Java 6 il tuo ciclo while è in realtà più veloce; entrambi sono migliorati nelle prestazioni con Java 7, ma la versione ricorsiva della coda ha superato il ciclo.

Spiegazione

differenza La performance è dovuta al fatto che nel vostro ciclo, è condizionatamente aggiunge 1 ai totali, mentre per la ricorsione si aggiunge sempre 1 o 0. Quindi non sono equivalenti. Il ciclo while equivalente al metodo ricorsivo è:

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

e questo dà esattamente lo stesso tempo di esecuzione come il metodo ricorsivo (indipendentemente dalla versione Java).

Discussione

Io non sono un esperto sul perché il Java 7 VM (hotspot) in grado di ottimizzare meglio di tua prima versione, ma direi che sia perché sta prendendo lo stesso percorso attraverso il codice ogni volta (piuttosto che ramificarsi lungo i percorsi if/else if), così il bytecode può essere sottolineato in modo più efficiente.

Ma ricorda che questo non è il caso in Java 6. Perché un ciclo while supera l'altro è una questione di interni JVM. Fortunatamente per il programmatore di Scala, la versione prodotta dalla coda-ricorsione idiomatica è la più veloce nell'ultima versione della JVM.

La differenza potrebbe anche verificarsi a livello di processore. Vedere this question, che spiega come il codice rallenta se contiene ramificazioni imprevedibili.

Answer 2

I due costrutti non sono identici. In particolare, nel primo caso non hai bisogno di salti (su x86, puoi usare cmp e setle e aggiungere, invece di dover usare cmp e jb e (se non salti) aggiungi.Non saltare è più veloce che saltare praticamente su ogni architettura moderna.

Quindi, se si dispone di codice che sembra

if (a < b) x += 1 

dove si può aggiungere o si può salto, invece, contro

x += (a < b) 

(che ha senso solo in C/C++ dove 1 = true e 0 = false), quest'ultimo tende ad essere più veloce in quanto può essere trasformato in un codice di assembly più compatto. In Scala/Java, non si può fare questo, ma è possibile fare

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

che una smart JVM dovrebbe riconoscere è la stessa di x + = (a < b), che dispone di un free-jump traduzione del codice macchina, che di solito è più veloce del salto. Una ancora più intelligente JVM sarebbe riconoscere che

if (a < b) x += 1 

è lo stesso ancora una volta (perché l'aggiunta di zero non fa nulla).

I compilatori C/C++ eseguono regolarmente ottimizzazioni come questa. Non essere in grado di applicare nessuna di queste ottimizzazioni non era un segno nel favore del compilatore JIT; a quanto pare può essere in 1.7, ma solo parzialmente (cioè non riconosce che l'aggiunta di zero è la stessa di una aggiunta condizionale, ma almeno converte x += if (a<b) 1 else 0 in codice macchina veloce).

Ora, nulla di tutto questo ha nulla a che fare con la ricorsione della coda o mentre i loop di per sé. Con la ricorsione della coda è più naturale scrivere il modulo if (a < b) 1 else 0, ma puoi farlo entrambi; e con cicli while puoi anche fare entrambi. È successo che hai scelto un modulo per la ricorsione della coda e l'altro per il ciclo while, facendo sembrare che la ricorsione e il ciclo fossero il cambiamento, invece dei due diversi modi di eseguire i condizionali.