Creating an array of random numbers in Swift is slow

[wigging (Gavin Wiggins)]

I'm trying to create a Swift function that creates an array of random numbers similar to the numpy.random.rand function in the NumPy package.

This example creates a large NumPy array with random numbers. I am using uv to run the Python code.

# Run with  ->  uv run main.py

import numpy as np

def main():
    n = 100_000_000
    a = np.random.rand(n)
    print("first value is", a[0])
    print("last value is", a[n - 1])

if __name__ == "__main__":
    main()

Here is my attempt to do the same thing in Swift.

// Build with  ->  swiftc main.swift -Ounchecked
// Run with    ->  ./main

func randomArray(_ count: Int) -> [Double] {
    let result = Array<Double>(unsafeUninitializedCapacity: count) { buffer, initCount in
        for i in 0..<count {
            buffer[i] = Double.random(in: 0...1)
        }
        initCount = count
    }
    return result
}

func main() {
    let n = 100_000_000
    let a = randomArray(n)
    print("first value is \(a[0])")
    print("last value is \(a[n - 1])")
}

main()

The Swift code is much slower than the NumPy code. Is there a better way to create a random array in Swift? Does Accelerate provide any functions that could speed this up?

[dnadoba (David Nadoba)]

There are two pitches that would address this:

Pitch: Requesting larger amounts of randomness from SystemRandomNumberGenerator

Introduction I propose adding a new method to SystemRandomNumberGenerator: randomBytes(count:), which will enable generating an arbitrary number of random bytes. This is a minor quality of life pitch that can provide a small but meaningful performance improvement to randomness-heavy code. Motivation SE-0202 introduced the RandomNumberGenerator protocol and provided a single standard library conforming type: SystemRandomNumberGenerator. This SystemRandomNumberGenerator implementation was delib…

An API for bulk random bytes

I'm proposing that we add the following requirement to the RandomNumberGenerator protocol: mutating func fill(_ buffer: UnsafeMutableRawBufferPointer) with a default implementation that uses the existing next() API to produce 64b at a time, and a customized implementation for SystemRandomNumberGenerator that directly requests the specified amount of random bytes from the underlying platform APIs. On its own, this doesn't change much, but we can then adopt it within the standard library in cas…

The later also has an implementation that you could use with some tweaks:

Initial implementation for RandomNumberGenerator.fill( )

[Jon_Shier]

Another issue is that I believe Swift's default RNG is more comparable to Python's SecureRandom, rather than the default numpy random, so you may want to compare that performance.

[scanon (Steve Canon)]

