より小さく一貫した乱数APIのためにrandをフォークした理由

 (casualhacks.net)
1 ポイント 投稿者 GN⁺ 2 시간 전 | 1件のコメント | WhatsAppで共有
  • Rustの代表的な乱数クレート rand は、日常的な操作が複数のトレイトに分散しているため、より小さな公開・実装サーフェスと一貫した使用体験を備えた urandom を開発した
  • 高水準の操作を1つの Random 構造体に集約し、Rng トレイトを封印することで、任意の生成器サポートよりも APIの発見しやすさ と内部最適化を優先した
  • 新しい乱数アルゴリズムは導入せず、Xoshiro256の出力関数を用途別に選択することで、1,000個の f64 生成ベンチマークで rand 0.10.2より約 31%高いスループット を記録した
  • 一様整数サンプリングは、しきい値を遅延計算する単一の 非バイアス実装 により、再利用・単発パスを統合し、500..20_000 範囲のベンチマークで rand の2つのパスより高速だった
  • 明示的シードの生出力は、対応アーキテクチャとSemVer互換リリースで再現性を保証する一方、任意の生成器接続 と rand の広大な分布・サードパーティ統合エコシステムは手放している

1つに集約した Random API

  • rand の有用な操作は複数のトレイトに分散している
    • 乱数範囲の生成には RngExt、シーケンス選択には IndexedRandom、シャッフルには SliceRandom が必要
    • rand 0.10は単発呼び出し向けに rand::random_range のようなルートレベルのヘルパーを提供している
    • RNGハンドルを保持したり、選択・シャッフルのようなシーケンス操作を使ったりするには、依然として複数のトレイトのメソッドを探す必要がある
  • preludeでインポートを減らしても、拡張メソッドがRNG、スライス、イテレータのどの型に適用されるかを知る必要があるため、IDEの自動補完だけでは見つけにくい
  • urandom は、高水準の利用者向けAPIを1つの Random ラッパー構造体 に配置する
    • urandom::new() で Random<urandom::rng::Xoshiro256Rng> を生成する
    • uniform、choose、shuffle を同じオブジェクトから呼び出せる
    • 自動補完で random、uniform、chance、choose、shuffle、sample などを確認できる
    • すべて固有メソッドなので、高水準の拡張トレイトを探したりインポートしたりする必要がない

拡張性ではなく最適化を選んだ封印済み Rng

  • rand は低水準RNGトレイトを公開された拡張ポイントとして扱うが、urandom の Rng トレイトは封印 されており、対応する生成器をクレート内部で選択して実装する
    • 任意の生成器を Random に接続することはできない
    • 新しい生成器を追加するには urandom 自体を変更する必要がある
  • よりよいアルゴリズムが目的なら、現在の役割別のデフォルト選択としてXoshiro256とChaChaがすでに定着しており、推奨もゆっくり変わる
    • よりよい選択肢が生まれれば、将来のメジャーリリースで採用できる
  • 他のプロジェクト・プログラミング言語・レガシーアルゴリズム・特殊ハードウェア・シミュレーション専用生成器と互換にするには、生成器が同じだけでは不十分
    • 一様サンプリングやシャッフルなど関連アルゴリズムまで同じである必要があるため、契約全体を実装した専用実装のほうが適している
  • 封印済みトレイトにより、未知の生成器や例外状況のための実装契約を設計・文書化せずに、urandom に必要なプリミティブ操作だけを追加できる
    • 生成器とアルゴリズムを互いに合わせて特殊化でき、rand では使えない一部の最適化が可能になる
  • ほとんどのアプリケーションでは、新しいPRNG実装よりも エントロピーの選択 のほうが有用
    • 具体的な生成器はネイティブな from_seed コンストラクタを公開する
    • ChaCha12Rng::from_seed(seed) のように、明示的シードを使った Random を作成できる
    • 任意のRNG実装は受け付けないが、上級ユーザーが必要とすると予想される拡張ポイントは維持している

