Pourquoi j’ai forké `rand` pour une API de nombres aléatoires plus petite et cohérente

• Le crate Rust de référence pour les nombres aléatoires, rand, répartit les opérations courantes sur plusieurs traits ; urandom a donc été développé avec une surface publique et d’implémentation plus réduite, ainsi qu’une expérience d’utilisation cohérente
• Les opérations de haut niveau sont regroupées dans une seule structure Random et le trait Rng est scellé, afin de privilégier la découvrabilité de l’API et les optimisations internes plutôt que la prise en charge de générateurs arbitraires
• Sans introduire de nouvel algorithme aléatoire, il choisit la fonction de sortie de Xoshiro256 selon l’usage et obtient environ 31 % de débit en plus que rand 0.10.2 dans un benchmark générant 1 000 f64
• L’échantillonnage uniforme d’entiers unifie les chemins réutilisables et ponctuels dans une seule implémentation non biaisée avec calcul différé du seuil ; dans un benchmark sur la plage 500..20_000, il a été plus rapide que les deux chemins de rand
• La sortie brute avec seed explicite garantit la reproductibilité sur les architectures prises en charge et entre versions compatibles SemVer, mais renonce au branchement de générateurs arbitraires ainsi qu’au vaste écosystème de distributions et d’intégrations tierces de rand

---

Une API Random réunie en un seul endroit

• Les opérations utiles de rand sont réparties sur plusieurs traits
  • La génération dans une plage aléatoire nécessite RngExt, la sélection dans une séquence requiert IndexedRandom, et le mélange utilise SliceRandom
  • rand 0.10 fournit des helpers à la racine comme rand::random_range pour les appels ponctuels
  • Mais dès qu’il faut conserver un handle RNG ou utiliser des opérations sur des séquences comme la sélection ou le mélange, il faut toujours retrouver les méthodes de plusieurs traits
• Même si les imports sont réduits via le prelude, il faut encore savoir si une méthode d’extension s’applique à un RNG, un slice ou un itérateur ; difficile donc de la retrouver avec le seul auto-complétion de l’IDE
• urandom place l’API consommateur de haut niveau dans une unique structure enveloppe Random
  • urandom::new() crée un Random<urandom::rng::Xoshiro256Rng>
  • uniform, choose et shuffle peuvent être appelés sur le même objet
  • L’auto-complétion permet de voir random, uniform, chance, choose, shuffle, sample, etc.
  • Ce sont toutes des méthodes propres ; inutile de retrouver ou d’importer des traits d’extension de haut niveau

Un Rng scellé pour privilégier l’optimisation à l’extensibilité

• rand traite son trait RNG bas niveau comme un point d’extension public, mais dans urandom, le trait Rng est scellé afin de choisir et implémenter les générateurs pris en charge à l’intérieur du crate
  • Impossible de brancher un générateur arbitraire à Random
  • Ajouter un nouveau générateur impose de modifier urandom lui-même
• Si l’objectif est d’avoir un meilleur algorithme, Xoshiro256 et ChaCha sont déjà les choix par défaut selon les usages, et les recommandations évoluent lentement
  • Si une meilleure option apparaît, elle pourra être adoptée dans une future version majeure
• Pour rester compatible avec d’autres projets, langages, algorithmes legacy, matériel spécialisé ou générateurs dédiés à la simulation, le générateur seul ne suffit pas
  • Il faut aussi partager les algorithmes associés, comme l’échantillonnage uniforme et le mélange ; une implémentation dédiée du contrat complet est donc plus adaptée
• Grâce au trait scellé, urandom peut ajouter uniquement les opérations brutes dont il a besoin, sans devoir concevoir ni documenter un contrat d’implémentation pour des générateurs inconnus et des cas particuliers
  • Les générateurs et les algorithmes peuvent être spécialisés les uns pour les autres, ce qui permet certaines optimisations impossibles dans rand
• Dans la plupart des applications, le choix de l’entropie est plus utile qu’une nouvelle implémentation de PRNG
  • Les générateurs concrets exposent des constructeurs natifs from_seed
  • On peut créer un Random avec une seed explicite, comme ChaCha12Rng::from_seed(seed)
  • Les implémentations RNG arbitraires ne sont pas acceptées, mais les points d’extension que les utilisateurs avancés devraient réellement vouloir restent présents

Des gains de performance avec les mêmes algorithmes

