Des tableaux d’enums économes en mémoire en Zig

 (alic.dev)
3 points par GN⁺ 2023-09-19 | 1 commentaires | Partager sur WhatsApp
  • Stocker en masse un enum/tagged union avec des variants de tailles différentes réserve de l’espace selon le plus grand variant, ce qui augmente les coûts de padding et de fragmentation dans Vec et HashMap
  • Grâce à comptime et à la réflexion de type, Zig peut inspecter la taille des champs, leur alignement et leur discriminant, puis transformer génériquement un conteneur d’enum en fonction de sa disposition mémoire
  • Un simple Vec<Enum> fait consommer à chaque élément l’espace du plus grand variant, et un SoA réduit le padding des tags mais laisse subsister la fragmentation des variants dans la zone des valeurs
  • Le dense AoVA, qui regroupe les variants de même taille, ramène dans l’exemple 15 vecteurs à 3 clusters de 2, 4 et 8 octets, mais il devient difficile d’itérer de façon type-safe si plusieurs variants cohabitent dans la même allocation
  • Les proc macros de Rust accèdent difficilement aux informations de taille et d’alignement des types, et le calcul générique de longueur de tableau reste limité, ce qui met mieux en évidence avec Zig la composabilité de l’efficacité mémoire dans le code système

Pourquoi les tableaux d’enums Rust gaspillent de l’espace

  • Un enum/tagged union dont les variants ont des tailles différentes doit réserver assez de mémoire pour contenir le plus grand variant
  • L’enum d’exemple Foo possède des variants u8, u16, u32 et u64, et à cause du tag et de l’alignement la taille du type atteint 16 octets
  • Quand on place beaucoup de ces enums dans un Vec ou un HashMap, chaque élément occupe l’espace du plus grand variant, ce qui accroît le padding et la fragmentation
  • Transformer la structure en struct of arrays (SoA), avec le tag dans une allocation séparée, réduit une partie du padding, mais n’élimine pas la fragmentation de la zone des valeurs causée par les écarts de taille entre variants
  • En Rust, on peut toujours construire à la main une structure dédiée à un enum donné, mais créer une structure générique aussi économe que possible en mémoire pour un enum arbitraire est difficile, voire pratiquement impossible
    • une proc macro s’applique mal à des types tiers ou à des alias de type via #[derive], et compose mal
    • elle n’a pas de connaissance des types, et les contournements fondés sur generic_const_expr propagent des clauses where verbeuses dans le graphe d’appels et s’accordent mal avec les paramètres de type génériques

Pourquoi le problème se voit particulièrement dans les AST de compilateurs

  • L’une des grandes motivations derrière des tableaux d’enums efficaces est l’empreinte mémoire des AST de compilateurs
  • Les gros AST provoquent de la latence mémoire et des évictions de cache pendant la compilation, avec un coût important pour les performances du frontend
  • Dans une vidéo sur le compilateur Carbon, Chandler Carruth explique qu’un AST clang parsé consomme fréquemment 50 fois plus de mémoire que le code source d’origine
  • En Rust, un exemple de représentation des nœuds d’expression prend la forme d’un enum Expr
    • Unit
    • Number
    • Binary(Operation, ExprId, ExprId)
    • Ident(Symbol)
    • Eval(ExprId, ExprSlice)
    • BlockExpression(ExprId, StatementSlice)
  • En OCaml, le runtime et le GC prennent en charge la gestion mémoire, ce qui permet d’exprimer des types récursifs sans indirection explicite
  • En Rust, Vec<Expr> fait consommer à chaque élément sizeof(Enum), ce qui inclut la taille du plus grand variant, le tag et le padding

Réduire la fragmentation avec SoA et AoVA

  • Quand un enum simple à 3 variants contient des membres de 8, 16 et 32 bits, un Vec classique réserve beaucoup d’espace à tous les éléments afin de satisfaire le variant 32 bits et les contraintes d’alignement
  • Une optimisation courante consiste à garder l’enum lui-même petit en utilisant par exemple un tagged index
    • le crate tagged_index du compilateur Rust
    • des cas de small-string optimization
    • c’est une optimisation fréquente dans les runtimes de langage, les GC, les compilateurs, les moteurs de jeu ou les noyaux d’OS
  • On peut aussi changer le conteneur et stocker séparément le discriminant et les valeurs via un SoA
    • c’est l’approche utilisée par le compilateur Zig auto-hébergé
    • cela réduit le padding lié aux tags, mais la collection de valeurs du union conserve une fragmentation entre variants
  • La compilation étagée de Zig permet de créer génériquement des conteneurs qui appliquent cette transformation SoA à des types arbitraires
  • Rust doit s’appuyer sur des proc macros comme soa_derive, avec la contrainte qu’on ne peut pas ajouter #[derive] à un type tiers sans modifier son code source

