Swift の乱数生成が遅い？

問題

自作アプリでシミュレーションシステムを開発する時、こんな要件がありました：
カードの特技がある確率で発動することにして、実際に発動するかどうかをシミュレートしてください。だが、シミュレートの回数が合計ほぼ百万回に近い。

言い換えると：
ある事象が発生する確率は rate であり、その事象の発生状況を百万回シミュレートしてください。

最初は Swift 4.2 から提供された Random API を使いました：

class LSSkill {
    // 発動確率（0.8 => 80%）
    let rate: Double

    // 小数を [0,1) の範囲で生成して、rate より小さい場合、発動したと判定。
    func simulatePossibility() -> Bool {
        Double.random(in: 0..<1) < rate
    }
｝

理屈はもちろん大丈夫ですが、Instrument で profile したところ、乱数生成が、スコアシミュレーション全体時間のほぼ四分の一を占めました。

シミュレーション自体が 0.3s 未満とはいえ、改善の余地があれば見逃すわけにはいけませんね！！（神経質）

改善策

代わりに見つけたのはdrand48()という少し Low-Level な関数。drand48 がちょうど [0, 1) 範囲の乱数を生成してくれます。

func simulatePossibility() -> Bool {
    drand48() < rate
}

drand48に入れ替わっただけで、時間が先程の方法よりだいぶ縮みました：

まともに測ろう

実機ではちゃんと整理できなかったので、テスト環境でmeasureを使っていろんな方法実行速度を比べましょう。

測定コードはこのよう、なるべく無関係要素を除きたいので、範囲と乱数 Generator を for…in 循環の外に置きます。

let total = 200_0000
func testDoubleRandom() throws {
    measure {
	let range = 0..<1.0
        var gene = SystemRandomNumberGenerator()
        for _ in 0..<total {
            let _ = Double.random(in: range, using: &gene)
        }
    }
}
// 他の５つを省略

測ったのは、[0,1) での小数生成と、[100, 200) での整数と小数の生成。Random API とその以前の方法を比べました：

Random API が範囲・型に関わらず大体同じ速度に保っていて、すべて Low-Level 関数に上回っていますね、やはりちょっと遅い気がします。

なぜ？

Random API が公式が実現してくれたもので、本来から言うと最適化されたはずですが、もともと存在した関数より遅いのはなぜ？

それを究明するには、ソースコードを覗く必要がありました。
Intの乱数方法は swift/Integers.swift に書いてあります。簡単に説明するため、半開区間だけを切り抜きます：

public static func random<T: RandomNumberGenerator>(
    in range: Range<Self>,
    using generator: inout T
) -> Self {
    // ...
    // 1
    let delta = Magnitude(truncatingIfNeeded: range.upperBound &- range.lowerBound) 
    // 2
    return Self(truncatingIfNeeded:
      Magnitude(truncatingIfNeeded: range.lowerBound) &+
      generator.next(upperBound: delta) // => 次のコードブロック
    ) 
  }

1. 与えられた範囲の長さを計算。メモリリークにならないためビット演算とtruncatingIfNeededによる初期化になります。Magnitude は数値の絶対値部分を表す。
2. その長さ delta を上限として乱数 Generator に渡して、[0, delta) の範囲の乱数を生成し、その乱数を最初に与えられた範囲の下限に足して、最終乱数になります。

では、その乱数 Generator がどのように乱数を生成したのですか？デフォルトとしてSystemRandomNumberGeneratorが使用されていますが、上限付きのnext()はプロトコルRandomNumberGeneratorのデフォルト関数として書いています：
（次の２つブロックは swift/Random.swift から）

public protocol RandomNumberGenerator {
  mutating func next() -> UInt64
}

extension RandomNumberGenerator {
  public mutating func next<T: FixedWidthInteger & UnsignedInteger>(
    upperBound: T
  ) -> T {
    _precondition(upperBound != 0, "upperBound cannot be zero.")
#if arch(i386) || arch(arm)
    let tmp = (T.max % upperBound) + 1
    let range = tmp == upperBound ? 0 : tmp
    var random: T = 0
    repeat {
      random = next() // => 次のコードブロック
    } while random < range
    return random % upperBound
#else
    // ...
#endif
  }
}

正直ここの乱数生成のアルゴリズムを理解していませんが、とりあえずSystemRandomNumberGeneratorのnext()使ったので、続きます：

public struct SystemRandomNumberGenerator: RandomNumberGenerator {
  public mutating func next() -> UInt64 {
    var random: UInt64 = 0
    swift_stdlib_random(&random, MemoryLayout<UInt64>.size) // => 次のコードブロック
    return random
  }
}

続きはswift_stdlib_random。ついに Swift 言語を実現した cpp の領域に踏み入りました。
swift/Random.cpp から

#if defined(__APPLE__) // APPLE のプラットフォームでしたら
SWIFT_RUNTIME_STDLIB_API
void swift_stdlib_random(void *buf, __swift_size_t nbytes) {
  arc4random_buf(buf, nbytes);
}
// ...他のプラットフォームでの実現

遠回りして、結局 arc4random に辿り着きましたか…ここまでにするともう次に探索する必要がありません。小数の実現 swift/FloatingPointRandom.swift を探ると同じくSystemRandomNumberGeneratorを使っていることがわかりました。

つまり、Random API がarc4randomを使った上で、ほかの操作を加えて今のInt.random関数になりました。生のarc4randomに比べると遅いのは当たり前のことです。

しかし、これまでのコードを見た結果、Low-Level 関数にいくつ欠点があります：

• 具体的な型に制限されています。arc4random系の関数がUInt32に、drand48がDoubleに。実際色んな場面で使うと型変換しなければなりません。
• 違う関数の範囲の指定がバラバラで紛らわしい。例えばarc4randomが上限しか指定できなくて、[100, 200) 範囲にしたい時、上限を100にして、その後乱数に100を足す必要があります。
• Swift が様々なところで実行しています。違うプラットフォームでは違う乱数生成の方法があって、クロスプラットフォーム開発者に対してはかなりの苦痛でしょう。

実際、Random API に関する最初の提案では Proposal Random Unification - Discussion - Swift Forums、同じことが言われたようです。

Swift コミュニティは、これらの欠点を解消するため、型・範囲・プラットフォームに対して汎用化した乱数 API を実装し、統一したことで開発に大きな利便性が持たされました。

まとめ

この記事は Swift の乱数生成の中の仕組みを探索し、ちょっとだけ遅い原因を究明しました。

遅いとは言え、短時間で百万回実行する必要がなく、一回二回だけでしたら全然気にすることはありません。そんな無視できる程度の性能改善より、コードの統一性と可読性が遥かに重要だと思います。

以上です。なにか間違えたことがあれば気軽にコメントお願いします！