同じアルゴリズムから得た性能向上

  • urandom は新しい乱数生成アルゴリズムを使っていない
    • 64ビットシステムで非暗号用途の urandom::new() と rand::rngs::SmallRng は同じ Xoshiro256系 を使う
    • 暗号用途の urandom::csprng() と rand::rngs::StdRng は ChaCha12 を使う
    • 便利関数 rand::rng() の内部生成器もChaCha12
  • rand の生成器インターフェースは整数ワードとバイト埋めを提供するため、f64 が必要な分布でも完全な u64 から要求する
  • urandom::Rng は next_u32、next_u64 だけでなく next_f32 と next_f64 も提供する
    • 浮動小数点乱数は完全なワードより少ない乱数ビットで済む
    • 生成器はこれらのメソッドをより安価な出力関数で再定義できる
  • Xoshiro実装は状態遷移を共有しつつ、出力パスを分けている
    • u64 にはXoshiro256++を維持する
    • u32 と浮動小数点には、上位ビットがその用途向けに設計された、より高速なXoshiro256+を使う
  • urandom 1.0と rand 0.10.2でそれぞれ1,000個の乱数を生成したマイクロベンチマーク結果は以下のとおり
    • Xoshiro u64: どちらも 814ns
    • Xoshiro u32: rand 836ns、urandom 788ns
    • Xoshiro f64: rand 1,033ns、urandom 788ns
    • ChaCha12 f64: rand 2,199ns、urandom 2,011ns
  • Xoshiro f64 のエンドツーエンドのスループットは約31%高く、実行時間は24%短かったが、同じ処理を行う u64 パスは実質的に同等だった
  • ChaCha12は next_f64 を再定義していないため、性能はおおむね近い
  • 正確な時間はマシンとコンパイラによって変わり、詳細な条件は 全ベンチマークノート で確認できる

1つに統合した一様サンプリングパス

  • 整数を範囲長で単純に剰余演算すると バイアス が生じるため、正しい一様整数サンプリングでは生成器出力の一部を棄却する必要がある
  • 正確な棄却しきい値の計算には、コストの高い剰余演算が必要
    • サンプラーを繰り返し使うなら、初期設定コストとして受け入れられる
    • 値を1つだけ生成する場合、このコストは相対的に大きくなる
  • rand はこの違いを UniformSampler トレイトとして公開する
    • 生成された UniformInt はしきい値を事前計算し、バイアスなしにサンプリングする
    • Rng::random_range は初期設定を避けるため、別の sample_single または sample_single_inclusive フックを使う
    • デフォルト機能では、単発の短縮パスがややバイアスのある第2のアルゴリズムを使う
    • オプションの unbiased 機能は、これをより複雑な反復版に置き換える
  • urandom はしきい値を 遅延計算 し、再利用範囲と単発範囲の両方に単一の非バイアスな乗算・棄却実装を使う
    • Daniel Lemireの2018年の論文 Fast Random Integer Generation in an Interval に記載された方式に従う
    • ほとんどの実用的な範囲では、最初の候補が除算前に返される
    • 最初の候補を返せない場合は、正確なしきい値を計算したうえでバイアスなく反復する
    • 全範囲が要求される range == 0 の例外も処理する
  • 別メソッドや第2のアルゴリズム、先行設定コスト、バイアスのある高速パスなしに、同じ実装で再利用分布と単発範囲を処理する
  • 500..20_000 の範囲で1,000個を抽出したベンチマーク結果は以下のとおり
    • 再利用 UniformInt: rand 1,098ns、urandom 950ns
    • 単発範囲: rand 1,079ns、urandom 942ns
  • rand の結果はデフォルト機能基準なので、より速い単発行もややバイアスのあるパスである一方、urandom は非バイアスのまま両方のパスより高速だった

