Développement d’un nouveau compilateur JIT pour PostgreSQL

 (pinaraf.info)
4 points par GN⁺ 2024-03-20 | 1 commentaires | Partager sur WhatsApp
  • Le moteur JIT expérimental pg-copyjit vise à produire un code « suffisamment rapide » même pour des requêtes PostgreSQL courtes, avec un coût de génération inférieur à celui de LLVM
  • Dans PostgreSQL, les estimations de coût ne correspondent pas directement au temps d’exécution réel, si bien qu’un JIT LLVM coûteux à optimiser peut au contraire pénaliser les requêtes courtes
  • L’approche copy-and-patch consiste à précompiler des stencils en C, puis à copier et patcher à l’exécution les fragments nécessaires pour les exécuter comme une nouvelle fonction
  • pg-copyjit se branche via l’interface de provider JIT de PostgreSQL et, lorsqu’il rencontre un opcode non implémenté, bascule automatiquement vers l’interpréteur PostgreSQL
  • Il s’agit actuellement d’une preuve de concept fonctionnant sur PostgreSQL 16 et AMD64 ; la génération de code se fait en quelques centaines de microsecondes, mais le build, la documentation et le support ne sont pas encore prêts

Ce que vise pg-copyjit

  • pg-copyjit est un moteur JIT expérimental destiné à accélérer le serveur PostgreSQL
  • Le code actuel est davantage au niveau d’un outil à expérimenter par des hackers spécialisés que d’un composant pour serveur de production
  • Les retours attendus portent sur des résultats d’expérimentation intéressants, des cas d’amélioration des performances et des idées d’implémentation ; ce n’est pas encore un stade où l’on peut accepter un temps d’arrêt sur une application critique

Pourquoi le JIT LLVM est coûteux dans PostgreSQL

  • PostgreSQL dispose déjà d’un compilateur JIT basé sur LLVM, introduit par Andres Freund
  • LLVM peut produire un code efficace, mais dans la manière dont PostgreSQL l’utilise, le coût de compilation JIT et d’optimisation est élevé
  • Sans l’optimiseur, le résultat peut être pire qu’une absence totale de compilation ; avec l’optimiseur, le coût peut encore augmenter
  • La décision d’appliquer ou non le JIT s’appuie sur l’habituel query cost estimation
    • Dans PostgreSQL, le coût est une valeur servant à comparer les requêtes entre elles, pas une mesure directe du temps d’exécution réel
    • Une requête de coût 100 peut prendre 1 seconde, tandis qu’une requête de coût 1000 peut se terminer en 100 ms
  • Si une requête gagne 10 ms mais que l’optimisation en coûte 50, le temps total d’exécution est perdant
  • Une piste pour rendre le JIT LLVM plus utile serait de mettre en cache et réutiliser les requêtes compilées, mais ce n’est pas une petite implémentation

Structure de l’approche copy-and-patch

  • Le copy-and-patch est une méthode de construction de compilateur JIT présentée dans un article en 2021, et utilisée aussi par le moteur JIT de Python 3.13
  • L’unité de base est le stencil, écrit en C
    • Un stencil est une fonction avec des trous
    • Il est précompilé avec clang
    • Le support de gcc est encore en attente
  • Au moment de la compilation, les stencils nécessaires sont assemblés, les trous sont remplis, puis l’exécution saute vers la nouvelle fonction « compilée »
  • Le flux de base est simple
    • Copier le stencil dans une nouvelle zone mémoire
    • Patcher les valeurs nécessaires
    • Exécuter le code obtenu
  • Il existe aussi des possibilités d’optimisation supplémentaires
    • Pré-calculer les valeurs connues au moment de la compilation
    • Découper une boucle en plusieurs stencils pour faire de l’unrolling
    • Fusionner plusieurs stencils pour créer un meta-stencil optimisable d’un seul bloc

