Java

Java 7 : fork / join et parallel arrays – 2

Cet article est la deuxième partie de la présentation des parallel arrays de la JSR 166, dirigée par Doug Lea. . Nous en étions restés au début de la présentation des opérations disponibles sur les parallel arrays. Continuons en terminant notre tour d’horizon des opérations disponibles sur ces tableaux, avant de donner une idée des gains en performance.

Opérations de mapping

Ces opérations sont les plus complexes à mettre en œuvre. Pour des raisons d’optimisation, elles reposent sur un nombre d’interfaces prohibitif (80 !), appelées par 15 méthodes différentes. Si l’on ajoute à cela que chaque classe ParallelArray, ParralelLongArray et ParallelDoubleArray, a sa propre version de chacune de ces méthodes, et de certaines de ces interfaces, on arrive à une API un peu dure à saisir… Tâchons de mettre de l’ordre dans tout cela.

Une opération de mapping consiste à prendre un tableau et à appliquer une transformation à ses valeurs. N’oublions pas que ces valeurs peuvent être des objets quelconques, pas nécessairement des valeurs numériques.

Les opérations de mapping se divisent en deux grandes familles.

  • Celles qui prennent en compte l’index de la valeur considérée dans le tableau. Le nom de ces méthodes est withIndexedMapping. L’opération prend alors en paramètre un index de type int, un paramètre de même type que les valeurs du tableau parallèle sur lequel on opère, et retourne un objet, un long ou un double. Pour un type de tableau donné, on a donc trois mappers disponibles.
  • Celles qui ne prennent pas en compte cet index. Leur nom est alors withMapping.

Cette deuxième famille se subdivise encore en deux.

  • Les opérations qui ne travaillent que sur le tableau parallèle considéré. L’opération prend alors un paramètre du même type que les valeurs du tableau parallèle considéré, et peut retourner un objet, un long ou un double. De même, pour un type de tableau donné, on a trois mappers de ce type disponibles.
  • Celles qui combinent deux tableaux parallèles différents. Ces opérations prennent en paramètre un combiner, et le second tableau.

Ce combiner prend deux paramètres, chacun du type des valeurs portées par les deux tableaux. Ces deux types ne sont pas nécessairement les mêmes. Il peut retourner un objet, un long ou un double. Comme chaque tableau peut être construit sur des objets, des long ou des double, on obtient neuf types de combiners possibles pour un type de tableau donné.

Le nom de chacune de ces méthodes suit une convention, documentée dans la Javadoc de l’API.

Voyons quelques cas d’utilisation classique, sur des exemples simples.

Addition d’une constante

L’addition d’une constante consiste à additionner la même valeur à chacun des éléments du tableau.

// opération pour l'addition d'une constante
Ops.LongOp add2 = new Ops.LongOp() {

	@Override
	public long op(long l1) {
		return l1 + 2 ;
	}
} ;

// application de cette opération sur a0
ParallelLongArrayWithLongMapping a2 = a0.withMapping(add2) ;

Comme nous l’avons déjà écrit, le calcul ne s’effectue pas sur l’appel à la méthode withMapping(...), mais sur un appel futur à la méthode all() de l’objet retourné.

Produit d’un tableau terme à terme avec un autre

Ce produit est une opération qui, dans le cadre de notre exemple, prend deux long en paramètre, et retourne un long.

// opération pour le produit terme à terme de deux tableaux
Ops.BinaryLongOp multAB = new Ops.BinaryLongOp() {

	@Override
	public long op(long l1, long l2) {
		return l1*l2 ;
	}

} ;

// application de cette opération sur a0 et a1
ParallelLongArrayWithLongMapping a3 = a0.withMapping(multAB, a1) ;

Calcul de la norme d’un tableau

Il ne nous manque pas grand chose pour calculer la norme d’un tableau. Écrivons la somme des termes d’un tableau sous forme d’une opération.

// opération pour la somme des termes d'un tableau
Ops.LongReducer sum = new Ops.LongReducer() {

	@Override
	public long op(long l1, long l2) {

		return l1 + l2 ;
	}
} ;

// norme de a0
long normeCarre = a0.withMapping(multAB, a0).reduce(sum, 0L) ;
double norme = Math.sqrt(normeCarre) ;

Notons que sur ce dernier exemple, on aurait pu aussi utiliser la méthode sum() définie sur les tableaux parallèles.

Opérations d’accumulation

Deux méthodes d’accumulation sont présentes : cumulate() et precumulate(). Ces deux méthodes prennent un reducer en paramètre. Rappelons qu’un reducer est une opération associative.

La méthode cumulate() accumule les valeurs successives du tableau, avec application de l’opération définie dans le reducer.

// application de cumulate(red) sur [a0, a1, a2] :
[a0, a1, a2] -> [a0, red(a0, a1), red(red(a0, a1), a2)]

