Looking over the proposal again, I have to wonder: should we include more protocol requirements (with default implementations) in RandomNumberGenerator?
For example, in addition to the “next() -> UInt64” function, we could make the generic FixedWidthInteger version a protocol requirement, so developers of custom generators can use optimized implementations.
Perhaps more importantly, we could include a requirement akin to arc4random_buf(), which takes an inout MutableRawBufferPointer and fills it with random bits. Depending on the algorithm, this could potentially bring a significant speedup.
So yeah, this is something that has been brought up a few times, and I hope to answer it as best as I can.
In regards to the generic next<T: FixedWidthInteger & UnsignedInteger>() -> T version of next(), this isn't a requirement due to the fact that generators are good at one thing; producing a number. Requiring generators to do a job that they aren't designed to do doesn't seem correct. This is reflected with the single requirement, next(), and the default implementation of the generic next().
I agree that developers should have control over their custom generators, and they do! There is currently no restriction in the current design that disallows developers to implement their own version of the generic next(). I actually encourage developers to implement their own version of this function so that they can optimize away for their custom needs.
So I touched on this a little in the discussion, but I want to add that another goal of this proposal is to kind of escape from these "lower" level facilities, such as arc4random_buf.
These types of APIs don't fit well with this proposal's "general use" design that it is heavily built for. While I understand a lot of use cases for such facility, there's only so many problems it solves. The current design is geared to satisfy many, if not all for some, of the current pain points. I understand it doesn't solve everybody's problems, but it deliberately isn't sufficient for some. Again, I encourage those to design solutions that solve every single problem that they have. More power to you!
It sounds like you are saying two different things at once, so perhaps one or the other of us has a misunderstanding. I am going to write a few paragraphs about how protocol requirements and default implementations work in Swift, and I hope this doesn’t come across as patronizing.
Protocol requirements—the methods declared within the protocol itself—are dynamically dispatched. When a variable (or function parameter) is constrained to conform to the protocol, protocol requirements can be called on that variable and those calls will use the variable’s own implementation of those methods.
Protocol requirements with default implementations—meaning the method is declared within the protocol, and a protocol extension provides an implementation—are also dynamically dispatched (because they are protocol requirements). However, conforming types are not required to provide an implementation (because there is a default implementation).
Protocol extension methods—methods which are *not* declared within the protocol, but which a protocol extension provides an implementation—are statically dispatched. When a variable (or parameter) is constrained to conform to the protocol, protocol extension methods can be called on that variable. However, those calls will always use the implementation from the protocol extension. Even if the variable has its own version, it will not be called.
• • •
In other words, protocol requirements define *customization points*: If you want conforming types to have the *ability* to provide their own version of a function, then that function must be a protocol requirement. If you do not want them to have that ability, then it must not be a requirement.
Moreover, if you want conforming types to be *able* to provide their own version, but not *required* to do so, then it must be a protocol requirement *and* there must be a default implementation.
Does that make sense?
• • •
In particular, if we make the generic version of next() a protocol requirement, and also give it a default implementation, then conforming types will *not* be required to implement it (because there is a default implementation) but they will be *able* to do so if they desire.
Currently, with generic next() as an extension method—not a protocol requirement—conforming types are *unable* to provide a custom implementation. Or rather, if they do provide their own implementation, it will not be called from a generic context.
Similarly, if we make a “fill the buffer with random bits” method, both putting it in the protocol itself and providing an implementation in an extension, then conforming types will get that behavior for free (because it is in an extension) while still having the ability to customize it if they need to.
• • •
In summary:
• Protocol requirement are customization points.
• Extension methods are not.
• Protocol requirements with default implementations are customization points which conforming types don’t have to implement if they don’t want to.
I think that last one is what we want for generic next() and for “fill a buffer with random bytes”. Conforming types don’t have to implement them (because there is a default implementation), but if they do implement them then their custom version will be called (unlike a pure extension method).
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.
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.
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.
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()
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)
}
}
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).
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.
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.
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?
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.