JetBrains – les secrets cachés de la compilation rapide pour Kotlin

Andrey Breslav

Traducteur

Delphine Massenhove

Pour réagir au contenu de ce tutoriel, un espace de dialogue vous est proposé sur le forum. Commentez

- Titre : JetBrains – les secrets cachés de la compilation rapide pour Kotlin

- Auteur : Andrey Breslav

- Traducteur : Delphine Massenhove

- Parution : 31 octobre 2020

- Licence : Copyright ® 2020 Andrey Breslav. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Préambule

- II. Pourquoi la compilation prend-elle autant de temps ?

- III. La position de Kotlin

- IV. Un compilateur peut-il être intelligent et rapide à la fois ?

- V. Éviter de compiler

- V-1. Suivi les modifications de l’ABI

- V-2. Avantages et inconvénients de l’évitement de compilation

- VI. La compilation incrémentale

- VI-1. Compiler les fichiers ayant été modifiés depuis la dernière compilation (dirty files)

- VI-2. Étendre l’ensemble de fichiers modifiés (dirty files)

- VI-3. La compilation incrémentale au-delà des limites des modules

- VII. Points non abordés dans cet article

- VIII. En résumé

- IX. Remerciements Developpez.com

I - Préambule

Il est difficile de compiler rapidement beaucoup de code, surtout lorsque le compilateur doit effectuer des analyses complexes telles que la résolution de surcharge et l’inférence de type avec des génériques. Dans cet article, j’aborde un aspect peu visible, mais essentiel de Kotlin qui rend beaucoup plus rapide sa compilation sur les petites modifications qui se produisent souvent dans les activités quotidiennes d’exécution/test/débogage.

Commençons par l’incontournable bande dessinée XKCD #303

Cet article traite d’un aspect très important du travail de tout développeur : combien de temps faut-il pour effectuer un test (ou juste atteindre la première ligne de votre programme) après avoir effectué une modification dans le code. C’est ce qu’on appelle le temps de test.

Pourquoi est-ce si important :

- si la durée du test est trop courte, vous n’avez même pas le temps de prendre un café (ou de commencer un combat à l’épée avec un collègue) ;

- si elle est trop longue, vous vous perdez sur les réseaux sociaux ou êtes distraite par autre chose et finalement vous en arrivez à oublier quelle modification vous avez apportée.

On peut considérer que les deux situations ont leurs avantages et leurs inconvénients, mais je pense qu’il est préférable de faire des pauses quand vous le souhaitez et non lorsque votre compilateur vous l’impose. Les compilateurs sont des logiciels intelligents, mais pas au point de pouvoir définir les meilleurs horaires de travail pour les humains.

En tant que développeurs, nous sommes généralement plus satisfaits lorsque nous nous sentons productifs. Les pauses dues à la compilation interrompent le déroulement des tâches et nous donnent l’impression d’être bloqués, stoppés dans notre élan, improductifs. Peu de gens apprécient cela.

II - Pourquoi la compilation prend-elle autant de temps ?

Il y a généralement trois raisons principales pour lesquelles les temps de compilation sont longs :

1. La taille de la base de code : la compilation d’un MLOC prend généralement plus de temps que celle d’un KLOC ;

2. Le niveau d’optimisation de votre chaîne d’outils, ce qui inclut le compilateur lui-même et tous les outils de build que vous utilisez ;

3. Le niveau d’intelligence du compilateur : trouve-t-il beaucoup d’éléments seul ou a-t-il constamment besoin de l’utilisateur et de code standard.

Les deux premiers facteurs étant assez évidents, parlons plutôt du troisième : l’intelligence du compilateur. Avec Kotlin, nous avons opté pour un code lisible, propre et sûr. Cela implique que le compilateur puisse être assez intelligent et voici pourquoi.

III - La position de Kotlin

Kotlin est conçu pour être utilisé dans un cadre « industriel », pour des projets qui ont une longue durée de vie, évoluent et impliquent beaucoup de monde. Nous voulons donc une sécurité de type statique pour détecter rapidement les bugs et disposer d’outils précis (saisie semi-automatique, refactorisations, recherche d’utilisations dans l’EDI, navigation précise dans le code, etc.). Nous souhaitons également avoir un code propre et lisible, sans « bruit » inutile. C’est pourquoi, entre autres, nous ne voulons pas de types partout dans le code et avons des algorithmes d’inférence de type et de résolution de surcharge intelligents qui prennent en charge les fonctions de type lambda et extensions, la conversion intelligente (typage basé sur le flux), etc. Dans le même temps, le compilateur Kotlin trouve un grand nombre d’éléments par lui-même pour garder le code propre.

