Quelques expériences de Dart avec LLVM

Dart est l’un des nombreux langages de programmation développés par Google. Il avait pour objectif premier de remplacer JavaScript dans les navigateurs (certaines versions préliminaires de Chrome avaient une machine virtuelle Dart), puis ses objectifs ont évolué pour être plus consensuels : un remplaçant potentiel de Java, mais avec toujours en tête l’idée de générer du code JavaScript très efficace. Le langage a donc un système de type dynamique et optionnel (les types des variables ne sont connus qu’à l’exécution), mais en limitant ses capacités dynamiques à la portion congrue (pas de fonction eval, pas d’ajout de propriétés à un objet après sa création).

Des ingénieurs de Google ont tenté une expérience : remplacer la machine virtuelle derrière l’implémentation standard de Dart par LLVM et une compilation avant l’exécution, voir si cela permettrait d’améliorer la performance à l’exécution, notamment — LLVM est l’infrastructure de compilation derrière Clang, notamment. La tâche n’est pas aisée a priori : la machine virtuelle de Dart effectue déjà un gros travail de compilation du code à la volée avec des optimisations. LLVM n’est pas non plus prévu pour des langages avec ramasse-miettes, qui perturbent ses routines d’optimisation du code.

De manière générale, une idée reçue est que l’implémentation d’un langage a droit à soit un ramasse-miette précis et efficace, soit un haut niveau d’optimisation du code. En effet, le ramasse-miette parcourt régulièrement les pointeurs sur de la mémoire allouée pour vérifier qu’elle est toujours utile ; après une passe d’optimisation, le code a tellement changé d’apparence qu’il est impossible de s’y retrouver. Une technique pour contourner le problème est de stocker les pointeurs dans une zone particulière, mais cela met en échec bon nombre d’optimisations possibles du code.

Il y a peu, LLVM a intégré une nouvelle fonctionnalité expérimentale, les points d’état, qui sert justement à laisser le compilateur effectuer ses optimisations sans perturber le fonctionnement d’un ramasse-miettes. Le principe est de marquer explicitement les modifications du code au ramasse-miettes, de telle sorte que, en cas de déplacement d’un objet en mémoire, tous les pointeurs concernés peuvent être mis à jour (plus d’informations dans la documentation de LLVM).

L’expérience s’est basée sur le code de Dartino, qui utilisait déjà LLVM pour optimiser du code Dart. Cependant, Dartino n’utilisait pas de ramasse-miettes, cette implémentation se limitait à lamentablement planter en cas de manque de mémoire. L’opération principale a été d’ajouter un ramasse-miettes à l’exécution et de le faire travailler de pair avec les optimisations. (Voir les détails d’implémentation.) Les résultats sont prometteurs : la performance est similaire à Flutter, qui a le même objectif (compiler du code Dart), tout en utilisant une infrastructure plus générique. Très peu de travail spécifique à Dart a été requis côté LLVM — certaines modifications pourraient augmenter la performance drastiquement, cependant. Des améliorations du ramasse-miettes pourraient aussi améliorer fortement la situation, les algorithmes actuellement utilisés pour cette expérience n’étant pas au même niveau que Flutter.

Globalement, l’objectif de cette “petite” expérience est atteint : oui, il est possible de mélanger LLVM, des optimisations très pointues du code, avec un ramasse-miettes, avec une performance tout à fait respectable.

Source : Dart-on-LLVM.

Advertisements

Les systèmes de JIT peuvent améliorer la performance des systèmes de gestion de bases de données

Les systèmes de gestion de bases de données traitent des volumes de données de plus en plus gros, avec des requêtes de plus en plus complexes, notamment pour la prise de décision. Les problèmes de performance du modèle relationnel ne viennent plus seulement de l’accès aux données sur les disques durs ou SSD, mais également du processeur, qui doit effectuer les opérations complexes.