Comment l’intégrer à PostgreSQL

  • Le JIT de PostgreSQL repose sur une architecture extensible de provider
  • Le .so fournit une seule fonction _PG_jit_provider_init, qui initialise trois callbacks
    • compile_expr
    • release_context
    • reset_after_error
  • Le callback central est compile_expr
    • Son entrée est un pointeur d’expression ExprState* composé d’opcodes
    • Il compile les opcodes selon la méthode voulue
    • Il marque le code généré comme exécutable
    • Il remplace evalfunc par le code généré au lieu de l’interpréteur PostgreSQL
  • Lorsqu’un opcode non implémenté est rencontré, il est possible de retomber automatiquement sur l’interpréteur PostgreSQL

Procédure de compilation de pg-copyjit

  • L’algorithme copy-and-patch de pg-copyjit est pour l’instant une version simple, avec seulement quelques petites optimisations
  • Pour chaque opcode, le compilateur vérifie une collection de stencils
    • Si un stencil correspondant existe, il l’ajoute au code en cours de génération
    • S’il n’existe pas, il interrompt la compilation et laisse l’interpréteur PostgreSQL exécuter la suite
    • Après ajout du stencil, il patche chaque trou avec les valeurs nécessaires
  • Le stencil de l’opcode CONST déclare op comme un ExprEvalStep externe, et laisse dans le fichier .o compilé un trou destiné à recevoir l’adresse de op
  • La collection de stencils conserve ces informations de relocation, ce qui permet au compilateur JIT d’insérer l’adresse de la structure d’opcode courante pour produire un code exécutable
  • Le build commence par créer les stencils dans un unique fichier .o, dont sont ensuite extraits le code assembleur et les relocations pour les convertir en structures utilisables depuis le C

État de l’implémentation et performances

  • Au départ, le code assembleur a été extrait manuellement afin de faire fonctionner les trois opcodes nécessaires à SELECT 42;
  • Ensuite, un script DirtyPython a été écrit pour automatiser l’extraction du code assembleur, ce qui a permis d’ajouter en quelques heures les fonctions suivantes
    • appels de fonction
    • requêtes sur une seule table
    • types de données plus complexes
    • quelques optimisations
  • L’état actuellement confirmé est le suivant
    • Fonctionne sur PostgreSQL 16
    • Les versions précédentes devraient probablement convenir aussi, mais l’environnement vérifié est PostgreSQL 16
    • L’architecture prise en charge est uniquement AMD64
    • Un support d’ARM64 est prévu
    • Des cibles comme POWER64 et S390x intéressent également l’auteur, mais elles pourraient nécessiter des patches du compilateur et un accès à ces machines
  • Les chiffres de performance proviennent encore d’un état très peu optimisé
    • La génération de code se termine en quelques centaines de microsecondes
    • C’est assez rapide pour être utilisable même sur des requêtes courtes
    • Pour SELECT 42;, sans JIT il faut 0,3 ms, avec copyjit 0,6 ms, avec LLVM sans optimisation 1,6 ms, et avec LLVM optimisé 6,6 ms
  • LLVM peut produire un code extrêmement rapide, mais l’objectif de pg-copyjit est de générer rapidement un code suffisamment rapide, ce qui rend une comparaison directe entre les deux outils difficile
  • Deux requêtes ont été benchmarkées sur une table simple non indexée de 90k lignes, et lorsqu’une clause where contenant du travail CPU est présente, les performances s’améliorent par rapport à l’interpréteur
  • Les benchmarks ont été réalisés sur un portable, ce qui limite leur fiabilité ; des mesures plus appropriées sur un poste fixe sont prévues
  • Même avec peu d’opcodes implémentés, il est déjà possible d’exécuter n’importe quelle requête
    • Le moteur JIT émet un message pour les parties non implémentées
    • L’exécution réelle est alors assurée par l’interpréteur