• urandom n’utilise pas de nouvel algorithme de génération aléatoire
  • Sur les systèmes 64 bits, urandom::new() pour les usages non cryptographiques et rand::rngs::SmallRng utilisent la même famille Xoshiro256
  • Pour les usages cryptographiques, urandom::csprng() et rand::rngs::StdRng utilisent ChaCha12
  • Le générateur interne de la fonction de confort rand::rng() est lui aussi ChaCha12
• L’interface de générateur de rand fournit des mots entiers et le remplissage d’octets ; une distribution qui a besoin de f64 demande donc aussi des u64 complets
• urandom::Rng fournit non seulement next_u32 et next_u64, mais aussi next_f32 et next_f64
  • Les nombres aléatoires à virgule flottante ont besoin de moins de bits aléatoires qu’un mot complet
  • Les générateurs peuvent redéfinir ces méthodes avec une fonction de sortie moins coûteuse
• L’implémentation Xoshiro partage la transition d’état tout en séparant les chemins de sortie
  • Pour u64, elle conserve Xoshiro256++
  • Pour u32 et les flottants, elle utilise le plus rapide Xoshiro256+, dont les bits de poids fort sont conçus pour cet usage
• Les résultats des microbenchmarks générant 1 000 nombres aléatoires avec urandom 1.0 et rand 0.10.2 sont les suivants
  • Xoshiro u64 : 814ns des deux côtés
  • Xoshiro u32 : rand 836ns, urandom 788ns
  • Xoshiro f64 : rand 1,033ns, urandom 788ns
  • ChaCha12 f64 : rand 2,199ns, urandom 2,011ns
• Le débit de bout en bout sur Xoshiro f64 est environ 31 % plus élevé et le temps d’exécution 24 % plus court, tandis que le chemin u64 réalisant la même tâche était pratiquement à égalité
• ChaCha12 ne redéfinit pas next_f64, donc les performances restent globalement proches
• Les temps exacts varient selon la machine et le compilateur ; les conditions détaillées sont disponibles dans les notes de benchmark complètes

Un chemin unifié pour l’échantillonnage uniforme

• Faire un simple modulo sur la longueur d’une plage d’entiers introduit un biais ; un échantillonnage uniforme correct doit donc rejeter une partie des sorties du générateur
• Le calcul exact du seuil de rejet nécessite une opération modulo coûteuse
  • Si l’échantillonneur est réutilisé de nombreuses fois, ce coût peut être amorti lors de l’initialisation
  • Pour générer une seule valeur, ce coût devient relativement important
• rand expose cette différence via le trait UniformSampler
  • Le UniformInt construit précalcule le seuil afin d’échantillonner sans biais
  • Rng::random_range utilise des hooks séparés sample_single ou sample_single_inclusive pour éviter le coût d’initialisation
  • Dans la fonctionnalité par défaut, le chemin rapide ponctuel utilise un second algorithme légèrement biaisé
  • La fonctionnalité optionnelle unbiased le remplace par une version itérative plus complexe
• urandom utilise un calcul différé du seuil pour servir à la fois les plages réutilisées et ponctuelles avec une seule implémentation non biaisée de multiplication-rejet
  • Elle suit l’approche décrite dans l’article de Daniel Lemire de 2018, Fast Random Integer Generation in an Interval
  • Pour la plupart des plages pratiques, le premier candidat est renvoyé avant toute division
  • Si le premier candidat ne peut pas être renvoyé, le seuil exact est calculé puis la boucle reprend sans biais
  • Le cas particulier range == 0, demandé pour couvrir toute la plage, est également géré
• La même implémentation traite donc les distributions réutilisées et les plages ponctuelles, sans méthode séparée, sans second algorithme, sans coût d’initialisation préalable ni chemin rapide biaisé
• Dans un benchmark tirant 1 000 valeurs de la plage 500..20_000, les résultats étaient les suivants
  • UniformInt réutilisé : rand 1,098ns, urandom 950ns
  • Plage ponctuelle : rand 1,079ns, urandom 942ns
• Les résultats de rand correspondent aux fonctionnalités par défaut ; la ligne ponctuelle plus rapide utilisait donc un chemin légèrement biaisé, tandis que urandom restait plus rapide que les deux chemins tout en restant non biaisé

Reproductibilité entre releases et architectures

