Scala collections au PSUG

le 01/03/2011 par Marc Bojoly
Tags: Évènements

Fin janvier j'ai assisté à la 9ème session du Paris Scala User Group dont l'invité était Martin Odersky, le père du langage Scala. Celui-ci nous a présenté le framework de collections de Scala et en particulier les nouveautés de la version 2.8. Le sujet était riche et instructif, et, en approfondissant mes notes, ce qui ne devait être qu'un compte rendu est devenu un article que j'ai souhaité partager.

La présentation était organisée au Scala User Group dans les locaux de Xebia. Elle était très proche de celle qu'il a donnée à Devoxx. Cette page sur la présentation donne un lien vers l'enregistrement vidéo et les slides. Pour ceux qui ne connaissent pas bien le langage Scala, les slides 67-70 contiennent un cheat sheet avec la syntaxe principale.

Synthèse

Scala 2.8 a amélioré et simplifié le framework de collections ce qui va être le thème de la présentation. Disposer d'un framework de collections efficace est l'un des points qui a simplifié le développement d'algorithmes. Scala propose un framework de collections avec une approche fonctionnelle et une syntaxe concise adaptée, cela constitue un pas de plus dans la simplification. Par ailleurs, le parallélisme est une nécessité car les hardwares n'augmentent plus en fréquence mais en nombre de coeurs. Pour pouvoir être mis en oeuvre, le parallélisme doit pouvoir être implémenté par tous les développeurs et pas seulement par les experts. Les outils tels les threads et même les acteurs permettent de gérer la concurrence : gérer des arrivées d'information en parallèle. Le parallélisme est différent : étant donné un programme séquentiel qui fonctionne, il doit permettre d'obtenir un programme parallèle fonctionnant de façon strictement identique mais plus rapidement. C'est l'objectif des collections parallèles de Scala 2.9 qui seront abordées. Pour terminer, Martin Odersky a levé un peu le capot pour expliquer la construction du framework de collections en Scala 2.8. Pour être simple d'utilisation, les méthodes doivent respecter le "Uniform Return Type Principle" : les méthodes ensemblistes doivent retourner le même type que leur opérande de gauche. L'implémenter de façon élégante nécessite pas mal de jeux avec les generics...

Compte rendu complet

Future-proofing collections from mutable to persistent to parallel

The challenge we are facing

Le prochain challenge en programmation vient de l'augmentation du parallélisme au niveau matériel. L'architecture Fermi des dernières cartes graphiques NVidia peut faire fonctionner 24 000 threads en parallèle. Comment les alimenter en permanence? Aujourd'hui au niveau serveur on distribue chaque connexion sur un thread. Au niveau client seules certaines tâches graphiques sont parallélisées. Les puces n'iront pas plus vite désormais. Pour pouvoir gérer des quantités de données importantes, des simulations et des modèles haute-résolution il faudra utiliser le parallélisme.

Au niveau des langages, le challenge est donc de rendre la programmation parallèle accessible. On parle de Popular parallel programming grand challenge que je noterai par la suite PPP challenge. Ce besoin a également été identifié chez Microsoft qui travaille sur Parallel Linq, Linq distribué et à plus long terme Linq sur GPU.

Concurrent Programming to the rescue?

Il existe aujourd'hui des outils : threads et locks, acteurs et messages, STM (Software Transactional Memory) qui sont efficaces pour la programmation concurrente mais n'adressent pas le challenge PPP.

  • Programmation concurrente : vous avez un grand nombre d'évènements auxquels vous devez réagir
  • Programmation parallèle : vous avez un programme séquentiel qui fonctionne et vous devez le paralléliser pour qu'il fonctionne plus rapidement.
The root of the problem

La programmation parallèle est aujourd'hui possible mais elle est l'oeuvre d'experts du fait de sa complexité. La cause profonde de cette complexité est le non-déterminisme causé par l'accès concurrent de plusieurs threads à un état muable et partagé. Cela peut conduire à des bugs de type heisenbugs qui disparaissent à l'instrumentation ou sur un autre matériel. Or le debugging est basé sur le caractère reproductible d'un programme.

Space versus time

