Random Numbers

[Paul Brook]

On Saturday 24 April 2004 00:00, Scott Robert Ladd wrote:
> Paul Brook wrote:
> > The random functions probably aren't thread safe.
>
> They are not.
>
> In general, the "best" random number generators maintain a sizable array
> as a "super seed" value. The Mersenne Twister (implemented in random.c)
> treats a 624-element array of 32-bit values as a 19,937-bit value. Other
> long-period algorithms (Marsaglia's) involve similar-sized arrays.
>
> Simple, short-period random number generators (like C's) are not
> thread-safe by nature, either, since all calls to rand() use a singular
> 32-bit seed value set by seed() and modified by each call to rand().
> Java uses class encapsulation to provide thread safety.
>
> I don't think it is reasonable for threads to share a single array for a
> Mersenne Twister; doing so will completely foul the underlying
> algorithm. My personal implementation of the Mersenne Twister uses a
> structure that must be passed to functions (much like the hidden "this"
> argument in C++), but that approach won't work for the intrinsics
> because we can't change the standard Fortran 95 interfaces.
>
> The big problem is portability. I could, for example, allocate
> per-process memory, using a look-up table to access the appropriate
> register array based on procid. However, the function calls for that are
> quite inconsistent across the myriad platforms supported by GCC.
>
> So I guess this boils down to: How have other library functions solved
> this issue?

AFAIK random is the only intrinsic that requires any state to be preserved 
between calls.

Our memory [de]allocation routines are not thread safe. These contain 
excessively complicated code that has been obsoleted by changes to the 
compiler. A simple malloc/free wrapper would suffice, and would be thread 
safe.
The IO library is not currently thread safe.

> Is there somethign built-in to GHCC for handlign situations 
> such as this? I've described the C and Java solutions above, neither of
> which "works" well for Fortran. I'm open to suggestions.

I don't think giving each thread its own RNG state is a good idea. This is 
certainly not the most obvious behaviour. I'd imagine it could also have 
issues in programs where threads are created and destroyed frequently. IMHO 
the default implementation should favour safety over performance.

My suggestion would be to somehow serialize access to the existing routines. 
libstdc++ contains serialization routines, so maybe we could use/steal those.

We might consider extending the standard to include an (optional) state 
parameter for random routines. Calls would then be serialized only if they 
referred to the same state.

> Another problem: random.c defines the array as 624 unsigned ints -- a
> real problem when moving to a platform where an unsigned int may be of
> another length (say, a 64-bit system). In the very least, we need to use
>   an explicit 32-bit type for the array.

This is one of the significant outstanding bugs I mentioned:) It should use 
explicit sized types. The IO library still has similar issues.

> > I think the rest are as long as the underlying C library is.
>
> Do we *know* that the underlying C library is thread safe? I can see
> potential problems ahead for the OpenMP implementation -- yet another
> item to add to my design document for GOMP... ;}

That depends on your target. I believe glibc is thread safe by default.

Paul