• urandom traite la reproductibilité comme une partie du contrat public
  • À seed explicite identique et séquence identique d’appels RNG bas niveau, la sortie brute des générateurs déterministes est conservée
  • La stabilité est garantie sur toutes les architectures prises en charge et entre releases compatibles SemVer
  • Un serveur 64 bits et un client WebAssembly 32 bits peuvent partager la même base de générateur pour rejouer une exécution
• Cette compatibilité se paie par un sacrifice de performance sur les architectures 32 bits
• Cela constitue une garantie plus forte que la politique de reproductibilité de rand
  • Les générateurs portables et les algorithmes d’échantillonnage de rand peuvent produire des sorties différentes dans une release mineure
  • SmallRng et StdRng ne sont explicitement pas portables et peuvent aussi changer selon la plateforme ou la release de la bibliothèque

Le coût du choix et quand l’adopter

• urandom regroupe les opérations générales dans Random, ce qui les rend faciles à trouver sans traits d’extension
• En concevant ensemble générateurs et distributions, il implémente un chemin de sortie Xoshiro moins coûteux et un chemin unique d’échantillonnage uniforme non biaisé
• Le flux brut stable de générateurs seedés explicitement peut servir à des jeux déterministes et simulations
• En contrepartie, on ne peut pas importer de générateur arbitraire et on ne bénéficie pas non plus de la liste plus large de distributions ni de l’écosystème d’intégrations tierces proposé par rand
• Si un vaste écosystème est nécessaire, rand reste adapté ; si l’on préfère une surface d’API réduite, la découvrabilité, des optimisations intégrées et une politique de reproductibilité forte, urandom peut être un meilleur choix
• Le package est disponible sur crates.io, dans la documentation API et dans les sources GitHub

[GN⁺]

Avis sur Lobste.rs

• Il y a suffisamment de raisons de forker rand, mais le nom urandom donne l’impression d’une bibliothèque liée à /dev/urandom

  • Elle semble utile, mais son nom peut prêter à confusion. Si je n’avais vu que le nom sans lire l’article, j’aurais pensé qu’elle dépendait des entrées/sorties de fichiers et je ne l’aurais probablement pas examinée

• Je partage le constat, mais pub fn new() -> Random<impl Rng + Clone> ne me plaît pas
  Paramétrer toute une application avec Random<T> where T: Rng ajoute beaucoup de travail pénible, et les problèmes de temps de compilation et liés à dyn deviennent sérieux. Je préférerais que struct Random ait un type concret, ou, à défaut, choisir struct Random<T = rng::Xoshiro256Rng>

• J’avais déjà créé quelque chose moi-même à cause d’une frustration similaire, mais ce n’est pas un fork, et il a beaucoup moins de fonctionnalités que rand

• Je suis content que quelqu’un qui ressent les mêmes problèmes que moi se soit vraiment attelé à les résoudre. Rust semble étrangement pousser à créer des bibliothèques en soupe de traits
  Les types de données centraux de la base de données sur laquelle je travaille doivent implémenter au moins 15 traits, ce qui rend l’autocomplétion catastrophique et la documentation confuse. Nous avons réduit une partie du nombre de traits, mais nous nous heurtons souvent à des dépendances circulaires ou à l’impossibilité d’écrire des tests essentiels

  • C’est un phénomène dû aux architectes astronautes venus de Java qui appliquent le même style orienté objet à Rust. Les dépendances circulaires signalent qu’on a artificiellement découpé une seule chose qui ne peut pas encore être séparée, ou qu’on n’a pas correctement distingué trois choses. Si vous contrôlez tout le code, utilisez des énumérations plutôt que des traits
  • Dans l’écosystème cryptographique de Rust, le problème de soupe de traits est particulièrement prononcé, au point d’en devenir exaspérant

• Cette bibliothèque me fait penser à la fois aux interfaces profondes d’APOSD et aux travaux de Filippo en cryptographie conçus pour être difficiles à mal utiliser, ce qui est dans les deux cas un grand compliment

  • Cela dit, comme urandom::new() ne renvoie pas un générateur de nombres aléatoires cryptographiquement sûr, la conception n’est pas totalement à l’épreuve des erreurs. C’est d’autant plus déroutant que, sous Linux, /dev/urandom est sûr

• Une autre alternative à rand est fastrand, un générateur de nombres aléatoires simple et rapide. Il est plus simple que rand et urandom, mais offre aussi moins de fonctionnalités