Request for feedback on slow Swift code

Using Swift
#1

Hi All,

I'm new to Swift and was exploring the language today by generating random numbers from a normal distribution. The performance of my code is noticeably slower than similar code that I had previously written in Chez Scheme. Are there any obvious performance pitfalls in the way I've written this code?

Thanks,

Travis

import Foundation

// rejection method from https://www.cse.wustl.edu/~jain/books/ftp/ch5f_slides.pdf
func rnorm(_ mu: Double = 0, _ sd: Double = 1) -> Double {
    func comp(_ x: Double) -> Double {
        return exp(-1 * pow(x-1, 2)/2)
    }
    var u1: Double; var u2: Double; var x: Double;
    repeat {
        u1 = Double.random(in: 0...1)
        u2 = Double.random(in: 0...1)
        x = -1 * log(u1)
    } while u2 > comp(x)
    if Double.random(in: 0...1) > 0.5{
        return (mu + sd * x)
    } else {
        return (mu - sd * x)
    }
}

func sampleNormal(_ n: Int, _ mu: Double = 0, _ sd: Double = 1) -> [Double] {
    var out = Array(repeating: 0.0, count: n)
    for i in 1..<n {
        out[i] = rnorm(mu, sd)
    }
    return out
}
let x = sampleNormal(1000000, 10, 10)
print(x.reduce(0, +)/Double(x.count))
#2

What build settings are you using?

#3

Good question. I guess I'm using the default build settings. I'm just using swift build and swift run. I'm using Swift 5.3.3 on Ubuntu 20.04. Thanks.

#4

Do the performance issues disappear when you build using release mode?

$  swift build --help | rg release
  --configuration, -c     Build with configuration (debug|release) [default: debug]
#5

No. Using swift build -c release did not yield a noticeable improvement.

#6

It’s also worth noting that, at least on Mac, the default SystemRandomNumberGenerator is relatively slow compared to, eg., linear congruence PRNGs. I don’t know if the same is true on Linux, but you could try writing a simple generator like WyRand or Xoroshiro or PCG, to see if that makes a difference.

(Or at least profile to see if most of the time is being spent in your code or in the system random number generator.)

• • •

Also, if you’re interested in some general feedback on the code you posted, I might make a few suggestions:

Code 
import Foundation

// rejection method from https://www.cse.wustl.edu/~jain/books/ftp/ch5f_slides.pdf
func rnorm(_ mu: Double = 0, _ sd: Double = 1) -> Double {
  var x: Double
  
  repeat {
    let u1 = Double.random(in: 0...1)
    let u2 = Double.random(in: 0...1)
    x = -log(u1)
    let y = exp(-(x-1)*(x-1) / 2)
  } while u2 > y
  
  return Bool.random() ? mu + sd * x : mu - sd * x
}

func sampleNormal(_ n: Int, _ mu: Double = 0, _ sd: Double = 1) -> [Double] {
  return (0..<n).map{ _ in
    rnorm(mu, sd)
  }
}

let x = sampleNormal(1000000, 10, 10)
print(x.reduce(0, +) / Double(x.count))

If I were writing this myself, I would probably use static methods instead of free functions. They would take a RandomNumberGenerator parameter, and be located on BinaryFloatingPoint where RawSignificand: FixedWidthInteger. And I’d use a non-abbreviated name like randomNormal(mean:standardDeviation:)

I would also try implementing a few different approaches to compare, such as Marsaglia’s polar method, the Box-Muller transform, and maybe the ziggurat algorithm.

1 Like
#7

Just to make doubly sure it is not related to the debug build being run instead of the release one:
swift run by default runs the debug build; did you try running swift run -c release and does that noticeably improve the performance?

#8

No, swift run -c release does not noticeably improve performance.

#9

Ok, then I agree with @Nevin about trying a custom less secure, but more performant RNG. Profiling the code would also go a long way towards understanding/confirming where the bottleneck may be, on macOS you can use Instruments to help pin down performance problems.

Edit:
From the documentation, SystemRandomNumberGenerator internally uses:

  • arc4random_buf(3) on macOS
  • getrandom(2) or /dev/urandom on Linux
  • BCryptGenRandom on Windows

These either use or are system calls which require costly context switching and are considered cryptographically secure. As such they may not be the best option when used heavily in tight loops when performance is more important than being cryptographically secure.

1 Like
#10

Went and profiled on macOS, it looks like ~80% of time is being spent in RNG

image
image2560×1684 660 KB

4 Likes
#11

I got about a 3x speedup by replacing Double.random(in: 0...1) with drand48(). And based on the other suggestions in this thread, it sounds like there are options out there to improve that even more. I'm not trying to extract maximum performance with this example. I was just trying to learn some Swift syntax and was surprised by the sluggish performance of my naive code. Thanks for all the helpful replies!

Terms of Service

Privacy Policy

Cookie Policy