Java 7 : plus loin dans le fork / join

La présentation du framework fork / join, objet de notre épisode précédent ne comportait qu’un seul exemple. Cet exemple était simple, mais non trivial tout de même. J’y avais glissé une remarque, que, précieux et averti lecteur, tu n’auras pas manqué de relever en te disant : « encore une remarque en l’air, qui tombe à plat, ces blogs techniques, tous les mêmes ! ».

Cette remarque est la suivante :

Chaque calcul et chaîne de calcul doivent être exécutés dans la même réserve, pour des raisons que nous verrons plus loin.

Eh bien nous y sommes, au « plus loin ». Je te propose, précieux lecteur, d’explorer plus avant les choses, afin qu’aucune zone d’ombre ne subsiste dans ce merveilleux framework.

Un problème inattendu

Reprenons l’exemple précédent, qui consistait à initialiser une matrice avec des coefficients aléatoires. Il y en avait 20 millions, ce qui prenait suffisamment de temps pour faire un petit bench, sans avoir à y passer des heures.

Mettons en place un petit test très simple : initialisons une matrice avec l’algorithme précédent, et comptons le nombre de coefficients nuls dans la matrice ainsi calculée. Combien doit-on en trouver ? Probablement une quantité très faible, voire nulle.

Le code de comptage suivant devrait bien faire l’affaire.

// initialisation d'un pool
ForkJoinPool pool = new ForkJoinPool() ;

// initialisation d'une matrice
Matrix m = Matrix.randomMatrix(pool, 20000, 1000) ;

// comptage des coefficients nuls
long nulls = 0 ;
for (int i = 0 ; i < m.height() ; i++) {
	for (int j = 0 ; j < m.width() ; j++) {
		if (m.data()[i][j] == 0.0) {
			nulls++ ;
		}
	}
}
System.out.println("nulls = " + nulls) ;

Voici le résultat affiché sur ma machine :

nulls = 19205425

Évidemment, ce n’est pas tout à fait celui escompté ! De plus, si l’on fait tourner plusieurs fois ce code, on a toutes les chances d’obtenir un résultat différent à chaque fois.

Un résultat aléatoire (ou qui semble l’être) comme celui-la éveille tout de suite les sens : il doit y avoir un problème de concurrence d’accès quelque part. Et c’est effectivement le cas !

Notre matrice est initialisée dans un pool de threads, créé par la classe ForkJoinPool. Ce sont ces threads qui initialisent les coefficients de notre matrice. Lire les valeurs de ces coefficients ailleurs que dans ces threads crée une race condition. Comme dans tous les cas de race condition, la lecture est imprévisible : lit-on la dernière valeur écrite dans la variable, ou la valeur précédente ? On ne peut pas le dire a priori.

Et là, cher et précieux lecteur, je pense que tu peux aller allumer un cierge en remerciement aux dieux du Java (ou sacrifier un poulet, un taureau, un artichaut, ce que tu veux). Car Java initialise systématiquement les variables qu’il crée. Si cela n’avait pas été le cas, la race condition n’aurait pas pu être détectée aussi simplement, en comptant les valeurs nulles.

Si tu veux en savoir plus sur ce point, précieux lecteur, je te conseille un de mes précédents articles. Je sais, c’est très mal de se citer soi-même. Mais d’abord, si je ne le fais pas, qui le fera à ma place ? Et d’autre part, il y a en fin de cet article plusieurs très bonnes références.

Comment garantir que la lecture des coefficients de cette matrice se fait bien de façon synchrone ? Je vois deux méthodes :

  • éteindre le pool, ce qui est long, et franchement pas terrible ;
  • compter les coefficients nuls à l’aide d’une tâche lancée dans le pool, ce qui est nettement mieux.

Voyons ces deux méthodes en détails.

Lecture après extinction du pool

J’ai dit que cette méthode n’était pas terrible, et franchement, le meilleur moyen de te convaincre, précieux lecteur, c’est de te la montrer. Voyons le code pour fermer un pool.

// initialisation d'un pool
ForkJoinPool pool = new ForkJoinPool() ;

// initialisation d'une matrice
Matrix m = Matrix.randomMatrix(pool, 20000, 1000) ;

// fermeture du pool
// si b est false, alors le pool n'est pas encore fermé
// dépasser le timeout ne jette pas d'exception ici
boolean b = pool.awaitTermination(10, TimeUnit.SECONDS) ;

Encore une fois sur ma machine, la fermeture du pool prend environ une seconde ! C’est donc à une valeur très élevée qu’il faut fixer le timeout de fermeture, sans quoi la relecture des coefficients de la matrice reste non synchronisée.

Une fois le pool correctement fermé, la lecture est synchronisée, et le nombre de coefficients nuls est bien égal à 0, comme on peut s’y attendre.

Cela dit, on a franchement un problème de performance : on ne peut pas se permettre d’attendre 1s pour pouvoir exploiter notre matrice, et, par exemple, la multiplier à une autre. Cette attente rend l’utilisation du fork / join inutile : autant tout faire dans un thread unique.

Lecture dans le pool

Une autre solution, formellement meilleure, consiste simplement à exécuter notre tâche de comptage dans le pool, comme suit.

// initialisation d'un pool
ForkJoinPool pool = new ForkJoinPool() ;

// initialisation d'une matrice
final Matrix m = Matrix.randomMatrix(pool, 20000, 1000) ;

// comptage dans le pool
RecursiveTask<Long> countNullTask = new RecursiveTask<Long>() {

	@Override
	protected Long compute() {
		long nulls = 0 ;
		for (int i = 0 ; i < m.height() ; i++) {
			for (int j = 0 ; j < m.width() ; j++) {
				if (m.data()[i][j] == 0.0) {
					nulls++ ;
				}
			}
		}
		return nulls ;
	}
} ;

long nulls = pool.invoke(countNullTask) ;

Cette fois le nombre de coefficients nuls est bien de zéro, comme on s’y attendait.

L’examen des performances est un peu plus délicat. Résumons ces valeurs dans le tableau suivant.

parallélismeinitialisation (ms)relecture (ms)
1125650
2125890
31251180
41401800

La première remarque à faire pour comprendre les résultats de ce tableau est que le temps de lecture observé est en fait un temps de synchronisation entre ce qui a été écrit, et ce qui est relu. Effectivement, si l’on fait une deuxième lecture, identique à la première, dans tous les cas le deuxième temps de lecture vaut zéro. La deuxième lecture de notre matrice est instantanée, car il n’y a plus de synchronisation à faire.

Conclusion

Plus le nombre de threads utilisé est important, et plus la synchronisation est longue, ce qui est logique. Du coup, on observe que le cycle d’initialisation / lecture est toujours plus long en utilisant le framework fork / join qu’en utilisant un calcul classique monothread. Le framework fork / join n’est à mon avis pas adapté aux calculs qui retournent des matrices (ou des tableaux), du fait des problèmes de synchronisation en lecture.

Il s’agit cependant d’une conclusion partielle. Nous aurons l’occasion d’examiner d’autres patterns dans un futur proche.

Références

Les références ici sont les mêmes que celles de l’article précédent.

Les documentations utiles sont avant tout celles publiées par le groupe de travail du JSR 266 : http://g.oswego.edu/dl/concurrency-interest/.

La Javadoc du package java.util.concurrent : http://download.java.net/jdk7/docs/api/java/util/concurrent/package-summary.html, et notamment les classes ForkJoinPool,ForkJoinTask<V>RecursiveAction et RecursiveTask<V>.