Warum ich rand für eine kleinere und konsistentere Zufallszahlen-API geforkt habe

• Das führende Rust-Crate für Zufallszahlen, rand, verteilt alltägliche Operationen über mehrere Traits; deshalb wurde urandom mit einer kleineren öffentlichen und Implementierungsoberfläche sowie einer konsistenteren Nutzungserfahrung entwickelt
• High-Level-Operationen werden in einer einzigen Random-Struktur gebündelt und der Rng-Trait ist sealed; Vorrang haben API-Auffindbarkeit und interne Optimierung statt Unterstützung beliebiger Generatoren
• Ohne einen neuen Zufallszahlenalgorithmus einzuführen, wählt es die Ausgabefunktionen von Xoshiro256 je nach Einsatzzweck und erzielt in einem Benchmark zur Erzeugung von 1.000 f64 gegenüber rand 0.10.2 rund 31 % höheren Durchsatz
• Für gleichverteiltes Integer-Sampling werden wiederverwendbare und einmalige Pfade in einer einzigen unverzerrten Implementierung mit verzögerter Schwellwertberechnung vereinheitlicht; im Benchmark für den Bereich 500..20_000 war sie schneller als beide Pfade von rand
• Die Rohausgabe bei explizitem Seed garantiert Reproduzierbarkeit über unterstützte Architekturen und SemVer-kompatible Releases hinweg, verzichtet aber auf Anbindung beliebiger Generatoren sowie auf das umfangreiche Ökosystem von rand für Verteilungen und Third-Party-Integrationen

---

Eine gebündelte Random-API

• Die nützlichen Operationen von rand sind über mehrere Traits verteilt
  • Für das Erzeugen von Zufallswerten in Bereichen braucht man RngExt, für die Auswahl aus Sequenzen IndexedRandom, für das Mischen SliceRandom
  • rand 0.10 bietet Helfer auf Root-Ebene wie rand::random_range für einmalige Aufrufe
  • Wer einen RNG-Handle behalten oder Sequenzoperationen wie Auswählen und Mischen nutzen will, muss weiterhin Methoden aus mehreren Traits finden
• Auch wenn ein prelude die Imports reduziert, muss man wissen, ob Erweiterungsmethoden auf RNGs, Slices oder Iteratoren angewendet werden; allein per IDE-Autovervollständigung sind sie schwer zu finden
• urandom platziert die High-Level-Consumer-API in einer einzigen Random-Wrapper-Struktur
  • urandom::new() erzeugt Random<urandom::rng::Xoshiro256Rng>
  • uniform, choose und shuffle lassen sich auf demselben Objekt aufrufen
  • Per Autovervollständigung sieht man random, uniform, chance, choose, shuffle, sample usw.
  • Da alles inhärente Methoden sind, muss man keine High-Level-Erweiterungstraits suchen oder importieren

Ein sealed Rng: Optimierung statt Erweiterbarkeit

• rand behandelt Low-Level-RNG-Traits als öffentliche Erweiterungspunkte, doch der Rng-Trait von urandom ist sealed; unterstützte Generatoren werden innerhalb des Crates ausgewählt und implementiert
  • Beliebige Generatoren können nicht an Random angeschlossen werden
  • Um neue Generatoren hinzuzufügen, muss urandom selbst geändert werden
• Wenn bessere Algorithmen das Ziel sind, sind Xoshiro256 und ChaCha bereits als aktuelle Standardauswahl für ihre jeweiligen Rollen etabliert, und Empfehlungen ändern sich nur langsam
  • Wenn bessere Optionen entstehen, können sie in einem künftigen Major-Release übernommen werden
• Für Kompatibilität mit anderen Projekten, Programmiersprachen, Legacy-Algorithmen, spezieller Hardware oder simulationsspezifischen Generatoren reicht es nicht, nur denselben Generator zu verwenden
  • Auch zugehörige Algorithmen wie gleichverteiltes Sampling und Mischen müssen identisch sein; daher ist eine dedizierte Implementierung, die den gesamten Vertrag erfüllt, besser geeignet
• Dank des sealed Traits kann urandom nur die benötigten Rohoperationen hinzufügen, ohne Implementierungsverträge für unbekannte Generatoren und Sonderfälle entwerfen und dokumentieren zu müssen
  • Generatoren und Algorithmen können aufeinander abgestimmt und spezialisiert werden, was einige Optimierungen ermöglicht, die in rand nicht nutzbar sind
• Für die meisten Anwendungen ist Entropy-Auswahl nützlicher als eine neue PRNG-Implementierung
  • Konkrete Generatoren stellen native from_seed-Konstruktoren bereit
  • Man kann ein Random mit explizitem Seed erzeugen, etwa ChaCha12Rng::from_seed(seed)
  • Beliebige RNG-Implementierungen werden nicht akzeptiert, aber die Erweiterungspunkte, die fortgeschrittene Nutzer voraussichtlich brauchen, bleiben erhalten

Leistungsgewinne mit denselben Algorithmen