IV - Un compilateur peut-il être intelligent et rapide à la fois ?

Pour qu’un compilateur intelligent fonctionne rapidement, vous devez impérativement optimiser chaque élément de la chaîne d’outils, et c’est un élément sur lequel nous travaillons en permanence. Nous travaillons entre autres sur un compilateur Kotlin nouvelle génération qui fonctionnera beaucoup plus vite que le compilateur actuel. Mais il ne s’agit pas de cela dans cet article.

Aussi rapide que soit un compilateur, il ne sera jamais trop rapide pour un gros projet. Et recompiler l’ensemble de la base de code sur chaque petit changement effectué pendant le débogage représente une perte de temps énorme. Nous essayons donc de réutiliser autant que possible les compilations précédentes et de ne compiler que lorsque c’est absolument nécessaire.

Il y a principalement deux approches pour réduire la quantité de code à recompiler :

- éviter la compilation : ne recompiler que les modules affectés ;

- utiliser la compilation incrémentale : ne recompiler que les fichiers affectés.

(On pourrait penser à une approche encore plus précise qui permettrait de suivre les changements dans les fonctions ou les classes individuelles et donc de recompiler encore moins qu’un fichier, mais je ne vois pas de mise en œuvre pratique pour une telle approche dans les langages industriels, et dans l’ensemble cela ne semble pas nécessaire.)

Examinons maintenant plus en détail les deux approches.

V - Éviter de compiler

Cette approche consiste principalement à :

- trouver les fichiers modifiés (« dirty files ») ;

- recompiler les modules auxquels ces fichiers appartiennent (en utilisant les résultats de la compilation précédente des autres modules comme dépendances binaires) ;

- déterminer quels autres modules peuvent être affectés par les modifications

- les recompiler également et vérifier aussi leurs ABI,

- répéter l’opération jusqu’à ce que tous les modules concernés soient recompilés.

L’algorithme est plus ou moins facile à comprendre si vous savez comment comparer les ABI. Sinon, il faut recompiler les modules qui ont été affectés par les modifications. Bien entendu, une modification d’un module dont personne ne dépend se compilera plus rapidement qu’une modification dans le module « util » dont tout le monde dépend (si cela affecte son ABI).

V-1 - Suivi les modifications de l’ABI

Une ABI (interface binaire d’application) équivaut à une API mais pour les binaires. L’ABI est la seule partie du binaire qui intéresse les modules dépendants (Kotlin ayant une compilation séparée, mais nous n’aborderons pas ce point ici).

En gros, un binaire Kotlin (que ce soit un fichier de classe JVM ou un KLib) contient des déclarations et des corps de fonctions. D’autres modules peuvent référencer des déclarations, mais pas toutes les déclarations. Ainsi, les classes privées et les membres, par exemple, ne font pas partie de l’ABI. Un corps de fonction peut-il faire partie d’une ABI ? Oui, si ce corps est inline à l’endroit de l’appel. Kotlin dispose de fonctions inline et de constantes de temps de compilation (« const val »). Si un corps d’une fonction inline ou une valeur d’une constante change, il peut être nécessaire de recompiler les modules dépendants.

Ainsi, l’ABI d’un module Kotlin est constituée de déclarations, de corps de fonctions inline et de valeurs « const val » visibles à partir d’autres modules.

Pour détecter facilement une modification de l’ABI :

- stockez l’ABI de la compilation précédente (stockez les hachages par souci d’efficacité) ;

- après avoir compilé un module, comparez le résultat avec l’ABI stockée :

- si le résultat est le même, c’est fini,

- sinon, recompilez les modules dépendants.

V-2 - Avantages et inconvénients de l’évitement de compilation

Le principal avantage de l’évitement de compilation est sa relative simplicité.

Cette approche est vraiment utile lorsque les modules sont petits, car l’unité de recompilation est un module entier. Pour les gros modules, les recompilations seront longues. Éviter la compilation requiert donc d’avoir un nombre important de petits modules et ce n’est pas forcément ce qu’un développeur veut. Les petits modules ne sont pas nécessairement mal conçus, mais je préfère structurer mon code pour les personnes et non pour les machines.

Par ailleurs, de nombreux projets ont un module « util » qui comprend beaucoup de petites fonctions utiles. Et pratiquement tous les autres modules dépendent de ce module « util », au moins de façon transitoire. Supposons maintenant que je veuille ajouter une autre petite fonction utile qui est utilisée trois fois dans ma base de code. Elle s’ajoute au module ABI, tous les modules dépendants sont affectés, et je me retrouve à attendre, car tout mon projet est recompilé.

