Réécrire du code C en Ruby pour accélérer Ruby

 (jpcamara.com)
2 points par GN⁺ 2024-12-06 | 1 commentaires | Partager sur WhatsApp
  • Dans un petit benchmark de langages, CRuby arrivait troisième en partant de la fin, mais cela montre que le goulot d’étranglement ne vient pas du langage dans son ensemble, plutôt d’une implémentation des boucles que YJIT ne peut pas inspecter
  • Sur un MacBook Pro M3, Ruby 3.3.6 prenait 12,17 s pour Fibonacci et 28,80 s pour Loops, tandis que node.js était autour d’une seconde pour les deux ; sur un MacBook Air M2, Ruby était encore plus lent avec respectivement 16,33 s et 33,43 s
  • En activant simplement ruby --yjit, Fibonacci passe fortement de 16,88 s à 2,06 s, mais Loops ne passe que de 33,43 s à 25,57 s : Range#each reste le goulot d’étranglement
  • Les méthodes dont l’implémentation en C a été déplacée côté Ruby, comme Integer#times dans Ruby 3.3 et Array#each dans Ruby 3.4, peuvent être optimisées par YJIT, ce qui améliore le benchmark de boucles jusqu’à environ 13 à 14 secondes
  • Avec le hook with_yjit, CRuby peut utiliser une implémentation Ruby quand YJIT est activé, tout en conservant l’implémentation C quand il ne l’est pas ; cela ouvre une tendance consistant à transformer les bibliothèques cœur en code Ruby compatible avec YJIT

La position de Ruby révélée par les benchmarks

  • Le language comparison repo, récemment partagé, est un dépôt collaboratif qui construit de petits benchmarks pour plusieurs langages
  • Dans ce dépôt, le résultat de CRuby était troisième en partant de la fin, seuls R et Python étant plus lents que Ruby
  • Le benchmark examine deux axes
    • Loops : met l’accent sur les performances des boucles, des conditions et des opérations mathématiques de base
    • Fibonacci : met en évidence le coût des appels de fonction et de la récursion
  • L’exemple Loops effectue des boucles imbriquées pour un total de 10 000 × 100 000 itérations, soit 1 milliard d’itérations
  • L’exemple Fibonacci n’utilise pas une implémentation optimisée, mais volontairement un Fibonacci naïf

Mesures initiales et effet de YJIT

  • Sur un MacBook Pro M3, Ruby 3.3.6 était au niveau suivant
    • Fibonacci : 12,17 s
    • Loops : 28,80 s
    • node.js : un peu plus d’une seconde pour les deux exemples
  • Sur un MacBook Air M2, le même benchmark était plus lent
    • Ruby Fibonacci : 16,33 s
    • Ruby Loops : 33,43 s
    • node.js Fibonacci : 1,36 s
    • node.js Loops : 2,07 s
  • La commande d’exécution du dépôt d’origine était de la forme ruby ./code.rb 40, sans YJIT
  • En exécutant avec ruby --yjit ./code.rb 40, les résultats changent
    • Fibonacci : 2,06 s
    • Loops : 25,57 s
  • YJIT a eu un effet important sur Fibonacci, mais l’amélioration reste limitée sur Loops

Pourquoi Range#each est défavorable à YJIT

  • Le cœur des boucles du code Loops prend la forme Range#each avec (0...10_000).each et (0...100_000).each
  • Dans Ruby 3.4, Range#each est toujours écrit en C
  • Dans CRuby, range.c relie la classe Range et la méthode each à la fonction C range_each
  • range_each bifurque vers différents chemins afin de gérer plusieurs formes de plages
    • (0...).each
    • (0...100).each
    • ("a"..."z").each
  • La fonction C elle-même peut être rapide, mais YJIT ne peut pas voir son intérieur
    • L’optimisation s’arrête au point d’appel de la fonction, puis reprend après le retour de la fonction C
    • YJIT peut produire des optimisations spécialisées pour les chemins d’exécution chauds, mais une implémentation C limite cet avantage

Ce qui change avec Integer#times

  • Dans Ruby 3.3, Integer#times a été converti d’une fonction C en méthode Ruby
  • Sa structure de base est une simple boucle Ruby composée de while i < self, yield i et i = i.succ
  • Comme elle est écrite en Ruby, YJIT peut analyser et optimiser son intérieur
  • En remplaçant les itérations sur des plages par 10_000.times et 100_000.times, le temps de Loops diminue fortement
    • Range#each : 25,57 s
    • Integer#times : 13,66 s
  • Dans un autre environnement de mesure, Integer#times est descendu à 9 s, et un résultat de 8 s a également été obtenu avec Ruby 3.4