• urandom verwendet keine neuen Zufallszahlenalgorithmen
  • Auf 64-Bit-Systemen nutzen urandom::new() für nicht-kryptografische Zwecke und rand::rngs::SmallRng dieselbe Xoshiro256-Familie
  • urandom::csprng() für kryptografische Zwecke und rand::rngs::StdRng verwenden ChaCha12
  • Der interne Generator der Komfortfunktion rand::rng() ist ebenfalls ChaCha12
• Die Generator-Schnittstelle von rand liefert Integer-Wörter und das Füllen von Bytes, daher fordern auch Verteilungen, die f64 benötigen, zunächst ein vollständiges u64 an
• urandom::Rng bietet neben next_u32 und next_u64 auch next_f32 und next_f64
  • Zufällige Fließkommazahlen benötigen weniger Zufallsbits als ein vollständiges Wort
  • Generatoren können diese Methoden mit günstigeren Ausgabefunktionen überschreiben
• Die Xoshiro-Implementierung teilt sich die Zustandsübergänge, trennt aber die Ausgabepfade
  • Für u64 bleibt Xoshiro256++ erhalten
  • Für u32 und Fließkommazahlen wird das schnellere Xoshiro256+ verwendet, dessen obere Bits für diese Zwecke ausgelegt sind
• Ergebnisse eines Mikrobenchmarks, der mit urandom 1.0 und rand 0.10.2 jeweils 1.000 Zufallszahlen erzeugte:
  • Xoshiro u64: beide 814 ns
  • Xoshiro u32: rand 836 ns, urandom 788 ns
  • Xoshiro f64: rand 1.033 ns, urandom 788 ns
  • ChaCha12 f64: rand 2.199 ns, urandom 2.011 ns
• Der End-to-End-Durchsatz für Xoshiro f64 war etwa 31 % höher und die Laufzeit 24 % kürzer; der u64-Pfad für dieselbe Arbeit lag dagegen praktisch gleichauf
• ChaCha12 überschreibt next_f64 nicht, daher ist die Performance weitgehend ähnlich
• Exakte Zeiten hängen von Maschine und Compiler ab; die genauen Bedingungen stehen in den vollständigen Benchmark-Notizen

Ein vereinheitlichter Pfad für gleichverteiltes Sampling

• Wendet man auf Integers schlicht den Restoperator mit der Bereichslänge an, entsteht Verzerrung; korrektes gleichverteiltes Integer-Sampling muss daher einen Teil der Generatorausgaben verwerfen
• Die genaue Berechnung des Rejection-Schwellwerts erfordert eine teure Restoperation
  • Wird ein Sampler wiederholt verwendet, lässt sich das als initialer Setup-Aufwand akzeptieren
  • Wenn nur ein Wert erzeugt wird, fällt dieser Aufwand relativ stark ins Gewicht
• rand macht diese Unterschiede über den UniformSampler-Trait sichtbar
  • Das erzeugte UniformInt berechnet den Schwellwert vorab und sampelt unverzerrt
  • Rng::random_range nutzt einen separaten Hook sample_single oder sample_single_inclusive, um initiales Setup zu vermeiden
  • In der Standardfunktionalität verwendet der einmalige Kurzpfad einen zweiten Algorithmus, der leicht verzerrt ist
  • Das optionale Feature unbiased ersetzt ihn durch eine komplexere iterative Version
• urandom berechnet den Schwellwert verzögert und verwendet für wiederverwendbare wie einmalige Bereiche dieselbe unverzerrte Multiplikations- und Rejection-Implementierung
  • Es folgt dem in Daniel Lemires Paper von 2018 Fast Random Integer Generation in an Interval beschriebenen Verfahren
  • Für die meisten praktischen Bereiche wird der erste Kandidat vor einer Division zurückgegeben
  • Kann der erste Kandidat nicht zurückgegeben werden, wird der exakte Schwellwert berechnet und anschließend unverzerrt iteriert
  • Auch der Sonderfall range == 0, bei dem der gesamte Bereich angefordert wird, wird behandelt
• Ohne separate Methoden, zweiten Algorithmus, vorgelagerten Setup-Aufwand oder verzerrten schnellen Pfad verarbeitet dieselbe Implementierung wiederverwendbare Verteilungen und einmalige Bereiche
• Benchmark-Ergebnisse für das Ziehen von 1.000 Werten aus dem Bereich 500..20_000:
  • Wiederverwendetes UniformInt: rand 1.098 ns, urandom 950 ns
  • Einmaliger Bereich: rand 1.079 ns, urandom 942 ns
• Die rand-Ergebnisse beziehen sich auf die Standardfunktionen; die schnellere einmalige Zeile nutzt also einen leicht verzerrten Pfad, während urandom unverzerrt schneller war als beide Pfade

Reproduzierbarkeit über Releases und Architekturen hinweg

