Comment optimiser les for-compréhensions et les boucles dans Scala?

Donc, Scala est censé être aussi rapide que Java. Je revisite quelques problèmes de Project Euler dans Scala que j'ai abordés à l'origine en Java. Plus précisément problème 5: "Quel est le plus petit nombre positif qui est divisible également par tous les nombres de 1 à 20?"

Voici ma solution Java, qui prend 0,7 seconde pour se terminer sur ma machine:

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

Voici ma "traduction directe" en Scala, qui prend 103 secondes (147 fois plus longtemps!)

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

Enfin voici ma tentative de programmation fonctionnelle, qui prend 39 secondes (55 fois plus longtemps)

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

Utilisation de Scala 2.9.0.1 sous Windows 7 64 bits. Comment améliorer les performances? Est-ce que je fais quelque chose de mal? Ou Java est-il simplement beaucoup plus rapide?

Le problème dans ce cas particulier est que vous revenez de l'intérieur de l'expression for. Cela à son tour est traduit en un jet d'une NonLocalReturnException, qui est interceptée à la méthode englobante. L'optimiseur peut éliminer le foreach mais ne peut pas encore éliminer le lancer / attraper. Et lancer / attraper coûte cher. Mais comme ces retours imbriqués sont rares dans les programmes Scala, l'optimiseur n'a pas encore résolu ce cas. Des travaux sont en cours pour améliorer l'optimiseur qui, espérons-le, résoudra bientôt ce problème.

Le problème est très probablement l'utilisation d'une forcompréhension dans la méthode isEvenlyDivisible. Le remplacement forpar une whileboucle équivalente devrait éliminer la différence de performances avec Java.

Contrairement aux forboucles de Java , les forcompréhensions de Scala sont en fait du sucre syntaxique pour les méthodes d'ordre supérieur; dans ce cas, vous appelez la foreachméthode sur un Rangeobjet. Scala forest très général, mais conduit parfois à des performances douloureuses.

Vous voudrez peut-être essayer l' -optimizeindicateur dans la version 2.9 de Scala. Les performances observées peuvent dépendre de la JVM particulière utilisée et de l'optimiseur JIT ayant suffisamment de temps de "préchauffage" pour identifier et optimiser les points chauds.

Des discussions récentes sur la liste de diffusion indiquent que l'équipe Scala travaille sur l'amélioration des forperformances dans des cas simples:

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

Voici le problème dans le bug tracker: https://issues.scala-lang.org/browse/SI-4633

Mise à jour du 28/05 :

• En tant que solution à court terme, le plugin ScalaCL (alpha) transformera de simples boucles Scala en l'équivalent de whileboucles.
• En tant que solution potentielle à plus long terme, les équipes de l'EPFL et de Stanford collaborent sur un projet permettant la compilation runtime de Scala "virtuelle" pour de très hautes performances. Par exemple, plusieurs boucles fonctionnelles idiomatiques peuvent être fusionnées au moment de l'exécution dans le bytecode JVM optimal, ou vers une autre cible telle qu'un GPU. Le système est extensible, permettant des DSL et des transformations définis par l'utilisateur. Consultez les publications et les notes de cours de Stanford . Le code préliminaire est disponible sur Github, avec une version prévue dans les mois à venir.

En guise de suivi, j'ai essayé l'indicateur -optimize et cela a réduit le temps de fonctionnement de 103 à 76 secondes, mais c'est toujours 107 fois plus lent que Java ou une boucle while.

Puis je regardais la version "fonctionnelle":

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

et essayer de comprendre comment se débarrasser du "forall" d'une manière concise. J'ai échoué lamentablement et j'ai trouvé

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