Chaque système de gestion optimise les requêtes SQL avant de les exécuter… et ces techniques ont permis de garder un très bon niveau de performance jusqu’à présent. C’est d’ailleurs la raison pour laquelle SQL a pu s’imposer par rapport à des langages d’interrogation de plus bas niveau : ces requêtes peuvent s’exécuter plus vite que du code écrit spécifiquement pour chaque requête (à moins que chaque développeur passe énormément de temps à optimiser ce code). La requête est analysée, puis l’optimiseur détermine un plan d’exécution de la requête : comment itérer à travers les éléments d’une table, les filtrer, les agréger, mais surtout l’ordre de ces opérations.

Cependant, quand les accès au disque ne sont plus prépondérants dans les temps de réaction, repenser cette partie devient important. La situation actuelle revient à utiliser un interpréteur pour un langage de programmation avec des optimisations simples (comme Python). Les dernières expériences de la communauté LLVM (plus connue pour le compilateur C et C++ Clang) montrent que, en changeant de paradigme, on peut diminuer les temps d’exécution des requêtes les plus complexes d’un facteur cinq à sept (sur des tests synthétiques).

Pour ce faire, les développeurs ont utilisé des techniques similaires à celles utilisées pour les implémentations rapides de Python ou pour les machines virtuelles Java et .Net : la compilation juste à temps. Il s’agit donc de générer du code qui effectue la requête, puis de l’optimiser avec les mêmes techniques que les compilateurs C et C++, notamment : elles sont éprouvées et donnent d’excellents résultats sur n’importe quel type de programme.

L’extension développée pour PostgreSQL exploite une bonne partie du code d’exécution déjà développé. Ainsi, les fonctions de base d’accès à la base de données sont réutilisés (comme pour itérer dans une table), puis appelées depuis le code de la requête : le tout est passé au moteur de compilation juste à temps (JIT). Il inclut automatiquement le code des primitives de PostgreSQL dans celui de la requête, ce qui lui permet d’optimiser fortement le fonctionnement du code complet.

Ces premiers développements sont assez partiels, toutes les opérations ne sont pas accélérées de la sorte, mais les résultats actuels sont prometteurs. Le fonctionnement global est améliorable, puisque l’implémentation est loin d’être peaufinée. Notamment, la compilation peut s’effectuer de manière parallèle. Après ces étapes de nettoyage, cette extension pourra être distribuée au plus grand nombre sous une licence libre.

Source : Speeding up query execution in PostgreSQL using LLVM JIT compiler.

Sortie de LLVM 3.9

La suite de compilateurs LLVM a vu une nouvelle version biannuelle paraître à la mi-août, avec quelques nouveautés intéressantes dans le domaine du calcul de haute performance (OpenCL, OpenMP), notamment, mais aussi pour diminuer les temps de compilation avec les optimisations lors de l’édition des liens (LTO).

Nouveautés pour LLVM

LLVM fournit un nouveau mode pour effectuer une passe LTO sur le code compilé. ThinLTO diminue drastiquement les besoins en mémoire et s’exécute nettement plus vite qu’une passe LTO habituelle, mais sans atteindre les mêmes gains en performance pour les exécutables générés. La manière de penser est radicalement différente : ThinLTO est prévu pour s’exécuter massivement en parallèle, en n’utilisant que des résumés des différents modules à optimiser pour les passes globales.

Au niveau des plateformes, LLVM peut générer des binaires pour les nouveaux processeurs Intel (génération Skylake, ainsi que les coprocesseurs Xeon Phi) en utilisant les instructions AVX-512. Côté ARM, les processeurs Qualcomm Kryo et Broadcom Vulcan sont gérés (les cœurs Cortex M8 et l’architecture ARMv8.2-A le sont de manière expérimentale).

