Back to Top

Friday, May 30, 2008

Multi-threaded Visual C rand

I was helping out a friend who was trying to generate random numbers in several threads and he was expecting those numbers to be (at least somewhat) different. After getting the obvious problem resolved (you must call srand to initialize the seed - using for example the current time), we were still getting threads which were outputting the same sequence of (pseudo-)random number.

At this point the question came up whether srand and rand were thread safe / thread aware (meaning that the static variables they use were per process or per thread). The documentation of srand didn't say anything nor did the documentation of rand. A few quick searches for keywords (like Visual C, stdlib, thread safety, MSDN) turned up only articles related to C++ STL. At this point we decided to give it a last go and tried setting the seed in each thread to time + thread number (because the time would have been identical, given that any modern OS can start up a few threads within the same second). The results were the same: different threads producing the same sequence. At this moment we had two options:

  • Creating a central wrapper around rand protected by a mutex
  • Implementing our own random number generator.

We went with the second option, searching for a public domain random number generator and found this page. We simply inlined it with our thread function and used a local (stack) variable to store the seed, which was unique to the thread (since stacks are unique to the threads).

PS. These random numbers are for toying only (doing some simple experiments). If you need to use them for production grade software, take a look at methods to generate strong random numbers.

Update: after loading a test program in IDA, it seems that the VC runtime does take threading into account (ie it stores the random values using the TLS on a per-thread basis), which means that my initial diagnosis is wrong...

Update: ok, I think I got it (man, multithreading is hard). The code was something like this:

InterlockedIncrement(&aGlobalVariable);
threadID = aGlobalVariable;

This code is not thread-safe, because only the incrementation part is guaranteed to be atomic and it is possible to have the following scenario (which is probably what was happening):

  1. Thread A increments the value
  2. Thread B increments the value
  3. Thread A reads the value
  4. Thread B reads the value

To avoid this, here are a couple of possible solutions:

  • Use the value returned by InterlockedIncrement directly, rather than doing a separate read of the value
  • Transmit the identifier to each thread through the parameter it is passed to them.
  • Use the GetCurrentThreadId function together with the current time to initialize the random numbere generator (this is again not 100% foolproof because thread id's - just as process id's - get reused), but is should be good enough.

0 comments:

Post a Comment

You can use some HTML tags, such as <b>, <i>, <a>. Comments are moderated, so there will be a delay until the comment appears. However if you comment, I follow.