SE-0202: Random Unification

Argh, my apologies. I agree these need to be requirements with default implementation to accompany them. So this raises the question, should next(upperBound:) also be a requirement? (I feel as if it should now). I’m not sure if I can update the proposal at this point (can I?), but I will definitely update it after a decision to accept or reject it has been made.

Glad we’re on the same page now! :-)

For next(upperBound:), do we expect some generators to have an optimized custom version? If so then yes.

I don’t know the procedural specifics. Perhaps update the proposal and ping the review manager @Ben_Cohen?

You can absolutely update your proposal, you just need to keep @Ben_Cohen in the loop about what you're changing and why.

I have a couple of questions: doesn't the lack of mutating in this design preclude most structs from implementing RandomNumberGenerator? If so, why isn't the protocol constrained to AnyObject?

Also, what was your reasoning for not making next mutating? I'm not saying it should be; I just think that the reason it isn't should be documented.

2 Likes

That’s a great point, @hlovatt and @Nobody1707. For small generators like Xoroshiro128+, a struct is a natural fit. There’s no reason to require a class (and thus a heap allocation) for a generator whose state is just two instances of UInt64.

So I concur: RandomNumberGenerator methods like next() should be mutating.

5 Likes

There is a reason to let the generator have an identity, it does have a state, after all. When you pass a generator as an argument through various functions, you expect it's state to have changed after you "get it back" and continue to use it for the next thing, right? So either all those random(... using: ...) has to be inout (for the generator), or you use a final class.

Details

I've experimented with different ways of structuring a Random API in Swift (focus on high performance and seedable prng for graphics/audio/general data processing) over the last couple of years, and one of the first things I settled on was to use final class for the generators. I've tested the performance of various implementations of eg SplitMix64 and Xoroshiro128+ generators extensively both in micro benchmarks and in several real use cases and using a final class rather than a struct doesn't incur any overhead at all (the optimizer does a good job in this case). But using a struct made it impossible/impractical to use in a lot of common situations.

Here's an example generator from the current version of my little lib:

/// The xoroshiro128+ generator, translated from:
/// http://xoroshiro.di.unimi.it/xoroshiro128plus.c
/// This generator is higher quality and "generally faster" than SplitMix64.
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
    }
}

This is really fast. Here is an example of using it to produce random simd float2 values in the range [-1, 1) (for x and y) using a similar method to the range conversion from UInt64 to unit range Double that I showed in my first post in this thread, but here the 64 bits are used as two 32-bit values that are converted to xy in [-1, 1):

import AppKit
import simd

func test() {
    // Generating and adding a billion random float2 values takes 1.7 seconds.
    // (MacBook Pro (Retina, 15-inch, Late 2013), 2 GHz Intel Core i7)
    let rg = Xoroshiro128Plus()
    let sampleCount = 5
    let iterationCount = 1_000_000_000
    for _ in 0 ..< sampleCount {
        var sum = float2(0, 0)
        let t0 = CACurrentMediaTime()
        for _ in 0 ..< iterationCount {
            let v = rg.next().float2InMirroredUnitRange // xy in [-1, 1)
            sum = sum + v
        }
        let t1 = CACurrentMediaTime()
        print("time:", t1 - t0, "seconds, sum:", sum)
    }
}
test()

Here's the output:

time: 1.77398550696671 seconds, sum: float2(8866.03, -3739.31)
time: 1.7318291279953 seconds, sum: float2(-2833.5, 9740.43)
time: 1.71480693900958 seconds, sum: float2(-9193.63, 31648.9)
time: 1.80105038301554 seconds, sum: float2(35128.7, 45299.6)
time: 1.92562632507179 seconds, sum: float2(7253.67, 28513.9)
3 Likes

So, would you agree that RandomNumberGenerator should be constrained to AnyObject?

Probably (but why : AnyObject rather than : class ?), here's what I have for my little lib:

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)
}

And they get a default initializer (with a truly random seed) like this:

import Security

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)
    }
}
2 Likes

Unless I'm mistaken, the class constraint has been deprecated in favor of AnyObject, and will be removed in a future version of Swift.

Edit: Yes, it was deprecated as part of SE-0156

Wow, I had no idea. Using ": class" compiles without warnings with Xcode 9.2 and Xcode 9.3 betas and latest dev snapshot. Will see how Xcode 9.3 behaves (installing).

Is there any reason why stateless generators need to become classes? Random?