Pour effectuer ses optimisations, la suite de compilation utilise une analyse de la mémoire utilisée par le code, principalement des interactions entre les opérations. Celle-ci est, jusqu’à présent, effectuée par une passe MemoryDependenceAnalysis, dont les inconvénients sont la lenteur et le manque de précision. Elle devrait être remplacée par MemorySSA, dont la complexité algorithmique est linéaire en la taille du code (quadratique pour MemoryDependenceAnalysis). Cette passe travaille sur une représentation virtuelle des opérations en mémoire sous forme SSA.

Nouveautés pour Clang

Le compilateur phare autour du projet LLVM est, sans nul doute, Clang, un compilateur pour les langages de la famille du C (principalement, le C++, mais aussi Objective-C, OpenCL ou encore CUDA).

La version 3.9 implémente maintenant complètement OpenCL 2.0, avec des fonctionnalités comme la conversion entre les espaces d’adressage de l’hôte et du périphérique et de meilleurs messages de diagnostic pour les noyaux OpenCL.

Côté OpenMP, la version 4.5 de la norme est maintenant complètement implémentée, à l’exception des parties sur le déchargement du code sur un accélérateur (l’infrastructure est toujours en chantier) — cela signifie que OpenMP est géré jusqu’à la version 3.1 complètement, puis seulement en partie pour les versions 4.0 et 4.5. Les nouveautés incluent des données membres dans des clauses statiques de fonctions non statiques et l’utilisation de telles variables comme itérateurs de boucle. Le code généré est aussi bien plus stable et rapide.

Comme pour chaque version, les analyses de code ont été améliorées. Pour cette fois, une nouvelle passe vérifie l’utilisation de l’API MPI. Sous Windows, les tests pour les fuites de mémoire, les doubles libérations de mémoire et les utilisations après libération sont activées par défaut.

Sources : notes de version de LLVM et de Clang.

Sortie de Qt 5.8 Alpha

Qt 5.8 Alpha est maintenant sorti. Cette version mineure apporte pas mal de nouveautés, mais les principales se situent sous le capot et n’auront pas vraiment d’impact pour le programmeur.

Celle qui a fait couler probablement le plus d’encre est une refactorisation à grande échelle du moteur de rendu de Qt Quick : la dépendance envers OpenGL a été fortement limitée, l’architecture globale du rendu est maintenant totalement agnostique en ce qui concerne l’API utilisée. Ces changements ont permis l’intégration du moteur de rendu purement logiciel qui était fourni avec les éditions commerciales de Qt, mais aussi la création d’une extension (expérimentale) qui utilise DirectX 12 pour le rendu. Rien n’est actuellement prévu pour Vulkan, les développeurs estimant que les gains en performance ne justifieront pas ce développement.

Le moteur d’exécution QML (le langage prévu pour Qt Quick) a également été fortement amélioré, en ce qu’il met maintenant en cache une forme binaire précompilée des fichiers QML chargés. Ainsi, le démarrage des applications QML est bien plus rapide que précédemment (sans chercher à se passer de QML et d’écrire ses applications Qt Quick uniquement en C++). Ces changements n’impliquent pas la possibilité de précompiler une application Qt Quick (qui reste l’apanage de l’édition commerciale).

Dans le monde de l’embarqué, l’espace est une denrée rare, tant pour le stockage qu’en mémoire vive… et Qt en occupe vite une belle quantité. Dans le cadre du projet Qt Lite, l’infrastructure de configuration de Qt a été retravaillée pour sélectionner les fonctionnalités nécessaires à l’intérieur de chaque module. Le travail est toujours en cours, mais continuera d’ici à la préversion Beta. Jusqu’à présent, il est possible de diminuer la taille d’une application Qt Quick (liée statiquement à Qt) de septante pour cent par rapport à Qt 5.6 — ce qui est un gain appréciable.

Certains modules quittent le statut de préversion technologique et sont maintenant pleinement supporté par le Qt Project (notamment, les évolutions de leur API ne pourront pas casser la compatibilité avec les prochaines versions de Qt 5). Ainsi, Qt Wayland Compositor, Qt SCXML et Qt Serial Bus sont ouverts au plus grand nombre, sans arrière-pensée. De nouveaux modules font aussi leur apparition comme préversions technologiques : Qt Speech pour la reconnaissance et la synthèse vocales, Qt Network Authentication pour l’authentification (notamment avec le protocole OAuth, versions 1 et 2).