Tableaux par variant et regroupement par taille

  • Pour réduire davantage la fragmentation de la zone des valeurs, on peut utiliser un vecteur par variant
  • Lors de l’insertion, on renvoie un tagged index qui contient à la fois le tag de l’enum et l’index dans le tableau du variant correspondant
  • Ce motif est appelé array of variant arrays (AoVA)
  • AoVA peut être implémenté avec une proc macro en Rust, et avec comptime en Zig
  • Quand il y a beaucoup de variants et que plusieurs ont la même taille, avoir un vecteur par variant devient excessif
    • l’enum d’exemple Foo comporte 15 variants
    • l’approche un vecteur par variant ajoute 15 vecteurs
    • cela peut augmenter le nombre de réallocations et d’appels système, et nécessiter plus de mémoire pour l’amortissement qu’un Vec naïf
    • les vecteurs peuvent se retrouver dispersés en mémoire, augmentant le risque de conflits de cache
    • le conteneur AoVA lui-même peut consommer beaucoup de mémoire et gonfler la structure qui l’embarque
  • En regroupant par taille, l’enum d’exemple se divise en trois clusters de 2 octets, 4 octets et 8 octets
    • c_2: Vec<[u8; 2]> stocke A à D
    • c_4: Vec<[u8; 4]> stocke E à I
    • c_8: Vec<[u8; 8]> stocke J à O
  • L’approche dense AoVA peut réduire de 80 % le nombre total de vecteurs
  • Si des variants différents partagent la même allocation, il devient difficile d’itérer sur le vecteur de façon type-safe
    • l’accès n’est alors possible qu’au moyen du tagged pointer produit à l’insertion
    • pour une structure arborescente basée sur des index aplatis, qui n’a pas besoin d’itération aveugle, ce compromis peut être acceptable
  • Si une itération type-safe est nécessaire, on peut réintroduire les tags en acceptant le coût du padding
  • Si le padding reste trop élevé, on peut appliquer une transformation SoA à chaque tableau de variant, au prix d’un doublement du nombre de vecteurs

La composabilité de la disposition mémoire grâce à comptime en Zig

  • Un prototype Zig est implémenté dans osmium
  • Le point clé est la réflexion à la compilation via des built-ins du compilateur pour inspecter le type des champs, leur taille en octets, leur taille en bits et leur discriminant
  • Le code d’exemple inspecte le type avec @typeInfo(inner) et ne traite que les unions
    • il parcourt les champs du union
    • il calcule l’espace requis avec @max(field.alignment, @sizeOf(field.type))
    • il stocke les informations de taille dans un vecteur alloué sur la pile
    • il construit un mapping entre les champs du union et l’index de cluster
    • s’il ne s’agit pas d’un union, il déclenche une erreur de compilation
  • L’extrait exact se trouve dans ce code source
  • Reproduire le même exemple avec une proc macro Rust est fondamentalement impossible
    • une proc macro n’a pas accès aux informations de taille ou d’alignement d’un type
    • elle peut générer un const fn qui calcule des clusters pour un enum précis, mais ne peut pas l’utiliser pour fixer la longueur de tableaux d’un type générique
  • En Rust, il est difficile de faire varier conditionnellement l’implémentation d’un conteneur générique selon que le type fourni est un enum ou une struct
  • En Zig, on peut conceptuellement choisir entre EfficientEnumArray<T> et EfficientStructArray<T> selon quelque chose comme T.isEnum()
  • L’implémentation AoVA peut elle aussi être sélectionnée en fonction des propriétés de l’enum
    • par exemple en spécialisant seulement si le fait de regrouper plusieurs variants dans une même allocation réduit de plus de 90 % le nombre de vecteurs
  • Si la capacité maximale est connue à la compilation, la fonction de création de type peut déterminer la largeur en bits nécessaire au tagged index
  • Si ce tagged index est ensuite embarqué dans une autre structure de données, par exemple un autre enum, les bits restants peuvent servir au discriminant
  • Zig permet de spécifier précisément le nombre de bits nécessaires, ce qui offre une efficacité mémoire composable que le reste du code peut exploiter naturellement
  • Grâce à l’implicit widening integer coercion, l’ergonomie reste bonne même avec des API manipulant des largeurs de bits différentes
  • Pour un langage de programmation système axé sur l’efficacité et les zero-cost abstractions, il vaut la peine de reconsidérer la programmation étagée, en particulier comptime de Zig