1 Like

The stateless generators should largely be the default ones inside the standard library. The syntactical overhead of making the stateless RNG's into classes should be made up for by the ease of use elsewhere. Do remember that they would have still been at least structs otherwise, they wouldn't have been free functions.

Wow. Well said, I was going to argue in favor of a PRNG but you convinced me. They should probably be left for external libraries to provide.

1 Like

What is your evaluation of the proposal?

9/10. I think it’s a step in the right direction!

Is the problem being addressed significant enough to warrant a change to Swift?

Yes.

Does this proposal fit well with the feel and direction of Swift?

I can’t say. I don’t have enough API experience with Swift. But crypto randomness is something that fits Swift’s correctness philosophy

If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

I mostly care about three things here: security, thread-safety and uniformity of implementation. This has two of those points. I think it fares well against other libraries on the same level.

How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Quick reading.


Fwiw, I’d like to see this implemented directly in the Stdlib. I’d like to see something as important as Randomness to be provided directly from Swift. I don’t like the idea of having the properties of the Random Engine change with the platform it’s run in.

Swift is very fast. Granted, not as fast as it could be with ownership semantics, but that’s coming sooner or later. We could replace the C random libraries with Swift libraries, and go beyond in features and correctness.

But that’s probably better left for a future proposal.

Implementing a whole Random suite would take a lot of work. On the other hand, this proposal is great because it fixes most of the current shortcomings that we need fixed today.

A Swift-based engine can wait. We need to take this step first, and I’m happy with that.

1 Like

I have another question: why is next(upperBound:) implemented using modulo instead of multipliedFullWidth(by: upperBound).high? Is there some issue with using a full width multiplication?

1 Like

This justification should be in the proposal honestly. This is great motivation as to why we cannot go 'all in' on ranges.

I am definitely in support of the proposal.

I believe the Swift standard library should offer the base protocols that have the ability to cover most use cases of randomness when extended. I also think that there should be a single RandomNumberGenerator provided for people to use as the default. This generator should not be able to seeded. Extra generators and distributions etcetera should be provided in a third-party module that may eventually become a sanctioned first-party non-standard library.

Luckily, my beliefs line up with the proposal as written, and I therefore have no blocking objections.

The only thing I would say is that Random.default is not a good name for the standard library provided generator. I think it should be DefaultRandomNumberGenerator or SystemRandomNumberGenerator or similar, with the property called shared.

5 Likes

That sort of implementation detail is not actually relevant to Swift Evolution. The proposal does not specify the algorithm, so it can always be updated in the future if improvements are found.

…that said, I just looked at the implementation for next(upperBound:) and I’m pretty sure it does not work as intended.

The current code
public func next<T: FixedWidthInteger & UnsignedInteger>(upperBound: T) -> T {
  let range = T.max % upperBound
  var random: T = 0
  
  repeat {
    random = self.next()
  } while random < range
  
  return random % upperBound
}

The line “let range = T.max % upperBound” really ought to be something like:

let temp = T.max % upperBound + 1
let range = (temp == upperBound) ? 0 : temp

I was only asking because I always use multipliedFullWidth in mine, and I was worried I was missing a drawback. It was a bit off-topic though, so sorry about that.

I like it overall.

Here are a few things I would like to see added:

  • An additional protocol for seedable/repeatable PRNGs that adds the ability to seed, store and restore a generator's state. That way we can build on them even if we don't know which one is being used.
  • More definition on the expected memory model. e.g. Are the using: parameters inout?
  • The variants of next defined in the protocol itself so they can be overridden by a particular implementation (From the comments, I believe this was the intent)
  • collection.randomElement() would be slightly clearer than collection.random()
  • Bool.random(oneIn: 1_000_000) //Returns true one out of the given UInt times.

Yes, definitely

Yes, the additions are minimal, but provide a good base to build on.

I would really like to see a protocol for seeded/repeatable generators as well, since those are the ones I will use most often, and it would be nice to interoperate with other's code in this area rather than reinventing the wheel for each PRNG...

I have built several random facilities in Swift myself, and this doesn't have as much power, but I am hoping it gives enough standardization that I can utilize the work of others and vice versa.

I like how GameKit allows interchangeable pieces of randomness, and I would like to see that in Swift in general.

I read and participated in the full discussion, and have built lots of randomness code for Swift (mainly for graphical effects which require a repeatable source).

4 Likes