Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #62713 > unrolled thread

thread-safe random numbers...

Back to article view | Back to comp.lang.c

Contents

  thread-safe random numbers... "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-05-27 20:22 -0700
    Re: thread-safe random numbers... "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-05-28 11:11 -0700
    Re: thread-safe random numbers... "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-05-28 11:19 -0700
      Re: thread-safe random numbers... Rosario19 <Ros@invalid.invalid> - 2015-05-29 07:28 +0200
    Re: thread-safe random numbers... James Kuyper <jameskuyper@verizon.net> - 2015-05-28 14:22 -0400
      Re: thread-safe random numbers... Keith Thompson <kst-u@mib.org> - 2015-05-28 12:38 -0700
        Re: thread-safe random numbers... James Kuyper <jameskuyper@verizon.net> - 2015-05-28 16:42 -0400
        Re: thread-safe random numbers... "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-05-28 13:57 -0700
        Re: thread-safe random numbers... Nobody <nobody@nowhere.invalid> - 2015-05-29 22:42 +0100
    Re: thread-safe random numbers... Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-10 11:56 -0700
      Re: thread-safe random numbers... "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-07-10 14:03 -0700
        Re: thread-safe random numbers... Tim Rentsch <txr@alumni.caltech.edu> - 2015-07-11 13:44 -0700
    Re: thread-safe random numbers... "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2015-07-10 12:01 -0700
      Re: thread-safe random numbers... "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-07-10 13:53 -0700
        Re: thread-safe random numbers... "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-07-10 13:58 -0700
        Re: thread-safe random numbers... "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2015-07-10 14:04 -0700
          Re: thread-safe random numbers... "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-07-10 14:23 -0700
            Re: thread-safe random numbers... Keith Thompson <kst-u@mib.org> - 2015-07-10 17:12 -0700
              Re: thread-safe random numbers... "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-07-10 18:58 -0700
        Re: thread-safe random numbers... Rosario19 <Ros@invalid.invalid> - 2015-07-11 11:13 +0200

#62713 — thread-safe random numbers...

I am trying to find the standard method for creating
random numbers in a thread-safe manner in C. So far,
I can only find the `rand_r()' function. However,
this seems to be a POSIX, or an "extension" to standard
C. In C++ it seems like I can make use of the
`std::default_random_engine' class . However, I need to know
if `rand_r()' is okay to use wrt standard C.

I am sorry if this is a stupid easy question!

;^o

[toc] | [next] | [standalone]

#62736

> "Chris M. Thomasson"  wrote in message 
> news:mk61l9$ap4$1@speranza.aioe.org...

> I am trying to find the standard method for creating
> random numbers in a thread-safe manner in C. So far,
> I can only find the `rand_r()' function. However,
> this seems to be a POSIX, or an "extension" to standard
> C. In C++ it seems like I can make use of the
> `std::default_random_engine' class . However, I need to know
> if `rand_r()' is okay to use wrt standard C.

Well, according to:

http://www.cplusplus.com/reference/cstdlib/rand

It appears that if I want thread-safe random numbers in C, I
have to roll my own, or use the non-portable function `rand_r()'.

Damn!

I hope I am simply missing something important here.

IMVHO, this seems to be a flaw, especially since threading is
now a standard aspect of C...

;^o 

[toc] | [prev] | [next] | [standalone]

#62737

> "Chris M. Thomasson"  wrote in message 
> news:mk61l9$ap4$1@speranza.aioe.org...

> I am trying to find the standard method for creating
> random numbers in a thread-safe manner in C. So far,
> I can only find the `rand_r()' function. However,
> this seems to be a POSIX, or an "extension" to standard
> C. In C++ it seems like I can make use of the
> `std::default_random_engine' class . However, I need to know
> if `rand_r()' is okay to use wrt standard C.

FWIW, I need a random number generator on a
per-thread basis with different seeds for each
one. I want to avoid using synchronization to
access a single global instance because it
would end up creating a massive bottleneck!