grâce à quoi ma solution astucieuse à 5 lignes est passée à 12 lignes. Cependant, cette version tourne en 0,71 seconde , la même vitesse que la version originale de Java, et 56 fois plus rapide que la version ci-dessus en utilisant "forall" (40,2 s)! (voir EDIT ci-dessous pour savoir pourquoi c'est plus rapide que Java)

De toute évidence, ma prochaine étape était de traduire ce qui précède en Java, mais Java ne peut pas le gérer et lance une StackOverflowError avec n autour de la marque 22000.

Je me suis ensuite gratté la tête un peu et j'ai remplacé le "while" par un peu plus de récursivité de queue, ce qui économise quelques lignes, fonctionne tout aussi vite, mais avouons-le, c'est plus déroutant à lire:

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

Donc, la récursion de queue de Scala l'emporte, mais je suis surpris que quelque chose d'aussi simple qu'une boucle «for» (et la méthode «forall») soit essentiellement interrompue et doive être remplacée par des «whiles» inélégants et verbeux, ou récursivité de queue . Une grande partie de la raison pour laquelle j'essaye Scala est à cause de la syntaxe concise, mais ce n'est pas bon si mon code va fonctionner 100 fois plus lentement!

EDIT : (supprimé)

MODIFICATION DE L'ÉDIT : Les anciennes divergences entre les durées d'exécution de 2,5 s et 0,7 s étaient entièrement dues à l'utilisation des JVM 32 bits ou 64 bits. Scala à partir de la ligne de commande utilise tout ce qui est défini par JAVA_HOME, tandis que Java utilise 64 bits s'il est disponible indépendamment. Les IDE ont leurs propres paramètres. Quelques mesures ici: Temps d'exécution de Scala dans Eclipse

La réponse concernant la compréhension est juste, mais ce n'est pas toute l'histoire. Notez que l'utilisation de returnin isEvenlyDivisiblen'est pas gratuite. L'utilisation de return dans le for, force le compilateur scala à générer un retour non local (c'est-à-dire à retourner en dehors de sa fonction).

Cela se fait via l'utilisation d'une exception pour quitter la boucle. La même chose se produit si vous créez vos propres abstractions de contrôle, par exemple:

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

Cela imprime "Salut" une seule fois.

Notez que le returndans les foosorties foo(qui est ce que vous attendez). Étant donné que l'expression entre crochets est un littéral de fonction, ce que vous pouvez voir dans la signature de loopcela force le compilateur à générer un retour non local, c'est-à-dire qu'il returnvous oblige à quitter foo, pas seulement le body.

En Java (c'est-à-dire la JVM), la seule façon d'implémenter un tel comportement est de lever une exception.

Revenons à isEvenlyDivisible:

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

Le if (a % i != 0) return falseest un littéral de fonction qui a un retour, donc chaque fois que le retour est atteint, le moteur d'exécution doit lancer et intercepter une exception, ce qui entraîne une surcharge de GC.

Quelques moyens d'accélérer la forallméthode que j'ai découverte:

L'original: 41,3 s

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

Pré-instanciation de la plage pour ne pas créer une nouvelle plage à chaque fois: 9,0 s

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

Conversion en liste au lieu d'une plage: 4,8 s

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

J'ai essayé quelques autres collections mais List était le plus rapide (bien que toujours 7x plus lent que si nous évitions complètement la fonction Range et d'ordre supérieur).

Bien que je sois nouveau sur Scala, je suppose que le compilateur pourrait facilement implémenter un gain de performances rapide et significatif en remplaçant simplement automatiquement les littéraux Range dans les méthodes (comme ci-dessus) par des constantes Range dans la portée la plus externe. Ou mieux, les interner comme des littéraux Strings en Java.

note de bas de page : Les tableaux étaient à peu près les mêmes que Range, mais il est intéressant de noter que le proxénétisme d'une nouvelle forallméthode (illustrée ci-dessous) a permis une exécution 24% plus rapide sur 64 bits et 8% plus rapide sur 32 bits. Lorsque j'ai réduit la taille du calcul en réduisant le nombre de facteurs de 20 à 15, la différence a disparu, alors peut-être que c'est un effet de ramasse-miettes. Quelle qu'en soit la cause, elle est importante lors d'un fonctionnement à pleine charge pendant de longues périodes.

Un proxénète similaire pour List a également permis d'améliorer les performances d'environ 10%.

  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)  

Je voulais juste dire aux gens qui pourraient perdre confiance en Scala sur des problèmes comme celui-ci que ce genre de problèmes survient dans la performance de presque tous les langages fonctionnels. Si vous optimisez un repli dans Haskell, vous devrez souvent le réécrire comme une boucle récursive optimisée pour les appels de queue, sinon vous aurez des problèmes de performances et de mémoire à résoudre.

Je sais que c'est malheureux que les PF ne soient pas encore optimisés au point où nous n'avons pas à penser à des choses comme ça, mais ce n'est pas du tout un problème particulier à Scala.

Des problèmes spécifiques à Scala ont déjà été discutés, mais le principal problème est que l'utilisation d'un algorithme de force brute n'est pas très cool. Considérez ceci (beaucoup plus rapide que le code Java d'origine):

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

Essayez le one-liner donné dans la solution Scala pour Project Euler

Le temps donné est au moins plus rapide que le vôtre, bien que loin de la boucle while .. :)