Integer#succ et optimisations au niveau de la VM

  • L’implémentation de Integer#times utilise i.succ pour l’incrémentation au lieu de i += 1
  • Integer#succ est une méthode qui renvoie la valeur entière suivante
  • Dans le bytecode de la VM Ruby, i.succ est représenté par une seule étape, opt_succ
  • À l’inverse, i += 1 est divisé en deux étapes
    • putobject_INT2FIX_1_ : place l’entier 1 sur la pile de la VM
    • opt_plus : exécute l’opération +
  • Dans un programme Ruby ordinaire, il n’est presque jamais nécessaire de s’en soucier, mais au niveau du JIT et de la VM, lorsqu’une opération est répétée des millions à des milliards de fois, même une étape de différence peut affecter les performances

Array#each passe aussi à une implémentation Ruby dans Ruby 3.4

  • Dans Ruby 3.4, Array#each a lui aussi été converti d’une implémentation C à une implémentation côté Ruby
  • La première tentative était un simple code Ruby, mais elle présentait une race condition liée aux internes de CRuby
  • L’implémentation finale utilise Primitive dans le code Ruby
    • Primitive.attr! :inline_block, :c_trace
    • Primitive.cexpr!
    • ary_fetch_next
  • Ce n’est pas du Ruby pur complet, mais plutôt un mélange d’évaluation de code C et de structure Ruby ; YJIT peut néanmoins effectuer des optimisations importantes
  • En créant un tableau à l’avance puis en itérant avec Array#each, les performances sont proches de celles de Integer#times
    • Range#each : 25,57 s
    • Integer#times : 13,66 s
    • Array#each : 13,96 s

Mesures Ruby Microbench

  • Un dépôt séparé, ruby_microbench, compare l’exemple d’origine et plusieurs formes de boucles Ruby
  • Avec Ruby 3.4 et YJIT activé, les résultats sont les suivants
    • Fibonacci : 2,19 s
    • array#each : 14,02 s
    • range#each : 26,61 s
    • times : 13,12 s
    • for : 14,91 s
    • while : 37,10 s
    • loop do : 13,95 s
  • Avec Ruby 3.4 et YJIT désactivé, la plupart deviennent plus lents
    • Fibonacci : 16,49 s
    • array#each : 34,29 s
    • range#each : 33,88 s
    • times : 33,18 s
    • for : 36,32 s
    • while : 37,14 s
    • loop do : 50,65 s
  • L’exemple while était plus lent que prévu, ce qui pourrait venir de son mode d’implémentation
  • for in et array#each sont presque identiques au niveau du bytecode de la VM Ruby, et leurs performances sont donc similaires
    • for in est globalement proche d’un sucre syntaxique transformé par la VM en appel à #each

Comparaison avec d’autres implémentations de Ruby

  • Le même benchmark a été exécuté sur plusieurs implémentations de Ruby
  • Voici une partie des résultats
    • TruffleRuby 24.1
      • Fibonacci : 0,92 s
      • array#each : 0,97 s
      • range#each : 0,92 s
      • times : 2,39 s
      • for : 2,06 s
      • while : 3,90 s
      • loop do : 0,77 s
    • MRuby 3.3
      • Fibonacci : 28,83 s
      • array#each : 144,65 s
      • range#each : 126,40 s
      • times : 128,22 s
    • Artichoke
      • Fibonacci : 19,71 s
      • array#each : 236,10 s
      • range#each : 214,55 s
      • times : 214,51 s

Expérience de monkey patch de Range#each en Ruby

  • En appliquant un monkey patch à Range#each avec une implémentation Ruby simple, les performances s’améliorent fortement
  • L’implémentation est une forme simple utilisant begin, end, loop, yield et i.succ
  • Les mesures sont les suivantes
    • Implémentation C de Range#each : 25,57 s
    • Implémentation Ruby de Range#each : 16,64 s
  • Cette implémentation est une version excessivement simplifiée qui ne gère pas tous les cas de Range
  • Elle montre néanmoins qu’en déplaçant du C vers Ruby, YJIT peut optimiser, et permettre des gains de performance difficiles, voire impossibles, à reproduire avec du C générique