This is not a problem in C++, but C seems to
be a different story. 

[toc] | [prev] | [next] | [standalone]

#62770

On Thu, 28 May 2015 11:19:56 -0700, "Chris M. Thomasson" wrote:
>> "Chris M. Thomasson"  wrote in message 
>> news:mk61l9$ap4$1@speranza.aioe.org...
>
>> I am trying to find the standard method for creating
>> random numbers in a thread-safe manner in C. So far,
>> I can only find the `rand_r()' function. However,
>> this seems to be a POSIX, or an "extension" to standard
>> C. In C++ it seems like I can make use of the
>> `std::default_random_engine' class . However, I need to know
>> if `rand_r()' is okay to use wrt standard C.
...
>This is not a problem in C++, but C seems to
>be a different story. 

I think it is possible call from assembly executable 
C++ function and operators too
if one just know their real name

one can debug a little these routines and see what they do,
the file where they are etc if all is easy or complex
one can change their name in one assembly dll something as
_CnameRand:
  call _CPPNameRand$
ret
if the function has no argument
and inport in a C file from assembly dll.

I don't know 100% if the new function will be multithread
but i think yes

Does this break copyright iussues?

[toc] | [prev] | [next] | [standalone]

#62738

On 05/27/2015 11:22 PM, Chris M. Thomasson wrote:
> I am trying to find the standard method for creating
> random numbers in a thread-safe manner in C. So far,
> I can only find the `rand_r()' function. However,
> this seems to be a POSIX, or an "extension" to standard
> C. In C++ it seems like I can make use of the
> `std::default_random_engine' class . However, I need to know
> if `rand_r()' is okay to use wrt standard C.

POSIX.1-2008 says that rand_r is supposed to be thread-safe, but it is
also marked "OB" for "Obsolescent".

As of the 2011, for the first time, the C standard actually addresses
threading issues. Unfortunately, what it says is "The rand function is
not required to avoid data races with other calls to pseudo-random
sequence generation functions." (7.22.2.1p3). It says the same thing
about the srand() function (7.22.2.2p3).

rand() has never been the recommended way of doing serious random number
generation - the standard imposes no meaningful restrictions on the
quality of the algorithm it uses. Older versions of the standard
actually gave a specific and very unsophisticated algorithm as an
example, and many implementations actually implemented that algorithm.
Creating your own random number generator, or borrowing someone else's,
is the recommended approach for serious random number generation. While
doing so, you can make it thread-safe.

If you're willing to restrict the portability of your code to POSIX
platforms, and a simple 48-bit linear congruential algorithm would be
sufficient for your needs, you can use erand48(), nrand48() or
jrand48(), depending upon whether you want the range of the random
numbers to be [0.0,1.0), [0,2^31) or (-2^31,2^31). The corresponding
drand48(), lrand48() and jrand48() functions are NOT guaranteed to be
thread-safe.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#62744

James Kuyper <jameskuyper@verizon.net> writes:
[...]
> rand() has never been the recommended way of doing serious random number
> generation - the standard imposes no meaningful restrictions on the
> quality of the algorithm it uses. Older versions of the standard
> actually gave a specific and very unsophisticated algorithm as an
> example, and many implementations actually implemented that algorithm.
> Creating your own random number generator, or borrowing someone else's,
> is the recommended approach for serious random number generation. While
> doing so, you can make it thread-safe.

The current standard still has that sample implementation (as a
non-normative example).

