This is as much a “before you forget about it” post as anything else.
Both Java and .NET have Random classes, which allow you to get random numbers within a certain range etc. Unless you specify otherwise, both are seeded with the current time. Neither class claims to be thread-safe. This presents a problem – typically you effectively just want one source of random numbers, but you want to be able to access it from multiple threads. You certainly don’t want to create a new instance of the Random class every time you want a random number – due to the granularity of the system clock, that commonly gives repeated sequences of random numbers (i.e. multiple instances are created with the same seed, so each instance gives the same sequence).
I suggest that very few people really need to specify seeds – which means they don’t really need instance methods in the first place. A class with static methods (matching the interface of Random) would be perfectly adequate. This could be implemented using a single Random instance and locking to get thread safety, but a slightly more elegant (or at least more interesting) way would be to use thread-local static variables. In other words, each thread gets its own instance of Random. Now, that introduces the problem of which seed to use for each of these instances. That’s pretty easily solved though – either you take some combination of the thread ID and the current time, or you create a new instance of Random the first time any thread accesses the class, and use that Random as the source of seeds for future Randoms. The only time locking is needed is to access that Random, which occurs once per thread.
This does, of course, break my “keep it as simple as possible” rule – the simplest solution would certainly be to lock each time. In this case though, as this will end up as a library class which may well be used by many threads simultaneously in situations where a lot of random numbers are being generated, I think it’s worth the extra effort. I’ll probably write this up as an article when I’ve written the tests and implementation…
7 thoughts on “System.Random (and java.util.Random)”
Well, whaddya know – it turns out that (at least on my single processor box) using a straight lock is faster than using a thread-local variable.
Good job I bothered testing it, isn’t it?
Did yoy every re-test with the newer java.util.Random implementation that uses volatiles/AtomicLong internally (and the newer ThreadLocal impl)?
Nope, never implemented it or tested on Java. I can’t see any thread-safety guarantees in the JDK 6 documentation though. To be honest, locking is so cheap when it’s uncontested, it’s probably easiest to use the same sort of implementation as I’ve done for .NET – just lock on every call.
Hi Jon. That the lock version is faster than a version that uses ThreadStatic variables is probably attributable to the fact that unfortunately) ThreadStatic variables are incredibly slow. When you want parallelism without locking, and don’t want to use ThreadStatic, there’s always a lock-free data structure to consider. In this case you’d have to design your own lock-free random number generator, or find an existing one. You couldn’t use System.Random.
Another solution to this type of problem was communicated to me by Jeffrey Richter. I hope he doesn’t mind me mentioning his name here – I want to give him credit for the idea. The idea is to have a lock-free stack of data structures. When a thread needs one of the data structures, it grabs one off the queue, uses it, and then returns it to the stack. This is a useful technique to know, as it applies to all sorts of data structures, not just random number generation. It avoids the slowness of ThreadStatic and it avoids having to maintain allocated memory for a data structure instance in each thread when a given thread might never use that memory again. In the case of random number generators, there could be a lock-free stack of System.Random instances. One advantage of this is that threads can grab a random number generator, use it in a localized region (such as a loop), and release it, without having to acquire or lock the generator each time it’s used in the localized region. For this, or any other scheme, using System.Random instances, I’d recommend keeping a global seed variable, and incrementing and using the value each time a new System.Random instance is created. That way you won’t run into two generators using the same seed – something that is bound to happen eventually if you use time-based seeding.
Why have you stopped blogging? Your articles are too good man! I also found another good article about random class which might help the newbie programmers-> http://www.codingalpha.com/random-class-in-java/
I haven’t stopped blogging… I’ve been doing more in the last couple of months than I had for a while before that, primarily on diagnostics.
Bear in mind that as well as a full-time job, I’m also writing the 4th edition of C# in Depth. There are only so many hours in the day…