De plus, en ayant beaucoup de petits modules (chacun d’eux dépendant de plusieurs autres) la configuration de mon projet peut devenir énorme, car chaque module comporte un ensemble unique de dépendances (sources et binaires). La configuration de chaque module dans Gradle prend normalement entre 50 et 100 ms. Il n’est pas rare que les grands projets comportent plus de 1 000 modules, le temps total de configuration peut alors largement dépasser une minute. Et la configuration doit être exécutée pour chaque build et à chaque fois que le projet est importé dans l’EDI (par exemple lorsqu’une nouvelle dépendance est ajoutée).

Un certain nombre de fonctionnalités de Gradle atténuent quelques-uns des inconvénients liés à l’évitement de compilation : par exemple, les configurations peuvent être mises en cache. Cependant, la marge d’amélioration reste encore assez importante et c’est pourquoi nous utilisons la compilation incrémentale dans Kotlin.

VI - La compilation incrémentale

La compilation incrémentale est une approche plus granulaire que l’évitement de compilation : elle s’applique aux fichiers individuels plutôt qu’aux modules. En conséquence, elle ne se préoccupe pas de la taille des modules et ne recompile pas l’ensemble du projet lorsqu’une ABI d’un module « populaire » est modifiée de manière insignifiante. En général, cette approche est moins restrictive pour l’utilisateur et réduit le temps de test. Les développeurs sont ainsi moins enclins à se lancer dans des combats à l’épée.

La compilation incrémentale est depuis toujours prise en charge par JPS, le système de build intégré d’IntelliJ. Gradle ne prend en charge que les évitements de compilation par défaut. À partir de la version 1.4, le plugin Kotlin Gradle apporte à Gradle une implémentation quelque peu limitée de la compilation incrémentale et la marge de progression est encore importante.

Idéalement, il suffirait d’examiner les fichiers modifiés, de déterminer exactement quels fichiers en dépendent et de recompiler tous ces fichiers. Cela peut sembler facile, mais en réalité, il n’est pas du tout évident de déterminer avec précision cet ensemble de fichiers dépendants. En effet, il peut y avoir des dépendances circulaires entre les fichiers sources, ce qui n’est pas autorisé pour les modules dans la plupart des systèmes de build modernes. De plus, les dépendances des fichiers individuels ne sont pas déclarées explicitement. Notez que les importations ne sont pas suffisantes pour déterminer les dépendances en raison des références au même paquet et aux mêmes appels de chaînes : pour A.b.c(), nous devons importer au maximum A, mais les changements au niveau de B nous affecteront également.

En raison de toutes ces complications, la compilation incrémentale tente de déterminer approximativement l’ensemble des fichiers concernés en procédant en plusieurs cycles qui consistent à :

- trouver les fichiers modifiés (« dirty files ») ;

- les recompiler (en utilisant les résultats de la compilation précédente comme dépendances binaires au lieu de compiler d’autres fichiers sources) ;

- vérifier si l’ABI correspondant à ces fichiers a changé

- si ce n’est pas le cas, c’est bon ,

- si c’est le cas, il faut trouver les fichiers affectés par les modifications, les ajouter à l’ensemble de fichiers modifiés et les recompiler,

- répéter l’opération jusqu’à ce que l’ABI se stabilise (c’est ce qu’on appelle un « point fixe »).

Comme nous savons déjà comment comparer les ABI, il n’y a en fait que deux problèmes qui peuvent se poser :

1. Utiliser les résultats de la compilation précédente pour compiler un sous-ensemble arbitraire de sources ;

2. Identifier les fichiers affectés par un ensemble de modifications donné de l’ABI.

Les deux sont au moins en partie des fonctionnalités de la compilation incrémentale de Kotlin. Examinons-les plus en détail.

VI-1 - Compiler les fichiers ayant été modifiés depuis la dernière compilation (dirty files)

Le compilateur sait comment utiliser un sous-ensemble des résultats de la compilation précédente afin d’éviter la compilation des fichiers n’ayant pas été modifiés depuis (non dirty files) et de charger seulement les symboles définis dans ces derniers pour produire les binaires pour les fichiers ayant été modifiés (dirty files). Un compilateur ne serait pas forcément capable de faire cela en l’absence d’incrémentalité : produire un gros binaire à partir d’un module au lieu d’un petit binaire par fichier source n’est pas si courant en dehors du monde de la JVM. Et il ne s’agit pas d’une fonctionnalité du langage Kotlin, c’est un détail de l’implémentation de la compilation incrémentale.