Some implementations have a rand() function that's even worse; unlike
the sample version in the standard, some versions return values in which
the low-order bit alternates on each call, the low-order 2 bits have a
cycle of 4, and so on.  (I think it's one of the BSDs.)

> If you're willing to restrict the portability of your code to POSIX
> platforms, and a simple 48-bit linear congruential algorithm would be
> sufficient for your needs, you can use erand48(), nrand48() or
> jrand48(), depending upon whether you want the range of the random
> numbers to be [0.0,1.0), [0,2^31) or (-2^31,2^31). The corresponding
> drand48(), lrand48() and jrand48() functions are NOT guaranteed to be
> thread-safe.

If the mediocre implementation given in the standard is good enough,
it's easy to adapt to be thread-safe.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#62746

On 05/28/2015 03:38 PM, Keith Thompson wrote:
> James Kuyper <jameskuyper@verizon.net> writes:
> [...]
>> rand() has never been the recommended way of doing serious random number
>> generation - the standard imposes no meaningful restrictions on the
>> quality of the algorithm it uses. Older versions of the standard
>> actually gave a specific and very unsophisticated algorithm as an
>> example, and many implementations actually implemented that algorithm.
...
> The current standard still has that sample implementation (as a
> non-normative example).

Ah - it's under the srand() section - I was expecting to find it in the
rand() section - I didn't scroll down far enough.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#62747

> "Keith Thompson"  wrote in message 
> news:87iobclch0.fsf@kst-u.example.com...

> > James Kuyper <jameskuyper@verizon.net> writes:
[...]
> > rand() has never been the recommended way of doing serious random number
> > generation - the standard imposes no meaningful restrictions on the
> > quality of the algorithm it uses. Older versions of the standard
> > actually gave a specific and very unsophisticated algorithm as an
> > example, and many implementations actually implemented that algorithm.
> > Creating your own random number generator, or borrowing someone else's,
> > is the recommended approach for serious random number generation. While
> > doing so, you can make it thread-safe.

> The current standard still has that sample implementation (as a
> non-normative example).

[...]


Are you perhaps referring to this one:
_________________________________________________
static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}
_________________________________________________


This can be easily modified to suit my needs.

FWIW, I am using these "random" numbers to pick
which complex root to follow during the processing
of an inverse nJulia set iterated function system.

Sometimes, the "quality" of the PRNG can start
to show some visual differences when I am caculating
a deep zoom on a given fractal by favoring certain
complex roots over the others...

Also, I am using a hybrid approach that relies on
more than one Julia point, so the PRNG is used
there as well...


;^) 

[toc] | [prev] | [next] | [standalone]

#62812

On Thu, 28 May 2015 12:38:03 -0700, Keith Thompson wrote:

> The current standard still has that sample implementation (as a
> non-normative example).
> 
> Some implementations have a rand() function that's even worse; unlike
> the sample version in the standard, some versions return values in which
> the low-order bit alternates on each call, the low-order 2 bits have a
> cycle of 4, and so on.  (I think it's one of the BSDs.)

It's not actually "worse" per se, it just requires a bit more care from
the user.

Any LCG inevitably has the property that the least-significant N bits of
the state will have a period of at most 2^(N+1). Carries propagate from
least-significant to most-significant, so the next state of any given bit
is dictated solely by the prior state of that bit and those below it.

Ignoring the lower bits of the state places a lower bound on the period of
the resulting sequence. The question is: how many bits should be discarded.

Some LCGs return the entire state and leave it up to the caller as to how
many bits to discard. Others (such as the sample implementation in the C99
standard and POSIX' *rand48() family) discard some fixed number of bits
automatically.

Returning the complete state gives the caller complete discretion over the
number of bits to discard. However, it also gives them the option of
shooting themself in the foot, so it seems to be disfavoured nowadays.

[toc] | [prev] | [next] | [standalone]

#65174

"Chris M. Thomasson" <nospam@nospam.nospam> writes:

> I am trying to find the standard method for creating
> random numbers in a thread-safe manner in C.  So far,
> I can only find the `rand_r()' function.  However,
> this seems to be a POSIX, or an "extension" to standard
> C. In C++ it seems like I can make use of the
> `std::default_random_engine' class . However, I need to know
> if `rand_r()' is okay to use wrt standard C.

Nothing available in regular C AFAIK.  The best bet might be
putting something together yourself and using that.  I think
the following code is not too bad - fairly good quality of
random numbers, small memory footprint, and IIANM completely
portable and usable in strictly conforming programs.  (If
anyone discovers an exception to that of course I would like
to hear about it.)  Also I believe most seed values give
very long periods, but in any case the period for any seed
value is a multiple of 4294901760 (which is 65536 * 65535).



/* Declarations */

extern void seed_uniform16( unsigned short (*)[4], unsigned long );
extern unsigned short uniform16( unsigned short (*state)[4] );


/* Definitions */

void
seed_uniform16( unsigned short (*state)[4], unsigned long seed ){
    unsigned short *s = *state;
    unsigned const M11 = 0x7FF;
    unsigned i;

    s[0] =  (seed >> 24  & 255) * 211;
    s[1] =  (seed >> 16  & 255) * 173;
    s[2] =  seed & 0xFFFF;
    s[3] =  1;
    for(  i = 0;  i < 13;  i++  )  uniform16( state );
}

unsigned short
uniform16( unsigned short (*state)[4] ){
    /* A simple but not too bad PRNG by Tim Rentsch */
    unsigned short *s = *state;
    unsigned const M16 = 0xFFFF;
    unsigned  a = s[0],  b = s[1],  c = s[2],  d = s[3] & M16;

    a -= b+c,  b -= a+d,  a &= M16,  b &= M16,  a ^= b >> 5;
    c += 1,  c &= M16;
    d ^= d >> 8,  d ^= d << 9 & M16,  d ^= d >> 7;

    return   s[0] = a,  s[1] = b,  s[2] = c,  s[3] = d,   a ^ b ^ d;
}

[toc] | [prev] | [next] | [standalone]

#65192

> "Tim Rentsch"  wrote in message 
> news:kfnh9pb4za3.fsf@x-alumni2.alumni.caltech.edu...

> > "Chris M. Thomasson" <nospam@nospam.nospam> writes:

> > I am trying to find the standard method for creating
> > random numbers in a thread-safe manner in C.  So far,
> > I can only find the `rand_r()' function.  However,
> > this seems to be a POSIX, or an "extension" to standard
> > C. In C++ it seems like I can make use of the
> > `std::default_random_engine' class . However, I need to know
> > if `rand_r()' is okay to use wrt standard C.

> Nothing available in regular C AFAIK.  The best bet might be
> putting something together yourself and using that.  I think
> the following code is not too bad - fairly good quality of
> random numbers, small memory footprint, and IIANM completely
> portable and usable in strictly conforming programs.

[...]

This looks good. Thank you for posting it Tim.

:^) 

[toc] | [prev] | [next] | [standalone]

#65337

"Chris M. Thomasson" <nospam@nospam.nospam> writes:

>> "Tim Rentsch"  wrote in message
>> news:kfnh9pb4za3.fsf@x-alumni2.alumni.caltech.edu...
>>
>>> "Chris M.  Thomasson" <nospam@nospam.nospam> writes:
>>>
>>> I am trying to find the standard method for creating
>>> random numbers in a thread-safe manner in C.  So far,
>>> I can only find the `rand_r()' function.  However,
>>> this seems to be a POSIX, or an "extension" to standard
>>> C.  In C++ it seems like I can make use of the
>>> `std::default_random_engine' class . However, I need to know
>>> if `rand_r()' is okay to use wrt standard C.
>>
>> Nothing available in regular C AFAIK.  The best bet might be
>> putting something together yourself and using that.  I think
>> the following code is not too bad - fairly good quality of
>> random numbers, small memory footprint, and IIANM completely
>> portable and usable in strictly conforming programs.
>
> [...]
>
> This looks good.  Thank you for posting it Tim.

Ahh it is nice to be appreciated.  :)  You
are most welcome sir!

[toc] | [prev] | [next] | [standalone]

#65175

On Wednesday, May 27, 2015 at 11:22:27 PM UTC-4, Chris M. Thomasson wrote:
> I am trying to find the standard method for creating
> random numbers in a thread-safe manner in C. So far,
> I can only find the `rand_r()' function. However,
> this seems to be a POSIX, or an "extension" to standard
> C. In C++ it seems like I can make use of the
> `std::default_random_engine' class . However, I need to know
> if `rand_r()' is okay to use wrt standard C.
> 
> I am sorry if this is a stupid easy question!
> 
> ;^o

I would just wrap the function you use the call to retrieve the next
random number in a semaphore of some kind.  That would give it fully
atomic access, first come, first served, and minimal delay because
of the speed in the random algorithm (assuming you're using the C
algorithm).

Best regards,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#65190

> "Rick C. Hodgin"  wrote in message news:5b63a727-afb4-42c2-93d6-> > 
> 844989aa7e58@googlegroups.com...

> > On Wednesday, May 27, 2015 at 11:22:27 PM UTC-4, Chris M. Thomasson 
> > wrote:
> > I am trying to find the standard method for creating
> > random numbers in a thread-safe manner in C.

[...]

> I would just wrap the function you use the call to retrieve the next
> random number in a semaphore of some kind.  That would give it fully
> atomic access, first come, first served, and minimal delay because
> of the speed in the random algorithm (assuming you're using the C
> algorithm).

Why not create an instance of PRNG on a per-thread basis? I
want to try and avoid threads fighting over shared location(s)
as much as possible. A semaphore would work fine, however, the
overheads would be way too much for some of my applications
Rick. 

[toc] | [prev] | [next] | [standalone]

#65191

> "Chris M. Thomasson"  wrote in message 
> news:mnpbbs$67h$1@speranza.aioe.org...

[...]

> Why not create an instance of PRNG on a per-thread basis?

I should specify that each instance would have a different seed of
course!   ;^)

