La programmation fonctionnelle Scala est-elle plus lente que le codage traditionnel ?

Question

Lors d'une de mes premières tentatives de création de code fonctionnel, j'ai rencontré un problème de performance.

J'ai commencé par une tâche courante : multiplier les éléments de deux tableaux et additionner les résultats :

var first:Array[Float] ...
var second:Array[Float] ...    
var sum=0f; 
for (ix<-0 until first.length) 
    sum += first(ix) * second(ix);

Voici comment j'ai réformé le travail :

sum = first.zip(second).map{ case (a,b) => a*b }.reduceLeft(_+_)

Lorsque j'ai évalué les deux approches, la deuxième méthode prend 40 fois plus de temps pour être achevée !

Pourquoi la deuxième méthode prend-elle autant de temps ? Comment puis-je réformer le travail pour être à la fois plus rapide et utiliser le style de programmation fonctionnelle ?

Answer 1

Les principales raisons pour lesquelles ces deux exemples sont si différents en termes de vitesse sont les suivantes :

• le plus rapide n'utilise pas de générique, donc il n'est pas confronté au boxing/unboxing.
• le plus rapide ne crée pas de collections temporaires et évite donc les copies de mémoire supplémentaires.

Considérons les ralentisseurs un par un. D'abord :

first.zip(second)

Cela crée un nouveau tableau, un tableau de Tuple2 . Il va copier tous les éléments des deux tableaux dans Tuple2 puis copier une référence à chacun de ces objets dans un troisième tableau. Maintenant, remarquez que Tuple2 est paramétrée, donc elle ne peut pas enregistrer Float directement. Au lieu de cela, de nouvelles instances de java.lang.Float sont créés pour chaque numéro, les numéros y sont stockés, puis une référence pour chacun d'entre eux est stockée dans le fichier Tuple2 .

map{ case (a,b) => a*b }

Maintenant, un quatrième tableau est créé. Pour calculer les valeurs de ces éléments, il faut lire la référence au tuple du troisième tableau, lire la référence à l'élément java.lang.Float stockés, lire les nombres, les multiplier, créer un nouveau java.lang.Float pour stocker le résultat, et ensuite renvoyer cette référence, qui sera de -référencé à nouveau pour être stocké dans le tableau (les tableaux ne sont pas effacés par type).

Mais nous n'avons pas fini. Voici la prochaine partie :

reduceLeft(_+_)

Celui-là est relativement inoffensif, sauf qu'il fait toujours le boxing/unboxing et java.lang.Float à l'itération, puisque reduceLeft reçoit un Function2 qui est paramétrée.

Scala 2.8 introduit une fonctionnalité appelée spécialisation qui permettra de se débarrasser d'une grande partie de ces boîtes et découpes. Mais considérons des versions alternatives plus rapides. Nous pourrions, par exemple, faire map y reduceLeft en une seule étape :

sum = first.zip(second).foldLeft(0f) { case (a, (b, c)) => a + b * c }

Nous pourrions utiliser view (Scala 2.8) ou projection (Scala 2.7) pour éviter de créer des collections intermédiaires :

sum = first.view.zip(second).map{ case (a,b) => a*b }.reduceLeft(_+_)

Cette dernière n'économise pas beaucoup, en fait, donc je pense que la non-strictivité est "perdue" assez rapidement (c'est-à-dire que l'une de ces méthodes est stricte même dans une vue). Il y a aussi une autre façon de zipper qui est non stricte (c'est-à-dire qui évite certains résultats intermédiaires) par défaut :

sum = (first,second).zipped.map{ case (a,b) => a*b }.reduceLeft(_+_)

Cette méthode donne de bien meilleurs résultats que la précédente. Mieux que la foldLeft un, mais pas de beaucoup. Malheureusement, nous ne pouvons pas combiner zipped con foldLeft parce que le premier ne soutient pas le second.

Le dernier est le plus rapide que j'ai pu obtenir. Plus rapide que ça, seulement avec la spécialisation. Maintenant, Function2 se trouve être spécialisée, mais pour Int , Long y Double . Les autres primitives ont été laissées de côté, car la spécialisation augmente la taille du code de manière assez spectaculaire pour chaque primitive. Sur mes tests, cependant Double prend en fait plus de temps. Cela peut être dû au fait qu'il est deux fois plus grand, ou à quelque chose que je fais mal.

Donc, en fin de compte, le problème est une combinaison de facteurs, y compris la production de copies intermédiaires d'éléments, et la façon dont Java (JVM) gère les primitives et les génériques. Un code similaire en Haskell utilisant la supercompilation serait égal à tout ce qui n'est pas de l'assembleur. Sur la JVM, il faut être conscient des compromis et être prêt à optimiser le code critique.

Answer 2

J'ai fait quelques variations de ceci avec Scala 2.8. La version en boucle est telle que vous l'écrivez mais la version fonctionnelle est légèrement différente :