Publication du code et travail restant

  • Le code est disponible sur GitHub dans pg-copyjit
  • Pour l’instant, l’accent est mis sur le code lui-même plutôt que sur le nettoyage de l’historique Git ou la documentation
  • Pour builder, il faut d’abord exécuter manuellement le fichier build-stencils.sh
  • Dans l’état actuel, aucun support ne peut être fourni, ce qui explique aussi l’absence de documentation
  • Le travail restant est relativement clair
    • implémenter davantage d’opcodes
    • explorer les optimisations
    • améliorer la facilité de build
    • préparer le projet à un état packagable
  • Le script de build est actuellement spécifique à Debian et à PostgreSQL 16

Cas d’usage envisagés et extension à d’autres architectures

  • L’objectif est d’atteindre un niveau où l’on pourra empaqueter le projet de manière sûre et le déployer sur son propre serveur de production
  • Une autre idée est de répartir l’usage des JIT selon les serveurs
    • utiliser le JIT LLVM sur des serveurs GIS, où les requêtes justifient le coût de l’optimisation
    • utiliser pg-copyjit pour des bases de données d’applications web, où les temps de requête courts sont essentiels
  • Le portage vers d’autres architectures est aussi un objectif sérieux
  • L’auteur dit regretter l’époque où coexistaient de nombreuses architectures comme Alpha, Itanium, Sparc ou M68k, et ne pas vouloir contribuer au problème de monoculture centré sur une seule architecture

À lire aussi

