java - ¿Cómo optimizar las comprensiones y los bucles en Scala?

performance for-loop

Question

Entonces se supone que Scala es tan rápido como Java. Estoy revisando algunos problemas de Project Euler en Scala que abordo originalmente en Java. Específicamente, problema 5: "¿Cuál es el número positivo más pequeño que es uniformemente divisible por todos los números del 1 al 20?"

Aquí está mi solución Java, que tarda 0,7 segundos en completar en mi máquina:

public class P005_evenly_divisible implements Runnable{
final int t = 20;
public void run() {
int i = 10;
while(!isEvenlyDivisible(i, t)){
i += 2;
}
System.out.println(i);
}
boolean isEvenlyDivisible(int a, int b){
for (int i = 2; i <= b; i++) {
if (a % i != 0)
return false;
}
return true;
}
public static void main(String[] args) {
new P005_evenly_divisible().run();
}
}

Aquí está mi "traducción directa" a Scala, que demora 103 segundos (¡147 veces más!)

object P005_JavaStyle {
val t:Int = 20;
def run {
var i = 10
while(!isEvenlyDivisible(i,t))
i += 2
println(i)
}
def isEvenlyDivisible(a:Int, b:Int):Boolean = {
for (i <- 2 to b)
if (a % i != 0)
return false
return true
}
def main(args : Array[String]) {
run
}
}

Finalmente, aquí está mi intento de programación funcional, que demora 39 segundos (55 veces más)

object P005 extends App{
def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
println (find (2))
}

Usando Scala 2.9.0.1 en Windows 7 de 64 bits. ¿Cómo puedo mejorar el rendimiento? ¿Estoy haciendo algo mal? ¿O es Java mucho más rápido?

Answer 1

Algunas formas de acelerar el método forall que descubrí:

El original: 41.3 s

def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}

Pre-instanciar el rango, por lo que no creamos un nuevo rango cada vez: 9.0 s

val r = (1 to 20)
def isDivis(x:Int) = r forall {x % _ == 0}

Conversión a una lista en lugar de un rango: 4.8 s

val rl = (1 to 20).toList
def isDivis(x:Int) = rl forall {x % _ == 0}

Probé algunas otras colecciones, pero List fue el más rápido (aunque aún 7 veces más lento que si evitáramos por completo el Rango y la función de orden superior).

Aunque soy nuevo en Scala, supongo que el compilador podría implementar fácilmente una ganancia de rendimiento rápida y significativa simplemente reemplazando automáticamente los literales de rango en los métodos (como arriba) con las constantes de rango en el alcance más externo. O mejor, internarlos como literales de cadenas en Java.

nota al pie : las matrices eran casi lo mismo que Rango, pero curiosamente, el proxenetismo de un nuevo método de forall (que se muestra a continuación) dio como resultado una ejecución un 24% más rápida en 64 bits y un 8% más rápido en 32 bits. Cuando reduje el tamaño del cálculo reduciendo el número de factores de 20 a 15, la diferencia desapareció, por lo que tal vez sea un efecto de recolección de basura. Cualquiera que sea la causa, es significativo cuando se opera a plena carga durante períodos prolongados.

Un proxeneta similar para List también resultó en un 10% mejor rendimiento.

 val ra = (1 to 20).toArray
def isDivis(x:Int) = ra forall2 {x % _ == 0}
case class PimpedSeq[A](s: IndexedSeq[A]) {
def forall2 (p: A => Boolean): Boolean = {
var i = 0
while (i < s.length) {
if (!p(s(i))) return false
i += 1
}
true
}
}
implicit def arrayToPimpedSeq[A](in: Array[A]): PimpedSeq[A] = PimpedSeq(in)

Answer 2

Como seguimiento, probé la bandera -optimize y redujo el tiempo de ejecución de 103 a 76 segundos, pero eso todavía es 107 veces más lento que Java o un ciclo while.

Luego estaba mirando la versión "funcional":

object P005 extends App{
def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
println (find (2))
}

y tratando de descubrir cómo deshacerse del "forall" de una manera concisa. Fallé miserablemente y se me ocurrió

object P005_V2 extends App {
def isDivis(x:Int):Boolean = {
var i = 1
while(i <= 20) {
if (x % i != 0) return false
i += 1
}
return true
}
def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
println (find (2))
}

por lo que mi astuta solución de 5 líneas se ha baloonado a 12 líneas. Sin embargo, esta versión se ejecuta en 0.71 segundos , la misma velocidad que la versión original de Java, y 56 veces más rápido que la versión anterior usando "forall" (40.2 s). (vea EDITAR a continuación para saber por qué esto es más rápido que Java)

Obviamente, mi próximo paso fue traducir lo anterior a Java, pero Java no puede manejarlo y arroja un Error con n alrededor de la marca 22000.

Luego me rasqué la cabeza un poco y reemplacé el "mientras" con un poco más de recursividad de cola, lo que ahorra un par de líneas, se ejecuta igual de rápido, pero seamos sinceros, es más confuso de leer:

object P005_V3 extends App {
def isDivis(x:Int, i:Int):Boolean =
if(i > 20) true
else if(x % i != 0) false
else isDivis(x, i+1)
def find(n:Int):Int = if (isDivis(n, 2)) n else find (n+2)
println (find (2))
}

Entonces la recursividad de la cola de Scala gana el día, pero estoy sorprendido de que algo tan simple como un bucle "for" (y el método "forall") esté esencialmente roto y deba ser reemplazado por "whiles" poco detallados y prolijos, o recurrencia de la cola . Mucho del motivo por el que estoy intentando con Scala es por la sintaxis concisa, ¡pero no sirve si mi código va a correr 100 veces más lento!

