Posts Swift の乱数生成が遅い?
Post
Cancel

Swift の乱数生成が遅い?

問題

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

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

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

1
2
3
4
5
6
7
8
9
10
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) 範囲の乱数を生成してくれます。

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

注意:ここは省略されましたが、drand48() を使う前に必ず srand48() によって一回初期化してください。

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

まともに測ろう

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

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

1
2
3
4
5
6
7
8
9
10
11
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)
        }
    }
}
// 他の5つを省略

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

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

なぜ?

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

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

1
2
3
4
5
6
7
8
9
10
11
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 は数値の絶対値部分を表す。 2: その長さ delta を上限として乱数 Generator に渡し、[0, delta) の範囲の乱数を生成し、その乱数を最初に与えられた範囲の下限に足して、最終乱数になります。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
  }
}

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

1
2
3
4
5
6
7
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 から

1
2
3
4
5
6
#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 に、drand48Double に。実際色んな場面で使うと型変換しなければならない。
  • 違う関数の範囲の指定がバラバラで、紛らわしい。例えば arc4random が上限しか指定できなくて、[100, 200) 範囲にしたい時、上限を100にして、その後乱数に100を足す必要がある。
  • Swift が様々なところで実行しています。違うプラットフォームでは違う乱数生成の方法があって、クロスプラットフォーム開発者に対してはかなりの苦痛でしょう。

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

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

まとめ

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

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

This post is licensed under CC BY 4.0 by the author.

Swift でアプリ内アイテム絞り込みの話

直感で性能改善をするな!

Comments powered by Disqus.