// ainsi, si red(ai, aj) = ai + aj, on a :
[1, 2, 3] -> [1, 3, 6]

La méthode precumulate() fonctionne différemment. Elle réalise en fait deux opérations : elle transforme le tableau sur lequel elle est appelée, et retourne une valeur résultat de l’accumulation. Cette valeur est du type retourné par le reducer utilisé.

// application du precumulate(red) sur [a0, a1, a2]
// le tableau est transformé de la façon suivante :
[a0, a1, a2] -> [0, red(0, a0), red(red(0, a0), a1)]
// et la méthode precumulate retourne
red(red(red(0, a0), a1), a2)

// ainsi, si red(ai, aj) = ai + aj, precumulate opère de la façon suivante :
[1, 2, 3] -> [0, 1, 3]
// et retourne
6

Méthodes utilitaires

La classe ParallelArray expose également des méthodes utilitaires, qui permettent d’accélérer certaines opérations courantes sur les tableaux.

  • Les méthodes addAll(...) permettent d’ajouter deux tableaux différents, terme à terme.
  • allNonIdenticalElements() et allUniqueElements() : ces méthodes retournent le tableau parallèle de tous les éléments non nuls de ce tableau parallèle, et différents, au sens de == ou de equals() respectivement.
  • sort(...) : cette méthode permet de trier ce tableau parallèle. On peut passer un comparateur à cette méthode.
  • summary(...) : cette méthode calcule des statistiques de base sur ce tableau. Elle peut prendre un comparateur en paramètre. Ces statistiques sont encapsulées dans un objet, et sont le max, le min, ainsi que l’index du max et du min de ce tableau, et le nombre d’éléments qu’il comporte.
  • binarySearch(...) : cette méthode retourne l’index de l’objet passé en paramètre. On peut également passer un comparateur à cette méthode, ce qui est utile si les objets de ce tableau ne sont pas comparables. Ces méthodes supposent que le tableau est trié dans l’ordre croissant.
  • get(int) et set(int) : ces méthodes permettent d’accéder directement à l’objet dont l’index est passé en paramètre.
  • indexOf(...) : retourne le premier index où se trouve l’objet passé en paramètre.
  • max(...) et min(...) : ces méthodes retournent le plus grand, ou plus petit élément de ce tableau. Ces méthodes peuvent prendre un comparateur en paramètre.
  • size() : cette méthode retourne le nombre d’éléments de ce tableau parallèle.
  • getArray() : cette méthode retourne le contenu de ce tableau parallèle, sous forme de tableau normal.
  • removeNulls() et removeConsecutiveDuplicates() : ces méthodes retirent les éléments nuls d’un tableau parallèle, ou les éléments égaux et consécutifs. La taille du tableau retourné est en général plus petite que celle du tableau original.
  • setLimit(...) : cette méthode permet de fixer la taille maximale du tableau parallèle. Si cette taille est plus grande que la taille courante, alors le tableau sous-jacent sera recopié dans un tableau de la bonne taille.

La classe ParallelArray expose enfin une méthode asList() qui retourne une vue de type List sur le tableau sous-jacent. La documentation nous précise que les opérations de List sont bien supportées, y compris celles qui mèneraient à une extension de ce tableau. Toutefois, ces opérations ne sont pas thread safe. Notamment, les modifications du tableau au travers de cette vue mèneront à des corruptions de données si elles sont réalisées alors que des opérations ont lieu sur ce tableau.

Performances

C’est évidemment sur le point des performances que l’on attend cette API. Le framework fork / join nous permet de profiter des différents processeurs disponibles pour mener à bien nos calculs. Mais comme nous l’avions montré dans nos précédents articles, on se retrouve rapidement confronté à des problèmes de synchronisation, qui rendent très délicate l’utilisation de ce framework avec les tableaux.

L’utilisation des tableaux parallèles règle ces problèmes (ce qui est déjà une immense avancée !), qu’en est-il des temps de calcul ?

Comme je sais que tu aimes bien les choses originales, précieux lecteur, nous allons jouer un peu sur ce cas de test, jouer à calculer π, par la formule dite ζ(2). Cette formule n’est certainement pas la meilleure pour calculer numériquement π, mais est suffisamment calculatoire pour notre test. De plus, elle nous permet simplement de vérifier que l’on n’a pas de problème de synchronisation, puisque son résultat est connu, et que l’on peut donc le vérifier. Si tu veux en savoir plus sur cette formule, cher lecteur, tu peux aller faire un tour sur ces deux pages de Wikipedia : celle de π, et celle sur la fontion ζ.

Voila l’algorithme utilisé pour ce calcul.

// size est un des paramètres de l'algorithme
ParallelDoubleArray a0 = ParallelDoubleArray.create(size, pool) ;

