Comment optimiser pour-compréhensions et boucles en Scala?

le problème est très probablement l'utilisation d'une for compréhension dans la méthode isEvenlyDivisible . Remplacer for par une boucle équivalente while devrait éliminer la différence de performance avec Java.

par opposition aux boucles for de Java, les compréhensions for de Scala sont en fait du sucre syntaxique pour les méthodes d'ordre supérieur; dans ce cas, vous appelez la méthode foreach sur un objet Range . Le for de Scala est très général, mais conduit parfois à des performances douloureuses.

vous pouvez essayer le drapeau -optimize dans la version 2.9 de Scala. Les performances observées peuvent dépendre de la JVM utilisée et de l'optimiseur JIT qui dispose d'un temps de "réchauffement" suffisant pour identifier et optimiser les points chauds.

des discussions récentes sur la liste de diffusion indiquent que L'équipe de Scala travaille à améliorer for la performance dans les 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 5/28 :

• comme solution à court terme, le ScalaCL plugin (alpha) transformera les simples boucles Scala en l'équivalent des boucles while .
• comme solution potentielle à long terme, les équipes de L'EPFL et de Stanford sont collaborer sur un projet permettant la compilation de temps d'exécution de "virtuel" Scala pour très haute performance. Par exemple, plusieurs idiomatiques les boucles fonctionnelles peuvent être fusionnées à l'exécution dans le bytecode optimal JVM, ou à une autre cible telle qu'un GPU. Le système est extensible, permettant DSLs défini par l'utilisateur et les transformations. Consultez les publications et Stanford notes de cours . Le code préliminaire est disponible sur Github, avec une sortie prévue dans les mois à venir.

comme suivi, j'ai essayé le drapeau-optimize et il a réduit le temps de fonctionnement de 103 à 76 secondes, mais c'est toujours 107x plus lent que Java ou une boucle while.

alors 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 de la "forall" d'une manière concise. J'ai échoué lamentablement et est venu avec

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

par lequel ma solution astucieuse de 5 lignes a diminué à 12 lignes. Cependant , cette version fonctionne en 0.71 secondes , la même vitesse que la version Java originale, et 56 fois plus rapide que la version ci-dessus en utilisant "forall" (40.2 s)! (voir éditer ci-dessous pour savoir pourquoi C'est plus rapide que Java)

évidemment, ma prochaine étape a été de traduire ce qui précède en Java, mais Java ne peut pas le gérer et lance un StackOverflowError avec n autour de la marque 22000.

j'ai alors griffé ma tête pendant un peu et remplacé le "tout" avec un peu plus de la queue de la récursivité, qui enregistre un couple de lignes, fonctionne tout aussi rapide, mais avouons-le, est plus difficile à 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 recursion de la queue de Scala gagne la journée, mais je suis surpris que quelque chose d'aussi simple qu'une boucle "for" (et la méthode "forall") soit essentiellement cassé et doit être remplacé par inélégant et verbeux "whiles", ou recursion de la queue. Une grande partie de la raison pour laquelle J'essaie Scala est en raison de la syntaxe concise, mais il est pas bon si mon le code va courir 100 fois plus lentement!

modifier : (supprimé)

EDIT OF EDIT : les anciennes différences entre les temps d'exécution de 2,5 s et 0,7 s étaient entièrement dues au fait que les JVM 32 bits ou 64 bits étaient utilisées. Scala de la ligne de commande utilise tout ce qui est défini par JAVA_HOME, tandis que Java utilise 64-bit si disponible indépendamment. Les IDEs ont leurs propres réglages. Quelques mesures ici: Scala temps d'exécution dans Eclipse

La réponse à propos de la compréhension est bonne, mais elle n'est pas toute l'histoire. Vous devez noter que l'utilisation de return dans isEvenlyDivisible n'est pas gratuite. L'utilisation du retour à l'intérieur du for , force le compilateur scala à générer un retour non local (c'est-à-dire à retourner en dehors de sa fonction).

Ceci est fait par l'utilisation d'une exception pour sortir de la boucle. La même chose se produit si vous construisez 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()

cette gravure "Salut" une seule fois.

notez que le return dans foo sort foo (ce qui est ce que vous attendez). Puisque l'expression entre crochets est une fonction littérale, que vous pouvez voir dans la signature de loop cela force le compilateur à générer un retour non local, c'est-à-dire, le return vous force à sortir foo , pas seulement le body .

en Java (C'est-à-dire la JVM) le seul façon de mettre en œuvre un tel comportement est à jeter une exception.

retour à 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 false est un littéral de fonction qui a un retour, de sorte que chaque fois que le retour est atteint, le moteur d'exécution est à lancer et à attraper une exception, ce qui provoque un peu de GC frais généraux.

quelques façons d'accélérer la méthode forall que j'ai découverte:

the original: 41.3 s

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

pré-instanciation de la gamme, donc nous ne créons pas une nouvelle gamme à chaque fois: 9.0 s

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

conversion à une 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 la liste était le plus rapide (bien que toujours 7x plus lent que si nous évitons la portée et la fonction d'ordre supérieur tout à fait).

alors que je suis nouveau à Scala, je suppose que le compilateur pourrait facilement mettre en œuvre un gain de performance rapide et significative en remplaçant simplement automatiquement les littérales de gamme dans les méthodes (comme ci-dessus) avec des constantes de gamme dans la portée externe. Ou mieux, les interner comme des cordes littérales en Java.

note de bas de page : Les tableaux étaient à peu près les mêmes que la portée, mais il est intéressant de noter que la mise en place d'une nouvelle méthode forall (voir ci-dessous) a permis une exécution 24% plus rapide sur 64 bits, et 8% plus rapide sur 32 bits. Quand j'ai réduit la taille du calcul en réduisant le nombre de facteurs de 20 à 15 la différence a disparu, donc peut-être que c'est un effet de collecte des ordures. Quelle qu'en soit la cause, c'est important quand on fonctionne à pleine charge pendant de longues périodes.

un proxénète similaire pour List a également résulté dans environ 10% de meilleure performance.

  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 commenter pour les gens qui pourraient perdre la foi en Scala sur des questions comme celle-ci que ce genre de questions surgissent dans la performance d'à peu près toutes les langues fonctionnelles. Si vous optimisez un pli dans Haskell, vous devrez souvent le réécrire sous forme de boucle recursive optimisée, sinon vous aurez des problèmes de performance et de mémoire à résoudre.

je sais qu'il est regrettable que les FPs ne soient pas encore optimisés au point où nous n'avons pas à penser à des choses comme cela, mais ce n'est pas du tout un problème particulier à la Scala.

les problèmes spécifiques à Scala ont déjà été discutés, mais le problème principal 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 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
}))

essayer la doublure unique donnée dans la solution Scala pour le projet Euler

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