La bibliothèque standard YJIT et with_yjit

  • Ruby Outperforms C d’Aaron Patterson décrit un cas où une extension C pour le parsing GraphQL a été réécrite en Ruby, et où le code Ruby était plus rapide que le C grâce aux optimisations de YJIT
  • L’équipe cœur de YJIT dans CRuby supprime le code C pour certaines fonctionnalités clés, ou applique une approche qui n’utilise l’implémentation Ruby que lorsque YJIT est activé
  • Le bloc with_yjit applique l’implémentation Ruby concernée uniquement lorsque YJIT est activé
    • Si YJIT est désactivé, l’implémentation C continue de s’exécuter
    • Si YJIT est activé, la version Ruby optimisable par YJIT est utilisée
  • Depuis Ruby 3.3, YJIT peut être initialisé paresseusement, et le code with_yjit applique la version de méthode appropriée au moment où YJIT est activé
  • with_yjit est un hook YJIT, supprimé à l’exécution via undef :with_yjit après son appel

Comment voir le code machine généré par YJIT

  • En compilant CRuby avec l’option --enable-yjit=dev, on peut voir le désassemblage du code machine généré par YJIT
  • Exemple de build
    • ./configure --enable-yjit=dev
    • make install
  • À l’exécution, on utilise le flag --yjit-dump-disasm
    • ./ruby --yjit --yjit-dump-disasm test.rb 40
  • Le i.succ de Integer#times apparaît sous forme de opt_succ dans le bytecode de la VM
  • L’implémentation Rust de YJIT effectue les opérations suivantes pour opt_succ
    • Vérifier que le receveur est un Fixnum
    • Si ce n’est pas un Fixnum, sortir vers un autre chemin d’exécution
    • Si c’est un Fixnum, ajouter en réalité 2 pour additionner 1, à cause de la représentation interne par tags
    • En cas d’overflow, sortir vers un autre chemin
  • Cet exemple montre que les optimisations JIT fonctionnent en traversant plusieurs couches : code Ruby, code C, bytecode de VM, implémentation Rust et code machine

La direction de l’optimisation de CRuby

  • Le travail d’implémentation de Ruby se fait largement dans des langages de plus bas niveau que Ruby ; dans CRuby, il s’agit surtout de C et d’un peu de Rust
  • Des couches comme YJIT ouvrent la possibilité de déplacer davantage de fonctionnalités du langage vers du code Ruby ordinaire
  • Si davantage de fonctionnalités cœur sont écrites en Ruby, il pourrait devenir plus facile pour les développeurs Ruby de contribuer à CRuby
  • Comme en Java, une structure où la majeure partie du langage est écrite dans lui-même au-dessus d’un petit cœur bas niveau est évoquée comme l’un des futurs possibles de CRuby
  • Dans la tendance actuelle, plutôt que de conserver telles quelles les implémentations C, il reste important d’introduire sur les chemins critiques des implémentations Ruby que YJIT peut optimiser

À lire aussi

