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) // => 次のコードブロック
)
}
- 与えられた範囲の長さを計算。メモリリークにならないためビット演算と
truncatingIfNeededによる初期化になります。Magnitude は数値の絶対値部分を表す。 - その長さ 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 の乱数生成の中の仕組みを探索し、ちょっとだけ遅い原因を究明しました。
遅いとは言え、短時間で百万回実行する必要がなく、一回二回だけでしたら全然気にすることはありません。そんな無視できる程度の性能改善より、コードの統一性と可読性が遥かに重要です。
以上です。
Discussion