リリースとアーキテクチャをまたぐ再現性

  • urandom は 再現性 を公開契約の一部として扱う
    • 同じ明示的シードと同じ低水準RNG呼び出し順序が与えられれば、決定論的生成器の生出力が維持される
    • 対応アーキテクチャとSemVer互換リリース全体で安定性を保証する
    • 64ビットサーバーと32ビットWebAssemblyクライアントが、再生用に同じ生成器基盤を使用できる
  • この互換性を維持するため、32ビットアーキテクチャでは性能を犠牲にしている
  • rand の再現性ポリシー より強い保証である
    • rand のポータブル生成器とサンプリングアルゴリズムは、マイナーリリースで出力が変わる可能性がある
    • SmallRng と StdRng は明示的にポータブルではなく、プラットフォームやライブラリリリースによっても変わり得る

選択の代償と適用基準

  • urandom は一般的な操作を Random に集約し、拡張トレイトなしで見つけやすくしている
  • 生成器と分布を一緒に設計することで、より安価なXoshiro出力パスと単一の非バイアス一様サンプリングパスを実装している
  • 明示的にシード指定された生成器の安定した生ストリームは、決定論的ゲームとシミュレーション に活用できる
  • その代わり、任意の生成器を持ち込むことはできず、rand が提供するより大きな分布リストやサードパーティ統合エコシステムも備えていない
  • 広範なエコシステムが必要なら rand が適しており、小さなAPIサーフェス・発見しやすさ・統合された最適化・強い再現性ポリシーを好むなら urandom を選べる
  • パッケージは crates.io、APIドキュメント、GitHubソース で確認できる

関連記事

1件のコメント

 
GN⁺ 2 시간 전
Lobste.rs のコメント

  • rand をフォークする理由は十分あるが、urandom という名前は /dev/urandom に関連するライブラリのように聞こえる

    • 有用そうではあるが、名前が混乱を招く可能性がある。記事を読まずに名前だけ見ていたら、ファイル入出力に依存すると思って調べなかっただろう

  • 問題意識には同意するが、pub fn new() -> Random<impl Rng + Clone> は気に入らない
    アプリケーション全体を Random<T> where T: Rng としてパラメータ化すると面倒な作業が増え、コンパイル時間や dyn 関連の問題が深刻になる。むしろ struct Random が具体型を持つようにするか、次善策として struct Random<T = rng::Xoshiro256Rng> を選ぶ

  • 似たようなもどかしさからすでに自作したことがあるが、フォークではなく、rand より機能はずっと少ない

  • 自分と同じ問題を感じた誰かが実際に解決に動いてくれてうれしい。Rust には妙に トレイトスープ ライブラリを作らせる傾向があるように思う
    仕事で扱うデータベースの中核データ型は少なくとも 15 個のトレイトを実装しなければならず、自動補完はひどいしドキュメントも混乱している。トレイト数をいくらか減らしたが、循環依存や中核テストを書けなくなる問題によく阻まれる

    • Java 出身の アーキテクチャ宇宙飛行士 たちが同じオブジェクト指向スタイルを Rust に持ち込んだ結果だ。循環依存は、まだ分離できない 1 つの対象を無理に分けたか、あるいは 3 つの対象をきちんと区別できていないことのシグナルだ。コードをすべて自分で制御できるなら、トレイトの代わりに列挙型を使えばよい
    • Rust の 暗号エコシステム ではトレイトスープ問題がとりわけひどく、うんざりする

  • このライブラリは APOSD の 深いインターフェース と、Filippo のミスしにくいよう設計された暗号関連の仕事の両方を思い出させる。どちらも大いに称賛したい

    • ただし urandom::new() は 暗号学的に安全な乱数生成器 を返さないので、完全にミス不可能な設計ではない。特に Linux の /dev/urandom は安全なので、なおさら紛らわしい

  • 別の rand 代替として、シンプルで高速な乱数生成器 fastrand もある。rand や urandom より単純だが、機能も少ない