1 commentaires

 
GN⁺ 2024-03-20
Avis sur Hacker News
  • La mise en cache et la réutilisation des requêtes compilées, une façon de rendre le compilateur JIT LLVM plus facile à utiliser, sont en fait implémentées dans LLVM depuis des années :) https://github.com/llvm/llvm-project/commit/a98546ebcd2a692e...
    • Exact, j’aurais dû être plus clair : le problème est du côté de PostgreSQL, pas de LLVM
      Le compilateur JIT doit injecter directement des adresses mémoire, ce qui lie le code généré à cette requête et à ce processus
    • PG utilise un processus par connexion et le code JIT LLVM est figé par processus, donc toutes les connexions à la DB ne peuvent pas partager le code
      Les plans d’exécution souffrent du même problème, car ils ne sont pas non plus des structures de données en mémoire conçues pour être partagées entre différents processus
      Les DB comme MSSQL ont une architecture à processus unique avec des threads, ce qui évite ce problème et explique aussi pourquoi elles peuvent gérer davantage de connexions simultanées sans pooler externe
      MSSQL peut aussi sérialiser les plans d’exécution dans une représentation non liée au processus et les stocker dans la DB, ce qui permet de les utiliser pour des fonctionnalités comme le figement des plans d’exécution
  • Je suis l’auteur. Merci d’avoir posté l’article sur Hacker News ; s’il y a des questions, je ferai de mon mieux pour y répondre
    • Je me demande s’il existe une différence fondamentale entre le copy-and-patch qui cible le C et ce que fait un compilateur lorsqu’il cible une représentation intermédiaire
      La compilation traditionnelle ressemble aussi à du « copy-and-patch » utilisant un langage intermédiaire autre que C
    • C’est toujours agréable de voir des améliorations de performances dans Postgres. Je me demande combien de temps LLVM prend sur de vraies requêtes, et comment LLVM est configuré
      Par exemple, quels passes et quelles optimisations de backend sont utilisés
      D’après notre expérience [1], si l’on désactive les optimisations et que l’on ajuste le pipeline backend -O0 pour le temps de compilation, LLVM peut aussi devenir assez rapide, mais reste 10 à 20 fois plus lent que d’autres approches
      Nous avons aussi constaté que le code généré par copy-and-patch est assez lent à l’exécution et difficile à optimiser. Nous avons tenté plusieurs choses [2 ; Sec. 5], mais l’écart reste important. Voir la Fig. 3 pour les résultats d’évaluation sur base de données
      Je me demande aussi s’il existe des chiffres sur la dégradation du temps d’exécution par rapport à LLVM, et s’il est prévu d’implémenter un JIT multi-niveaux qui bascule dynamiquement du code compilé rapidement vers du code optimisé par LLVM
      [1]: https://home.in.tum.de/~engelke/pubs/2403-cgo.pdf
      [2]: https://home.in.tum.de/~engelke/pubs/2403-cc.pdf
    • Je me demande si le copy-and-patch est vraiment une idée nouvelle, ou si c’est une idée ancienne avec un nouveau nom
      Vers 2010, quand j’apprenais la programmation, en particulier les interpréteurs, je pensais qu’il était bien connu qu’avec prudence on pouvait faire un memcpy de fragments de code exécutable produits par un compilateur
      À l’époque, le gros piège était que le bit NX commençait tout juste à se généraliser. Même sous Linux, la plupart des gens considéraient encore les distributions 32 bits comme allant de soi, et certains étaient surpris d’apprendre que leur CPU prenait en charge le 64 bits
      Plus tard, j’ai même utilisé un netbook qui ne prenait pas du tout en charge le code 64 bits
      Malheureusement, j’ai passé trop de temps sur le reste du code et je n’ai pas pu creuser suffisamment cette idée pour en faire quelque chose d’utilisable
    • Ce serait un très bon sujet à traiter à pgconf.eu en juin. pgcon a été déplacée à Vancouver
      Malheureusement, l’appel à propositions est terminé, mais il y a une partie « unconference ». Cela dit, les sujets sont décidés sur place, donc rien n’est garanti
  • Il reste surprenant que PostgreSQL n’ait toujours pas de cache de requêtes/plans d’exécution
    Avec un cache, les requêtes fréquemment exécutées seraient mises en cache et optimisées plus agressivement, ce qui permettrait aux deux approches de bien s’articuler en amortissant le coût de compilation
    Bien sûr, cela ajouterait en soi un tout nouvel ensemble de complexité et de casse-têtes
    • PG dispose bien d’une forme de mise en cache des plans d’exécution. Pour les requêtes préparées, si PG estime que les valeurs effectives des paramètres n’ont pas une grande influence sur le plan d’exécution, il utilise un « generic plan » et réutilise le même plan pour toutes les exécutions de la même requête préparée
      Voir les « notes » de https://www.postgresql.org/docs/current/sql-prepare.html
    • J’avais moi aussi cette intuition au départ, mais après l’avoir construit moi-même, j’ai compris que ce serait vraiment difficile
      Pour simplifier énormément, des pointeurs vers des parties de la requête fuient un peu partout dans le moteur d’exécution
      Les supprimer nécessiterait une refonte assez importante, impliquant le moteur d’exécution, le planificateur, et probablement bien d’autres choses
      Même au sein d’une seule session, deux requêtes compilées finissent donc avec du code compilé différent. LLVM comme mon copyjit doivent injecter dans le code assembleur les adresses de plusieurs structures
    • Le cache de plans d’exécution d’Oracle a été assez pénible par le passé quand l’optimiseur ne pouvait pas examiner les paramètres des requêtes préparées
      En général, il fallait intervenir manuellement pour ajouter des hints ou forcer un plan d’exécution
      Même une requête simple comme SELECT * FROM t WHERE x = TRUE; pouvait devenir un cauchemar selon la distribution des valeurs de x dans la table
      Je n’ai presque jamais rencontré ce genre de problème avec Postgres, mais j’admets ne pas avoir utilisé Postgres avec des requêtes préparées
      J’ai déjà vu des requêtes dont la planification était lente (plus de 100 ms), donc un cache aurait pu être utile, mais je ne me souviens pas d’un cas où l’optimisation était vraiment indispensable
  • À l’époque du 386, il existait en assembleur le concept de code auto-modifiant
    C’est similaire aux stencils présentés ici, mais comme le code était généralement en instance unique, il était rare d’en faire des copies
    Par exemple, Doom sous DOS utilisait aussi ce genre de technique d’optimisation. C’était nécessaire pour tirer suffisamment de performances des boucles de rendu serrées sur les anciens CPU