Swift の乱数生成が遅い？

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

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

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

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

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

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

![ins.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/194364/c8c2087c-20ab-5841-b702-c0f01d77b69c.jpeg)

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

# 改善策
代わりに見つけたのは`drand48()`という少し Low-Level な関数。[drand48](https://pubs.opengroup.org/onlinepubs/007908799/xsh/drand48.html) がちょうど [0,1) 範囲の乱数を生成してくれます。

```swift
func simulatePossibility() -> Bool {
    drand48() < rate
}
```
注意：ここで省きましたが、`drand48()`を使う前に必ず `srand48()`によって一回初期化してください。

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

![ins2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/194364/d3b21043-32f3-aefc-6b13-1999362a22c8.jpeg)

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

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

```swift
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 とその以前の方法を比べました：

![ran.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/194364/7d4455ef-4657-eb1a-9702-baeb00b9de2f.jpeg)


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

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

それを究明するには、ソースコードを覗く必要がありました。
`Int`の乱数方法は [swift/Integers.swift](https://github.com/apple/swift/blob/2335eb87f8840aea231f12c3f21a33519354bb13/stdlib/public/core/Integers.swift#L2635) に書いてあります。簡単に説明するため、半開区間だけを切り抜きます：

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

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

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

```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()`使ったので、続きます：

```swift
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](https://github.com/apple/swift/blob/main/stdlib/public/stubs/Random.cpp) から

```swift
#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](https://github.com/apple/swift/blob/main/stdlib/public/core/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](https://forums.swift.org/t/proposal-random-unification/6626)、同じことが言われたようです。

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

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

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

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