What about putting all random functions in an own random object. That would always make it explicit which random number generator is used and we would not have some „hidden“ global state.
Then just create a default generator called random to make everything easily discoverable. And if there really is a need to use a custom generator, the app could simply create a new one and use exactly the same API.
@tali I suggested the same a while back - it would be great to have a library of generators.
I'd also rather see static members over free functions. One more argument: In contexts where the type is known, leading dot syntax allows for shorter code while still not cluttering global namespace:
something.color = .random()
// vs
something.color = randomColor()
7 Likes
As the thread about sequences started to talk about RNGs, I think it's fair to talk about Sequence here ;-)
Isn't RandomNumberGenerator just Sequence where Element == Int64 in disguise?
And on the other hand, wouldn't it be desirable to be able to use distributions like those in @nnnnnnnn's cool playground as RNGs themselves?
I think it's feasible to build a "random number generator generator" on top of the proposal without changing any detail, but I didn't try yet...
Hmm, my Xoroshiro128Plus final class implementation seems to be about 40 (!) times faster than your Xorshift128Plus , ie, it performs 400 million masking additions in the same time as your Xorshift128Plus does 10 million. Yes they are different generators, but I'm assuming that Xoroshiro128Plus isn't 40 times faster than Xorshift128Plus algorithmically?
Anyway, here's what I did:
I converted your code into a Command Line App (just a few minor adjustments) as I don't like to do performance metrics in any other way (except on some iOS device when necessary of course).
These are the results that I got (on my MBP late 2013, 2 GHz Intel Core i7):
arc4random (2 calls) 1.4396 4294967295
arc4random_buf 2.2526 648368209
Xorshift128Plus (struct) 0.1782 610931914
Xorshift128Plus 0.7387 707966945
ThreadLocking<Xorshift128Plus> 1.3608 2348117867
LinearCongruential (struct) 0.1701 4010776896
LinearCongruential 0.5071 1913470656
ThreadLocking<LinearCongruenti 1.0558 4288772416
They look very similar to yours (except that the class versions are not marked with "(class)" by the code in the gist).
Running my entirely separate (but I think essentially equivalent) test program (see below), that is testing only my implementation of Xoroshiro128Plus (and again, it is a different generator than Xorshift128Plus, but I'm guessing that it's not 40 times faster algorithmically), I get this:
time: 0.0169437950244173 seconds (checksum: 11605410945142439131 )
time: 0.0169420730089769 seconds (checksum: 17241852839264922271 )
time: 0.0168698579072952 seconds (checksum: 17685997167798807342 )
time: 0.0165533649269491 seconds (checksum: 8398418167523955030 )
time: 0.0166222950210795 seconds (checksum: 2212566004850123018 )
Would you be interested in checking out my test program, verify that it is relevant to compare it to your test, and maybe add Xoroshiro128Plus (as a final class) to your test and see if it somehow gets slower when doing so (or, which I doubt, 40 times faster than Xorshift128Plus)?
Here's my test program (just copy paste it into the main of a fresh Command Line Project in Xcode 9.3, default toolchain):
import AppKit
protocol RandomGenerator : class {
/// Returns the next random bit pattern and advances the state of the
/// random generator.
func next() -> UInt64
}
/// A pseudo random UInt64 bit pattern generator type.
///
/// The generated UInt64 values can be converted to other types by using eg
/// extensions on UInt64 for converting it to Double or float2 in unit range.
///
/// A random generator only have to implement two initializers and the
/// next() -> UInt64 method.
protocol PseudoRandomGenerator : RandomGenerator {
associatedtype State
/// The current state of the random generator.
var state: State { get }
/// Creates a a new random generator with the given state. The initializer
/// fails if the given state is invalid according to the random generator.
init?(state: State)
/// Creates a a new random generator with a state that is determined by
/// `seed`. Each `seed` must result in a unique valid state.
init(seed: UInt64)
}
// NOTE: The SplitMix64 is included here only because it is used to scramble
// the seed of Xoroshiro128Plus, this is the way I have it in my original code
// and I've just copy pasted these in here so ...
/// The splitmix64 generator, translated from:
/// http://xorshift.di.unimi.it/splitmix64.c
final class SplitMix64 : PseudoRandomGenerator {
var state: UInt64
/// Every UInt64 value is a valid SplitMix64 state.
init(state: UInt64) { self.state = state }
init(seed: UInt64) { self.state = seed }
func next() -> UInt64 {
state = state &+ 0x9E3779B97F4A7C15
var z = state
z = (z ^ (z >> UInt64(30))) &* 0xBF58476D1CE4E5B9
z = (z ^ (z >> UInt64(27))) &* 0x94D049BB133111EB
return z ^ (z >> UInt64(31))
}
}
final class Xoroshiro128Plus : PseudoRandomGenerator {
var state: (UInt64, UInt64)
/// The state of Xoroshiro128Plus must not be everywhere zero.
init?(state: (UInt64, UInt64)) {
guard state.0 != 0 || state.1 != 0 else { return nil }
self.state = state
}
init(seed: UInt64) {
// Uses SplitMix64 to scramble the given seed into a valid state:
let sm = SplitMix64(seed: seed)
state = (sm.next(), sm.next())
}
func next() -> UInt64 {
func rol55(_ x: UInt64) -> UInt64 {
return (x << UInt64(55)) | (x >> UInt64(9))
}
func rol36(_ x: UInt64) -> UInt64 {
return (x << UInt64(36)) | (x >> UInt64(28))
}
let result = state.0 &+ state.1
let t = state.1 ^ state.0
state = (rol55(state.0) ^ t ^ (t << UInt64(14)), rol36(t))
return result
}
}
extension PseudoRandomGenerator {
/// Creates a new pseudo random generator seeded with a cryptographically
/// secure random seed.
init() {
var seed: UInt64 = 0
withUnsafeMutableBytes(of: &seed) { (ptr) -> Void in
let sc = SecRandomCopyBytes(nil, ptr.count, ptr.baseAddress!)
precondition(sc == errSecSuccess)
}
self.init(seed: seed)
}
}
func test() {
let rg = Xoroshiro128Plus()
let sampleCount = 5 // Number of times to perform the test.
let iterationCount = 10_000_000 // Number of values to sum.
for _ in 0 ..< sampleCount {
var cs = 0 as UInt64
let t0 = CACurrentMediaTime()
for _ in 0 ..< iterationCount {
cs = cs &+ rg.next()
}
let t1 = CACurrentMediaTime()
print("time:", t1 - t0, "seconds (checksum:", cs, ")")
}
}
test()
EDIT: Gah! I can't believe I actually did the Debug/Release mistake ... (double checked this right after posting the above). The correct results for your test program (converted to Command Line) on my machine is:
arc4random (2 calls) 0.5864 4294967295
arc4random_buf 2.2445 733145136
Xorshift128Plus (struct) 0.0129 3613348595
Xorshift128Plus 0.0129 2955512274
ThreadLocking<Xorshift128Plus> 0.2393 3016061566
LinearCongruential (struct) 0.0127 3534163904
LinearCongruential 0.0127 3739340608
ThreadLocking<LinearCongruenti 0.2270 3775278784
Which makes much more sense ...
I'm leaving this here as a warning example to others, and because: Look! The results for the struct and class versions of your Xorshift128Plus and LinearCongruential are now the same!
(yes, I ran the test a couple of times until they were exactly the same.)
I'm afraid it looks an awful lot like you might have done the old Release/Debug mistake too ... : ) Did you?
If so, the conclusion is that there is indeed no difference between having them as final class vs struct, once the optimizer has been allowed to do its work. This is in line with my previous experience and experiments in this exact matter.
1 Like
I ended up just adding your generator to @nnnnnnnn's test, both in struct and class form, so they're all run under the same conditions (I also changed this to a command line program):
import Foundation
let N = 10_000_000
public protocol RandomNumberGenerator {
mutating func next() -> UInt64
}
/// A struct version of the Xorshift128+ PRNG.
public struct Xorshift128PlusStruct : RandomNumberGenerator {
private var xS: UInt64
private var yS: UInt64
public init(xSeed: UInt64 = 0, ySeed: UInt64 = UInt64.max) {
xS = xSeed == 0 && ySeed == 0 ? UInt64.max : xSeed
yS = ySeed
for _ in 0..<10 { _ = next() }
}
public mutating func next() -> UInt64 {
var x = xS
let y = yS
xS = y
x ^= x &<< 23
yS = x ^ y ^ (x &>> 17) ^ (y &>> 26)
return yS &+ y
}
}
/// A class version of the Xorshift128+ PRNG.
public final class Xorshift128Plus : RandomNumberGenerator {
private var xS: UInt64
private var yS: UInt64
public init(xSeed: UInt64 = 0, ySeed: UInt64 = UInt64.max) {
xS = xSeed == 0 && ySeed == 0 ? UInt64.max : xSeed
yS = ySeed
for _ in 0..<10 { _ = next() }
}
public func next() -> UInt64 {
var x = xS
let y = yS
xS = y
x ^= x &<< 23
yS = x ^ y ^ (x &>> 17) ^ (y &>> 26)
return yS &+ y
}
}
final class SplitMix64 : RandomNumberGenerator {
var state: UInt64
/// Every UInt64 value is a valid SplitMix64 state.
init(state: UInt64) { self.state = state }
init(seed: UInt64) { self.state = seed }
func next() -> UInt64 {
state = state &+ 0x9E3779B97F4A7C15
var z = state
z = (z ^ (z >> UInt64(30))) &* 0xBF58476D1CE4E5B9
z = (z ^ (z >> UInt64(27))) &* 0x94D049BB133111EB
return z ^ (z >> UInt64(31))
}
}
struct Xoroshiro128PlusStruct : RandomNumberGenerator {
var state: (UInt64, UInt64)
/// The state of Xoroshiro128Plus must not be everywhere zero.
public init(xSeed: UInt64 = 0, ySeed: UInt64 = UInt64.max) {
state = (xSeed == 0 && ySeed == 0 ? UInt64.max : xSeed, ySeed)
for _ in 0..<10 { _ = next() }
}
mutating func next() -> UInt64 {
func rol55(_ x: UInt64) -> UInt64 {
return (x << UInt64(55)) | (x >> UInt64(9))
}
func rol36(_ x: UInt64) -> UInt64 {
return (x << UInt64(36)) | (x >> UInt64(28))
}
let result = state.0 &+ state.1
let t = state.1 ^ state.0
state = (rol55(state.0) ^ t ^ (t << UInt64(14)), rol36(t))
return result
}
}
final class Xoroshiro128Plus : RandomNumberGenerator {
var state: (UInt64, UInt64)
public init(xSeed: UInt64 = 0, ySeed: UInt64 = UInt64.max) {
state = (xSeed == 0 && ySeed == 0 ? UInt64.max : xSeed, ySeed)
for _ in 0..<10 { _ = next() }
}
func next() -> UInt64 {
func rol55(_ x: UInt64) -> UInt64 {
return (x << UInt64(55)) | (x >> UInt64(9))
}
func rol36(_ x: UInt64) -> UInt64 {
return (x << UInt64(36)) | (x >> UInt64(28))
}
let result = state.0 &+ state.1
let t = state.1 ^ state.0
state = (rol55(state.0) ^ t ^ (t << UInt64(14)), rol36(t))
return result
}
}
/// A struct version of a linear congruential PRNG.
public struct LCRNGStruct: RandomNumberGenerator {
private var state: UInt64
public init(seed: Int) {
self.state = 0
reseed(seed)
}
public mutating func reseed(_ seed: Int) {
state = UInt64(truncatingIfNeeded: seed)
for _ in 0..<10 { _ = next() }
}
public mutating func next() -> UInt64 {
// Values from https://nuclear.llnl.gov/CNP/rng/rngman/node4.html
state = 2862933555777941757 &* state &+ 3037000493
return state
}
}
/// A class version of a linear congruential PRNG.
public final class LCRNG: RandomNumberGenerator {
private var state: UInt64
public init(seed: Int) {
self.state = 0
reseed(seed)
}
public func reseed(_ seed: Int) {
state = UInt64(truncatingIfNeeded: seed)
for _ in 0..<10 { _ = next() }
}
public func next() -> UInt64 {
// Values from https://nuclear.llnl.gov/CNP/rng/rngman/node4.html
state = 2862933555777941757 &* state &+ 3037000493
return state
}
}
/// A wrapper that makes an underlying RNG thread-safe using a mutex lock.
public final class ThreadLocking<Base: RandomNumberGenerator & AnyObject> : RandomNumberGenerator {
private var base: Base
private var mutex = pthread_mutex_t()
public init(_ base: Base) {
self.base = base
pthread_mutex_init(&mutex, nil)
}
public func next() -> UInt64 {
pthread_mutex_lock(&mutex)
defer { pthread_mutex_unlock(&mutex) }
return base.next()
}
}
/// Run the given test and print the time it took.
func test(name: String, body: () -> UInt) {
let start = Date()
let result = body()
let elapsed = Date().timeIntervalSince(start)
print(name.padding(toLength: 30, withPad: " ", startingAt: 0), terminator: "")
print(String(format: "% 9.4f %15u", elapsed, result))
}
/// Create a low-level test - call next() directly on a generator
func makeLowLevelTest<T: RandomNumberGenerator>(_ generator: inout T) -> () -> UInt {
var gen = generator
return {
var x = 0 as UInt64
for _ in 0..<N {
x = x &+ gen.next()
}
return UInt(x)
}
}
var xorshift = Xorshift128Plus(xSeed: numericCast(arc4random()))
var xoroshiro = Xoroshiro128Plus(xSeed: numericCast(arc4random()))
var lcrng = LCRNG(seed: numericCast(arc4random()))
var xorshiftTS = ThreadLocking(Xorshift128Plus(xSeed: numericCast(arc4random())))
var xoroshiroTS = ThreadLocking(Xoroshiro128Plus(xSeed: numericCast(arc4random())))
var lcrngTS = ThreadLocking(LCRNG(seed: numericCast(arc4random())))
var xorshiftStruct = Xorshift128PlusStruct(xSeed: numericCast(arc4random()))
var xoroshiroStruct = Xoroshiro128PlusStruct(xSeed: numericCast(arc4random()))
var lcrngStruct = LCRNGStruct(seed: numericCast(arc4random()))
test(name: "arc4random (2 calls)") {
var x = 0 as UInt64
for _ in 0..<N {
x = x &+ UInt64(truncatingIfNeeded: arc4random() as UInt32) << 32 |
UInt64(truncatingIfNeeded: arc4random() as UInt32)
}
return UInt(x)
}
test(name: "arc4random_buf") {
var x = 0 as UInt64
for _ in 0..<N {
var y = 0 as UInt64
arc4random_buf(&y, 8)
x = x &+ y
}
return UInt(x)
}
test(name: "Xorshift128Plus (struct)", body: makeLowLevelTest(&xorshiftStruct))
test(name: "Xorshift128Plus", body: makeLowLevelTest(&xorshift))
test(name: "ThreadLocking<Xorshift128Plus>", body: makeLowLevelTest(&xorshiftTS))
test(name: "Xoroshiro128Plus (struct)", body: makeLowLevelTest(&xoroshiroStruct))
test(name: "Xoroshiro128Plus", body: makeLowLevelTest(&xoroshiro))
test(name: "ThreadLocking<Xoroshiro128Plus>", body: makeLowLevelTest(&xoroshiroTS))
test(name: "LinearCongruential (struct)", body: makeLowLevelTest(&lcrngStruct))
test(name: "LinearCongruential", body: makeLowLevelTest(&lcrng))
test(name: "ThreadLocking<LinearCongruential>", body: makeLowLevelTest(&lcrngTS))
I compiled with swiftc -O rngtest.swift and ran just as ./rngtest. On my machine, xorshift128+ is faster than xoroshiro128+, but also, the classes run at the same speed as the structs, which surprises me (partly because the value types seem like they should be faster, and also because it's so different to @nnnnnnnn's results: maybe they weren't run with optimisations?) .
arc4random (2 calls) 0.3911 4294967295
arc4random_buf 1.5705 530869187
Xorshift128Plus (struct) 0.0096 1904382362
Xorshift128Plus 0.0098 1113546016
ThreadLocking<Xorshift128Plus> 0.1752 2366965213
Xoroshiro128Plus (struct) 0.0113 225536279
Xoroshiro128Plus 0.0106 2172793984
ThreadLocking<Xoroshiro128Plus 0.1745 903944754
LinearCongruential (struct) 0.0094 101854656
LinearCongruential 0.0096 288215360
ThreadLocking<LinearCongruenti 0.1750 4284116288
Please see the EDIT of my previous post, which I probably wrote while you were writing your reply.
Your results (and mine) is exactly what I'd expect.
I wrote some weeks ago upthread that my experiments has shown that having the generators as final class doesn't incur any performance overhead at all (compared to struct passed as inout), I guess the optimizer does a very good job with these and manages to turn them into code that is identical to struct. I remember that I implemented generators as final class, struct, and as closures (closing over their state). They were all equally fast.
Xoroshiro128Plus might be a bit slower than the older Xorshift128Plus, but I haven't looked into it. It is a very slight difference anyway, but it would be interesting to know why/if it should actually be the case.
EDIT:
I did a quick check. According to the comments in what I think is the official C implementation of xorshift+:
This generator has been replaced by xoroshiro128plus, which is significantly faster and has better statistical properties.
But let's remember that this is only a single (very basic) test, perhaps in the majority of other kinds of tests, it is indeed faster, or perhaps there is some opportunity for improvement in this particular Swift implementation (and/or in Swift's optimizer!) that would make it faster.
I think BCryptoGenRandom() in Windows is a typo in CryptoGenRandom().
@tinysun212, please see CryptGenRandom (deprecated) and BCryptGenRandom.
That's right—in an extremely Nate move, those stats are from an unoptimized run. (I swear I double-checked.)
The primary performance factors look to me like (1) the size of the state (arc4random is huge compared to the others) and (2) locking vs not. I don't think we want to take either of those out of the default generator, so there will definitely be room for one of the other generators for people who need maximum performance and are willing to manage a generator dependency.
My answer would be "no" on both of these — generators are used fundamentally differently than distributions, and we don't want or need the cost of wrapping the next random value in an optional. If you want to use the output of a generator in a sequence context, it'd be easy to wrap the generator in an AnySequence or another custom sequence type.
On the second point, the idea of the distributions is that they are deliberately limited in range (which a generator's output cannot be) and/or non-uniform (likewise).
Proposal Accepted With Revision
The core team has decided to accept this proposal, with the following revisions:
-
The method to get a random element from a collection should be named
Collection.randomElement() -> Element? -
Since not all platforms will be able to provide an implementation of random that’s a cryptographically secure source of randomness, and that different platforms and users have different priorities, the decision of exactly which implementation to use for the default random number generator will be left to that platform's implementation of Swift. Where a platform vendor recommends certain sources of randomness, that should be preferred. Note that users should not rely on a particular implementation:
we intentionally give the vendor permission to change the implementation in the future.The standard library should document the implementation used on each platform. The recommendation is that it should aspire to being cryptographically secure and provide a high quality source of randomness, balanced with a need for reasonable performance. When the vendor cannot achieve these goals, they should document it.
-
The core team decided to keep the proposal's use of static methods. While the use of a free function may help with discoverability, it would lead to a proliferation of overloaded free functions for generating random values for other types. In particular, "full-width" random functions, such as for a
Bool, would require overloading purely by return type with a free function. -
The random number generator argument should be taken
inout. This is in keeping with other similar parts of the language (such as the recently acceptedHasher), will allow for value-typed stateful generators, and in the future, move-only generators.
Thanks again to everyone for participating in the review!
9 Likes
Was there consideration of the Random and Random.default naming? It seems like a sub-par name for the standard library random number generator. I proposed DefaultRandomNumberGenerator and it appeared to get consensus acceptance (e.g. here). I don't mind if the core team decided against an alternative naming, just checking this detail wasn't overlooked.
Basically, that's what I meant with "Sequence in disguise": Conformance isn't included, but it's very simple and straightforward to add it -- even more simple than I thought... (edited: but not that much more simple - none-optional return values aren't enough for conformance ;-)
extension Random: IteratorProtocol, Sequence {
public func next() -> UInt64? {
let result: UInt64 = next()
return result
}
}
What is the exact difference you see between a generator and a distribution?
I'm no expert for RNGs, but I have the strong expectation that those try to mimic a discrete uniform distribution, just like your DiscreteDistribution.
Or is the output of the generator not a single UInt64 (which obviously is limited in range), but rather the whole sequence of bits produced by the generator?
(this might once again be a situation where math collides with computer science: It's very common for "real" distributions to allow true infinite values).
A generator is a particular type of distribution: a uniform distribution over the range 0...UInt64.max. Those are the semantic requirements of the RandomNumberGenerator protocol. If a generator is non-uniform or has a different range, none of the other methods that take a RandomNumberGenerator will behave as documented.
The distributions that I included in the playground show a variety of kinds of distributions, with a variety of kinds of domains. For example, the GuassianDistribution produces floating-point values from a normal distribution with a given mean and standard deviation. So while every generator could be used as a distribution, not every distribution could be used as a generator.
More important, in my opinion, is that generators are a low-level tool that enable high-level APIs like the distributions in the playground or myArray.randomElement(). I don't see a compelling use case for needing to iterate over the raw UInt64 values that a generator produces, and would rather encourage people to develop high-level APIs (either in third-party libraries or the stdlib) that can transform a generator's raw random data into something meaningful for a developer to use.
4 Likes
I think it's sensible to call anything that can generate a sequence of pseudo-random numbers (no matter if those are int or floats, or have specific limits) a generator, but...
I agree on that: Swift needs a source of randomness, and it's good to have a protocol for that, so that you can decouple those levels.
But the border between those layers is quite jaggy:
I'm quite sure most developers will never have to specify a custom RandomNumberGenerator -- but they'll always see this option in autocompletion.
More important, transformation of "raw randomness" already happens on many occasions:
Methods like randomElement and ClosedRange.random need a different distribution than RandomNumberGenerator, so they have to perform the same task that UniformIntegerDistribution does.
UniformContinuousDistribution, on the other hand, is equivalent to BinaryFloatingPoint.random -- and I think for floats, the issues might become more clear:
Uniform distribution is often the right choice for integers, but it's uncommon for everything else, and you much more often need a gaussian distribution.
So, now (or in the near future ;-), we'll be able generate floats out of the box easily -- but with a distribution that most likely isn't what we need.
It is very simple to specify a low-level detail (RandomNumberGenerator), but we have no standardized way to specify an important high-level aspect. Therefor, my worry is that we might end up with two completely different ways to to the same thing (that is, choosing a random number with a certain distribution):
let uniform = Double.random(in: 0.0..<360.0) // uniform distribution has special support
let distanceToCenter = GaussianDistribution(standardDeviation: 10).next()!
Sorry,@bzamayo, this is my bad. I missed your suggestion from my review summary when we discussed it.
I agree with you that a more explicit name would be an improvement. Putting Default in the name also has precedent from DefaultIndices. Can you do me a favor and post this suggestion as a new thread in pitches? We could then consider it as an amendment to the proposal, depending on the feedback there.
No worries Ben! I wrote up an amendment thread as requested.
1 Like
I am not a math geek, nor a simulation enthusiast. The times when I've relied on seeded RNGs providing the same results have all been where no changes in my toolchain are occurring. Unit testing, or debugging some algorithm. I suspect most developers that Swift would be reaching fall into this category. Those that need predictability across toolchains are probably using portable implementations anyway, as the problem already exists if you cross languages or platforms.