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

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

Aquí está mi solución Java, que tarda 0.7 segundos en completarse 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" al Scala, que toma 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 lleva 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 mejoro el rendimiento? ¿Estoy haciendo algo mal? ¿O es Java mucho más rápido?

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

El problema es muy probablemente el uso de una forcomprensión en el método isEvenlyDivisible. Sustitución forpor un equivalentewhile bucle debería eliminar la diferencia de rendimiento con Java.

A diferencia de los forbucles de Java , las forcomprensiones de Scala son en realidad azúcar sintáctica para métodos de orden superior; en este caso, estás llamando al foreachmétodo en un Rangeobjeto. Scala'sfor es muy general, pero a veces conduce a un rendimiento doloroso.

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

Las discusiones recientes en la lista de correo indican que el equipo de Scala está trabajando para mejorar el forrendimiento 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á bucles Scala simples en el equivalente de whilebucles.
• Como una posible solución a más 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 se pueden fusionar en tiempo de ejecución en el código de bytes JVM óptimo, o en otro objetivo, como una GPU. El sistema es extensible, lo que permite transformaciones y DSL definidas por el usuario. Consulte las publicaciones y las notas del curso de Stanford . El código preliminar está disponible en Github, con un lanzamiento previsto para los próximos meses.

Como seguimiento, probé el indicador -optimize y reduje el tiempo de ejecución de 103 a 76 segundos, pero 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 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 ha aumentado 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 siguiente paso fue traducir lo anterior nuevamente a Java, pero Java no puede manejarlo y arroja un StackOverflowError con n alrededor de la marca 22000.

Luego me rasqué la cabeza por un momento y reemplacé el "while" con un poco más de recursión de la cola, lo que ahorra un par de líneas, corre 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 recursión de cola de Scala gana el día, pero me sorprende que algo tan simple como un bucle "for" (y el método "forall") se rompa esencialmente y tenga que ser reemplazado por "silbidos" poco elegantes y detallados, o recursión de cola . Gran parte de la razón por la que estoy probando Scala se debe a la sintaxis concisa, ¡pero no es bueno si mi código se ejecutará 100 veces más lento!

EDITAR : (eliminado)

EDITAR DE EDITAR : Las discrepancias anteriores entre tiempos de ejecución de 2.5 sy 0.7 s se debieron por completo a si se estaban utilizando las JVM de 32 o 64 bits. Scala desde la línea de comando usa lo que sea establecido por JAVA_HOME, mientras que Java usa 64 bits si está disponible independientemente. Los IDE tienen su propia configuración. Algunas medidas aquí: tiempos de ejecución de Scala en Eclipse

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

Esto se realiza mediante el uso de una excepción para salir del bucle. Lo mismo sucede si construye sus 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 returnen cuenta que las foosalidas en foo(que es lo que esperaría). Dado que la expresión entre corchetes es una función literal, que puede ver en la firma de loopeste, obliga al compilador a generar un retorno no local, es decir, lo returnobliga a salir foo, no solo al 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 falsees 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 lanzar y capturar una excepción, lo que causa bastante sobrecarga de GC.

Algunas formas de acelerar el forallmétodo que descubrí:

El original: 41,3 s

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

Preinstalación del 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}

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

Si bien 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 constantes de Rango en el ámbito más externo. O mejor, practíquelos como cadenas literales en Java.

nota al pie : Las matrices eran casi lo mismo que Range, pero curiosamente, el proxenetismo de un nuevo forallmétodo (que se muestra a continuación) resultó en una ejecución 24% más rápida en 64 bits y 8% más rápida en 32 bits. Cuando reduje el tamaño del cálculo al reducir 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 sea la causa, es importante cuando se opera bajo carga completa durante períodos prolongados.

Un proxeneta similar para List también resultó en un 10% de 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)  

Solo quería comentar para las personas que podrían perder la fe en Scala sobre temas como este que este tipo de problemas surgen en el desempeño de casi todos los lenguajes funcionales. Si está optimizando un pliegue en Haskell, a menudo tendrá que volver a escribirlo como un bucle recursivo optimizado para llamadas de cola, o de lo contrario tendrá que lidiar con problemas de rendimiento y memoria.

Sé que es lamentable 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 para Scala.

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

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

Pruebe el one-liner dado en la solución Scala para el Proyecto Euler

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