This will probably get re-pitched sometime in the future now that ~Copyable constraints (which this really wants to use) are becoming viable. (Specifically, I either want to relax the RandomNumberGenerator protocol to allow non-copyable conformers, or introduce a new protocol that does that, and I've been waiting for the compiler support for such things to get ironed out).

@Jon_Shier's point is really important, though. You can use a custom random source for this use case, and it will be much, much faster than using the SystemRNG.

[wigging (Gavin Wiggins)]

After reading the replies from @Jon_Shier and @scanon, I ditched the system random number generator Double.random(in: 0...1) and replaced it with drand48() as shown below. This runs about 1.5x faster than the NumPy code. I guess I could write a custom random generator using the RandomNumberGenerator protocol but now I know to avoid the system generator.

import Accelerate

func randomArray(_ count: Int) -> [Double] {
    let result = Array<Double>(unsafeUninitializedCapacity: count) { buffer, initCount in
        for i in 0..<count {
            buffer[i] = drand48()
        }
        initCount = count
    }
    return result
}

func main() {
    let n = 100_000_000
    let a = randomArray(n)
    print("first value is \(a[0])")
    print("last value is \(a[n - 1])")
}

main()

[wigging (Gavin Wiggins)]

I discovered this blog post from Daniel Lemire about a hash function called wyhash. The original wyhash function and associated wyrand function are available in this wyhash repo. The relevant code is in wyhash.h. Below are snippets from wyhash.h related to the wyrand function:

// 128bit multiply function
static inline uint64_t _wyrot(uint64_t x) { return (x>>32)|(x<<32); }

static inline void _wymum(uint64_t *A, uint64_t *B){
#if(WYHASH_32BIT_MUM)
  uint64_t hh=(*A>>32)*(*B>>32), hl=(*A>>32)*(uint32_t)*B, lh=(uint32_t)*A*(*B>>32), ll=(uint64_t)(uint32_t)*A*(uint32_t)*B;
  #if(WYHASH_CONDOM>1)
  *A^=_wyrot(hl)^hh; *B^=_wyrot(lh)^ll;
  #else
  *A=_wyrot(hl)^hh; *B=_wyrot(lh)^ll;
  #endif
#elif defined(__SIZEOF_INT128__)
  __uint128_t r=*A; r*=*B;
  #if(WYHASH_CONDOM>1)
  *A^=(uint64_t)r; *B^=(uint64_t)(r>>64);
  #else
  *A=(uint64_t)r; *B=(uint64_t)(r>>64);
  #endif
#elif defined(_MSC_VER) && defined(_M_X64)
  #if(WYHASH_CONDOM>1)
  uint64_t  a,  b;
  a=_umul128(*A,*B,&b);
  *A^=a;  *B^=b;
  #else
  *A=_umul128(*A,*B,B);
  #endif
#else
  uint64_t ha=*A>>32, hb=*B>>32, la=(uint32_t)*A, lb=(uint32_t)*B, hi, lo;
  uint64_t rh=ha*hb, rm0=ha*lb, rm1=hb*la, rl=la*lb, t=rl+(rm0<<32), c=t<rl;
  lo=t+(rm1<<32); c+=lo<t; hi=rh+(rm0>>32)+(rm1>>32)+c;
  #if(WYHASH_CONDOM>1)
  *A^=lo;  *B^=hi;
  #else
  *A=lo;  *B=hi;
  #endif
#endif
}

// Multiply and xor mix function, aka MUM
static inline uint64_t _wymix(uint64_t A, uint64_t B) {
  _wymum(&A, &B);
  return A^B;
}

//The wyrand PRNG that pass BigCrush and PractRand
static inline uint64_t wyrand(uint64_t *seed) {
  *seed+=0x2d358dccaa6c78a5ull;
  return _wymix(*seed, *seed^0x8bb84b93962eacc9ull);
}

The blog post links to a Swift implementation of wyrand that is available at the SwiftWyhash repo. The code in the SwiftWyhash repo lags behind recent changes in the wyhash repo by several years. So I attempted to update the Swift implementation based on the latest code in the wyhash repo. Below is my Swift attempt:

import Foundation

struct WyRand: RandomNumberGenerator {
    private var state : UInt64

    init(seed: UInt64 = mach_absolute_time()) {
        state = seed
    }

    mutating func next() -> UInt64 {
        state &+= 0x2d358dccaa6c78a5
        let mul = state.multipliedFullWidth(by: state ^ 0x8bb84b93962eacc9)
        return mul.low ^ mul.high
    }
}

Using this random number generator to fill an array with random values is shown below. This is significantly faster than using Swift's default Double.random.

let n = 100_000_000
var rng = WyRand()

let result = Array<Double>(unsafeUninitializedCapacity: n) { buffer, initCount in
    for i in 0..<n {
        buffer[i] = Double.random(in: 0..<1, using: &rng)
    }
    initCount = n
}

print(result[0])

I'm not great with C/C++ code so can someone take a look at the wyrand function in wyhash.h and let me know if the WyRand struct is a good Swift representation of the wyrand function?

[wigging (Gavin Wiggins)]

I compared the Swift Wyrand version to the Rust wyrand version using a seed of 42 and got the same results. So I guess the Swift code is working fine.

[tera]

@wigging

This is significantly faster than using Swift's default Double.random

How does the speed of this compare to drand48? I occasionally need a fast, insecure, low-quality random number generator, so this could be useful to keep in mind. Thanks!

[wigging (Gavin Wiggins)]

It is about 2.2x faster than drand48 and 42x faster than Double.random when filling a Double array of 100,000,000 elements. This was measured on an M4 Mac, compiling with -Ounchecked, and using hyperfine for the benchmark. I will write a short article with all the details soon.