• urandom behandelt Reproduzierbarkeit als Teil des öffentlichen Vertrags
  • Bei gleichem explizitem Seed und gleicher Abfolge von Low-Level-RNG-Aufrufen bleibt die Rohausgabe deterministischer Generatoren erhalten
  • Stabilität wird über unterstützte Architekturen und SemVer-kompatible Releases hinweg garantiert
  • Ein 64-Bit-Server und ein 32-Bit-WebAssembly-Client können dieselbe Generatorbasis für Replay verwenden
• Um diese Kompatibilität zu wahren, wird auf 32-Bit-Architekturen Performance geopfert
• Das ist eine stärkere Garantie als die Reproduzierbarkeitsrichtlinie von rand
  • Portable Generatoren und Sampling-Algorithmen von rand können in Minor-Releases andere Ausgaben liefern
  • SmallRng und StdRng sind ausdrücklich nicht portabel und können sich auch je nach Plattform oder Bibliotheksrelease ändern

Kosten der Entscheidung und Einsatzkriterien

• urandom bündelt allgemeine Operationen in Random, sodass sie ohne Erweiterungstraits leicht auffindbar sind
• Durch gemeinsames Design von Generatoren und Verteilungen implementiert es günstigere Xoshiro-Ausgabepfade und einen einzigen unverzerrten Pfad für gleichverteiltes Sampling
• Der stabile Rohstrom explizit geseedeter Generatoren kann für deterministische Spiele und Simulationen genutzt werden
• Dafür können keine beliebigen Generatoren eingebracht werden, und auch die größere Liste an Verteilungen sowie das Third-Party-Integrationsökosystem von rand fehlen
• Wer ein breites Ökosystem braucht, ist mit rand gut bedient; wer eine kleine API-Oberfläche, Auffindbarkeit, integrierte Optimierungen und eine starke Reproduzierbarkeitsrichtlinie bevorzugt, kann urandom wählen
• Das Paket ist auf crates.io, in der API-Dokumentation und im GitHub-Quellcode verfügbar

[GN⁺]

Lobste.rs-Kommentare

• Es gibt gute Gründe, rand zu forken, aber der Name urandom klingt wie eine Bibliothek, die mit /dev/urandom zu tun hat

  • Sieht nützlich aus, aber der Name kann verwirrend sein. Hätte ich nur den Namen gesehen, ohne den Artikel zu lesen, hätte ich vermutlich gedacht, dass sie von Datei-Ein-/Ausgabe abhängt, und sie mir nicht näher angesehen

• Ich stimme dem Problemverständnis zu, aber pub fn new() -> Random<impl Rng + Clone> gefällt mir nicht
  Wenn man die gesamte Anwendung mit Random<T> where T: Rng parametrisiert, bringt das mehr umständliche Arbeit mit sich, und Kompilierzeit sowie dyn-bezogene Probleme werden gravierend. Ich würde lieber struct Random einen konkreten Typ geben oder ersatzweise struct Random<T = rng::Xoshiro256Rng> wählen

• Aus ähnlicher Frustration habe ich schon einmal selbst etwas gebaut, aber keinen Fork, und mit deutlich weniger Funktionen als rand

• Es freut mich, dass jemand mit demselben Problem tatsächlich versucht hat, es zu lösen. Rust scheint einen seltsamerweise dazu zu drängen, Bibliotheken voller Trait-Suppe zu bauen
  Der zentrale Datentyp der Datenbank, mit der ich beruflich arbeite, muss mindestens 15 Traits implementieren, deshalb ist die Autovervollständigung katastrophal und die Dokumentation verwirrend. Ich habe die Zahl der Traits etwas reduziert, stoße dabei aber oft auf Probleme wie zyklische Abhängigkeiten oder darauf, dass sich zentrale Tests nicht schreiben lassen

  • Das ist ein Phänomen, das entsteht, wenn Architektur-Astronauten aus der Java-Welt denselben objektorientierten Stil auf Rust anwenden. Zyklische Abhängigkeiten sind ein Zeichen dafür, dass man entweder ein einziges Ding gewaltsam aufgeteilt hat, das sich noch nicht trennen lässt, oder drei Dinge nicht sauber unterschieden hat. Wenn man die vollständige Kontrolle über den Code hat, kann man statt Traits einfach Enums verwenden
  • Im Rust-Krypto-Ökosystem ist das Problem der Trait-Suppe besonders schlimm, geradezu zum Wahnsinnigwerden

• Diese Bibliothek erinnert mich sowohl an APOSDs deep interfaces als auch an Filippós kryptografische Arbeit, die so gestaltet ist, dass man nur schwer Fehler machen kann, und das ist beides hohes Lob

  • Allerdings gibt urandom::new() keinen kryptografisch sicheren Zufallszahlengenerator zurück, also ist das Design nicht völlig fehlersicher. Gerade weil Linux-/dev/urandom sicher ist, ist das noch verwirrender

• Als weitere rand-Alternative gibt es den einfachen und schnellen Zufallszahlengenerator fastrand. Er ist einfacher als rand und urandom, bietet aber auch weniger Funktionen