Tree-shaking, l’algorithme à l’analogie horticole trompeuse (2023)

Les limites de WebAssembly et l’importance du tree-shaking

• Malgré l’intérêt et les attentes qu’il a suscités, WebAssembly n’a connu qu’un succès limité sur le web

  • Il existe des réussites comme Photoshop, mais dans l’ensemble les projets exploitant WebAssembly restent peu nombreux
  • WebAssembly est particulièrement peu adapté aux applications qui utilisent fortement le DOM
  • L’une des principales raisons est la différence de modèle de programmation entre JavaScript et WebAssembly

• En dehors de langages comme C ou Rust, WebAssembly n’a pas vraiment percé

  • Des langages comme C# ont l’inconvénient de devoir embarquer un runtime, notamment avec un garbage collector
  • Mais de nouvelles fonctionnalités de WebAssembly, avec prise en charge des types de référence et du garbage collection, devraient bientôt arriver, ce qui devrait améliorer la situation

La capacité d’optimisation du code par le compilateur est la clé du succès de WebAssembly

• Pour que WebAssembly réussisse sur le web, les compilateurs doivent pouvoir générer un code petit et efficace

  • Il est important de maintenir une taille de fichier réduite, de l’ordre de quelques kilo-octets
  • Sinon, il faut inévitablement s’appuyer sur le battage médiatique ou sur une base d’utilisateurs spécifique

• Dans l’univers JavaScript, l’optimisation de la taille du code se fait via des bundlers et d’autres outils

  • Le tree-shaking est une technique qui consiste à n’inclure que les fonctions et types de données réellement utilisés par le programme

• Le tree-shaking est une métaphore inadaptée sur les plans horticole et algorithmique, mais c’est un terme largement employé

État du tree-shaking dans d’autres langages

• Dans des langages au runtime lourd comme Go ou Python, le tree-shaking n’est pas encore bien optimisé

  • Même le programme Go le plus simple dépasse 2 Mo une fois compilé en WebAssembly
  • Pyodide, pour Python, impose lui aussi le téléchargement d’environ 20 Mo de fichiers

• En environnement serveur, la taille des binaires n’est pas un problème majeur

  • Pour des environnements contraints comme le mobile, des toolchains allégées comme MicroPython ou TinyGo sont parfois développées séparément

• Les implémentations de langages destinées au web ne peuvent qu’être différentes des implémentations existantes

  • Interagir avec le DOM constitue en soi un environnement particulier
  • Dans le cas de ClojureScript, les différences avec Clojure sont documentées à part

Discussion sur les algorithmes de tree-shaking

• Le compilateur Hoot Scheme en cours de développement par l’auteur génère actuellement environ 70 Ko de code Wasm

  • N’inclure que les définitions de fonctions (procédures) est relativement simple
  • Mais il existe plusieurs difficultés, comme les suivantes

• Dans le modèle d’évaluation de letrec*, les liaisons sont récursives tout en étant ordonnées, ce qui complique l’analyse par le compilateur

  • Dans le cas des types d’enregistrements, les callbacks de vtable maintiennent en vie beaucoup de code

• Lorsqu’on utilise une fonction très polymorphe comme display, cela entraîne l’inclusion de beaucoup de code associé

  • Il vaut mieux utiliser des fonctions plus concrètes comme write-string

• Pour obtenir un tree-shaking optimal, une flow analysis est nécessaire

  • Si l’on sait qu’aucun argument bitvector n’est transmis à display, on peut supprimer le code correspondant

• En Python, c’est encore plus difficile à cause du dispatch dynamique et de fonctionnalités dynamiques comme __getattr__

  • La structure modulaire de Python est elle aussi un facteur qui complexifie le tree-shaking

Résumé

• Grâce au support du GC, il devient possible de faire de la programmation DOM dans WebAssembly avec d’autres langages que JavaScript
• Mais pour réduire suffisamment la taille des artefacts produits, un investissement important dans les toolchains de chaque langage reste nécessaire
• Cela demande le développement de toolchains distinctes appliquant des algorithmes de tree-shaking ainsi qu’une optimisation des bibliothèques standard