En comparant les ABI des fichiers ayant été modifiés aux résultats précédents, nous pouvons découvrir que nous avons de la chance et qu’aucun autre cycle de recompilation n’est nécessaire. Voici quelques exemples de modifications qui requièrent seulement la recompilation des fichiers ayant été modifiés (dirty files) car l’ABI n’est pas affectée :

- commentaires, littéraux de chaîne (sauf pour les « const val ») et autres

exemple : modifier quelque chose dans le résultat du débogage ;

- modifications se limitant aux corps de fonction qui ne sont pas inline et n’affectant pas l’inférence du type de retour

exemple : ajouter/supprimer un résultat de débogage ou modifier la logique interne d’une fonction ;

- modifications limitées aux déclarations privées (elles peuvent être privées au niveau des classes ou des fichiers)

exemple : introduire ou renommer une fonction privée ;

- réorganisation les déclarations.

Comme vous pouvez le constater, ces cas sont assez fréquents lors du débogage et de l’amélioration itérative du code.

VI-2 - Étendre l’ensemble de fichiers modifiés (dirty files)

Si nous ne sommes pas très chanceux et qu’une déclaration a été modifiée, certains fichiers qui dépendent de ceux qui ont été modifiés pourraient produire des résultats différents lors de la recompilation, même lorsqu’aucune ligne de leur code n’a été modifiée.

La stratégie la plus simple serait d’abandonner à ce stade et de recompiler tout le module. Cela met en évidence tous les problèmes liés à l’évitement de compilation : les modules volumineux qui deviennent problématiques dès que vous modifiez une déclaration et de nombreux petits modules qui ont également un coût en termes de performance, comme décrit plus haut. Il faut donc avoir une approche plus granulaire : trouver les fichiers concernés et les recompiler.

Nous voulons donc identifier les fichiers qui dépendent des parties de l’ABI qui ont effectivement changé. Par exemple, si l’utilisateur a renommé foo en bar, il faut seulement recompiler les fichiers contenant les noms foo et bar et ne pas toucher aux autres fichiers, même s’ils font référence à d’autres parties de cette ABI. Le compilateur incrémental se souvient des fichiers qui dépendent de telle ou telle déclaration de la compilation précédente et nous pouvons utiliser ces données un peu comme un graphique de dépendance de module. Là encore, il s’agit d’une opération que les compilateurs non incrémentaux n’effectuent pas normalement.

Idéalement, pour chaque fichier, nous devrions stocker les fichiers qui en dépendent et les parties de l’ABI qui les intéressent. En pratique, il est trop coûteux de stocker toutes les dépendances avec autant de précision. Et dans de nombreux cas, il est inutile de conserver des signatures complètes.

Prenons cet exemple :

Fichier : dirty.kt

// rename this to be 'fun foo(i: Int)'
fun changeMe(i: Int) = if (i == 1) 0 else bar().length

Fichier : clean.kt

fun foo(a: Any) = ""
fun bar() =  foo(1)

Supposons que l’utilisateur ait renommé la fonction changeMe en foo. Notez que, bien que clean.kt ne soit pas modifié, le corps de bar() changera à la recompilation : il appellera désormais foo(Int) de dirty.kt, et non plus foo(Any) de clean.kt, et son type de retour changera également. Il faut donc recompiler les fichiers dirty.kt et les fichiers clean.kt. Comment le compilateur incrémental peut-il trouver cela ?

Nous commençons par recompiler le fichier modifié : dirty.kt. Nous constatons ensuite que quelque chose a changé dans l’ABI :

- Il n’y a plus de fonction changeMe,

- La fonction foo prend un Int et renvoie un Int.

Nous constatons maintenant que clean.kt dépend du nom foo. Cela signifie que nous devons recompiler les deux fichiers clean.kt et dirty.kt une nouvelle fois. Pourquoi ? Parce qu’on ne peut pas faire confiance aux types.

La compilation incrémentale doit produire le même résultat qu’une recompilation complète de toutes les sources. Considérez le type de retour du nouveau foo dans dirty.kt. Il est déduit et en réalité dépend du type de bar de clean.kt qui est une dépendance circulaire entre les fichiers. Le type de retour pourrait donc changer lorsque nous ajoutons clean.kt. Dans ce cas, nous obtiendrons une erreur de compilation, mais jusqu’à ce que nous recompilions clean.kt avec dirty.kt, nous n’en savons rien.

La règle majeure de la compilation incrémentale pour Kotlin est : ne faites confiance qu’aux noms. Et c’est pourquoi, pour chaque fichier, nous stockons :

