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

loops tail-recursion

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 que contiene los recuentos de valores menores que v, igual a v, y mayor 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í hay algunos resultados de muestra:

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

¿Por qué el método while es mucho 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).

Answer 1

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.

Entonces, si tienes un código que se parece a

if (a < b) x += 1

donde puedes agregar o puedes saltar en cambio, vs.

x += (a < b)

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

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

lo que una JVM inteligente debería reconocer es lo mismo que x + = (a <b), que tiene una traducción de código máquina sin salto, que generalmente es más rápido que saltar. Una JVM aún más inteligente reconocería que

if (a < b) x += 1

es lo mismo una vez más (porque agregar 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 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 máquina rápida código).

Ahora, nada de esto tiene nada que ver con la recursividad de la cola o los ciclos en sí. Con la recursividad de cola es más natural escribir la forma if (a < b) 1 else 0 , pero puede hacer cualquiera; 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.

Answer 2

Resultados de la prueba (después de reducir el tamaño de la matriz a 20000000)

En Java 1.6.22 obtengo 151 and 122 ms para la recursividad de cola y while-loop, respectivamente.

En Java 1.7.0 obtengo 55 and 101 ms

Entonces, en Java 6 su while-loop 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

La diferencia de rendimiento se debe al hecho de que en su ciclo, agrega de manera condicional 1 a los totales, mientras que para la recursión siempre agrega 1 o 0. Por lo tanto, no son equivalentes. El ciclo 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 que el método recursivo (independientemente de la versión de Java).

Discusión

No soy un experto en por qué el Java 7 VM (HotSpot) puede optimizar esto 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 del if / else if paths), 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 ciclo while 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. Vea esta pregunta , que explica cómo el código se ralentiza si contiene ramificaciones impredecibles.