Qt 5.8 Beta devrait arriver dans un mois, début octobre, avant une version finale fin novembre. Si tout se passe bien, évidemment.

Télécharger Qt 5.8 Alpha.

Source : Qt 5.8 Alpha released.

LLVM lance un nouveau projet : parallel-lib

Il y a trois mois, Google proposait son projet StreamExecutor à LLVM. Cette bibliothèque sert à lancer des calculs sur des processeurs graphiques et d’autres types d’accélérateurs, principalement pour leur solution d’apprentissage profond TensorFlow. L’avantage est de disposer d’un système unique pour lancer des calculs sur ce type d’accélérateur, sans dépendre de la bibliothèque qui sera effectivement utilisée pour les calculs. Cette couche d’abstraction ne fait “que” gérer l’évolution des calculs sur les accélérateurs selon le concept de flux (emprunté à NVIDIA CUDA), d’où le nom de la bibliothèque. Ce projet StreamExecutor s’inscrit notamment dans la lignée d’OpenMP 4, avec la possibilité de décharger une partie du code sur des accélérateurs à l’aide d’une directive spécifique (offload).

Suite à cette proposition de code de la part de Google, après quelques mois de discussions, lancées par la proposition de Google, LLVM lance un nouveau sous-projet orienté programmation concurrente : parallel-libs. Ce projet est présenté comme un parallèle concurrent à compiler-rt, qui rassemble diverses fonctionnalités (implémentation générique d’instructions non disponibles sur certains processeurs, assainisseurs de code, etc.).

En quelques mots, les objectifs de parallel-libs sont plus étendus que ceux de StreamExecutor : ce sous-projet pourra contenir des moteurs d’exécution comme celui d’OpenMP, des bibliothèques d’accès au matériel à l’instar de StreamExecutor, voire des fonctions mathématiques implémentées en parallèle. La seule contrainte pour une inclusion dans parallel-libs est d’être à la croisée des chemins des compilateurs et de l’exécution concurrente, ce qui permettra de partager du code.

Pour le moment, les décisions sont prises, mais le projet n’a pas encore d’existence physique (pas d’emplacement sur le dépôt SVN de LLVM, pas de liste de diffusion). Cela ne devrait pas tarder. D’ailleurs, IBM pourrait rejoindre la danse, avec leurs projets d’interface unique pour lancer du code, que ce soit avec CUDA ou OpenMP, pour lesquels un premier commit est arrivé.

Source : [llvm-dev] parallel-lib: New LLVM Suproject.

Un nouvel optimiseur de code pour Visual C++

Les compilateurs sont des programmes informatiques d’une importante complexité. Ils sont généralement structurés en une partie frontale, qui comprend le langage d’entrée, puis d’une partie arrière, qui s’occupe de traduire le programme d’entrée en du code binaire exécutable par le processeur. Les deux parties communiquent à l’aide d’une représentation intermédiaire (IR). Ainsi, pour qu’une même suite de compilateurs comprenne plusieurs langages et puisse générer du code pour plusieurs processeurs, il n’est pas nécessaire d’écrire un compilateur spécifique pour chaque paire langage-processeur : il suffit d’écrire les paires langage-IR et IR-processeur. Tout le travail effectué pour un processeur sera alors utilisable pour n’importe quel langage d’entrée.

Dès la génération du code intermédiaire, un compilateur utilise énormément de passes d’optimisation, afin de rendre le code plus rapide. Elle utilise des techniques comme la propagation des valeurs : si une variable a une valeur connue à un endroit du code (initialisation, condition…), alors cette valeur peut être propagée dans une série de calculs, qui seront alors effectués à la compilation au lieu de l’exécution. Ces passes sont effectuées en partie sur la représentation intermédiaire, pour les optimisations indépendantes du processeur, mais également sur du code machine déjà généré, pour tirer le meilleur parti possible du matériel.

