Premiers benchmarks (expérimentaux) relatifs aux boucles vectorisées d'Abstrasy 2.0-beta2

Je suis heureux de pouvoir vous présenter (en avant première, car la révision qui a servi pour les tests si dessous n'est pas encore publiée au moment où j'écris ces lignes) les tous premiers résultats de tests de performances des opérateurs de boucles vectorisées d'Abstrasy 2.0-beta2.

Le test est très simple. Supposons que nous avons un tableau composé d'un million de nombres à virgule flottante de précision double (64 bits). Nous voulons calculer pour chaque nombre la formule suivante et remplacer le contenu du tableau par le résultat obtenu:

$$a_{i} = \sqrt{ | ( \arcsin( a_{i} ) \times 1000 )^{ 3.5 } | }$$

Bien sûr, cette formule n'a rien de particulier. C'est juste un moyen de réaliser un enchaînement d'opérations successives à partir de chaque élément du tableau a_i.

Commençons d'abord par une boucle classique pour avoir une idée de départ:

(define 'a (array-of-doubles 1000000))
(display "filling array-of-doubles...")
(for 'i (iterator (length a)){set! (a i) (random)})
 
 
(display "computing...")
(define 'd (now))
(for 'i (enumerator (length a)) {
  (set! (a i) (sqrt (abs (pow (* (asin (a i)) 1000) 3.5))) )
})
(define 'f (now))
 
(display "Time: " (int (- f d)) "ms.")
#(for 'x (enumerator a) {display x})

⇒

filling array-of-doubles...
computing...
Time: 1477ms.
Ready...
filling array-of-doubles...
computing...
Time: 1316ms.
Ready...
filling array-of-doubles...
computing...
Time: 1215ms.
Ready...
filling array-of-doubles...
computing...
Time: 1307ms.
Ready...
filling array-of-doubles...
computing...
Time: 1227ms.
Ready...

Nous évaluons le script ci-dessus plusieurs fois pour obtenir une idée du temps moyen pour réaliser la même suite d'opérations mathématiques sur un million de nombres flottants à double précision.

Le temps moyen obtenu est de 1308 ms.

Testons maintenant un script similaire, mais écrit cette fois en Javascript pour établir une comparaison…

a = new Array(1000000);
 
print("filling array-of-doubles...");
for(i=0;i<a.length;i++)
    a[i]=Math.random();
 
print("computing...")
d = new Date().getTime();
for(i=0;i<a.length;i++) {
    a[i] =  Math.sqrt( Math.abs( Math.pow( Math.asin(a[i])*1000, 3.5 ) ) );
}
f = new Date().getTime();
 
print("Time: " + (f-d) + "ms.");

⇒

luc:~$ js 'array-of-doubles_simple_set_loop.js' 
filling array-of-doubles...
computing...
Time: 1118ms.
luc:~$ js 'array-of-doubles_simple_set_loop.js' 
filling array-of-doubles...
computing...
Time: 1124ms.
luc:~$ js 'array-of-doubles_simple_set_loop.js' 
filling array-of-doubles...
computing...
Time: 1071ms.
luc:~$ js 'array-of-doubles_simple_set_loop.js' 
filling array-of-doubles...
computing...
Time: 1121ms.
luc:~$ js 'array-of-doubles_simple_set_loop.js' 
filling array-of-doubles...
computing...
Time: 1140ms.
luc:~$ 

Comme pour le script Abstrasy plus haut, on relance plusieurs fois le script pour estimer un temps moyen.

Le temps moyen obtenu par Rhino est de 1115 ms.

C'est mieux qu'avec l'interpréteur Abstrasy. L'interpréteur Javascript de Rhino est environ 15% plus performant que l'interpréteur Abstrasy dans ce cas.

Voyons à présent les résultats que nous pouvons obtenir simplement en vectorisant la boucle dans le script Abstrasy.

Nous testons donc la forme suivante:

(define 'a (array-of-doubles 1000000))
(display "filling array-of-doubles...")
(for 'i (iterator (length a)){set! (a i) (random)})
 
(display "computing...")
(define 'd (now))
 
(put a 0  (sqrt (abs (pow (* (asin (doubles a)) 1000) 3.5))) )
 
(define 'f (now))
 
(display "Time: " (int (- f d)) "ms.")
# (for 'x (enumerator a) {display x})

⇒

filling array-of-doubles...
computing...
Time: 714ms.
Ready...
filling array-of-doubles...
computing...
Time: 670ms.
Ready...
filling array-of-doubles...
computing...
Time: 668ms.
Ready...
filling array-of-doubles...
computing...
Time: 662ms.
Ready...
filling array-of-doubles...
computing...
Time: 669ms.
Ready...

Comme précédemment, nous faisons quelques essais et nous obtenons maintenant le temps moyen de 677 ms!…

Grâce à la vectorisation de la boucle, l'interpréteur est maintenant beaucoup plus performant.

Il nécessite un temps moyen 40% moindre que celui obtenu par Rhino.

Que s'est-il passé?…

On a simplement créé un vecteur de doubles à partir du tableau array-of-doubles. Ensuite, on applique toutes les opérations mathématiques comme si le vecteur n'était qu'un seul nombre à virgule flottante. Enfin, on replace le vecteur résultant dans le tableau à l'aide de put.

On constate que cette forme permet non seulement de faire abstraction de la boucle for, mais qu'en plus le résultat est obtenu beaucoup plus rapidement.

Le principe du SIMD est très simple : On considère le traitement des données par lots un à un.

La vectorisation permet de bénéficier d'une optimisation du type Single Instruction Multiple Data.

La JVM est capable de reconnaître les boucles qui peuvent bénéficier de ce type d'optimisation. Cependant, pour ce faire la JVM doit reconnaître ces boucles à partir du bytecode. Or, il s'avère que cela est beaucoup plus difficile à partir des classes obtenues à partir d'un compilateur dynamique (comme celui de Rhino) qu'à partir du compilateur statique javac. Ainsi, bien que compilant le Javascript en bytecode Java pour améliorer ses performances, Rhino ne peut pas bénéficier de l'optimisation des boucles vectorisées alors qu'Abstrasy le peut sans rien compiler du tout.

Pour obtenir ce résultat, Abstrasy propose des types particuliers qui bénéficient automatiquement et nativement de cette optimisation. La JVM reconnait sans aucune difficulté les boucles vectorisée dans le codes source de l'interpréteur Abstrasy (et non pas dans l'Abstract Syntax Tree du script en cours d'évaluation, cette optimisation est donc automatiquement répercutée sans nécessiter de compilation.

Rappelons qu'il ne faut pas confondre la vectorisation d'une boucle avec le fait de l'exécuter d'une manière parallélisée. Lorsqu'une boucle est vectorisée, son évaluation est parfaitement séquentielle (mais sa forme permet de traiter plusieurs données successives tout en réduisant le nombre d'opérations - on parle aussi de «déroulement de boucle»). Elle est évaluée par un seul Thread. Il est donc possible de lancer en parallèle l'évaluation simultanée de plusieurs boucles vectorisées sur une machine qui dispose de plusieurs unités de calculs (multi-CPUs).

Pour plus d'informations sur la vectorisation des boucles, voyez aussi cet article ce la Wikipédia Loop unwinding.