A simple approach would be to setup a system where each thread
has a unique id, and that is incorporated into, or used as a per-thread
seed.


I have already mocked up something of a half-assed C11 threading
on top of PThreads:

https://groups.google.com/d/topic/comp.lang.c/WPH7ed5uS4Y/discussion

This has thread specific storage! No raw atomics yet...

;^) 

[toc] | [prev] | [next] | [standalone]

#65193

On Friday, July 10, 2015 at 4:53:28 PM UTC-4, Chris M. Thomasson wrote:
> > "Rick C. Hodgin"  wrote in message news:5b63a727-afb4-42c2-93d6-> > 
> > 844989aa7e58@googlegroups.com...
> 
> > > On Wednesday, May 27, 2015 at 11:22:27 PM UTC-4, Chris M. Thomasson 
> > > wrote:
> > > I am trying to find the standard method for creating
> > > random numbers in a thread-safe manner in C.
> 
> [...]
> 
> > I would just wrap the function you use the call to retrieve the next
> > random number in a semaphore of some kind.  That would give it fully
> > atomic access, first come, first served, and minimal delay because
> > of the speed in the random algorithm (assuming you're using the C
> > algorithm).
> 
> Why not create an instance of PRNG on a per-thread basis? I
> want to try and avoid threads fighting over shared location(s)
> as much as possible. A semaphore would work fine, however, the
> overheads would be way too much for some of my applications
> Rick.

That would work.  You'd have to bear in mind that the random numbers
in use would be re-used in each thread (unless possibly you seeded
them differently, or used different algorithms in each).

Best regards,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#65195

> "Rick C. Hodgin"  wrote in message news:1970f801-752a-415f-935e-> > 
> 0a12e39eaff5@googlegroups.com...

> > On Friday, July 10, 2015 at 4:53:28 PM UTC-4, Chris M. Thomasson wrote:
[...]
> > Why not create an instance of PRNG on a per-thread basis? I
> > want to try and avoid threads fighting over shared location(s)
> > as much as possible. A semaphore would work fine, however, the
> > overheads would be way too much for some of my applications
> > Rick.