Généralement, cette phase d’optimisation est extrêmement cruciale, étant donné que la représentation intermédiaire est suffisamment générale pour plusieurs types de processeurs et relativement simple dans les instructions disponibles : pour effectuer certaines opérations, il est parfois nécessaire d’écrire des dizaines d’instructions IR, alors que certains processeurs peuvent réaliser la même opération en une seule instruction. De plus, une représentation intermédiaire doit être prête pour les phases d’optimisation qui suivent, notamment en simplifiant toutes les étapes de raisonnement : dans les IR de type SSA, notamment, une variable ne peut être assignée qu’une seule fois, ce qui allonge d’autant plus le code.

Un nouvel optimiseur pour Visual C++

Le compilateur C++ de Microsoft, connu sous le nom de Visual C++, a longtemps été laissé dans un état proche de l’abandon. Depuis quelques années, les équipes de développement ont mis les bouchées doubles pour ramener le compilateur dans la course, avec une compatibilité avec les normes les plus récentes, au niveau de GCC ou Clang. Depuis lors, ils ont effectivement rattrapé en grande partie leur retard à ce niveau, mais pas encore pour les optimisations du code.

L’optimiseur actuel ne disposait que d’une série de transformations assez basiques, n’exploitant qu’une vue assez limitée des fonctions. Bon nombre d’optimisations fonctionnent en trouvant des motifs et en les remplaçant par une version améliorée, mais tous les motifs les plus utiles ne sont pas toujours implémentés. De plus, le code vectorisable n’est pas optimisé au meilleur de ses possibilités. Toutes ces limitations ont une origine historique : le compilateur C++ de Microsoft a des origines très anciennes, il provient de l’époque DOS où la mémoire était très limitée, ce qui limite les possibilités. Les efforts actuels portent principalement sur une modernisation du code, en éliminant les compromis d’un autre âge.

Le nouvel optimiseur exploite désormais une représentation intermédiaire SSA. Les algorithmes implémentés par-dessus peuvent ainsi être plus efficaces en temps par rapport aux approches par analyse du flux de données. Il se base sur une bibliothèque C++ avancée, exploitant les templates à foison, pour décrire les transformations à effectuer, ce qui a permis d’ajouter bon nombre d’optimisations simples en très peu de temps (surtout par rapport à l’infrastructure précédente).

Les développeurs de Visual C++ indiquent également avoir prêté attention à la correction de ces optimisations : il n’y a rien de plus désagréable que de passer des journées à déboguer son code pour trouver que, finalement, le problème n’est pas dû au code, mais bien au compilateur. Linus Torvalds a récemment torpillé GCC à ce sujet. Ici, les développeurs ont absolument cherché à éviter ces écueils, en testant leurs passes d’optimisation sur des programmes courants comme Chrome ou Firefox, puis sur des bibliothèques imposantes côté Microsoft comme CoreCLR ou Chakra.

Ils ont aussi employé des techniques de vérification formelle (à l’aide d’ALIVE et l’outil de démonstration automatique Z3, tous deux issus de Microsoft Research et aussi utilisés pour LLVM) et de la génération de code aléatoire avec Csmith (et C-Reduce pour réduire le code posant problème au strict minimum). Certains outils du projet LLVM ont pu être utilisés, puisque Visual C++ peut en exploiter les parties avant, comme Opt-fuzz, qui génère des expressions arithmétiques à optimiser.

Un exemple

Ces nouvelles optimisations peuvent avoir un effet assez radical sur certains bouts de code. Par exemple, pour un test de parité :

[cce lang=”cpp”]int test(int a) {
return a % 2 != 0 ? 4 : 2;
}[/cce]

