SE-0202: Random Unification

Evolution Proposal Reviews
89

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