(xs, ys).zipped map (_ * _) reduceLeft(_ + _)

J'ai utilisé Double au lieu de Float, parce qu'actuellement la spécialisation ne s'applique qu'à Double. J'ai ensuite testé avec des tableaux et des vecteurs comme type de support. De plus, j'ai testé les variantes Boxed qui fonctionnent sur les java.lang.Double au lieu des Doubles primitifs pour mesurer l'effet du boxing et du unboxing des types primitifs. l'effet du boxing et du unboxing des types primitifs. Voici ce que j'ai obtenu (en utilisant Java 1.6_10 server VM, Scala 2.8 RC1, 5 exécutions par test).

loopArray               461             437             436             437             435
reduceArray             6573            6544            6718            6828            6554
loopVector              5877            5773            5775            5791            5657
reduceVector            5064            4880            4844            4828            4926

loopArrayBoxed          2627            2551            2569            2537            2546
reduceArrayBoxed        4809            4434            4496            4434            4365
loopVectorBoxed         7577            7450            7456            7463            7432
reduceVectorBoxed       5116            4903            5006            4957            5122

La première chose à remarquer est que la plus grande différence, et de loin, se situe entre les boucles de tableaux primitifs et les réductions fonctionnelles de tableaux primitifs. Elle est d'environ un facteur 15 au lieu des 40 que vous avez vus, ce qui reflète les améliorations de Scala 2.8 par rapport à 2.7. Pourtant, les boucles de tableaux primitifs sont les plus rapides de tous les tests, tandis que les réductions de tableaux primitifs sont les plus lentes. Cela s'explique par le fait que les tableaux Java primitifs et les opérations génériques ne sont pas très bien adaptés. L'accès aux éléments des tableaux primitifs de Java à partir de fonctions génériques nécessite beaucoup de boxing/unboxing et parfois même de la réflexion. Les futures versions de Scala spécialiseront la classe Array et nous devrions alors voir une certaine amélioration. Mais pour l'instant, c'est ce qu'il en est.

Si vous passez des tableaux aux vecteurs, vous remarquez plusieurs choses. Premièrement, la version réduite est maintenant plus rapide que la boucle impérative ! Cela s'explique par le fait que la réduction vectorielle peut utiliser des opérations de masse efficaces. Deuxièmement, la réduction vectorielle est plus rapide que la réduction de tableau, ce qui illustre la surcharge inhérente que les tableaux de types primitifs représentent pour les fonctions génériques d'ordre supérieur.

Si vous éliminez les frais généraux de mise en boîte et de mise hors boîte en ne travaillant qu'avec des valeurs java.lang.Double mises en boîte, le tableau change. Maintenant, la réduction sur des tableaux est un peu moins de 2 fois plus lente que le bouclage, au lieu d'une différence de 15 fois auparavant. Cela se rapproche davantage de la surcharge inhérente aux trois boucles avec des structures de données intermédiaires au lieu de la boucle fusionnée de la version impérative. Le bouclage sur les vecteurs est maintenant de loin la solution la plus lente, alors que la réduction sur les vecteurs est un peu plus lente que la réduction sur les tableaux.

La réponse générale est donc : cela dépend. Si vous avez des boucles serrées sur des tableaux de valeurs primitives, rien ne vaut une boucle impérative. Et il n'y a aucun problème pour écrire les boucles car elles ne sont ni plus longues ni moins compréhensibles que les versions fonctionnelles. Dans toutes les autres situations, la solution FP semble compétitive.

Answer 3

C'est un microbenchmark, et cela dépend de la façon dont le compilateur optimise votre code. Vous avez 3 boucles composées ici,

zip . carte . pli

Maintenant, je suis presque sûr que le compilateur Scala ne peut pas fusionner ces trois boucles en une seule, et le type de données sous-jacent est strict, donc chaque (.) correspond à la création d'un tableau intermédiaire. La solution impérative/mutable réutiliserait le tampon à chaque fois, en évitant les copies.

Maintenant, il est essentiel de comprendre ce que signifie la composition de ces trois fonctions pour comprendre les performances dans un langage de programmation fonctionnel - et en effet, en Haskell, ces trois boucles seront optimisées en une seule boucle qui réutilise un tampon sous-jacent - mais Scala ne peut pas faire cela.

Il y a cependant des avantages à s'en tenir à l'approche combinatoire : en distinguant ces trois fonctions, il sera plus facile de paralléliser le code (remplacer map par parMap, etc.). En fait, si l'on choisit le bon type de tableau (comme un tableau réseau parallèle ) un compilateur suffisamment intelligent sera en mesure de paralléliser automatiquement votre code, ce qui vous permettra de gagner en performance.

Donc, en résumé :