Les précédentes versions du compilateur produisaient un code qui prenait entre cinq et dix cycles en x86, selon que tout le processeur est exploité (prédiction du branchement parfaite) ou non :

[cce lang=”asm”]?test@@YAHH@Z PROC
and ecx, -2147483647
jge SHORT $LN3@test
dec ecx
or ecx, -2
inc ecx
$LN3@test:
test ecx, ecx
mov eax, 2
mov edx, 4
cmovne eax, edx
ret 0[/cce]

Sauf que… Dans le test [ccei lang=”cpp”]a % 2 == 0[/ccei], le signe de [ccei lang=”cpp”]a[/ccei] n’a aucune espèce d’importance, seul un bit est important : le modulo peut être remplacé par une opération logique, c’est-à-dire [ccei lang=”cpp”]a & 1 == 0[/ccei]. Or, la comparaison implique un branchement dans le code, forcément lent sur les architectures x86 modernes : pour s’en débarrasser, la structure [ccei lang=”cpp”]bool(a) ? C1 : C2[/ccei] peut être remplacée par [ccei lang=”cpp”]C2 + a*(C1-C2)[/ccei], c’est-à-dire exclusivement des calculs. Par conséquent, le nouveau code assembleur est le suivant :

[cce lang=”asm”]?test@@YAHH@Z PROC
and ecx, 1
lea eax, DWORD PTR [rcx*2+2]
ret 0[/cce]

Celui-ci prend, à tous les coups, deux cycles d’horloge : par rapport à cinq à dix cycles, le gain est important, tant en rapidité qu’en taille de l’exécutable.

D’autres mécanismes effectuent une analyse statique du code, en précalculant autant de bits que possible dans les variables. Par exemple, lors d’une conversion vers un type plus grand, une série de bits est forcément à zéro, peu importe la valeur d’entrée. Ensuite, cette information peut être adaptée en fonction des opérations effectuées, ce qui peut guider le reste du processus.

[cce lang=”cpp”]int test(unsigned char a) {
short b = a; // b: 00000000________, a: ________
b <<= 4; // b: 0000________0000
b |= 3; // b: 0000________0011
return b != 0; // -> return true
}[/cce]

Impact sur la taille du code généré

L’impact de ces modifications sur le code généré n’est pas facile à établir : certaines optimisations diminuent forcément la quantité de code, le compilateur sera alors plus enclin à recopier in extenso le code de petites fonctions pour éviter le surcoût dû à tout appel de fonction (qui n’est négligeable que pour des fonctions plus grandes) — ce qui conduit à l’augmentation de la taille du code. Il n’empêche, les résultats sont intéressants : sur tout Windows, c’est-à-dire plus d’un gigaoctet, les gains sont de 438 Ko par rapport à l’optimiseur précédent (0,3 %) ; sur SQL Server, 46 Ko sur 64 Mo (0,8 %) ; sur Chakra, le nouveau moteur JavaScript, 10 Ko sur 6 Mo (1,7 %).

En analysant plus en détail l’impact au niveau des instructions, les plus lentes sont largement évitées (branchements, multiplications, divisions), remplacées par des opérations plus rapides (comme des déplacements conditionnels). Les temps de compilation ont été impacté de diverses manières : une augmentation de 1,7 % pour Chrome ou une diminution de 2,6 % pour le noyau Windows.

Et alors ?

Les travaux sur l’optimiseur viennent seulement d’être annoncés : l’architecture choisie permettra aux développeurs d’ajouter des optimisations supplémentaires rapidement (et certaines sont déjà en cours de planification). Cet optimiseur devrait arriver dès Visual C++ 2015 Update 3, mais le travail continuera sur cet aspect du compilateur, afin de le rendre compétitif par rapport à ses concurrents, voire de les dépasser. Il est d’ores et déjà possible de le tester.

Source : Introducing a new, advanced Visual C++ code optimizer.
L’image a été créée par l’auteur et est soumise au droit d’auteur.