L’avis de GN⁺

• Avec la prise en charge du GC par WebAssembly, il devient possible d’utiliser divers langages pour le développement web, mais il semble très difficile de reprendre tels quels les toolchains des langages existants. Il faudra sans doute développer des implémentations de langages et des techniques d’optimisation spécialisées pour l’environnement web.

• Pour que le tree-shaking fonctionne bien avec des langages à typage dynamique, l’analyse statique semble indispensable. Mais pour des langages comme Python, riches en mécanismes dynamiques, cela ne paraît pas simple. Concevoir dès le départ un nouveau langage plus favorable à l’analyse statique pourrait même être une autre voie possible.

• Des projets expérimentaux comme Hoot ou TinyGo semblent fournir de bonnes références. Mais il est peut-être encore trop tôt pour les appliquer à des produits réels. Il faudra probablement avancer par améliorations progressives.

• Pour des projets peu sensibles aux performances et où la rapidité de développement prime, quelque chose comme Pyodide peut valoir le coup d’être essayé. Mais pour un produit où l’expérience utilisateur est essentielle, JavaScript semble pour l’instant rester le meilleur choix.

• On peut aussi imaginer intégrer à WebAssembly lui-même des fonctionnalités de type tree-shaking. Mais ce ne serait pas simple, car les besoins diffèrent selon les langages. Et si un langage offrant un excellent support du tree-shaking émerge, il pourrait devenir plus avantageux de coder directement dans ce langage. Il sera intéressant de voir comment se répartiront les rôles entre WebAssembly et les langages de programmation.

[GN⁺]

Avis sur Hacker News

En résumé, voici les points principaux :

• Dans le projet OpenEtG, les efforts suivants ont été déployés pour maintenir la taille du binaire WASM écrit en Rust sous les 400 Ko
  • utilisation d’arithmétique en virgule fixe à la place de float
  • utilisation de Vec à la place de HashMap
  • réduction au minimum de l’usage des chaînes de caractères
  • utilisation d’un petit allocateur (talc)
  • minimisation des dépendances (uniquement rand et fxhash)
  • éviter la diversité des génériques
  • concevoir des algorithmes en tenant compte de la taille
• Le tree-shaking est une appellation trompeuse ; dans le compilateur Virgil, cela s’appelle Reachability Analysis. Pendant la compilation, on parcourt le code à partir du point d’entrée main et seuls les éléments atteignables sont inclus dans le binaire final.
• Grâce à WasmGC, Java et Kotlin peuvent produire de petits binaires WASM d’environ 2 à 3 Ko. Il faut toutefois faire attention au choix des API.
• La manipulation du DOM avec WASM reste encore dépendante de JS.
• Le terme Tree Shaking est apparu parce que le Dead Code Elimination existait déjà depuis longtemps.
• Le problème de taille du code en WASM vient du fait qu’il faut embarquer à la fois le runtime du langage et la bibliothèque standard.
• Pour y remédier, on peut envisager des bibliothèques partagées et de l’édition de liens dynamique.
  • Pyodide est un exemple représentatif prenant en charge l’édition de liens dynamique
  • si le navigateur préchargeait les runtimes des langages populaires, les pages web pourraient partager ce runtime
• Le langage Zig est adapté à la production de petits binaires WASM. Toutefois, en dessous de 100 Ko, la taille n’est pas un facteur important.
• Un GC intégré n’est pas essentiel pour toutes les applications, et il vaut mieux créer des web apps sans GC.
• Le principal facteur de réussite des applications utilisant WASM reste encore le gain de performances.
• Cela fait longtemps qu’on programme le DOM dans d’autres langages que JS via des langages qui compilent vers JS, comme ClojureScript, TypeScript et ReasonML.
• Avant même WASM, on compilait déjà et utilisait sur le web des langages basés sur C via asm.js et emscripten.
• Google Maps et Google Earth sont des exemples représentatifs d’applications utilisant WASM.