• les traductions naïves peuvent avoir des copies et des inefficacités inattendues
• les compilateurs FP intelligents suppriment cette surcharge (mais Scala ne le peut pas encore).
• il est intéressant de s'en tenir à l'approche de haut niveau si vous souhaitez recibler votre code, par exemple pour le paralléliser.

Answer 4

Don Stewart a une bonne réponse, mais il n'est peut-être pas évident que le passage d'une boucle à trois crée un ralentissement d'un facteur 40. J'ajouterai à sa réponse que Scala se compile en bytecodes JVM, et que non seulement le compilateur Scala ne fusionne pas les trois boucles en une seule, mais qu'il alloue presque certainement tous les tableaux intermédiaires. Notoirement, Les implémentations de la JVM ne sont pas conçues pour gérer les taux d'allocation requis par les langages fonctionnels. . L'allocation est un coût important dans les programmes fonctionnels, et c'est pour cela que les transformations de fusion de boucles que Don Stewart et ses collègues ont implémentées pour Haskell sont si puissantes : elles éliminent beaucoup d'allocations. Lorsque vous n'avez pas ces transformations, et que vous utilisez un allocateur coûteux tel que celui que l'on trouve sur une JVM typique, c'est de là que vient le gros ralentissement.

Scala est un excellent moyen d'expérimenter la puissance expressive d'un mélange inhabituel d'idées de langage : classes, mixins, modules, fonctions, etc. Mais il s'agit d'un langage de recherche relativement jeune et il fonctionne sur la JVM. Il n'est donc pas raisonnable de s'attendre à de grandes performances, sauf pour le type de code pour lequel les JVM sont performantes. Si vous voulez expérimenter avec le mélange d'idées de langage que Scala offre, c'est génial - c'est une conception vraiment intéressante - mais ne vous attendez pas à obtenir les mêmes performances sur du code fonctionnel pur que celles que vous obtiendriez avec un compilateur mature pour un langage fonctionnel, tel que GHC o MLton .

La programmation fonctionnelle en scala est-elle plus lente que le codage traditionnel ?

Pas nécessairement. . Les choses à faire avec les fonctions de première classe, le pattern matching et le currying ne doivent pas être particulièrement lentes. Mais avec Scala, plus qu'avec d'autres implémentations d'autres langages fonctionnels, vous devez vraiment attention aux allocations -Ils peuvent être très chers.

Answer 5

La bibliothèque de collections Scala est entièrement générique, et les opérations fournies sont choisies pour une capacité maximale, et non pour une vitesse maximale. Donc, oui, si vous utilisez un paradigme fonctionnel avec Scala sans faire attention (surtout si vous utilisez des types de données primitifs), votre code sera plus long à exécuter (dans la plupart des cas) que si vous utilisez un paradigme impératif/itératif sans faire attention.

Cela dit, vous pouvez facilement créer des opérations fonctionnelles non génériques qui s'exécutent rapidement pour la tâche que vous souhaitez. Dans le cas du travail avec des paires de flottants, nous pourrions faire ce qui suit :

class FastFloatOps(a: Array[Float]) {
  def fastMapOnto(f: Float => Float) = {
    var i = 0
    while (i < a.length) { a(i) = f(a(i)); i += 1 }
    this
  }
  def fastMapWith(b: Array[Float])(f: (Float,Float) => Float) = {
    val len = a.length min b.length
    val c = new Array[Float](len)
    var i = 0
    while (i < len) { c(i) = f(a(i),b(i)); i += 1 }
    c
  }
  def fastReduce(f: (Float,Float) => Float) = {
    if (a.length==0) Float.NaN
    else {
      var r = a(0)
      var i = 1
      while (i < a.length) { r = f(r,a(i)); i += 1 }
      r
    }
  }
}
implicit def farray2fastfarray(a: Array[Float]) = new FastFloatOps(a)

et ces opérations seront alors beaucoup plus rapides. (Plus rapide encore si vous utilisez Double et 2.8.RC1, car alors les fonctions (Double,Double)=>Double sera spécialisée, et non générique ; si vous utilisez quelque chose d'antérieur, vous pouvez créer votre propre abstract class F { def f(a: Float) : Float } et ensuite suivre avec new F { def f(a: Float) = a*a } au lieu de (a: Float) => a*a .)

Quoi qu'il en soit, le fait est que ce n'est pas le style fonctionnel qui rend le codage fonctionnel lent en Scala, mais que la bibliothèque est conçue dans l'optique d'une puissance/flexibilité maximale, et non d'une vitesse maximale. C'est logique, car les exigences de chaque personne en matière de vitesse sont généralement subtilement différentes, et il est donc difficile de couvrir tout le monde de manière optimale. Mais si c'est quelque chose que vous faites plus qu'un peu, vous pouvez écrire votre propre matériel où la pénalité de performance pour un style fonctionnel est extrêmement faible.