> That would work.  You'd have to bear in mind that the random numbers
> in use would be re-used in each thread (unless possibly you seeded
> them differently, or used different algorithms in each).

:^)

You read my mind wrt trying to use different PRNG algorithms
in each thread. There could be a "pool of algorithms" that
threads choose from. After they make the choice they seed the
selected PRNG and use it. Just a very simple idea.

All of this functionality wrt choosing an algorithm and seeding
it can be accomplished during the "constructor" of a thread's
specific storage. tss_t in C11.

This has to scale MUCH better than using mutual exclusion...

FWIW, I actually have to use the emulation layer for C11 pretty
soon because my fractal cypher algorithm happens to be
embarrassingly parallel in nature...

;^)
make the choice they seed the selected PRNG and use it. 

[toc] | [prev] | [next] | [standalone]

#65203

"Chris M. Thomasson" <nospam@nospam.nospam> writes:
[...]
> You read my mind wrt trying to use different PRNG algorithms
> in each thread. There could be a "pool of algorithms" that
> threads choose from. After they make the choice they seed the
> selected PRNG and use it. Just a very simple idea.
>
> All of this functionality wrt choosing an algorithm and seeding
> it can be accomplished during the "constructor" of a thread's
> specific storage. tss_t in C11.
[...]

Why would you want to use a different *algorithm* in each thread?  Or
did you mean to say you'd use the same algorithm with a different seed
(and internal state) in each thread?

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#65223

> "Keith Thompson"  wrote in message 
> news:lnd1zzr1re.fsf@kst-u.example.com...

> > "Chris M. Thomasson" <nospam@nospam.nospam> writes:
[...]
> > You read my mind wrt trying to use different PRNG algorithms
> > in each thread. There could be a "pool of algorithms" that
> > threads choose from. After they make the choice they seed the
> > selected PRNG and use it. Just a very simple idea.
>
> > > All of this functionality wrt choosing an algorithm and seeding
> > it can be accomplished during the "constructor" of a thread's
> > specific storage. tss_t in C11.
[...]

> Why would you want to use a different *algorithm* in each thread?  Or
> did you mean to say you'd use the same algorithm with a different seed
> (and internal state) in each thread?

To observe what happens if you have a group of threads caculating
an iterated function system with different PRNG's. Each thread
would be a different color, then I think it might be interesting
to take a look at the renderings. BTW, I am doing this for fun.

:^) 

[toc] | [prev] | [next] | [standalone]

#65237

On Fri, 10 Jul 2015 13:53:03 -0700, "Chris M. Thomasson"
<nospam@nospam.nospam> wrote:

>> "Rick C. Hodgin"  wrote in message news:5b63a727-afb4-42c2-93d6-> > 
>> 844989aa7e58@googlegroups.com...
>
>> > On Wednesday, May 27, 2015 at 11:22:27 PM UTC-4, Chris M. Thomasson 
>> > wrote:
>> > I am trying to find the standard method for creating
>> > random numbers in a thread-safe manner in C.
>
>[...]
>
>> I would just wrap the function you use the call to retrieve the next
>> random number in a semaphore of some kind.  That would give it fully
>> atomic access, first come, first served, and minimal delay because
>> of the speed in the random algorithm (assuming you're using the C
>> algorithm).
>
>Why not create an instance of PRNG on a per-thread basis? I
>want to try and avoid threads fighting over shared location(s)
>as much as possible. A semaphore would work fine, 

prng function can be something as

u32  rnd(data*  data)

that return some random value
where data is a pointer to data change each call rnd

if data is different each thread [there is a different data space each
thread] there is no need of semaphore or other... 
(if rnd not use other global varibles)

>however, the
>overheads would be way too much for some of my applications
>Rick. 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web