¿Por qué mi Scala tail-recursión es más rápida que el ciclo while?

Question

Aquí hay dos soluciones para el ejercicio 4.9 en Scala para el impaciente de Cay Horstmann: "Escribe una función lteqgt (valores: Array [Int], v: Int) que devuelve un triple conteniendo los recuentos de valores menores que v, igual a v y más grande que v. " Uno usa recursividad de cola, el otro usa un ciclo while. Pensé que ambos compilarían un bytecode similar pero el ciclo while es más lento que la recursión de cola en un factor de casi 2. Esto me sugiere que mi método while está mal escrito.

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

Ajuste el tamaño de bigArray de acuerdo con su tamaño de almacenamiento dinámico. Aquí está un ejemplo de salida:

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

¿Por qué es el método mientras tanto más lento que el tailrec? Ingenuamente, la versión tailrec parece estar en una ligera desventaja, ya que siempre debe realizar 3 "si" para cada iteración, mientras que la versión while a menudo solo realizará 1 o 2 pruebas debido a la construcción else. (Nota: al invertir el orden en que realizo los dos métodos, no afecta el resultado). resulta

Answer 1

Prueba (después de la reducción de tamaño de la matriz a 20000000)

Bajo Java 1.6.22 llego 151 and 122 ms para tail-recursión y bucle while respectivamente.

Bajo Java 1.7.0 consigo 55 and 101 ms

Así, bajo el Java 6 bucle while es realmente más rápido; ambos han mejorado en rendimiento bajo Java 7, pero la versión recursiva de cola ha superado al bucle.

Explicación

diferencia El rendimiento se debe al hecho de que en su bucle, condicionalmente agrega 1 a los totales, mientras que para la recursividad siempre se agrega 1 o 0. Por tanto, no son equivalentes. El bucle while equivalente a su método recursivo es:

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

y esto da exactamente el mismo tiempo de ejecución como el método recursivo (independientemente de la versión de Java).

Discusión

No soy un experto en la razón por la Java 7 VM (HotSpot) puede optimizar esta mejor que su primera versión, pero supongo que es porque está tomando el mismo camino a través del código cada vez (en lugar de ramificarse a lo largo de las rutas if/else if), por lo que el bytecode se puede insertar de manera más eficiente.

Pero recuerde que este no es el caso en Java 6. Por qué un while-loop supera al otro es una cuestión de internos de JVM. Afortunadamente para el programador de Scala, la versión producida a partir de la repetición de cola idiomática es la más rápida en la última versión de la JVM.

La diferencia también podría estar ocurriendo en el nivel del procesador. Consulte this question, que explica cómo se ralentiza el código si contiene ramificaciones impredecibles.

Answer 2

Las dos construcciones no son idénticas. En particular, en el primer caso no necesita saltos (en x86, puede usar cmp y setle y agregar, en lugar de tener que usar cmp y jb y (si no lo hace) agregar.No saltar es más rápido que saltar en casi todas las arquitecturas modernas.

Por lo tanto, si usted tiene código que se parece a

if (a < b) x += 1 

donde puede agregar o que puede salto en cambio, frente a

x += (a < b) 

(que sólo tiene sentido en C/C++ donde 1 = verdadero y 0 = falso), este último tiende a ser más rápido ya que se puede convertir en un código de ensamblaje más compacto. En Scala/Java, no se puede hacer esto, pero usted puede hacer

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

el que una JVM inteligente debe reconocer es lo mismo que x + = (a < b), que tiene una caída libre traducción automática de códigos, que generalmente es más rápida que saltar. Una JVM aún más inteligente reconocería que

if (a < b) x += 1 

es lo mismo una vez más (debido a la adición de cero no hace nada).

Los compiladores C/C++ rutinariamente realizan optimizaciones como esta. Ser incapaz de aplicar cualquiera de estas optimizaciones no era una marca en favor del compilador de JIT; aparentemente puede hacerlo a partir de 1.7, pero solo parcialmente (es decir, no reconoce que agregar cero es lo mismo que agregar uno condicional, pero al menos convierte x += if (a<b) 1 else 0 en código de máquina rápida).

Ahora, nada de esto tiene algo que ver con la recursividad de cola o los ciclos en sí. Con recursividad de cola es más natural escribir el formulario if (a < b) 1 else 0, pero puede hacerlo; y con while loops también puedes hacer cualquiera. Dio la casualidad de que eligió un formulario para la recursividad de la cola y el otro para el ciclo while, lo que hace que parezca que la recursividad vs. el bucle era el cambio en lugar de las dos formas diferentes de hacer los condicionales.