- l’ABI qu’il produit ;

- les noms (et non les déclarations complètes) qui ont été recherchés lors de sa compilation.

Certaines optimisations sont possibles dans la façon dont nous stockons tout cela. Par exemple, certains noms ne sont jamais recherchés en dehors du fichier, comme les noms des variables locales et, dans certains cas, des fonctions locales. Nous pourrions donc les exclure de l’index. Pour affiner l’algorithme, nous enregistrons les fichiers qui ont été consultés lors de la recherche de chacun des noms. Et pour compresser l’index, on utilise le hachage. Il est possible d’apporter d’autres améliorations.

Comme vous l’avez sans doute remarqué, nous devons recompiler plusieurs fois l’ensemble de fichiers qui ont été modifiés. Il n’y a malheureusement pas d’autre solution : il peut y avoir des dépendances circulaires et seule la compilation de tous les fichiers concernés en une seule fois donnera un résultat correct. Dans le pire des cas, la compilation incrémentale peut faire plus que l’évitement de compilation, il devrait donc y avoir des heuristiques en place pour l’éviter.

VI-3 - La compilation incrémentale au-delà des limites des modules

La compilation incrémentale peut dépasser les limites des modules.

Supposons que nous ayons des fichiers qui ont été modifiés dans un module, que nous fassions quelques tests et que nous atteignions un point fixe. Nous avons maintenant la nouvelle ABI de ce module et nous devons faire quelque chose pour les modules dépendants.

Bien sûr, nous savons quels noms ont été affectés dans l’ABI de notre module initial et quels fichiers dans les modules dépendants ont recherché ces noms. Nous pourrions appliquer essentiellement le même algorithme incrémental, mais en partant du changement d’ABI et non d’un ensemble de dirty files. Au fait, s’il n’y a pas de dépendances circulaires entre les modules, il suffit de recompiler les fichiers dépendants seuls. Mais si leur ABI a changé, il faudra ajouter d’autres fichiers du même module à l’ensemble et recompiler de nouveau les mêmes fichiers.

Implémenter ceci dans Gradle représente un véritable défi. Il faudra probablement apporter quelques modifications à l’architecture de Gradle, mais nous savons par expérience que c’est possible et bien accueilli par l’équipe Gradle.

VII - Points non abordés dans cet article

Mon but ici était de vous donner un aperçu de la fascinante machinerie de la compilation rapide pour Kotlin. Il y a beaucoup d’autres éléments à prendre en compte que j’ai délibérément laissés de côté, notamment :

- le cache de build ;

- le cache de configuration ;

- comment éviter la configuration de tâche ;

- comment stocker efficacement les index de compilation incrémentale et autres caches sur le disque ;

- la compilation incrémentale pour les projets mixtes Kotlin+Java ;

- la réutilisation des structures de données javac en mémoire pour éviter de lire deux fois les dépendances Java ;

- l’incrémentalité dans KAPT et KSP ;

- les file watchers pour identifier rapidement les dirty files.

VIII - En résumé

Maintenant, vous avez une meilleure idée des défis de la compilation rapide dans un langage de programmation moderne. Notez que certains langages ont délibérément choisi de rendre leurs compilateurs peu intelligents pour éviter d’avoir à faire tout cela. Pour le meilleur ou pour le pire, Kotlin a pris une autre voie, et il semble que les fonctionnalités qui rendent le compilateur Kotlin si intelligent soient celles qui sont le plus appréciées des utilisateurs, car elles fournissent à la fois des abstractions puissantes et un code lisible et concis.

Alors que nous travaillons sur un compilateur front-end de nouvelle génération qui rendra la compilation beaucoup plus rapide, en repensant l’implémentation des algorithmes de base de contrôle de type et de résolution de noms, nous savons que tout ce qui est décrit dans cet article ne disparaîtra jamais. L’une des raisons à cela est l’expérience avec le langage de programmation Java, qui bénéficie des capacités de compilation incrémentale d’IntelliJ IDEA, même en ayant un compilateur beaucoup plus rapide que celui de kotlinc aujourd’hui. Une autre raison est que notre objectif est de nous rapprocher le plus possible du développement des cycles des langages interprétés qui bénéficient d’une prise en charge instantanée des modifications sans aucune compilation. Ainsi, la stratégie de Kotlin pour une compilation rapide consiste en : un compilateur optimisé + une chaîne d’outils performante + une incrémentalité sophistiquée.

IX - Remerciements Developpez.com

Nous tenons à remercier Malick pour la mise au gabarit et escartefigue pour la relecture orthographique.