I have a little project which runs simulations by generating random numbers. I am wanting to speed things up by processing things in parallel. However I find that concurrently performing the tasks can end up taking longer than if they were run serially.
Here is some code to demonstrate.
import Foundation
func formatTime(_ date: Date) -> String
{
let df = DateFormatter()
df.dateFormat = "h:mm:ss.SSS"
return df.string(from: date)
}
func doSomething(_ iteration: Int)
{
var tally = 0.0
let startTime = Date()
print("Start #\(iteration) - \(formatTime(startTime))")
for _ in 1...1_000_000
{
// tally += Double.random(in: 0...100)
tally += 3.5
}
let endTime = Date()
print("End #\(iteration) - \(formatTime(endTime)) - elapsed: \(endTime.timeIntervalSince(startTime))")
}
print("Single task performed on main thread")
doSomething(0) // Used to get a baseline for single run
print("\nMultiple tasks performed concurrently")
DispatchQueue.concurrentPerform(iterations: 5, execute: doSomething)
If you run this code it will output the time taken to run a task once, then run it multiple times in parallel. As it stands, the total time taken should be about equal (assuming your machine has enough cores).
Then if you comment out the fixed increment of tally, and substitute in the random version, I find that the parallel tasks take about 4 times longer than the single one.
SystemRandomNumberGenerator is automatically seeded, is safe to use in multiple threads, and uses a cryptographically secure algorithm whenever possible.
The internals of next() are quite possibly serialized at some level by the platform itself.
If you want the tradeāoffs weighed differently then yes. Tradeāoffs include thread safety, cryptographic quality, speed, repeatability, etc.
You may not have to write your own from scratch though. Your platform may already provide what you want in C, which you would only have to wrap in a RandomNumberGenerator type. Or you could look for a thirdāparty package out in the wild.
You also still get many of tieāins for free, like random(using:) on Bool, random(in:using:) on Int and Double, randomElement(using:) and shuffle(using:) on Array.
Think I may have found the solution. I had tried previously using arc4random() and encountered the same issues. I thought I'd also tested drand48() previously and that suffered from the same issue, but I've just revisited and it seems to be immune from the effect. Possibly because it doesn't seed itself.
Other upside is that it is about 4 times as fast. So that looks like what I'll have to use.
Iād say for you to please carefully read the man page for drand48 and take that into account given your requirement of concurrent computation.
I canāt give more details right now as Iām on the move, but I can come back later and explain possible issues you might encounter.
The Swift project has a couple RNG implementations to support various tests. The SplitMix RNG is good and a lot faster than the system RNG ā if you initialize it with a seed from the system RNG, you should get what you're looking for:
I've read the drand48 man page several times now but nothing in there gave me any insight in to concurrency issues. Not saying that there wasn't crucial information in there. Just that I couldn't recognise it.
Ok, one of the issues is that it is not thread safe and drand48 uses a seed for each generated number that is shared inside a process between different threads. Although in this case that doesn't mean anything will crash, it does mean that you might frequently get the same random numbers returned from separate iterations. If you try to synchronise access to this function using a lock or something else you will most definitely run again into the same performance issues you ran into with the SystemRandomNumberGenerator which is thread safe.
I think in your case what you want is to be able to use a separate random number generator for each call to doSomething so that each iteration generates their own sequence of random numbers without depending on global state. Now, in this case, if you use the same algorithm for random number generation for each iteration, you need to choose a different initial seed for each of them or you will get the exact same sequence of numbers in each of the different iterations, this initial seed you can get with SystemRandomNumberGenerator since it is thread safe and you will only call it once at the start of each iteration.
For the separate random number generator you can use the SplitMix64 mentioned above instantiated in each separate iteration.
As an example I did an experiment and in 10 concurrent tight loops generating random numbers using drand48, of 1000_000 total numbers generated from all those 10 concurrent loops, only about 150_000 of the them were unique, so about 85% of all of the generated numbers across possibly 10 different threads were repeated. Of course this will vary with the amount of work you do other than generating random numbers, and with the amount of concurrent iterations you do, but still, you are very likely to get the exact same random numbers several times across different iterations.
Additionally if you want your results to always be repeatable you should display the initial seed generated from the SystemRandomNumberGenerator and/or store it on disk somewhere, so if an issue arises you can investigate using the same seed.
I did find that analysis of the repeated numbers quite sobering, as well as interesting. I've not figured out what I'm doing wrong when I try something similar.
What I did is create a function (basing it on the previous doSomething routine) which generates 10E6 random numbers in 0...1 and allocates them in to bins, using the generated number rounded off to 7dp. I then ran that routine using drand48 as well as Double.random(), both as a single process as well as 10 concurrent ones.
The results I came up with is that in the single process version, both RNG about 63% "uniqueness". When I repeated using concurrency, I got no change in result for either approach.
I am genuinely interested if there is a flaw in my approach. I've found that computing is a great place to demonstrate that every problem has an obvious solution ā which is wrong.