EDITAR : (eliminado)

EDITAR EDITAR : Las antiguas discrepancias entre los tiempos de ejecución de 2.5s y 0.7s se debían enteramente a si se estaban utilizando las JVM de 32 bits o de 64 bits. Scala desde la línea de comandos usa lo que JAVA_HOME establece, mientras que Java usa 64 bits si está disponible. Los IDEs tienen su propia configuración. Algunas medidas aquí: tiempos de ejecución de Scala en Eclipse

Answer 3

El problema en este caso particular es que regresas desde dentro de la expresión for. Eso a su vez se traduce en un lanzamiento de una NonLocalReturnException, que se captura en el método adjunto. El optimizador puede eliminar el foreach pero aún no puede eliminar el lanzamiento / captura. Y lanzar / atrapar es costoso. Pero dado que dichos retornos anidados son raros en los programas de Scala, el optimizador aún no se ocupó de este caso. Se está trabajando para mejorar el optimizador que, con suerte, resolverá este problema pronto.

Answer 4

El problema es muy probable que el uso de a for comprensión en el método sea isEvenlyDivisible . Sustituir por un ciclo while equivalente debería eliminar la diferencia de rendimiento con Java.

A diferencia de los bucles for de Java, los de Scala for comprensiones son en realidad azúcar sintáctico para métodos de orden superior; en este caso, llama al método foreach en un objeto Range . El de Scala es muy general, pero a veces conduce a un rendimiento doloroso.

Es posible que desee probar el indicador -optimize en la versión 2.9 de Scala. El rendimiento observado puede depender de la JVM particular en uso, y el optimizador JIT tiene suficiente tiempo de "calentamiento" para identificar y optimizar puntos calientes.

Las discusiones recientes en la lista de correo indican que el equipo de Scala está trabajando para mejorar el rendimiento en casos simples:

• http://groups.google.com/group/scala-user/browse_thread/thread/86adb44d72ef4498
• http://groups.google.com/group/scala-language/browse_thread/thread/94740a10205dddd2

Aquí está el problema en el rastreador de errores: https://issues.scala-lang.org/browse/SI-4633

Actualización 5/28 :

• Como solución a corto plazo, el complemento ScalaCL (alfa) transformará los simples bucles de Scala en el equivalente de los bucles while.
• Como una solución potencial a largo plazo, los equipos de EPFL y Stanford están colaborando en un proyecto que permite la compilación en tiempo de ejecución de Scala "virtual" para un rendimiento muy alto. Por ejemplo, múltiples bucles funcionales idiomáticos pueden fusionarse en tiempo de ejecución en un bytecode de JVM óptimo, o en otro objetivo, como una GPU. El sistema es extensible, permitiendo DSL y transformaciones definidas por el usuario. Consulte las publications y notas del curso de Stanford. El código preliminar está disponible en Github, con un lanzamiento previsto en los próximos meses.

Answer 5

La respuesta sobre la comprensión es correcta, pero no es toda la historia. Debe tener en cuenta que el uso de return en isEvenlyDivisible no es gratuito. El uso de return dentro de for , obliga al compilador de scala a generar un retorno no local (es decir, a regresar fuera de su función).

Esto se hace mediante el uso de una excepción para salir del ciclo. Lo mismo ocurre si construyes tus propias abstracciones de control, por ejemplo:

def loop[T](times: Int, default: T)(body: ()=>T) : T = {
var count = 0
var result: T = default
while(count < times) {
result = body()
count += 1
}
result
}
def foo() : Int= {
loop(5, 0) {
println("Hi")
return 5
}
}
foo()

Esto imprime "Hola" solo una vez.

Tenga en cuenta que el return en foo sale de foo (que es lo que cabría esperar). Como la expresión entre corchetes es una función literal, que puede verse en la firma del loop esto obliga al compilador a generar un retorno no local, es decir, el return obliga a salir de foo , no solo del body .

En Java (es decir, la JVM), la única forma de implementar dicho comportamiento es lanzar una excepción.

Volviendo a isEvenlyDivisible :

def isEvenlyDivisible(a:Int, b:Int):Boolean = {
for (i <- 2 to b)
if (a % i != 0) return false
return true
}

El if (a % i != 0) return false es un literal de función que tiene un retorno, por lo que cada vez que se golpea el retorno, el tiempo de ejecución tiene que arrojarse y atrapar una excepción, lo que causa un poco de sobrecarga del GC.

Answer 6

Prueba el one-liner dado en la solución Scala para Project Euler

El tiempo otorgado es al menos más rápido que el tuyo, aunque está lejos del ciclo while ... :)

Answer 7

Solo quería hacer un comentario para las personas que podrían perder la fe en Scala por cuestiones como esta, que surgen este tipo de problemas en el rendimiento de casi todos los lenguajes funcionales. Si está optimizando un doblez en Haskell, a menudo tendrá que volver a escribirlo como un bucle recursivo de llamada de cola optimizada, o de lo contrario tendrá que lidiar con problemas de rendimiento y memoria.

Sé que es desafortunado que los FP aún no estén optimizados hasta el punto en que no tengamos que pensar en cosas como esta, pero esto no es en absoluto un problema particular de Scala.

Answer 8

Ya se han discutido los problemas específicos de Scala, pero el principal problema es que usar un algoritmo de fuerza bruta no es muy bueno. Considere esto (mucho más rápido que el código original de Java):

def gcd(a: Int, b: Int): Int = {
if (a == 0)
b
else
gcd(b % a, a)
}
print (1 to 20 reduce ((a, b) => {
a / gcd(a, b) * b
}))