De façon un peu philosophique, la programmation impérative est basée sur la notion de temps : faire ceci, puis utiliser le résultat pour faire cela. La programmation concurrente est complexe car les différents threads s'entrecroisent sur l'axe temps. La programmation fonctionnelle est basée au contraire sur la notion d'espace : à partir d'une structure de données on peut construire une autre structure de données ou les combiner. Il est plus facile de les paralléliser car chaque transformation travaille sur ses propres données.

Scala (slides 8 to 9)

Scala est plus concis que Java. Ainsi une classe peut être définie ainsi

class Person(val name:String, val age:Int)

Un algorithme partitionnant une liste de personnes entre les mineurs et les majeurs prend près de 10 lignes en Java contre 2 en Scala

val people = Array(new Person("A", 10), new Person("B", 20))
val (minors, adults) = people partition (_.age < 18)

Il existe des frameworks fonctionnels en Java, mais ils nécessitent beaucoup trop de code. Oracle aurait finalement introduit les closures dans Java 8 car Doug Lea aurait refusé de construire quoi que ce soit de plus dans son framework Fork Join en attendant d'avoir des closures dans le langage.

The Scala Way of collections

Scala a une approche différente sur les collections en ne proposant pas (par défaut) de modifications sur les collections (type CRUD par élément comme en Java) mais des transformations qui prennent une collection en entrée et en créent une autre.

val ys = List(1,2,3)
ys map(_+1) //Renvoie une toute nouvelle instance

Il s'agit de collections immuables (persistent collections) (voir la fin de la présentation pour des détails d'implémentation optimisant les performances de la recopie). Les collections sont orientées objet, génériques, avec des méthodes de haut niveau (foreach, map, filter). Elles implémentent le Uniform Return Type Principle : les opérations sur les collections retournent des collections du même type que leur argument de gauche tant que cela fait du sens. Par exemple ys map(_+1) renverra une List[Int]]. Avec un framework de type commons.util ou en .NET on travaille à plus haut niveau en renvoyant une collection (commons.util) ou un énumérateur (.NET).

Using collections

Les slides 15 à 17 présentent des exemples de méthodes de haut niveau sur les collections :

  • map _+1 : ajouter 1 à tous les éléments
  • map 0 to 1 : créer un intervalle borné par chaque valeur de la collection
  • ys filter (_%2 == 0) : évident
  • as.flatten : pour transformer une collection de collections en collection
  • ys flatmap (0 to _) : map suivi de flatten
  • f groupBy (_.head) : pour construire à partir de la collection f une map dont les clés sont les valeurs extraites par la closure. Ici, pour une collection de String (vue comme une collection de Char). Plus simplement ici, cela crée un index des String par première lettre de la String (extraite par la closure _.head)

La syntaxe for permet d'être plus lisible. Le compilateur la retransforme en un ensemble de map, flatmap, filter.... for x <- xs) yield x+1 se lit "Ajouter +1 à chaque x généré par le générateur xs et renvoyer la collection correspondante". Cela équivaut à xs.map(_+1). Voir les slides pour plus d'exemples.

Map

Le type Map est un dictionnaire avec une syntaxe allégée également.

val m = Map(1 -> "ABC", 2 -> "DEF", 3 -> "GHI")

Voir slide 18 pour plus d'exemples.

Remarque : Le type Vector est également une implémentation de collection mais plus efficace pour un accès aléatoire que le type List.

Phone Mnemonics

Lutz Prechelt a réalisé en 2000 un comparatif de différents langages à partir d'un cahier des charges assez simple. A chaque numéro d'un clavier téléphonique sont associées des lettres. L'objectif est d'écrire un programme qui à partir d'un dictionnaire (liste de mots) construit toutes les phrases mnémoniques correspondant à ce numéro. Les langages de scripts (Python, etc.) le faisait en 100 LOCs à peu près, les autres langages (Java, C++) en 200 à 300 LOCs. Scala le fait en 20 LOCs à peu près. Cette classe Coder s'utilise comme cela avec un dictionnaire heu fictif

scala> val coder = new Coder(List("Scala", "rocks", "pacla", "pobls"))
coder: Coder = Coder@19a8c41

scala> coder.translate("7225276257")
res2: Set[String] = Set(Scala rocks, Scala pobls, pacla rocks, pacla pobls)

Le code Scala se trouve sur les slides 2-21 à 2-34. Comme c'est très dense j'ai dû l'exécuter morceau par morceau pour bien le comprendre. Je vous donne la sortie de la console correspondante:

C:\Users\mbo\Desktop>scala
Welcome to Scala version 2.8.1.final (Java HotSpot(TM) Client VM, Java 1.6.0_20)
.
Type in expressions to have them evaluated.
Type :help for more information.

scala> import collection.mutable.HashMap
import collection.mutable.HashMap

scala> val mnemonics = Map('2' -> "ABC", '3' -> "DEF", '4' -> "GHI", '5' -> "JKL
", '6' -> "MNO", '7' -> "PQRS", '8' -> "TUV", '9' -> "WXYZ")
mnemonics: scala.collection.immutable.Map[Char,java.lang.String] = Map((8,TUV),
(4,GHI), (9,WXYZ), (5,JKL), (6,MNO), (2,ABC), (7,PQRS), (3,DEF))

scala> /** Invert the mnemonics map to give a map from chars 'A'... 'Z' to '2'..
. '9' */

scala> val upperCode: Map[Char, Char] = for ((digit, str) <- mnemonics; ltr <- s
tr) yield (ltr -> digit)
upperCode: Map[Char,Char] = Map((E,3), (X,9), (N,6), (T,8), (Y,9), (J,5), (U,8),
 (F,3), (A,2), (M,6), (I,4), (G,4), (V,8), (Q,7), (L,5), (B,2), (P,7), (C,2), (H
,4), (W,9), (K,5), (R,7), (O,6), (D,3), (Z,9), (S,7))

scala> /** Maps a word to the digit string it can represent */

scala> def wordCode(word: String) : String = word.toUpperCase map (upperCode)
wordCode: (word: String)String

scala> val words = List("Scala", "rocks", "pacla", "pobls")
words: List[java.lang.String] = List(Scala, rocks, pacla, pobls)

scala> val keyExtractedByWordCode = wordCode("Scala")
keyExtractedByWordCode: String = 72252

scala> /** A map from digit strings to the words that represent them */

scala> val wordsForNum : Map[String, List[String]] = words groupBy wordCode
wordsForNum: Map[String,List[String]] = Map((76257,List(rocks, pobls)), (72252,L
ist(Scala, pacla)))

scala> /** Encode function step by step: return all ways to encode a number as a
 list of words */

scala> val number = "7225276257"
number: java.lang.String = 7225276257

scala> 1 to number.length
res0: scala.collection.immutable.Range.Inclusive with scala.collection.immutable
.Range.ByOne = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> Set(1 to number.length: _*)//Equivalent to range.toSet: finds the number of possible letters for the first word
res1: scala.collection.immutable.Set[Int] = Set(8, 4, 9, 5, 10, 6, 1, 2, 7, 3)

scala> //First iteration of the loop: looks for a word of 5 letters corresponding to the 5 first figures

scala> val splitPoint=5
splitPoint: Int = 5

scala> val first = number take splitPoint
first: String = 72252

scala> val next = number drop splitPoint
next: String = 76257

scala> //Check added to avoid failure with a small dictionnary. If in a for comprehension filters the corresponding element i.e. breaks the loop

scala> wordsForNum contains first
res2: Boolean = true

scala> val word=wordsForNum(first)
word: List[String] = List(Scala, pacla)

scala> //Recursive call for the rest of the phone number

scala> def encode(number:String) : Set[List[String]] = {
     | if(number.isEmpty)
     | Set(List[String]())
     | else
     | for {
     | //A number of 8 figures can be represented by one word of 8 characters
     | //or two words: 1 of 1 character and 1 of characters, etc.
     | //Find all possible number of characters for the first word
     | splitPoint <- Set(1 to number.length: _*)
     | //Extract the first
     | val first = number take splitPoint
     | val next = number drop splitPoint
     | if wordsForNum contains first
     | word <- wordsForNum(first)
     | rest <- encode(next)
     | } yield word :: rest
     | }
encode: (number: String)Set[List[String]]

scala> for(rest <- encode(next)) yield "Scala " :: rest
res3: scala.collection.immutable.Set[List[String]] = Set(List(Scala , rocks), Li
st(Scala , pobls))

scala> //Other combination (4 letter word + 1 letter word, etc.) will be tested
by the next iterations of the loop

scala> Set(List("Scala" , "rocks")) map (_ mkString " ")
res4: scala.collection.immutable.Set[String] = Set(Scala rocks)

scala>

Par rapport à la version présentée j'ai dû ajouter le if pour éviter une erreur quand le dictionnaire n'était pas complet.

Lors de l'étude en 2000, l'implémentation dans chaque langage avait été réalisée par différents programmeurs. Les meilleures performances en absolu étaient en C++ . La moyenne des performances de toutes les équipes C++ était cependant inférieure à la moyenne des performances dans d'autres langages. L'explication donnée par M. Odersky est qu'à l'époque C++ n'avait pas de librairie de collections complète. Les moins bonnes équipes en C++ en réécrivant leurs collections avaient de très mauvaises performances. Java a été un progrès en introduisant une librairie de collections performante. Scala va plus loin en proposant une API de collections immuables avec une approche fonctionnelle. L'API est :

  • Facile à utiliser
  • Concise
  • Sûre (typée fortement)
  • Rapide (et peut être parallélisée)
  • Universelle (même API pour toutes les collections)
Going parallel

Rendre ce code parallèle (i.e. résoudre le PPP Grand Challenge) en Scala 2.9 revient à utiliser ParArray\[String\] en argument du constructeur et à utiliser la méthode .par sur une collection traditionnelle splitPoint <- Set(1 to number.length: _*).par. On n'est pas allé plus loin dans la décomposition de ce qui s'exécutait en parallèle. A tester sans doute avec une version 2.9 finale. A la question "Pourquoi un ParArray et pourquoi pas une liste dans un autre namespace comme la différence collection muable/immuable, il a répondu que la 2.9 était encore en bêta. A suivre donc. A la question "Pouquoi pas simplement un for parallèle", il a répondu qu'il est très complexe pour un compilateur de savoir comment optimiser une boucle for. Seuls les compilateurs fortran y arrivent car la structure de mémoire en fortran est très simple (pas? (ou peu) de structures avec pointeurs).

How is all this implemented?

That was the bright side, Now to the dark side Je confirme, là il a vraiment mis un coup d'accélérateur...

Everything is a library

Les collections Scala sont uniquement écrites sous forme de librairie. C'est le langage qui permet d'avoir une syntaxe très intégrée. Les collections sont organisées en une hiérarchie : Traversable => Iterable => Seq, Set, Map (voir slide 4-40). Traversable a été introduit pour des raisons de performance pour les cas où on ne fait qu'appliquer une transformation à chaque élément (e.g. map). Il existe 3 namespaces de collection (voir slide 4-41) :

  • scala.collection: les types communs aux collections muables et immuables
  • scala.collection.muable
  • scala.collection.immutable
New implementations: Vector and Hash Tries

Une collection immuable nécessite en théorie de recopier tous les éléments. L'implémentation a été revue dans la version 2.8 et tirée de celle de Clojure. Les collections sont stockées en interne sous forme de tableaux de tableaux de 32 éléments. Donc en moins de 3 sauts on peut adresser 4 échelons donc 324=220=1 milliard d'éléments soit 4 GB pour des entiers. Les performances d'update et d'append sont en temps constant car il suffit de recopier le tableau feuille modifié et les 3 tableaux du chemin jusqu'à la racine pour obtenir une instance complètement différente.

The Uniform Return Type Principle and collections refactoring in Scala 2.8

Afin qu'il soit simple d'utiliser les collections elles suivent le Uniform Return Type Principle : les opérations ensemblistes renvoient une collection du même type que celui de leur opérande de gauche. Avant la version 2.8 de Scala cela nécessitait, au sein du code des collections, de dupliquer les méthodes filter, map, partition au sein de chaque implémentation (voir slide 4-46). M. Ordesky n'aimait pas cela "pattern de la rue sale ou Broken-Window effect" : les classes avaient tendance de plus en plus à se charger de code dédié à ce contournement.

How to do better?

Il est nécessaire d'abstraire le type constructeur ce qui peut se faire avec un type de plus haut niveau en Scala (Higher Order type) (il est noté CC au slide 4-50). Un exemple d'implémentation est donné avec un un trait Builder qui permet à lui seul de reconstruire n'importe quel type de collection Traversable. Ainsi il suffit de spécialiser le type de plus haut niveau CC dans chaque sous-classe.

trait Builder[A, Coll] {
	def += (elem: A) //Add elems
	def result: Coll
}

trait TraversableLike[A,CC[X]] {
	def foreach(f:A=>Unit) 
	def newBuilder[B]:Builder[B,CC[B]]
	def map[B](f:A=>B):CC[B]={
		val b=newBuilder[B]
		foreach(x=>b+=f(x))
		b.result
	}
}
Unfortunately things are not as parametric as it seems at first

Cela ne fonctionne pas partout. Par exemple pour un BitSet(1,2,3} la fonction map (x => x+1) doit renvoyer un BitSet mais map (x => "["+x+"]") doit renvoyer un Set[String].

Facts about CanBuildFrom and Implicitly injected theories

L'objectif est de trouver le "meilleur type possible" qui convienne après ajout de l'élément. L'idée a été d'exprimer le besoin comme un nouveau système de type de façon théorique. Une fonction CanBuildFrom[From,Elem,To] a été définie et les axiomes correspondants à "trouver le meilleur type possible" ont été exprimés au slide 55 dans une syntaxe Prolog.

L'astuce a consisté à utiliser le mot clé implicit en Scala. Celui-ci permet d'injecter dans l'argument implicit un élément (ici une méthode CanBuildFrom) qui correspond au type demandé. Enfin en réinjectant dans l'exemple précédant de map on obtient l'implémentation Scala 2.9.

Objections

Ce genre de détail est très complexe. Pour la majorité des développeurs il suffit de considérer que le type renvoyé par la fonction map est approximé au meilleur type possible (voir slide 4-60). Ce genre de détail n'a d'utilité que pour les développeurs de framework. Pour l'instant ce genre de détail apparaît dans la Scala doc mais cela devrait être corrigé.

Going further

Scala 2.9 apporte le support des collections parallèles en ajoutant les méthodes .par et .seq aux collections pour les convertir en collections parallèles ou séquentielles. C'est ce qui, d'après M. Odersky doit permettre de répondre en partie au challenge PPP en Scala. Mais cela ne suffira probablement pas pour alimenter les 10 000 threads nécessaires à une architecture Fermi. Pour cela il envisage la création d'une API qui permettra d'écrire des DSL permettant d'écrire des algos métiers de façon parallèle. Ce sont des recherches en cours (voir slide 63).

Questions

Scala dans 5-10 ans?

Que pouvez-vous dire sur Scala dans 5-10 ans pour rassurer les décideurs d'entreprise? Scala a reçu des fonds qui lui permettent d'être financé pendant les 5 prochaines années. Le langage est désormais maintenu par une société commerciale. Pour l'instant le code est sous licence de l'EPFL mais comme cela correspond de moins en moins aux committers réels la question de mettre le langage dans une fondation (type Apache, Eclipse) est en étude.

L'échéance des prochaines releases?

L'objectif est de sortir une release majeure par an. M. Odersky souhaite éviter les grandes attentes comme pour la version 2.8. Cela s'expliquait par la difficulté de refondre les collections.

Scala va-t-il rester au dessus de la JVM?

L'effort pour porter Scala sur .NET est très actif. Il repose en partie sur IKVM donc cela ne supporte pas certaines librairies comme Spring. Des tentatives sont en cours, notamment pour le porter sur JavaScript. C'est intéressant mais il n'est pas directement impliqué.

Scala sur Android

La demande de découper Scala en module pour tourner sur des plateformes existe. Il est prévu d'attendre le projet Jigsaw pour effectuer ce découpage.

Acteurs Scala versus acteurs Akka

Les acteurs Akka sont globalement meilleurs que les acteurs Scala au niveau performance. De plus les acteurs Akka sont plus tolérants à certaines erreurs de programmation. M. Odersky le sait. Les acteurs Scala ont été fait très rapidement en 3 mois et en reprenant beaucoup de la logique d'Erlang. Les acteurs Akka sont beaucoup plus adaptés à Scala. Cependant, il ne se résout pas encore à les transformer tout de suite en acteurs Akka car cela enlèverait un peu de simplicité. Ainsi aujourd'hui pour les acteurs Scala, chaque thread est un acteur de sorte qu'il est très facile d'envoyer un message depuis le programme principal. C'est moins facile avec les acteurs Akka.