1 commentaires

 
GN⁺ 2024-12-06
Avis sur Hacker News

  • L’exemple de boucle ressemble à un benchmark étrange qui exécute un milliard de boucles imbriquées, et avec une optimisation à la main, plus de 99 % du temps d’exécution devrait se concentrer au début
    Avec une analyse de vivacité (liveness analysis) élément par élément du tableau, il semble possible de supprimer toute la boucle externe ; je me demande s’il existe des compilateurs qui font réellement ce genre d’analyse
    Même si u n’est pas connu à la compilation, la boucle interne pourrait elle aussi être remplacée par quelques instructions, et cela ressemble à une optimisation plus standard que des outils comme clang pourraient bientôt faire

    • Les compilateurs ne font généralement pas d’analyse de vivacité sur les éléments individuels d’un tableau
      Il y a trop de données à suivre, et cela n’a probablement d’intérêt que pour du code erroné de ce genre
      À l’époque où je travaillais sur un compilateur IA, l’analyse de vivacité des éléments individuels de tenseurs aurait réellement été utile, mais nous ne l’avons pas faite tellement le temps de compilation et les besoins mémoire auraient été absurdes
    • Dans la plupart des cas, on peut le calculer sous forme fermée :
      result = ((u * (u - 1)) / 2 * (100000/u)) + (100000%u * (100000%u - 1) / 2) + r)

  • L’article parle de versions de Ruby à venir, et par curiosité j’ai regardé : ruby 3.4.0 devrait sortir à Noël cette année, et ruby 3.5.0 à Noël prochain
    Je me demande aussi quel effet le JIT minimal de Python pourrait avoir sur ce genre de boucles
    Python 3.13 doit être compilé avec le JIT activé, donc ce serait intéressant que quelqu’un lance le benchmark dans un environnement construit ainsi : https://drew.silcock.dev/blog/everything-you-need-to-know-ab...

    • Ruby est toujours publié à Noël, donc son calendrier est prévisible et assez mignon
      Il me semble que des améliorations de performance pouvaient aussi être intégrées dans des versions de maintenance

  • Integer#succ est souvent utilisé non seulement pour les performances, mais aussi pour la lisibilité
    Par exemple, dans la méthode #bytes d’une bibliothèque UUID, je l’ai utilisé deux fois pour garder mon cerveau en « mode découpage de bits » pendant la lecture du code
    La boucle sur 16 itérations est exprimée avec 0xF.succ, et la division par 256 dans la boucle avec 0xFF.succ : https://github.com/okeeblow/DistorteD/blob/ba48d10/Globe%20G...

    • Je serais curieux de savoir pourquoi, dans ce cas, 0xF.succ te semble préférable à 0x10

  • Je contribue à https://github.com/bddicken/languages, et après avoir tenté l’approche avec Lua, j’ai aussi pensé à TruffleRuby, mentionné quelque part, mais en exécutant main.rb, il n’y avait pratiquement pas de grande différence entre TruffleRuby et Ruby classique
    Parfois, Ruby classique était même plus rapide que TruffleRuby
    J’aimerais vérifier après quel changement le benchmark de vitesse de TruffleRuby dans l’article a été obtenu, et si c’est vérifiable, l’ajouter au dépôt principal sous forme de commit
    Si l’implémentation TruffleRuby est réellement plus rapide que Node.js et proche de Bun ou Go, ce serait assez surprenant

    • Avec TruffleRuby, il faut tenir compte du temps de démarrage et du temps nécessaire pour atteindre les performances maximales, qui dépendent de la configuration du runtime natif/JVM
      Pour plus de détails, voir https://github.com/oracle/truffleruby

  • Ruby est vraiment devenu rapide, et TruffleRuby est particulièrement impressionnant

    • C’est un projet d’Oracle : https://github.com/oracle/truffleruby
    • Rails ne fonctionne pas sur Truffle, et d’après ce que j’ai compris, cela restera difficile pendant un moment
      C’est dommage, car c’est probablement la combinaison qui aurait le plus d’impact sur les performances de Ruby

  • Je ne savais pas que YJIT était écrit en Rust, c’est vraiment intéressant

    • Il avait d’abord été écrit en C, puis porté en Rust, et cela semble avoir été une bonne décision
      L’inconvénient est qu’il peut ne pas être activé à la compilation si la chaîne d’outils ou la plateforme appropriée n’est pas disponible, mais cela paraît être un compromis raisonnable

  • Il existe aussi un dépôt de comparaison de langages plus ancien et couvrant davantage de langages : https://github.com/niklas-heer/speed-comparison

    • Encore un dépôt de comparaison de langages, mais sa présentation est difficile à lire
      Les libellés des axes et des barres du graphique se chevauchent, et il n’y a pas non plus de lignes de grille verticales
      J’aimerais bien un simple tableau HTML

  • Il est intéressant de constater que Python était le langage le plus lent du benchmark, tout en étant le langage le plus utilisé sur GitHub en octobre 2024
    On dirait qu’il existe une corrélation selon laquelle plus un langage est lent, plus il est populaire

    • Pour refaire la comparaison, il faudrait aussi inclure le temps de compilation et l’amortir sur le nombre d’exécutions attendu pour ce build
      Même si j’aime beaucoup Rust, chaque langage et runtime, interpréteur ou compilateur reste un outil
      Selon le problème et l’approche choisie pour le résoudre, il faut le bon ensemble d’outils, et si un programme ne s’exécute que quelques fois, une vitesse d’exécution lente n’a pas beaucoup d’importance
      C’est souvent le cas des programmes en Python ou en R
    • C’est un peu comme la nourriture : si on ajoute du sucre dessus, les gens aiment beaucoup plus
      Ruby est globalement lent, mais il est vraiment agréable pour coder, ce qui le rend plus attirant pour les débutants
    • Les langages lents sont de plus haut niveau, donc plus faciles à utiliser
    • Je me demande si cette corrélation se maintient quand on regarde les 20 langages les plus populaires

  • Mes solutions à Advent of Code ressemblent étonnamment à ça, donc cela ressemble à un changement qui pourrait rebattre les cartes