À lire aussi

1 commentaires

 
GN⁺ 2023-09-19
Commentaires Hacker News

  • Il existe une autre stratégie qui offre une bonne efficacité de stockage tout en conservant l’itération sur les éléments. Le premier vecteur contient la liste des tags, le deuxième les offsets en octets de chaque élément, et le troisième n’est pas vraiment un vecteur, mais les données compressées des variants pointées par le deuxième vecteur.
    Ainsi, on a deux fois moins de vecteurs que dans la solution finale de l’auteur (6 contre 3), on ne gaspille pas d’octets de padding sauf si c’est nécessaire pour l’alignement, et les données sont disposées en mémoire dans l’ordre, indépendamment du type, ce qui permet une itération favorable au cache. L’accès à un élément par indice est également possible en O(1). Globalement, cela offre des caractéristiques de performance proches de Vec pour des données hétérogènes.

    • Stocker les offsets en octets inline est une bonne idée. Cela dit, une fois les offsets stockés en mémoire, l’itération introduit une dépendance de données qui, même avec une bonne localité cache, peut provoquer de sérieux blocages mémoire dans le pipeline du processeur.
    • Si l’on doit modifier une telle collection, on risque au final d’utiliser soi-même un allocateur mémoire pour gérer les suppressions, les changements vers des variants plus grands et la fragmentation.
    • Si l’on n’optimise pas la taille des offsets, ils peuvent occuper pas mal d’espace par rapport à un petit T. Par exemple avec un size_t 64 bits et un uint8_t T. En faisant simplement attention à la taille des offsets, l’approche semble raisonnable.

  • Je me demande comment cette structure de données AoVA fonctionne réellement. Du point de vue d’un tableau, l’arithmétique des indices peut ne plus avoir de sens ; ne perd-on pas alors l’accès par indice ? L’itération ne semble pas non plus préserver l’ordre d’insertion.
    Dans ce contexte, je pense qu’on utilise plus couramment le TLV (tag-length-value), qui a de meilleures propriétés de cache. La longueur peut être implicite dans le tag, et cela fournit au moins une itération vers l’avant qui a du sens. Voir getdents, inotify et la messagerie Netlink.

    • D’après la légende de la figure 4, il faut considérer que le pattern AoVA n’est pas adapté lorsqu’il faut préserver l’ordre global des éléments insérés.
      Par rapport au layout SoA précédent, on obtient un ordre partiel plutôt qu’un ordre global. À l’insertion, la structure renvoie un indice tagué contenant à la fois le tag de l’enum et l’indice dans le tableau du variant correspondant. L’accès trié semble donc hors périmètre ici. Stocker un indice global dans chaque élément permettrait de retrouver une itération triée, mais cela n’aiderait toujours pas pour l’accès aléatoire trié et produirait probablement un code avec pas mal de branchements.
    • Le « tag d’enum et l’indice dans le tableau du variant correspondant » renvoyés à l’insertion sont, fondamentalement, un pointeur. Si l’on veut itérer, il suffit de stocker les pointeurs dans un tableau dans l’ordre d’utilisation souhaité. C’est la même chose que ce que fait un programme qui alloue de la mémoire sur le tas.
      Le stockage d’objets par taille est aussi utilisé dans les garbage collectors et les allocateurs généralistes. On peut gagner en efficacité parce que toutes les tailles d’objets possibles sont connues, ou grâce à un mode de libération plus simple, comme dans une arena.
    • Le fait qu’AoVA n’ait pas son propre ordre total sur les indices peut poser problème dans certains cas d’usage, mais ce n’est pas forcément un problème pour les nœuds d’AST proposés ici.
      Dans ce cas, les tableaux peuvent être vus comme un composant d’une structure ressemblant au tas, autrement dit comme une arena. Le coût est que l’indice doit devenir bidimensionnel, du type (tag_idx, va_for_tag_idx). Mais comme le nombre de tags est connu à la compilation, on peut optimiser le stockage en plaçant tag_idx dans les 4 ou 5 bits de poids fort et en laissant va_for_tag_idx utiliser le reste. Référence : https://www.cs.cornell.edu/~asampson/blog/flattening.html
    • Les écritures dans un tableau qui changent le type de l’indice semblent devoir être extrêmement coûteuses.

  • Je trouve un peu dommage que le pattern matching de Rust ne puisse pas être exprimé davantage comme une sorte de trait du système de types auquel des structures arbitraires pourraient se conformer, plutôt que comme un type d’objet explicite, de première classe et codé en dur, avec sa propre structure de stockage.
    Récemment, comme dans cet article, j’ai implémenté à la fois un AST et un interpréteur d’opcodes/bytecode, et j’ai eu l’impression que les enums de Rust n’étaient totalement idéales pour aucun des deux. Pour l’AST, je voulais attacher des attributs de numéro de ligne/colonne à tous les nœuds de statement ; mettre ligne/colonne dans chaque cas de l’enum Stmt rendait le boilerplate pénible, tandis qu’envelopper l’enum d’origine dans une nouvelle structure Stmt contenant à la fois l’enum et les attributs ligne/colonne impliquait beaucoup de refactoring et n’était pas élégant. Côté opcodes, il est difficile de dire qu’une enum Rust utilisée avec du pattern matching soit l’encodage idéal pour les performances d’un interpréteur de bytecode de VM, mais le langage pousse dans cette direction et les fonctionnalités de motifs de déstructuration sont très séduisantes. Il semble y avoir de la place pour améliorer le système de types afin de permettre d’utiliser l’implémentation bas niveau voulue tout en bénéficiant du pattern matching.

    • J’aimerais avoir un exemple plus concret. Ce qui me vient d’abord à l’esprit, c’est une forme de système de types structurel, mais je ne suis pas sûr de l’avoir bien compris ainsi.
      https://en.wikipedia.org/wiki/Structural_type_system
    • Une vieille technique pour les interpréteurs de bytecode consiste à utiliser des sauts indirects pour passer à l’implémentation de l’opcode suivant. gcc avait une extension computed goto pour cela, et en Rust il faudrait sans doute quelque chose qui force les pointeurs de fonction et l’optimisation des appels terminaux.
      Si l’on place ce saut indirect au début de chaque implémentation d’opcode, le prédicteur de sauts indirects que les CPU possèdent à cause de l’OOP peut maintenir des modèles distincts pour les fins de différents opcodes, ce qui peut améliorer le taux de prédiction. L’instruction suivante elle-même peut être difficile à prédire, mais par exemple il est beaucoup plus probable qu’un test soit suivi d’un branch. Cela dit, d’autres techniques, comme garder le sommet de pile dans un registre sur une machine à pile, sont probablement plus importantes, et je ne sais pas si cette technique a encore du sens aujourd’hui.
    • Plusieurs langages ont des fonctionnalités proches de ce que vous voulez. Voir les extractors de Scala ou les active views de F#.

  • Le fait que « l’AST clang parsé consomme régulièrement 50 fois plus de mémoire que le code source d’origine » paraît assez énorme, mais le contexte manquant est jusqu’où on peut l’améliorer. Si l’on doit préserver la position source de chaque token et encoder assez d’informations pour pouvoir les reconstruire correctement depuis l’AST, je me demande si l’augmentation idéale par rapport à l’original est de 1,5× ou de 15×.

    • Par exemple, si une réduction de 30 % de la mémoire est possible, ce serait une annonce assez importante. Mais si cela rend le compilateur plus difficile à maintenir à l’avenir pour seulement 30 % de gain, cela peut ne pas en valoir la peine. À l’inverse, si l’on peut obtenir une réduction de 80 % même en malmenant un peu le compilateur, ça vaut le coup d’essayer.
      Il est difficile de dire quel est le taux idéal de gonflement source→AST pour un langage à la fois convivial pour les utilisateurs et pour les développeurs du compilateur, mais 50× fonctionne malgré tout. Le texte original utilise ce facteur 50× comme motivation pour automatiser une optimisation particulière. Il serait intéressant que les vecteurs d’enum de Rust puissent automatiquement décomposer les valeurs d’enum en tags et valeurs opaques, afin de les stocker sous forme de structure de tableaux comme le fait l’article en Zig. Il ne semble pas non plus y avoir beaucoup d’endroits où cacher l’usage de unsafe.
    • À titre de comparaison, le tape de simdjson ne fait qu’environ 3 fois la taille du document original. On peut en réduire une bonne partie en plaçant les nombres dans un seul slot du tape, ou en ne copiant pas les chaînes sans séquences d’échappement et en référençant leur position dans le document d’origine.
      Pour des documents composés majoritairement de caractères [] ou de caractères 0,, le surcoût maximal semble être d’environ 8×.
    • Le code source est étonnamment dense. Comme donnée sur jusqu’où on peut aller, il y a le résultat du parseur Zig lui-même lorsqu’il parse le parseur Zig lui-même.
      Octets source : 139 KiB, tokens : 24 646 (120 KiB), nœuds AST : 10 998 (140 KiB). Chaque token est très minimal, à 5 octets (tag d’1 octet + offset de fichier de 4 octets), et les nœuds AST sont également encodés de manière dense et non uniforme, autour de 13 octets par nœud dans ce cas. Même avec cet encodage minimal, le parse tree atteint presque 2 fois la taille du fichier source. Cela dit, 2× reste bien meilleur que 50×. Source : zig ast-check -t lib/std/zig/Parse.zig | head -n7
    • Mieux vaut simplement regarder la présentation liée. Elle est excellente. De mémoire, je ne crois pas qu’elle donnait de chiffres précis, et il était peut-être encore trop tôt pour en être sûr. Il manque peut-être des données dont on n’a pas encore réalisé la nécessité, ce qui pourrait faire paraître les chiffres plus faibles.

  • Cet espace de problèmes ressemble à une variante des problèmes de packing.
    Ce serait bien de pouvoir partir de la structure finale, facile à manipuler pour un humain, puis générer des recommandations de structures de données qui réduisent le gaspillage mémoire, respectent les règles d’alignement et améliorent la localité spatiale. https://en.wikipedia.org/wiki/Packing_problems

  • J’aimerais que les proc macros évoluent pour pouvoir interroger le compilateur. Cela nécessiterait une conception prudente autour de l’ajout d’étapes de compilation, mais des choses comme « cette structure implémente-t-elle ce trait ? » ou « donne-moi la liste de tous les traits concrètement implémentés » sont souvent très utiles dans une proc macro.

    • Si je me souviens bien, le compilateur exécute les plugins en deux phases. La première reçoit l’AST avant la vérification des types et peut le modifier ; les macros et certains lints clippy s’exécutent là. La deuxième phase a lieu après la vérification des types : elle reçoit les informations de type, mais ne peut pas modifier le code, et d’autres lints clippy s’y exécutent.

  • Je n’ai compris qu’une partie de l’article, mais pour quelqu’un qui veut écrire un moteur de tableur en Rust, cela semble très pertinent. Les valeurs des cellules ont besoin d’une forme comme celle-ci :
    pub enum Expr { Number(i32), String(String), Reference(Position), Binary(Box, char, Box), Function(String, Vec), }
    Je compte continuer à lire et à étudier le sujet, et toute ressource de référence est bienvenue.

    • Le problème mis en avant ici est que les variants ont des tailles très différentes et que, s’il y a beaucoup de valeurs de ce type dans un tableau, les performances se dégradent à cause de l’espace gaspillé par le padding.
      Une technique courante venue du jeu vidéo consiste à découper un tableau de structures (AoS) en structure de tableaux (SoA). Par exemple, avec struct Humans { healths: Vec, ammo: Vec, … }, l’index i de chaque vecteur correspond au iᵉ Human de la disposition AoS. Ces vecteurs parallèles ne sont qu’un exemple et ne sont pas optimalement efficaces, car la comptabilité de longueur et de capacité est dupliquée pour chaque champ, ce qui gaspille de l’espace. L’article cherche essentiellement à appliquer automatiquement une idée similaire aux enums, ce qui est difficile à faire tel quel en Rust. L’importance réelle du problème est peut-être un peu exagérée. Pour un tableur, il vaut mieux garder cela en tête comme une optimisation possible, puis décider d’abord si l’objectif est la vitesse ou la simplicité et la compréhensibilité.
    • Ça ressemble à un projet intéressant. Si vous ciblez des utilisateurs ordinaires, il faut s’attendre à ce qu’ils mettent du contenu aux quatre coins extrêmes de la feuille pour voir si le moteur s’écroule.
      Si vous autorisez 1 million × 1 million de cellules et stockez null dans toutes les cellules non remplies, vous allez épuiser la mémoire. Il faut donc envisager un stockage clairsemé du contenu des cellules. Une solution consiste à utiliser une implémentation de table de hachage comme hashbrown. Le propos de cet article porte sur des détails de bas niveau ; si vous commencez par une table de hachage pour éviter les premières contraintes mémoire, vous n’avez pas besoin d’y réfléchir trop profondément pour l’instant.
    • J’ai effectivement déjà créé un moteur de tableur en Rust. Il n’est pas open source, mais je peux donner quelques conseils. Avant de tirer profit de la méthode de cet article, vous rencontrerez d’abord beaucoup d’autres problèmes de performance.
      Le problème isolé le plus difficile est la stratégie d’évaluation.

  • Et https://doc.rust-lang.org/reference/type-layout.html#the-alignment-modifiers ?

  • Il me semble qu’il y a un bug dans le code d’exemple.
    field_map[idx] = svec.len - 1;
    Ce sera incorrect si svec contient déjà size ailleurs que dans la dernière entrée.