// chaque case du tableau vaut 1/index^2
IntAndDoubleToDouble mapper = new IntAndDoubleToDouble() {

	@Override
	public double op(int index, double d1) {
		double d = 1.0d/((double)(index + 1)*(double)(index + 1)) ;
		return d ;
	}
} ;

// la somme de toutes ces cases vaut π^2/6, enfin presque
Ops.DoubleReducer sum = new Ops.DoubleReducer() {

	@Override
	public double op(double d1, double d2) {
		return d1 + d2 ;
	}
} ;

// le calcul de ζ(2)...
double zeta2 = a0.withIndexedMapping(mapper).reduce(sum, 0d) ;
// ... puis celui de π
double pi = Math.sqrt(dzeta2*6.0d) ;

// on calcule l'erreur commise,
// que l'on peut tester par rapport à 1e-4
// cet algorithme ne converge pas spécialement vite...
double espilon = Math.abs(pi - Math.PI) ;

Le tableau suivant montre le résultat en faisant varier trois paramètres.

  • Le taux de parallélisation, que l’on fait varier de 1 à 4. La machine de votre serviteur comporte quatre cœurs. C’est en train de devenir une brouette ; si Java le soir me rend riche, je la changerai rapidement (je pense donc qu’elle va encore me servir quelques temps !).
  • La taille du tableau, et donc la précision de l’approximation.
  • Le nombre de fois que l’on fait tourner le calcul de π, de façon à garder un nombre d’itérations total constant.

On regarde le temps de calcul, par une méthode qui vaut ce qu’elle vaut, c’est-à-dire qu’elle est imprécise, tant il devient complexe de mesurer précisément les performances d’un JVM en calcul pur.

Qu’observe-t-on ?

Sur la colonne 500k, on fait tourner 10 mille fois le calcul de π avec un tableau de 500 mille lignes. On observe un gain substantiel lorsque l’on donne plusieurs CPU au framework. En revanche, lorsque l’on diminue la taille du tableau, on observe que ce gain diminue aussi, jusqu’à devenir un handicap : pour les petits tableaux (5 mille cases), il vaut mieux fonctionner en monothread qu’enmultithread !

[table id=3 use_tablesorter= »false »/]

Dans un monde idéal, on pourrait s’attendre à ce qu’en doublant les CPU, on double également les performances. Évidemment cela ne peut se produire, puisque que l’on doit payer la gestion du framework elle-même, et que, dès que l’on passe à plusieurs CPU, on doit aussi payer la synchronisation des opérations. Si l’on augmente le nombre de CPU, on peut même s’attendre à ce que ce coût de synchronisation augmente.

Le tableau suivant nous montre le déficit de performance que l’on a en fonction du nombre de CPU, pour chaque configuration du test. Par exemple, un déficit de 22% pour 2 CPU signifie qu’au lieu d’observer une augmentation des performances d’un facteur 2 (on a doublé le nombre de CPU), on observe une augmentation de 1,6. Idéalement, on devrait avoir un déficit de 0% (on peut toujours rêver !). Si l’on a un déficit de plus de 100%, cela signifie que le fait d’ajouter des CPU ralentit en fait le processus global, donc que la surcharge de gestion du framework et de la synchronisation devient inacceptable par rapport au calcul pur.

C’est ce que l’on observe lorsque l’on travaille sur des tableaux trop petits : le framework passe manifestement son temps à synchroniser les données d’un CPU à l’autre, ce qui fait perdre tout son intérêt à la parallélisation !

[table id=4 use_tablesorter= »false »/]

Conclusion

Comme on le voit, cette API expose des méthodes classiques de traitement de tableaux. La bonne approche pour l’utiliser est l’approche fonctionnelle, ce qui a ses avantages et ses inconvénients.

Personnellement, je regrette deux choses.

  • L’API ne permet pas d’effectuer les calculs « en place », ce qui permettrait de gagner en mémoire. Lorsque l’on en est à utiliser ce genre d’API, c’est que l’on a des calculs lourds à effectuer, sur de grands volumes de données. La bonne utilisation de la mémoire est le plus souvent cruciale.
  • L’API ne s’intéresse qu’aux tableaux. Si elle traite le cas très général des tableaux d’objets, au moins dans le cas des nombres (entiers ou flottants), elle aurait pu être étendue aux tableaux multidimensionnels, notamment aux matrices. De plus, les opérations exposées ne permettent pas de faire du calcul matriciel, ce qui est dommage. Disposer d’une API parallèle performante pour le calcul matriciel directement dans le JDK serait une réelle avancée. On n’en est pas loin, mais on n’y est pas encore !

Référence

La page de la JSR-166 : http://g.oswego.edu/dl/concurrency-interest/
La Javadoc du package extra166y : http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/